Efficient output-pruning of the 2-D FFT algorithm

In this paper, an efficient algorithm for pruning the output samples of the radix-(2 × 2) two dimensional decimation-in-time FFT algorithm is presented. Comparisons with the existing algorithm show that substantial savings on the arithmetic operations, data transfers, address computations, and twiddle factor evaluations or accesses to the lookup table can be made. This is achieved by grouping in the radix-(2 × 2) 2-D DIT FFT algorithm all the stages that involve unnecessary operations into a single stage and introducing a new recursive technique for computing the resulting stage. Due to this grouping and the efficient indexing process introduced in this paper, the implementation of the proposed algorithm requires a minimum number of stages; however, that of the existing algorithm uses all the stages required by the radix-(2 × 2) 2-D DIT FFT. Therefore, the proposed algorithm also reduces the overall control and structural complexities.