<< >>

module_fft

The FFT module implements a set of functions that can be used to compute the FFT of a set of complex data points, or the inverse.

API

Sine arrays

The include file “fft.h” defines a set of arrays that are to be used with the FFT functions, called sine_8[], sine_16[], ..., sine_8192[]. Depending on the number of points, pick the appropriate array and pass it to fftForward and fftInverse as required.

FFT functions

void fftTwiddle(int re[], int im[], int N)

This function twiddles the arrays around prior to computing an FFT.

A calling sequence for a forward FFT involves fftTwiddle() followed by fftForward(), and for an inverse FFT it involves fftTwiddle() followed by fftInverse(). In some cases twiddling can be avoided, for example when computing a convolution.

Parameters:
  • re – real part of each input point
  • im – imaginary part of each input point
  • N – number of points. Must be a power of 2, both re and im should be N long
void fftForward(int re[], int im[], int N, int sine[])

This function computes a forward FFT.

The complex input array is supplied as two arrays of integers, with numbers represented as fixed-point values. The number of points must be a power of 2, and the array of sine values should contain a quarter sine-wave. Use one of sine_N provided in sine.h. The function does not perform a bit-twiddle - if required then fftTwiddle() should be called beforehand.

Parameters:
  • re – real part of each input point
  • im – imaginary part of each input point
  • N – number of points. Must be a power of 2, both re and im should be N long
  • sine – array of N/4+1 sine values, each represented as a sign bit, and a 31 bit fraction. 1 should be represented as 0x7fffffff.
void fftInverse(int re[], int im[], int N, int sine[])

This function computes an inverse FFT.

The complex input array is supplied as two arrays of integers, with numbers represented as fixed-point values. The number of points must be a power of 2, and the array of sine values should contain a quarter sine-wave. Use one of sine_N provided in sine.h. The function does not perform a bit-twiddle - if required then fftTwiddle() should be called beforehand.

Parameters:
  • re – real part of each input point
  • im – imaginary part of each input point
  • N – number of points. Must be a power of 2, both re and im should be N long
  • sine – array of N/4+1 sine values, each represented as a sign bit, and a 31 bit fraction. 1 should be represented as 0x7fffffff.
void fftTwoRealsForward(int re1[], int re2[], int im1[], int im2[], int N, int sine[])

This function computes the FFT of two real sequences in one go.

It uses a nifty trick () that enables one to use a single complex FFT to compute two real FFTs simultaneously. The real inputs should be in the first two real arrays, the output is in the real and imaginary arrays (the output of a real FFT is still a complex number).

Parameters:
  • re1 – array of first set of real numbers on which to compute FFT, on output this array stores the real part of the complex FFT on this set of numbers.
  • re2 – array of second set of real numbers on which to compute FFT, on output this array stores the real part of the complex FFT on this set of numbers.
  • im1 – imaginary parts of complex FFT of first array
  • im2 – imaginary parts of complex FFT of second array
  • N – number of points
  • sine – table with sine values.
void fftTwoRealsInverse(int re1[], int re2[], int im1[], int im2[], int N, int sine[])

This function computes the inverse FFT on two sets of complex data that are known to result in real numbers only in one go.

It uses a nifty trick () that enables one to use a single complex inverse FFT to compute two real inverse FFTs simultaneously. The outputs are in the two real arrays, the imaginary arrays are unchanged.

Parameters:
  • re1 – real part of first set of complex numbers on which to compute inverse FFT
  • re2 – real part of second set of complex numbers on which to compute inverse FFT
  • im1 – imaginary part of first set of complex numbers on which to compute inverse FFT
  • im2 – imaginary part of second set of complex numbers on which to compute inverse FFT
  • N – number of points
  • sine – table with sine values.

Example program

Below is an example calling sequence:

#include "fft.h"

int main(void) {
  int re[8], im[8];

  for(int i = 0; i < 8; i++) {
    // Fill re and im.
  }
  fftTwiddle(re, im, 8);
  fftForward(re, im, 8, sine_8);

  // Modify re and im, which are in the frequency domain

  fftTwiddle(re, im, 8);
  fftInverse(re, im, 8, sine_8);

  // and back to the time domain
}

DSP transformations (0v1)