Complex Fast Fourier Transform (CFFT) and Complex Inverse Fast Fourier Transform (CIFFT) is an efficient algorithm to compute Discrete Fourier Transform (DFT) and Inverse Discrete Fourier Transform (IDFT).
Computational complexity of CFFT reduces drastically when compared to DFT.

This library implements CFFT/CIFFT for Q15 data type. The functions operates on in-place buffer which uses same buffer for input and output. Complex input is stored in input buffer in an interleaved fashion.

The functions operate on blocks of input and output data and each call to the function processes 2*fftLen samples through the transform. pSrc points to In-place arrays containing 2*fftLen values.
The pSrc points to the array of in-place buffer of size 2*fftLen and inputs and outputs are stored in an interleaved fashion as shown below :

 {real[0], imag[0], real[1], imag[1],..}

Internally, the function utilize a radix-4 decimation in frequency algorithm and the size of the FFT supported are of the lengths [16, 64, 256, 1024, 4096].

Complex Fast Fourier Transform

Input real and imaginary data

x(n) = xa + j * ya
x(n+N/4 ) = xb + j * yb
x(n+N/2 ) = xc + j * yc
x(n+3N 4) = xd + j * yd

where N is length of FFT.

Output real and imaginary data

X(4r) = xa'+ j * ya'
X(4r+1) = xb'+ j * yb'
X(4r+2) = xc'+ j * yc'
X(4r+3) = xd'+ j * yd'

Twiddle factors for radix-4 FFT

Wn =  co1 + j * (- si1)   
W2n = co2 + j * (- si2)   
W3n = co3 + j * (- si3)

Output from Radix-4 CFFT results in digit reversal order. Interchange middle two branches of every butterfly results in bit reversed output./p>

Butterfly CFFT equations

xa' = xa + xb + xc + xd   
ya' = ya + yb + yc + yd   
xc' = (xa+yb-xc-yd)* co1 + (ya-xb-yc+xd)* (si1)   
yc' = (ya-xb-yc+xd)* co1 - (xa+yb-xc-yd)* (si1)   
xb' = (xa-xb+xc-xd)* co2 + (ya-yb+yc-yd)* (si2)   
yb' = (ya-yb+yc-yd)* co2 - (xa-xb+xc-xd)* (si2)   
xd' = (xa-yb-xc+yd)* co3 + (ya+xb-yc-xd)* (si3)   
yd' = (ya+xb-yc-xd)* co3 - (xa-yb-xc+yd)* (si3)

CIFFT uses same twiddle factor table as CFFT with modifications in the design equation as shown below.

Modified Butterfly CIFFT equations

xa' = xa + xb + xc + xd   
ya' = ya + yb + yc + yd   
xc' = (xa-yb-xc+yd)* co1 - (ya+xb-yc-xd)* (si1)   
yc' = (ya+xb-yc-xd)* co1 + (xa-yb-xc+yd)* (si1)   
xb' = (xa-xb+xc-xd)* co2 - (ya-yb+yc-yd)* (si2)   
yb' = (ya-yb+yc-yd)* co2 + (xa-xb+xc-xd)* (si2)   
xd' = (xa+yb-xc-yd)* co3 - (ya-xb-yc+xd)* (si3)   
yd' = (ya-xb-yc+xd)* co3 + (xa+yb-xc-yd)* (si3)   

Separate instance structure must be defined for each instance, but the twiddle factors and bit reversal tables can be reused.

Initialization Function

The initialization function performs the following operations :

• Sets the values of the internal structure fields.
• Initializes twiddle factor table and bit reversal table pointers.

Use of the initialization function is optional. However, if the initialization function is used, then the instance structure cannot be placed into a const data section.
To place an instance structure into a const data section, the instance structure must be manually initialized as follows :

TFFT_Radix4_Instance fftInstance = {fftLen, ifftFlag, bitReverseFlag, pTwiddle, pBitRevTable, twidCoefModifier, bitRevFactor}; 

where :

• fftLen: length of CFFT/CIFFT;
• ifftFlag: flag for selection of CFFT or CIFFT (set ifftFlag to calculate CIFFT, otherwise calculates CFFT);
• bitReverseFlag: flag for selection of output order (set bitReverseFlag to output in normal order, otherwise output in bit reversed order);
• pTwiddle: points to array of twiddle coefficients;
• pBitRevTable: points to the array of bit reversal table.
• twidCoefModifier: modifier for twiddle factor table which supports all FFT lengths with same table;
• bitRevFactor: modifier for bit reversal table which supports all FFT lengths with same table.

Pseudo code for generation of bit reversal table is :

for(l = 1; l <= N/4; l++) {
  for(i = 0; i < logN2; i++) {
    a[i] = l & (1 << i);   
  }   
  for(j = 0; j < logN2; j++){   
    if (a[j] != 0)   
      y[l] += (1 << ((logN2 - 1) - j));   
  }   
  y[l] = y[l] >> 1;   
}

where N = 1024, log2N = 10 and N is the maximum FFT size supported.

Pseudo code for generation of Q15 twiddle factors :

for(i = 0; i < N; i++) {   
  twiddleCoefQ15[2*i] = cos(i * 2*PI/(float)N);   
  twiddleCoefQ15[2*i+1] = sin(i * 2*PI/(float)N);   
}    

where cos and sin are in interleaved fashion.

Library Routines

• FFT_Radix4_Init
• FFT_Radix4

FFT_Radix4_Init

var status : byte;
    cfft_instance : TFFT_Radix4_Instance;
    cfft_instance_ptr : ^TFFT_Radix4_Instance;

cfft_instance_ptr := @cfft_instance;

// Initialize the CFFT function to compute 64 point FFT
status := FFT_Radix4_Init(cfft_instance_ptr, 64, 0, 1);

FFT_Radix4

const FFT_BLOCKSIZE : word = 128;

var Ak : array[FFT_BLOCKSIZE] of integer;      // q15 input A
    cfft_instance : TFFT_Radix4_Instance;
    cfft_instance_ptr : ^TFFT_Radix4_Instance;

cfft_instance_ptr = @cfft_instance;

// Transform input a[n] from time domain to frequency domain A[k]
FFT_Radix4(cfft_instance_ptr, @Ak);

Input and output formats

Internally input is downscaled by 2 for every stage to avoid saturations inside CFFT/CIFFT process. Hence the output format is different for different FFT sizes.
The input and output formats for different FFT sizes and number of bits to upscale are mentioned in the tables below for CFFT and CIFFT :

Input and Output Formats for Q15 CFFT

Input and Output Formats for Q15 CIFFT