Compiler/TMS320C5517: How can i proceed 16384 or 32768 point FFT with dsplib, could you give help?

Hello Ralf,

The Radix-2 FFT algorithm works by breaking down an N-point FFT into 2 N/2-point FFTs then recombining the results. It repeats this breakdown until several 2-point FFTs are remaining, but we use the FFT butterfly to calculate these 2-point FFTs easily. Then there is just the matter of stitching back together the nested sub-FFTs with some complex math, applying the twiddle factors in the process.

The FFT appnote - SPRABB6 describes the high-level algorithm for using 1024-point FFTs to calculate larger FFTs. See an excerpt below.

Download SPRABB6 here: http://www.ti.com/lit/an/sprabb6b/sprabb6b.pdf

See below MATLAB code for generating and plotting twiddle factors for any length FFT. Note that you can use a subset of a twiddle table for larger FFTs for smaller sized FFTs.

clear;
close all;

% Creates Twiddle Factors for an N-point FFT %

N = 4096;

twidle = zeros(1,N);    % Real and Imag combined in [Re,Im,Re,Im] format
twid_r = zeros(1,N/2);  % Just Real part of Twiddle 
twid_r = zeros(1,N/2);  % Just Imag part of Twiddle 

n = 0:(N/2-1);    % discrete-time grid 

% Add Real part
twid_r = cos(2*pi*n/N);        
twiddle(1:2:N) = cos(2*pi*n/N);

% Create Imag part
twid_i = -sin(2*pi*n/N);
twiddle(2:2:N) = -sin(2*pi*n/N);

% Quantize to S16Q15 Fixed-Point Format
twiddle_fi = fi(twiddle,1,16,15);
twiddle_fi_hex = twiddle_fi.hex;

twid_r_fi = fi(twid_r,1,16,15);
twid_r_fi_hex = twid_r_fi.hex;

twid_i_fi = fi(twid_i,1,16,15);
twid_i_fi_hex = twid_i_fi.hex;

subplot(2,1,1)
plot(twid_r_fi)
title('Re\{Twiddle\}')

subplot(2,1,2)
plot(twid_i_fi)
title('Im\{Twiddle\}')

For optimization, it is possible to adapt the DSPLIB assembly code to support larger FFTs, but for proof of concept, C-code can be used.

Another optimization would be to use the Radix-4 FFT algorithm instead of the Radix-2. Radix-4 breaks the FFT problem into 4 smaller problems instead of 2.

Keep in mind that C55xx is a fixed-point processor (16-bit natural words), so dynamic range and precision become a problem with these larger FFTs. If you lose too much information about the signal, consider a floating point processor like C6000.

Hope this helps,
Mark