Fast Fourier transform: Difference between revisions
Jump to navigation
Jump to search
Miraheze>Marshall (Port from old aplwiki.com) |
Miraheze>Marshall mNo edit summary |
||
| 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 '''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. | ||
See [ | 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. | ||
In this page the FFT is implemented with the [ | 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. | ||
== APLX FFT Code == | == APLX FFT Code == | ||
| Line 15: | Line 15: | ||
* 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 <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. | ||
* 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 <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'. | ||
* This is an elegant algorithm, and works by transforming the input data into an array of 2×2 [ | * 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> | <source lang=apl> | ||
Revision as of 14:53, 14 November 2019
The fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier transform of a vector in time , where a naive implementation achieves only time.
See fast Fourier transform and 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.
In this page the FFT is implemented with the Cooley–Tukey algorithm by dividing the transform into two pieces of size N÷2 at each step.
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.
- X and Z are two-row matrices representing the input and output 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] Zare 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 FFT Butterflies.
Z←fft X;N;R;M;L;P;Q;S;T;O ⍝ ⍝ Apl Congress 1973, p 267. Robert J. Korsan. ⍝ ⍝ 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 ⍝ 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