The Moshe And Hertz's Algorithm Of Discrete Fourier Transform Generalization And Its Application

Efficient DFT computation has been a challenge to the signal processing community over the last several decades. Moshe and Hertz present a method to compute the discrete Fourier transform (DFT) of an N-point real vector and the inverse DFT (IDFT) of the DFT of another real N-point vector by carrying out a single complex N-point DFT. This result is elegant and effective.This dissertation makes systematic research Moshe and Hertz's algorithm generalization and its application. The research results of this dissertation are summarized as fellow:1. This paper gives a brief prove proof that a 2-D circular convolution can be converted into 2-D linear convolution by adding zeroes.2. A briefer proof of Moshe and Hertz algorithm of DFT for the k-D case is given in this paper.3. This paper present a method to compute the Mensenne transform (MT) of an N-point integers sequence and the inverse MT(IMT)of the MT of another N-pointintegers sequence by carrying out a single MT of an N-point complex integers sequence over the finite field with q² elements (We abbreviate it F_q²). A newalgorithm which can calculate the complex number transform of two integer sequences simultaneous is presented in this paper.4. The results in 3 possibly exploit a new algorithm for computing the cyclic convolutions of integer sequences, which can apply to some digital signal analysis to reduce the computational complexity of convolutions and a number example is given.5. Present paper describes the generalization of Moshe and Hertz's algorithm over F_q² for the k-D case, where k≥2.6. A new singular value decomposition-discrete wavelet transform (SVD-DWT) composite image watermarking algorithm that is robust against geometric attacks and ordinary image processing is presented. The cover image is decomposed into four different frequency images by DWT and inverse discrete wavelet transform (IDWT). The watermarking can be embedded in the four different frequency images by singular value decomposition (SVD). In order to reduce the calculation complexity of DWT, a new fast Mallat decomposition algorithm is presented simultaneity. The 2-D Moshe and Hertz's algorithm of fast convolution is used in the fast Mallat decomposition algorithm. Experimental evaluation demonstrates that the watermarking algorithm is the most robust withstand a variety of attacks including common geometric attacks.