Texas Instruments TMS320C64X manual DSPfft16x16imre

DSP_fft16x16_imre

The routine uses log4(nx) − 1 stages of radix-4 transform and performs either a radix-2 or radix-4 transform on the last stage depending on nx. If nx is a power of 4, then this last stage is also a radix-4 transform, otherwise it is a radix-2 transform. The conventional Cooley Tukey FFT is written using three loops. The outermost loop “k” cycles through the stages. There are log N to the base 4 stages in all. The loop “j” cycles through the groups of butterflies with different twiddle factors, and loop “i” reuses the twiddle factors for the different butterflies within a stage. Note the following:

		Butterflies With Common
Stage	Groups	Twiddle Factors	Groups*Butterflies
1	N/4	1	N/4
2	N/16	4	N/4
..	..	..	..
logN	1	N/4	N/4

The following statements can be made based on above observations:

1)Inner loop “i0” iterates a variable number of times. In particular, the number of iterations quadruples every time from 1..N/4. Hence, software pipelining a loop that iterates a variable number of times is not profitable.

2)Outer loop “j” iterates a variable number of times as well. However, the number of iterations is quartered every time from N/4 ..1. Hence, the behavior in (a) and (b) are exactly opposite to each other.

3)If the two loops “i” and “j” are coalesced together then they will iterate for a fixed number of times, namely N/4. This allows us to combine the “i” and “j” loops into one loop. Optimized implementations will make use of this fact.

In addition, the Cooley Tukey FFT accesses three twiddle factors per iteration of the inner loop, as the butterflies that reuse twiddle factors are lumped together. This leads to accessing the twiddle factor array at three points, each separated by “ie”. Note that “ie” is initially 1, and is quadrupled with every iteration. Therefore these three twiddle factors are not even contiguous in the array.

4-12