The Algorithm For Two Dimensional Discrete Fourier Transform Of Different Length

With the development of modern technology, FFT (Fast Fourier Transform) is widely used in more and more fields such as acoustics, structure dynamics, number theory, combinatorial mathematics, statistics, cryptology, oceanography, communi- cation, etc. Especially in the digital signal processing, FFT speeds up the numerical calculation involved in tens of thousands of times. We may even consider that the most fields of modern digital processing hadn't been explored until this technology applied on.Therefore, an increasing number of people begin to focus on the study of FFT. They intend to find some better ways for speeding up FFT's calculation.Vector coding algorithms is a new-style of FFT which applied vector-coding for multidimensional integral point. Compared with row-column algorithm, it signify- cantly reduces the number of multiplication and iterations and also skips the data transposing.In this paper, Cooley-Tukey algorithm, which is the most fundamental algorithm in DFT, is analyzed and elaborated in detail. Then some other one-dimensional FFT algorithms are introduced for a comparison. After that, vector coding algorithm is particularly analyzed with an emphasis on the application of vector coding algorithm for two-dimensional DFT while the lengths are different. In the end, this algorithm is tested for its validity. Its accuracy and speed are evaluated.