离散傅里叶变换的算术傅里叶变换算法

离散傅里叶变换(DFT)在数字信号处理等许多领域中起着重要作用.本文采用一种新的傅里叶分析技术—算术傅里叶变换(AFT)来计算DFT.这种算法的乘法计算量仅为O(N);算法的计算过程简单,公式一致,克服了任意长度DFT传统快速算法(FFT)程序复杂、子进程多等缺点;算法易于并行,尤其适合VLSI设计;对于含较大素因子,特别是素数长度的DFT,其速度比传统的FFT方法快;算法为任意长度DFT的快速计算开辟了新的思路和途径.

An Algorithm for Computing DFT Using Arithmetic Fourier Transform

The Discrete Fourier Transform (DFT) plays an important role in digital signal processing and many other fields.In this paper,a new Fourier analysis technique called the arithmetic Fourier transform (AFT) is used to compute DFT.This algorithm needs only O(N) multiplications.The process of the algorithm is simple and it has a unified formula,which overcomes the disadvantage of the traditional fast method that has a complex program containing too many subroutines.The algorithm can be easily performed in parallel,especially suitable for VLSI designing.For a DFT at a length that contains big prime factors,especially for a DFT at a prime length,it is faster than the traditional FFT method.The algorithm opens up a new approach for the fast computation of DFT.