Fast Implementation of Recursive DFTs

A fast implementation of recursive DFTs is presented. It only needs (N-1)/2 real multiplications to compute all N frequency components. A factor $$R_{T}$$ R T is introduced. If the ratio $$T_{m}/T_{a}$$ T m / T a of multiplier’s and adder’s period is greater than $$R_{T}$$ R T , this scheme is faster than FFT. The error of systems is studied. A parallel scheme of adders is proposed. This scheme is much faster than the usual serial adder. A scheme for fast re-ordering the input data is proposed. This increases the reordering speed and saves the memory size.