Fast Fourier Transform

Overview

• [Still being edited by Beau]
• A Fourier Transform (FFT) is a method of calculating the frequency components in a data set - and the inverse FFT converts back from the frequency domain - 4 applications of the FFT rotates you round the complex plane and leaves you back with the original data.

  Wikipedia :

• • A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fouriertransform (DFT) and its inverse.

• • By far the most common FFT is the Cooley-Tukey algorithm :

• • The most well-known use of the Cooley-Tukey algorithm is to divide the transform into two pieces of size N / 2 at each step...

APLX FFT Code

This is as given in <NAME>'s article in Apl Congress 1973, p 267, with just a few comments added.

• X and Z are two row matrixes representing the real and imaginary data. The data length must be 2*N (N integer), and the algorithm will cope with varying N, unlike many DSP versions which are for fixed N.
• Zero frequency is at Z[1;], maximum frequency in the middle; from there to ¯1↑[1] Z are negative frequencies. i.e. for an input Gaussian they transform a 'bath-tub' to a 'bath-tub'.

• This is an elegant algorithm, and works by transforming the input data into a array of 2×2 FFT Butterflies.

•     Z←fft X;N;R;M;L;P;Q;S;T;O
  ⍝
  ⍝ Apl Congress 1973, p 267.
  ⍝
  ⍝ Restructure as an array of primitive 2×2 FFT Butterflies
  X←(2,R←(M←⌊2⍟N←¯1↑⍴X)⍴2)⍴⍉X
  ⍝ Build sin and cosine table :
  Z←R⍴⍉2 1∘.○○(-(O←?1)-⍳P)÷P←N÷2
  ⍝ Z←R⍴⍉2 1∘.○○((-(O←?1)-⍳N)-P)÷P←N÷2
  ⍝
  Q←⍳P←M-1+L←0
  T←M-~O
  loop:→(M≤L←L+1)⍴done
  X←(+⌿X),[O+¯0.5+S←M-L](-/Z×-⌿X),[O+P-0.5]+/Z×⌽-⌿X
  Z←(((-L)⌽Q),T)⍉R⍴((1+P↑(S-1)⍴1),2)↑Z
  →loop
  done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X

Variants

• I also have this code as APL\11 or aplc plain text - contact me if you need these : J.B.W.Webber@kent.ac.uk

• As Lab-Tools Ltd. I can supply well-tested variants that have a time column, work with real and imaginary data, are correctly normalised in both amplitude and time, and (say) transform a centralised Gaussian to a centralised Gaussian. Also variants that transform Q to R (and R to Q) for neutron and X-Ray scattering. These have been tested with up to 100k data point (2*17) arrays : Beau@Lab-Tools.com

• CategoryDigitalSignalProcessing