28 May 2003 Binary matrices, decomposition and multiply-add architectures
Author Affiliations +
Binary matrices or (±1)-matrices have found numerous applications in coding, signal processing, and communications. In this paper, a general and efficient algorithm of decomposition of binary matrices is developed. As a special case, Hadamard matrices are considered. The proposed scheme requires no zero padding of the input data. The problem of the construction of 4n-point Hadamard transform is related to the Hadamard problem: the question of existence of Hadamard matrices. (It is not proved whether for every integer n, there exists an orthogonal 4n×4n matrix with elements ±1). The number of real operation in developed algorithms is reduced from 0(N2) to 0(Nlog2N). Comparisons 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 I s 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 two. The algorithm has a simple and symmetric structure. The results of numerical examples are presented.
© (2003) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Hakob Sarukhanian, Hakob Sarukhanian, Sos S. Agaian, Sos S. Agaian, Jaakko T. Astola, Jaakko T. Astola, Karen O. Egiazarian, Karen O. Egiazarian, "Binary matrices, decomposition and multiply-add architectures", Proc. SPIE 5014, Image Processing: Algorithms and Systems II, (28 May 2003); doi: 10.1117/12.473134; https://doi.org/10.1117/12.473134

Back to Top