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 = 1, 2, 3,...) is presented. The DFT of length N can be realized from three DFT sequences, each of length N/3. If the input signal has length N, direct calculation of DFT requires O (N2) complex multiplications (4N2 real multiplications) and some additions. This radix-3 algorithm reduces the number of multiplications required for realizing DFT. For example, the number of complex multiplications required for realizing 9-point DFT using the proposed radix-3 algorithm is 60. Thus, saving in time can be achieved in the realization of proposed algorithm.