Danielson-Lanczos Lemma

The discrete Fourier transform of length N (where N is even) can be rewritten as the sum of two discrete Fourier transforms, each of length N/2. One is formed from the even-numbered points; the other from the odd-numbered points. Denote the nth point of the discrete Fourier transform by F_n. Then


where W=e^(-2pii/N) and n=0,...,N. This procedure can be applied recursively to break up the N/2 even and odd points to their N/4 even and odd points. If N is a power of 2, this procedure breaks up the original transform into lgN transforms of length 1. Each transform of an individual point has F_n^(eeo...)=f_k for some k. By reversing the patterns of evens and odds, then letting e=0 and o=1, the value of k in binary is produced. This is the basis for the fast Fourier transform.

See also

Discrete Fourier Transform, Fast Fourier Transform, Fourier Transform

Explore with Wolfram|Alpha


Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 407-411, 1989.

Referenced on Wolfram|Alpha

Danielson-Lanczos Lemma

Cite this as:

Weisstein, Eric W. "Danielson-Lanczos Lemma." From MathWorld--A Wolfram Web Resource.

Subject classifications