FAST FOURIER TRANSFORM ALGORITHM USING FERMAT NUMBER TRANSFORM.

A fast Fourier transform (FFT) algorithm using Fermat number transform (FNT) is proposed, and the economical merit of the FFT processor via the algorithm is presented. The algorithm is based on the following three facts: (1) the DFT of prime transform length turns into discrete cyclic convolution (DCC). (2) The DCC can be computed through the number theoretic transform. (3) When the transform sequence length can be decomposed into the product of mutual prime integers, there exists the direct product of the individual factors of the DFT. Among number theoretic transforms, the FNT can be decomposed easily into modules and can be computed by an efficient algorithm. However, for the method using only (1) and (2) above, the transform length is limited. Using (3) above, the variety of transform length can be introduced. Since the proposed algorithm can be decomposed easily into modules, it may be realized easily in hardware. By computing the number of FNT butterfly and multiplication operations of the algorithm, the hardware cost is evaluated. The method costs approximately half that of the corresponding processor based on the radix-2 FFT.