TOPICS
Search

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

F_n=sum_(k=0)^(N-1)f_ke^(-2piink/N)
(1)
=sum_(k=0)^(N/2-1)e^(-2piikn/(N/2))f_(2k)+W^nsum_(k=0)^(N/2-1)e^(-2piikn/(N/2))f_(2k+1)
(2)
=F_n^e+W^nF_n^o,
(3)

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

References

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. https://mathworld.wolfram.com/Danielson-LanczosLemma.html

Subject classifications