Structural considerations for large FFT programs on the TI TMS 32010 DSP microchip

The very first analyses of software FFT implementation details ignored such practicalities as amount of main memory available. However, Singleton\´s classic paper [1] -- appearing at a relatively early date -- described how very large FFT\´s could be implemented when a limited amount of fast, main data memory (i.e., "core") was available together with a large, but slower, secondary memory (e.g., tapes or discs). In this paper we describe the analogous steps taken in creating a family of time-efficient 64-, 128- and 256-point complex FFT\´s for the TI TMS 320, a DSP microchip with only 144 words of fast data memory but able to transfer data to and from a 4K program memory at a comparatively slow rate. The objective was to produce the fastest possible FFT\´s concommitant with having enough of the 4K of program memory remaining to double buffer incoming data and to contain the necessary non-time-critical, compact compact control code required to implement non-trivial DFT-based systems, such as vocoders. The resultant programs have 64/128/256 complex point execution times of 0.535, 2.3, and 6.3 msec, respectively, including bit reversal. This suggests that, for the first time, single chip DFT vocoders are feasible.