Abstract
This paper presents a full and well-developed view of the Fast Fourier Transform (FFT). It is intended for the reader who wishes to learn and develop his own fast Fourier algorithm. The approach presented here utilizes the matrix description of fast Fourier transforms. This approach leads to a systematic method for greatly reducing the complexity and the space required by variety of signal flow graph descriptions. This reduced form is called SNOCRAFT. From this representation, it is then shown how one can derive all possible fast Fourier transform algorithms, including the Weinograd Fourier transform algorithm. It is also shown from the SNOCRAFT representation that one can easily compute the number of multiplications and additions required to perform a specified fast Fourier transform algorithm.
After an elementary introduction to matrix representation of fast Fourier transform algorithm, the method of generating all possible fast Fourier transform algorithms is presented in detail and is given in three sections. The first section discusses the Generation of SNOCRAFT and the second section illustrates how Operations on SNOCRAFT are made. These operations include inversion and rotation. The last section deals with the FFT Analysis. In this section, examples are provided to illustrate how one counts the number of multiplications and additions involved in performing the transform that one has developed.
Get full access to this article
View all access options for this article.