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

摘要

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