4,500
edits
(Reference for early Quote Quad implementation) |
m (Text replacement - "<source" to "<syntaxhighlight") |
||
(10 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
The '''fast Fourier transform''' ('''FFT''') is an algorithm to compute the discrete Fourier transform of a [[vector]] in time <math>O(n log(n))</math>, where a naive implementation achieves only <math>O(n^2)</math> time. APL implementations of the fast Fourier transform began appearing as early as 1970, with an 8-line implementation by Alan R. Jones published in [[APL Quote-Quad]].<ref>Jones, Alan R. ([[IBM]]). "Fast Fourier transform". [[APL Quote-Quad]] Volume 1, Number 4. 1970-01.</ref> | The '''[[wikipedia:fast Fourier transform|fast Fourier transform]]''' ('''FFT''') is an algorithm to compute the [[wikipedia:discrete Fourier transform|discrete Fourier transform]] of a [[vector]] in time <math>O(n log(n))</math>, where a naive implementation achieves only <math>O(n^2)</math> time. APL implementations of the fast Fourier transform began appearing as early as 1970, with an 8-line implementation by Alan R. Jones published in [[APL Quote-Quad]].<ref>Jones, Alan R. ([[IBM]]). "Fast Fourier transform". [[APL Quote-Quad]] Volume 1, Number 4. 1970-01.</ref> | ||
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. | |||
== Implementations == | |||
=== APLX === | |||
This FFT code is implemented with the [[wikipedia:Cooley–Tukey FFT algorithm|Cooley–Tukey FFT algorithm]] by dividing the transform into two pieces of size <syntaxhighlight lang=apl inline>N÷2</syntaxhighlight> at each step. It will run under [[APLX]]. | |||
This is as given in Robert J. Korsan's article in APL Congress 1973, p 259-268, with just line labels and a few comments added. | This is as given in Robert J. Korsan's article in APL Congress 1973, p 259-268, with just line labels and a few comments added. | ||
* X and Z are two-row [[Matrix|matrices]] representing the input and output real and imaginary data. The data length must be < | * X and Z are two-row [[Matrix|matrices]] representing the input and output real and imaginary data. The data length must be <syntaxhighlight lang=apl inline>2*N</syntaxhighlight> (N integer), and the algorithm will cope with varying N, unlike many DSP versions which are for fixed N. | ||
* Zero frequency is at < | * Zero frequency is at <syntaxhighlight lang=apl inline>Z[1;]</syntaxhighlight>, maximum frequency in the middle; from there to <syntaxhighlight lang=apl inline>¯1↑[1] Z</syntaxhighlight> 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 an array of 2×2 [[wikipedia:Butterfly diagram|FFT Butterflies]]. | * This is an elegant algorithm, and works by transforming the input data into an array of 2×2 [[wikipedia:Butterfly diagram|FFT Butterflies]]. | ||
< | <syntaxhighlight lang=apl> | ||
Z←fft X;N;R;M;L;P;Q;S;T;O | Z←fft X;N;R;M;L;P;Q;S;T;O | ||
⍝ | ⍝ | ||
Line 34: | Line 30: | ||
→loop | →loop | ||
done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X | done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X | ||
</ | </syntaxhighlight> | ||
=== Simple recursive implementation === | |||
<syntaxhighlight lang=apl> | |||
fft←{ | |||
1>K←2÷⍨M←≢⍵:⍵ | |||
0≠1|2⍟M:'Length of the input vector must be a power of 2' | |||
odd←∇(M⍴1 0)/⍵ | |||
even←∇(M⍴0 1)/⍵ | |||
exp←*(0J¯2×(○1)×(¯1+⍳K)÷M) | |||
(odd+T),odd-T←even×exp | |||
} | |||
</syntaxhighlight> | |||
{{Works in|[[Dyalog APL]]}} | |||
Sample usage: | |||
fft 1 1 1 1 0 0 0 0 | |||
4 1J¯2.414213562 0 1J¯0.4142135624 0 1J0.4142135624 0 1J2.414213562 | |||
Inverse FFT can be defined for testing: | |||
<syntaxhighlight lang=apl> | |||
ifft←{(≢⍵)÷⍨+fft+⍵} | |||
test←{⌈/(10○⊢)(⍵-ifft fft ⍵)} | |||
test 1 1 1 1 0 0 0 0 | |||
7.850462E¯17 | |||
</syntaxhighlight> | |||
2-dimensional FFT and inverse 2D FFT: | |||
<syntaxhighlight lang=apl> | |||
fft2D←{ | |||
∨/0≠1|2⍟⍴⍵:'Matrix dimensions must be powers of 2' | |||
⍉(fft⍤1)⍉(fft⍤1)⍵ | |||
} | |||
ifft2D←{(≢∊⍵)÷⍨+fft2D+⍵} | |||
</syntaxhighlight> | |||
Sample usage: | |||
fft2D 2 2⍴⍳4 | |||
10 ¯2 | |||
¯4 0 | |||
ifft2D fft2D 2 2⍴⍳4 | |||
1 2 | |||
3 4 | |||
=== Dyalog APL === | |||
FFT appears in [[dfns.dws]], a [[workspace]] supplied with [[Dyalog APL]], in the context of fast multi-digit multiplication<ref>dfns.dws: [http://dfns.dyalog.com/n_xtimes.htm xtimes] — Fast multi-digit product using FFT</ref>. Extracted from there, it is there defined as: | |||
<syntaxhighlight lang=apl> | |||
roots←{×\1,1↓(⍵÷2)⍴¯1*2÷⍵} | |||
cube←{⍵⍴⍨2⍴⍨2⍟⍴⍵} | |||
floop←{(⊣/⍺)∇⍣(×m)⊢(+⌿⍵),[m-0.5]⍺×[⍳m←≢⍴⍺]-⌿⍵} | |||
FFT←{,(cube roots⍴⍵)floop cube ⍵} | |||
</syntaxhighlight> | |||
== References == | == References == | ||
<references /> | <references /> | ||
[[Category:Applications]] |