A fast algorithm is proposed for recursively computing the DFTs of prime length. Only (N-1) / 2 real multiplications are required to compute all N frequency components in terms of permuting the input data. The multipl...A fast algorithm is proposed for recursively computing the DFTs of prime length. Only (N-1) / 2 real multiplications are required to compute all N frequency components in terms of permuting the input data. The multiplication in recursive computation is replaced by shifting. Complexity of the algorithm is studied. A factor η is introduced and presented. When the ratio of multiplier's period Tm to adder's period Ta is greater than the factor η (i.e.Tm / Ta >η), the new algorithm is faster than FFT. The necessary condition and error of the algorithm are studied. The signal-to-noise ratio for different length N is presented. A high accuracy scheme is proposed for improving the SNR about 20 -30dB.展开更多
文摘A fast algorithm is proposed for recursively computing the DFTs of prime length. Only (N-1) / 2 real multiplications are required to compute all N frequency components in terms of permuting the input data. The multiplication in recursive computation is replaced by shifting. Complexity of the algorithm is studied. A factor η is introduced and presented. When the ratio of multiplier's period Tm to adder's period Ta is greater than the factor η (i.e.Tm / Ta >η), the new algorithm is faster than FFT. The necessary condition and error of the algorithm are studied. The signal-to-noise ratio for different length N is presented. A high accuracy scheme is proposed for improving the SNR about 20 -30dB.
