离散傅立叶变换的迭代算法

An Iterative Algorithm for the Discrete Fourier Transform

本文提出了一种新的离散傅立叶变换算法(Iterative Algorithm for theDiscrete Fourier Transform),简称IAFT。IAFT算法和FFT算法在其本原理上完全不同,IAFT采用循环迭代的计算过程来实现DFT。这种算法能够使第一个采样点进入后就开始运算,而和其他点的运算没有关系。各点的运算可以互不影响地进行。当最后一个采样点输入后,就可以往外连续输出变换的结果。这种算法的特点是充分利用了输入时间进行计算,因而得到快速处理的效果。该算法对信号的点数无限制,可以是任意的自然数。该算法所需的硬件在并行处理的情况下比EET简单而且规则,其变换时间极限情况达到输入信号所需时间加上作一次乘法所需的时间,一般考虑所需硬件最少,极限最长时间为输入信号所需时间加上作N次乘法所需时间。

It is well known that FFT (Fast Fourier Transform) hardwares must waitfor all sample points of a signal to be received and sent into storage beforethe FFT processor can start computing. In this paper, in order to eliminate the delay just mentioned, a new algo-rithm, called by the author as IAFT (Iterative Algorithm for the Discrete Fo-urier Transform), is presented. The new algorithm is quite different from FFTin basic method and offers the following three advantages, of which the first isthe most important: (1) As each sample point of a signal is received, IAFT can start comput-ing immediately. When the last sample point of the signal comes in, most ofthe computation has been done and the results of DFT (Discrete FourierTransform) of the signal can be given one after another. (2) when the input signals are sequences of real numbers, IAFT, unlikeFFT (FFT always computes in complex numbers), can execute all computationsin the real domain. (3) Unlike common FFT (common FFT's signal size N must be powersof 2), the signal size N of IAFT can be any natural number. Some preliminary computing has been done with IAFT and the results arepromising. It should be emphasized that IAFT is valuable only when speed is of pa-ramount importance; in other words, it is suitable for highly parallel real-timesignal processing.