Fast Fourier transform: Difference between revisions

Jump to navigation Jump to search

Fast Fourier transform (view source)

Revision as of 21:06, 10 September 2022

1,906 bytes added ,  21:06, 10 September 2022
m
Text replacement - "<source" to "<syntaxhighlight"
m (2 revisions imported: Migrate from miraheze)
m (Text replacement - "<source" to "<syntaxhighlight")
 
(11 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.
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>


See [[wikipedia:FFT|fast Fourier transform]] and [[wikipedia:Discrete Fourier transform|Discrete Fourier transform]] on Wikipedia.
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.


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 ===
In this page the FFT is implemented with the [[wikipedia:FFT#Cooley–Tukey algorithm|Cooley–Tukey algorithm]] by dividing the transform into two pieces of size <source lang=apl inline>N÷2</source> at each step.
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]].
 
== APLX FFT Code ==
 
Note that [[APLX]] is no longer under development.


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</source> (N integer), and the algorithm will cope with varying N, unlike many DSP versions which are for fixed N.
* 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 <source lang=apl inline>Z[1;]</source>, maximum frequency in the middle; from there to <source lang=apl inline>¯1↑[1] Z</source> are negative frequencies. i.e. for an input Gaussian they transform a 'bath-tub' to a 'bath-tub'.
* 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]].


<source lang=apl>
<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
</source>
</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 />
 
[[Category:Applications]]
Retrieved from ‘https://aplwiki.com/wiki/Special:MobileDiff/1587...9195’

Navigation menu