4,494
edits
Fast Fourier transform: Difference between revisions
Jump to navigation
Jump to search
m
Fast Fourier transform (view source)
Revision as of 21:01, 10 September 2022
, 21:01, 10 September 2022Text replacement - "</source>" to "</syntaxhighlight>"
(→Simple recursive implementation: otherwise produces text garbage on incorrect input) |
m (Text replacement - "</source>" to "</syntaxhighlight>") |
||
| Line 5: | Line 5: | ||
== Implementations == | == Implementations == | ||
=== APLX === | === 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 <source lang=apl inline>N÷2</ | 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 <source 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 <source lang=apl inline>2*N</ | * X and Z are two-row [[Matrix|matrices]] representing the input and output real and imaginary data. The data length must be <source 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 <source lang=apl inline>Z[1;]</ | * Zero frequency is at <source lang=apl inline>Z[1;]</syntaxhighlight>, maximum frequency in the middle; from there to <source 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]]. | ||
| Line 30: | 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 === | === Simple recursive implementation === | ||
| Line 42: | Line 42: | ||
(odd+T),odd-T←even×exp | (odd+T),odd-T←even×exp | ||
} | } | ||
</ | </syntaxhighlight> | ||
{{Works in|[[Dyalog APL]]}} | {{Works in|[[Dyalog APL]]}} | ||
Sample usage: | Sample usage: | ||
| Line 55: | Line 55: | ||
test 1 1 1 1 0 0 0 0 | test 1 1 1 1 0 0 0 0 | ||
7.850462E¯17 | 7.850462E¯17 | ||
</ | </syntaxhighlight> | ||
2-dimensional FFT and inverse 2D FFT: | 2-dimensional FFT and inverse 2D FFT: | ||
| Line 64: | Line 64: | ||
} | } | ||
ifft2D←{(≢∊⍵)÷⍨+fft2D+⍵} | ifft2D←{(≢∊⍵)÷⍨+fft2D+⍵} | ||
</ | </syntaxhighlight> | ||
Sample usage: | Sample usage: | ||
| Line 81: | Line 81: | ||
floop←{(⊣/⍺)∇⍣(×m)⊢(+⌿⍵),[m-0.5]⍺×[⍳m←≢⍴⍺]-⌿⍵} | floop←{(⊣/⍺)∇⍣(×m)⊢(+⌿⍵),[m-0.5]⍺×[⍳m←≢⍴⍺]-⌿⍵} | ||
FFT←{,(cube roots⍴⍵)floop cube ⍵} | FFT←{,(cube roots⍴⍵)floop cube ⍵} | ||
</ | </syntaxhighlight> | ||
== References == | == References == | ||