具有（N-1）/2次乘法的快速傅里叶变换

 本文提出递归傅里叶变换的一种快速实现方法。对于一个质数长度的离散傅里叶变换,仅需用一个复数系数就可以递归算出全部N个（N=P）频率分量。恰当地选用这个系数,使其为2^-m形式,就可以用（m-1）次移位代替乘法,免去了递归结构内部的乘法,大大提高运算速度。这种方法结构简单,总共需用（N-1）/2次实数常数乘法,尤其适于硬件实现。文中给出快速运算的系数表、硬件实现的方案及乘法次数的比较,讨论了系数误差的影响,并提出了高精度实现的方案。

FAST DFT WITH (N-1 )/2 MULTIPLICATIONS

A fast recursive algorithm for computing DFTs with prime length is proposed. This algorithm has a very simple structure and needs only one coefficient for computing all N frequency components in terms of permuting the input sequences. This coefficient has （N1l）possible choice, some of the coefiicients approximate to the form of 2-m, so one multiplication in the recursive loop can be replaced by shifting （m-1） steps. The shift is much faster than multiplication, the speed of the algorithm is very high. Only （N-1）/2 real multiplications are required to compute all N frequency components, they are much less than 2Nlog2N real multiplications of FFT.The errors and the coefficients with the form of 2-m are presented.The complexity of the algorithm is studied. The number of additions, multiplications and shifts for the algorithm are listed. A factor η is introduced, when the period ratio Tm/T3 of multiplier and adder is greater than the factor η, this algorithm is faster than FFT algorithm.The effect of coefficient error is analysed. The phase and ampli- tude errors are presented.The necessary condition of this algorithm is proposed. The noise introduced from the coefficient errors is presented. An implementation method for increasing the accuracy of coefficients, reducing errors and noise of systems is proposed. The sum of two shifts （2-m±2-n） is used to approximate to the coefficient. This implementation reduces the noise of systems about 20 db. The high accuracy scheme is presented.The coefficients with high ace uracy and noise are listed.The hardware scheme of this algorithm is presented. It is very simple, fast and cheap.