Treffer: Equivalent Relationship of Function-level Representation and Implementation of Unified Indexing of FFT Algorithms

With the advance of the VLSI technology, the FFT algorithm has been pushed further in solving the multidimensional array signal processing in real time. Many DSP chip users have tried to find ways to improve addressing huge data in multidimension systems with minimum cost and maximum performance. However, there is no efficient method to address data for 1-D to M-D FFTs. A methodology has been defined to conquer the addressing problem of M-D FFT. It is well known that the twiddle factor matrix of Discrete Fourier Transform (DFT) can be recursively factored into basic butterfly stage matrices. The matrix can be factored into three matrices practically specifying the input data, twiddle factor, and output data sequence of the Fast Fourier Transform (FFT). The equivalent relationship of these matrices will be introduced. The equivalent relationship for a variety of the FFT algorithms can be obtained by equivalent transformations. Furthermore, the multidimensional (M-D) FFT can be represented by the same vector-matrix form as the one-dimensional (1-D) FFT. In addition, the addressing sequences of the 1-D FFT is a subset of the M-D FFT. Therefore, the signal flow graph of the 1-D FFT can be used to describe that of the M-D FFT and all M-D indexing can be implemented by 1-D indexing. Finally, this unified indexing approach was implemented into the WinDSP software simulator. Examples of M-D FFTs implemented with the unified indexing method are simulated on the WinDSP and the computation performance were analyzed. From the benchmark analysis, the 2-D FFT applications implemented with unified methodology use less instructions and the execution time is almost two times faster than the traditional method. WinDSP is a software simulator that simulates the functional characteristics of Sharp LH9124/LH9320 DSP chip set. It intended to manage the complete development of DSP applications, from conceptualization and experimentation, to verification of unified indexing for 1-D to M-D FFT. It is also intended for system ...