Research on the Improved Vector Coding Algorithm for Two Dimensional Discrete Fourier Transform

摘要

Discrete Fourier Transform (DFT) plays a crucial role in signal processing. In this paper, a new fast algorithm is presented for two dimensional DFT with different lengths. This algorithm is derived using a technique for multidimensional integral point called 'vector coding'. The new algorithm significantly reduces the multiplications and recursive stages compared with row-column algorithm, and also skip the data transposing. The algorithm can spread to multidimensional DFT. For two dimensional, compared with row-column algorithm, the vector coding algorithm has the same addition, but about three-quarters of multiplication, and reduce the recursive stages a half.