CMSIS-DSP: Radix-8 Complex FFT Functions

| CMSIS-DSP Version 1.4.7 CMSIS DSP Software Library

- Main Page
- Usage and Description
- Reference

All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
Radix-8 Complex FFT Functions
Transform Functions

  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 set of functions implements CFFT/CIFFT for floating-point data types. 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],..}

Lengths supported by the transform:

  Internally, the function utilize a Radix-8 decimation in frequency(DIF) algorithm and the size of the FFT supported are of the lengths [ 64, 512, 4096].

Algorithm:

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-8 FFT:

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

  Radix-8 Decimation-in Frequency Complex Fast Fourier Transform

  Output from Radix-8 CFFT Results in Digit reversal order. Interchange middle two branches of every butterfly results in Bit reversed output.

  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)

  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; `pBitRevTable` modifier for bit reversal table which supports all FFT lengths with same table. `onebyfftLen` value of 1/fftLen to calculate CIFFT;

Fixed-Point Behavior
  Care must be taken when using the fixed-point versions of the CFFT/CIFFT function. Refer to the function specific documentation below for usage guidelines.