Abstract:

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.

Key words: signal processing, algorithm, fast DFT, digital hardware