基3FFT与FHT的新算法

本文首先提出了适合于N=3~m的按频率抽取快速Fourier变换(DIF FFT)与按时间抽取快速Fourier变换(DIT FFT)的新算法,分别导出了算法的一般公式,给出了信号流图,分析了计算复杂性。对于实序列的FFT算法也相应作了探讨,然后按照类似的方式提出了适合于N=3~m的按频率抽取快速Hartley变换(DIF FHT)与按时间抽取快速Hartley变换(DIT FHT)的新算法。最后将本文提出的基3FFT算法、基3FHT算法与其他基3算法进行了比较。结果表明,新算法不仅所需运算量少,优于其他基3算法,而且可进行原位计算,结构简单规则,易用硬件或软件实现。本文算法扩展了FFT算法与FHT算法的可适用范围。

New Algorithms for Radix-3 FFT and FHT

First, the new decimation-in-frequency and decimation-in-time algorithms for the fast Fourier transform of length-3m are proposed in this paper. The general formulae are derived and the signal flowgraph is given. The computational complexity is analysed. The FFT algorithms for real data are also discussed. Then,similarly the new decimation-in-frequency and decimation-in-time algorithms for the fast Hartley transform of length-3m are proposed. Finally ,the algorithms proposed in this paper are compared with other ones. Results show that the new algorithms require fewer number of arithmetic operations and are superior to other radix-3 algorithms. Besides,the new algorithms allow in-place computation with simple and regular structure being easily implemented by either hardware or software. The applicability of FFT and FHT is extended.