Decomposition of Binary Matrices and Fast Hadamard Transforms |
| |
Authors: | Hakob Sarukhanyan Sos Agaian Jaakko Astola Karen Egiazarian |
| |
Affiliation: | (1) Institute for Informatics and Automation Problems of NAS of Armenia, Yerevan, Armenia;(2) University of Texas at San Antonio, San Antonio, TX, USA;(3) Tampere International Center on Signal Processing, Tampere University of Technology, Tampere, Finland |
| |
Abstract: | Binary matrices or (± 1)-matrices have numerous applications in coding, signal processing, and communications. In this paper,
a general and efficient algorithm for decomposition of binary
matrices and the corresponding fast transform is developed. As a
special case, Hadamard matrices are considered. The difficulties
of the construction of 4n-point Hadamard transforms are
related to the Hadamard problem: the question of the existence of
Hadamard matrices. (It is not known whether for every integer n,
there is an orthogonal 4n × 4n matrix with elements ± 1.)
In the derived fast algorithms, the number of real
operations is reduced from O(N2) to O(N log N) compared to
direct computation. The proposed scheme requires no zero padding
of the input data. Comparisions revealing the efficiency of the
proposed algorithms with respect to the known ones are given. In
particular, it is demonstrated that, in typical applications,
the proposed algorithm is significantly more efficient than the
conventional Walsh-Hadamard transform. Note that for Hadamard
matrices of orders ≥ 96 the general algorithm is more
efficient than the classical Walsh-Hadamard transform whose
order is a power of 2. The algorithm has a simple and
symmetric structure. The results of numerical examples are
presented. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|