Fast Fourier transform: Difference between revisions
Jump to navigation
Jump to search
m
Fast Fourier transform (view source)
Revision as of 14:53, 14 November 2019
, 14:53, 14 November 2019no edit summary
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> | ||