Research On Jacket Matrices Over Finite Field And Its Fast Transforms

Amidst numerous matrices that are being utilized in engineering applications, Hadmarad matrices are in the forefront, which are used in image analysis and signal processing. There are also Conference matrix, C-matrix, Paley matrix, circulant matrix, circulent weighting matrix, which are used in conference telephony, weighting designs,Pn-matrix, and so on. As a ramification of Hadamard matrices and its generalized, a new concept called "Jacket matrices" was proposed by one of the authors Moon Ho Lee in 1989. Since the inverse of Jacket matrices can be easily determinded by element-wise inverse or block-wise inverse, most of interesting matrices, such as Discrete Fourier transform (DFT), Discrete Cosine transform (DCT), Slant and Haar matrix, all belong to Jacket matrices family. Such kinds of matrices have highly practical values for signal processing, communications, image compression and cryptography.With the aid of elengant propreties of Jacket matrices, the prime innovation of this thesis is based on this matrix along with Abstract algebra, Combinatorics, famous Fibonacci sequence and generalized prime factor algorithm. In summary, the thesis is organized as follows.Firstly, we propose a new notaion called the Fibonacci Jacket matrices which can be algebraically constructed via Fibonacci numbers over Galois field GF(p). Based on the algebraic structure, such kind of matrix with some inverse-constrains belong to Jacket matirces family. Employing the well-known Kronecker product of sparse matrices and successively lower order Fibonacci Jacket matrices, the fast construction and decomposition algorithms for large size Fibonacci Jacket matrices are investigated in detail.Secondly, enlighten by the idea of fast Jacket transforms, the simple factorization and construction algorithms for M-dimensional DFT matrices underlying generalized CRT index mappings are proposed.Finally, a notation referred as Cocyclic DFT matrix is proposed using Chinese Remainder Theorem (CRT) index mapping for DFT matrix. Following the mathematical proof, it can be seen that using CRT index scheme proves the resulting DFT matrix in possession of cocyclic property. By exploiting the close relationship of successively lower order DFT matrices, a fast construction (decomposition) approach for general cocyclic DFT matrix is describled in simple way.In our proposal, the new notations called as Fibonacci Jacket matrix and Cocyclic DFT matrix, belong to Jacket matrices family. Furthermore, we investigate fast construction and decomposition algorithms corresponding to the new members. Also, fast DFT matrices transforms based on generalized prime factor algorithm are suggested. Based on Kronecker product, successively lower order matrices, indentity matrices and recursive relations, the proposed algorithms are presented for implicity and clarity for it only minimally related to sparse matrices. The results indicate the presented algorithms perform quite well at decreasing the computation complexity.