For even length , split the input of a discrete Fourier transform into its even and odd samples, and . Let be their length- discrete Fourier transforms, with negative-exponent convention. Splitting the original sum by the parity of its index gives, for ,
The sign change follows from . Thus the same two short transforms supply both halves of the result through an FFT butterfly. For , recursive splitting reaches length one after levels. Each level needs arithmetic operations, so the time complexity is . For example, a length-four transform uses the two length-two transforms of and , then twiddle factors and .[ref]

Articles by others on the same topic (0)

There are currently no matching articles.