Microsoft Word - H.Sarukhanyan_2.doc Mathematical Problems of Computer Science 34, 2010. 10 Orthogonal Transforms for Digital Signal and Image Processing Hakob Sarukhanyan Institute for Informatics and Automation Problems of NAS RA Abstract In this report there are presented some primary results obtained in Digital Signal and Image Processing laboratory of the Institute for Informatics and Automation Problems of NAS RA. Fast Discrete Orthogonal Transforms: The computation of unitary transforms is a complicated and time-consuming task. However, it would not be possible to use the orthogonal transforms in signal and image processing applications without effective algorithms to calculate them. Note that both complexity issues–efficient software and circuit implementations are the heart of the most applications. An important question in many applications is how to achieve the highest computation efficiency of the discrete orthogonal transforms (DOT) [1]. The suitability of unitary transforms in each of the above applications depends on the properties of their basis functions as well as on the existence of fast algorithms, including parallel ones. A fast DOT is an efficient algorithm to compute the DOT and its inverse with an essentially smaller number of operations than direct matrix multiplication. Recall that the DOT of the sequence )(nf is given by     1 0 1 ,1,0],[][][ N n nN NkknfkY  where ]}[{ kn is an orthogonal system. It follows that the determination of each Y[k] requires N multiplication and N – 1 addition. Because we have to evaluate Y[k] for ,1,0  Nk it follows that the direct determination of DFT requires N(N – 1) operations, which means that the number of multiplication and additions/subtractions is proportional to 2N , i.e., the complexity of DFT is ).( 2NO General Concept in Design of the Fast DOT Algorithms: A fast transform fTN may be achieved by factoring the transform matrix NT by the multiplication of k sparse matrices. Typically, nN 2 and ,1212 FFFFT nnn  where iF are very sparse matrices so that the complexity of multiplying by iF is ),( NO .,1 ni  Fast Fourier Transform: Particularly, the Fourier matrix NF of order nN 2 can be represented as ,112211 BABABABF nnnN  where rA and iA are sparse matrices of the following form 11     .,1, ,1,1, 222 12 2 1 2 0 222 1 1111 niIHIB nrWWWIIA ini rn rnrnrnrnr i r       ,2         H  is a sign of Kronecker product, and        k M jW kM 2 exp .Therefore the fast Fourier transform has the complexity )log( 2 NNO . The nN 2 -point Fourier transform of a },,,{ 110  Nxxxx  with assumption ]1[]1[  Nxx can be represented as (see also [2,3]) .1,0,]14[]14[]4[][ 1 0 1 0 1 0 4 4 4 4 2 2          NnWkxWWkxWWkxnX N N N N N N k nkn N k nkn N k nk By introducing the notations ;1,0,]4[][ 2 1 0 0 2 2     N k nk nWkxnY N N ,]14[][ 1 0 1 4 4    N N k nkWkxnY ,1,0,]14[][ 4 1 0 2 4 4     N k nk nWkxnY N N FFT can be realized as follows         .1,0,][][][][ ,][][][][ ,][][][][ ,][][][][ 421404 3 2104 2 21404 210         Nn N n N NN n N n N N n N n N NN n N n N nnYWnYWjnYnX nYWnYWnYnX nYWnYWjnYnX nYWnYWnYnX The number of operations for a realization of FFT given below .6)1( 9 2 9 38 log 3 4 ,2)1( 9 2 9 16 log 3 8 2 2 log 2 log 2     N N N N NNNC NNNC Fast Hadamard Transform: The Hadamard matrix NH of order nN 2 can be factorized as follows: ,121 FFFFH nnN  where   .,,2,1,222 1 niIHIF inii   It is not difficult to show that nN 2 -point fast Hadamard transform (FHT) has the complexity )log( 2 NNO (Note that FHT requires only the additions and subtraction operations). Later, in [4] were developed more general FHT which have the complexity  1log 2  knnknD with assumption that Hadamard matrix nH of order n has the following representation kkn AvAvAvH  2211 where iv are k-size (-1,+1) mutualy orthogonal vectors, and kjA j ,1,  are nk n  size (0,-1,+1) matrices with the following conditions .,,2,1, ,,,2,1,,,0 , ,)1,1( ,,,2,1,,, 1 1 kiIAA kjijiAA IAA matrixaisA kjijiAA k nk n i T i j T i nk n k i T ii k i i ji             12 A-S theorem and its generalization: In 1981 Agaian and Sarukhanyan [5] have offered a construction method of Hadamard matrix (H-matrix) of order mn/2 proceeding from existence H-matrices of order m and n (see Figure below). Later, this result has been named by multiplicative theorem A-S (the multiplicative theorem of Agaian-Sarukhanyan) [6]. In the same place, the existence of H-matrix of order mnpq/16 is proved based on A-S theorem. Further, by using of the Multiplicative method there have been developed methods of construction hybrid orthogonal matrices and corresponding fast transform algorithms. Last years A-S methodwas successfully applied at construction of Lapped transforms and Filter Banks, and also at construction Antipodal Paraunitary matrices and their application in orthogonal frequency division multiplexing (OFDM) systems [7, 8]. References 1. N. Ahmed and K. R. Rao, Orthogonal Transforms for Digital Signal Processing. Springer-Verlag, New York (1975). 2. R. Yavne, “An economical method for calculating the discrete Fourier transform,” Proc. AFIPS Fall Joint Computer Conf., vol. 33, 1968, pp. 115–125. 3. M. Frigo and S. G. Johnson, “A modified split-radix FFT with fewer arithmetic operations,” IEEE Transactions on Signal Processing, vol. 55, pp. 111-119, 2007. 4. H. Sarukhanyan. Decomposition of the Hadamard Matrices and Fast Hadamard Transform. Computer Analysis of Images and Patterns, Lecture Notes in Computer Science, vol. 1296, 1997, pp. 575-581 5. S. Agaian, H. Sarukhanyan. Recurrence Formulae Construction of Williamson’s Type Matrices. Math. Notes, vol. 30, No.3- 4, 1981, pp. 796-804 6. J. Seberry and M. Yamada, “Hadamard matrices, sequences, and block designs,” in Contemporary Design Theory: A Collection of Surveys, J. H. Dinitz and D. R. Stinson, Eds. New York: Wiley, 1992. 7. See-May Phoong, Yuan-Pei Lin. Lapped Hadamard Transforms and Filter Banks, IEEE, ICASSP 2003, vol. 6, 2003, pp. 509-512. 8. See-May Phoong, Kai-Yen Chang. Antipodal Paraunitary Matrices and Their Application to OFDM Systems, IEEE Trans. on Signal Processing, vol. 53, No. 4, 2005, pp. 1374-1386.