Radix-3 Algorithm for Realization of Discrete Fourier Transform

In this paper, a new radix-3 algorithm for realization of discrete Fourier transform (DFT) of length N = 3m (m =\ud 1, 2, 3,...) is presented. The DFT of length N can be realized from three DFT sequences, each of length N/3. If\ud the input signal has length N, direct calculation of DFT requires O (N\ud 2\ud ) complex multiplications (4N\ud 2\ud real\ud multiplications) and some additions. This radix-3 algorithm reduces the number of multiplications required for\ud realizing DFT. For example, the number of complex multiplications required for realizing 9-point DFT using the\ud proposed radix-3 algorithm is 60. Thus, saving in time can be achieved in the realization of proposed algorithm