Mixed-Radix and CORDIC Algorithm for Implementation of FFT

Abstract

The Fast Fourier Transform (FFT) is an efficient algorithm to compute the Discrete Fourier Transform (DFT) which exploits symmetry and periodicity in the DFT. Because of its efficiency, the algorithm is implemented in many Digital Signal Processing (DSP) applications and hardware platforms for real-time applications. FFT applications also include spectrum analysis, speech processing and filter designs where filter coefficients are determined according to the frequency of the filter. In this paper, a 128-point FFT is designed by employing mixed-radix number representation to effectively reduce the number of additions and multiplications. In addition, the computational complexity of twiddle factors (essentially involving the sine and cosine trigonometric computations) in butterfly operations of FFT is reduced by using CORDIC module, to confine the multiplication operations to simple addition and shift operations.