Binary matrices, decomposition, and multiply-add architectures

Hakob Sarukhanian; Sos S. Agaian; Jaakko T. Astola; Karen O. Egiazarian

doi:10.1117/12.473134

28 May 2003 Binary matrices, decomposition and multiply-add architectures

Hakob Sarukhanian, Sos S. Agaian, Jaakko T. Astola, Karen O. Egiazarian

Proceedings Volume 5014, Image Processing: Algorithms and Systems II; (2003) https://doi.org/10.1117/12.473134
Event: Electronic Imaging 2003, 2003, Santa Clara, CA, United States

Abstract

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(N²) to 0(Nlog₂N). 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.

Citation Download Citation

Hakob Sarukhanian, Sos S. Agaian, Jaakko T. Astola, and Karen O. Egiazarian "Binary matrices, decomposition and multiply-add architectures", Proc. SPIE 5014, Image Processing: Algorithms and Systems II, (28 May 2003); https://doi.org/10.1117/12.473134

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available