An Algorithm for Computing 4^M-Point DFT Based on 4-Point DFT Block

摘要

An algorithm for computing 4M-point DFT based on 4-point DFT block is developed. The new algorithm, in comparison to radix-4 FFT algorithm, requires the same number of additions and multiplications, but employs a dissimilar flow-graph. In the flow-graph of the new algorithm, the 4-point DFT blocks replace the accustomed butterfly computational networks. The new algorithm permits one 4M-point DFT to be computed using a 4-point DFT block, and the block requirements is M×4M-1. Because the total number of computational requirements of directly computing a 4-point DFT is only 16 real additions, a command block and hardware block for computing 4-point DFT may be obtained. When using a processor which integrates with a fast 4-point DFT block to compute 4M-point DFT, the speed of DFT will be faster than that of radix-4 FFT. The algorithm based on 4-point DFT block will be helpful to improve the DSP technology and speed.