Translator Disclaimer
Chapter 5:
Fast Williamson-Hadamard Transforms

Hadamard matrices have recently received attention due to their numerous known and promising applications. The FHT algorithms were developed for the orders N = 2n, 12 · 2n, 4n. The difficulties of the construction of the N ≡ 0(mod 4)-point HT are related to the problem of the existence of Hadamard matrices (the so-called Hadamard problem).

In this chapter, we have utilized a Williamson's construction of parametric Hadamard matrices in order to develop efficient computational algorithms of a special type of HTs-the Williamson-Hadamard transforms. Several algorithms for fast computation of a special type of HTs, namely, the Williamson-Hadamard transform, are presented. An efficient algorithm to compute 4t-point (t is an "arbitrary" integer number) Williamson-Hadamard transforms is traced. Comparative estimates revealing the efficiency of the proposed algorithms with respect to ones known are given, and the results of numerical examples are presented.

Section 5.1 describes the Hadamard matrix construction from Williamson matrices. Sections 5.2 and 5.3 present the block representation of parametric Williamson-Hadamard matrices and the fast Williamson-Hadamard block transform algorithm. In Section 5.4, the Williamson-Hadamard transform algorithm on add/shift architecture is developed. Sections 5.5 and 5.6 present fast Williamson-Hadamard transform algorithms based on multiplicative theorems. In Section 5.7, complexities of developed algorithms and also comparative estimates are presented, revealing the efficiency of the proposed algorithms with respect to ones known.

Online access to SPIE eBooks is limited to subscribing institutions.

Back to Top