二维离散傅里叶变换DFT(2~n;2)的快速新算法

New Fast Algorithm for Computing Two-dimensional Discrete Fourier Transform DFT(2n;2)

本文提出一种计算二维离散傅里叶变换DFT(2~n;2)的快速新算法,这种算法所需的非平凡实数乘法和加法次数是现有相应算法中最少的,而且这种算法仅使用实数乘法,在实数据输入情况下有更好的适应性,能在不改变算法实现结构条件下减少一半乘法次数。

This paper presents a new fast algorithm for computing two-dimensional discrete Fourier transform DFT(2n; 2). This algorithm has the lowest number of non-trivial real multiplications compared with any publisbed algorithms for computing DFT(2n;2). Furthermore, this algorithm uses only real multiplications and it shows that this algorithm is more suitable for real input data.