APL Wiki|
Size: 3034
Comment:
|
Size: 2852
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 6: | Line 6: |
| . 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. . [[http://en.wikipedia.org/wiki/FFT|Wikipedia]] : . • A '''fast Fourier transform''' ('''FFT''') is an efficient [[http://en.wikipedia.org/wiki/Algorithm|algorithm]] to compute the [[http://en.wikipedia.org/wiki/Discrete_Fourier_transform|discrete Fourier]][[http://en.wikipedia.org/wiki/Discrete_Fourier_transform|transform]] (DFT) and its inverse. . • By far the most common FFT is the [[http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm|Cooley-]][[http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm|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... |
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 [[WikiPedia:FFT|fast Fourier transform]] ('''FFT''') is an efficient algorithm to compute the [[WikiPedia:Discrete_Fourier_transform|discrete Fourier transform]] (DFT) and its inverse. * By far the most common FFT is the [[WikiPedia:Cooley-Tukey_FFT_algorithm|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... |
| Line 13: | Line 15: |
| 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. |
| Line 15: | Line 17: |
| * X and Z are two row matrixes representing the imput 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] 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 [[http://en.wikipedia.org/wiki/Butterfly_(FFT_algorithm)|FFT Butterflies]]. |
* X and Z are two row matrixes representing the imput 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] 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 [[WikiPedia:Butterfly_(FFT_algorithm)|FFT Butterflies]]. |
| Line 39: | Line 41: |
| * 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 [[http://www.lab-tools.com|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 |
* I also have this code as '''APL\11''' or '''aplc''' plain text - contact me if you need these : <<MailTo(BUBBELBLUB J.B.W.Webber AT kent NONSENSE DOT ac DOT uk)>> * As [[http://www.lab-tools.com|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 : <<MailTo(VERY SPAMFREE Beau AT BLUR Lab-Tools DOT com)>> |
| Line 44: | Line 47: |
| . CategoryDigitalSignalProcessing CategoryScience CategoryMaths CategoryAlgorithm CategoryAplX | . CategoryDigitalSignalProcessing CategoryScience CategoryMaths CategoryAlgorithm CategoryAplx |
Fast Fourier Transform
Overview
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 fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (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 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 matrixes representing the imput 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] 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. 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
Variants
I also have this code as APL\11 or aplc plain text - contact me if you need these : <BUBBELBLUB J.B.W.Webber AT kent NONSENSE DOT ac DOT 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 : <VERY SPAMFREE Beau AT BLUR Lab-Tools DOT com>