Filter
Top Products
DSP_fft16x16t
4-118
Special Requirements
- In-place computation is not allowed.
- The size of the FFT, nx, must be power of 2 or 4, and 16 ≤ nx ≤ 32768.
- The arrays for the complex input data x[ ], complex output data y[ ], and
twiddle factors w[ ] must be double-word aligned.
- The input and output data are complex, with the real/imaginary
components stored in adjacent locations in the array. The real
components are stored at even array indices, and the imaginary
components are stored at odd array indices. All data are in short precision
or Q.15 format.
- The FFT coefficients (twiddle factors) are generated using the program
tw_fft16x16 provided in the directory ‘support\fft’. The scale factor must be
32767.5. No scaling is done with the function; thus, the input data must be
scaled by 2
log2(nx)
to completely prevent overflow.
Implementation Notes
- Bank Conflicts: nx/8 bank conflicts occur.
- Interruptibility: The code is interrupt-tolerant but not interruptible.
The routine uses log
4
(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:
Stage
Groups
Butterflies With Common
Twiddle Factors
Groups*Butterflies
1 N/4 1 N/4
2 N/16 4 N/4
.. .. .. ..
logN
1 N/4 N/4