Bruun's FFT Algorithm - A Polynomial Approach To The DFT

A Polynomial Approach To The DFT

Recall that the DFT is defined by the formula:

X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk }
\qquad
k = 0,\dots,N-1.

For convenience, let us denote the N roots of unity by ωNn (n = 0, ..., N − 1):

and define the polynomial x(z) whose coefficients are xn:

The DFT can then be understood as a reduction of this polynomial; that is, Xk is given by:

where mod denotes the polynomial remainder operation. The key to fast algorithms like Bruun's or Cooley–Tukey comes from the fact that one can perform this set of N remainder operations in recursive stages.

Read more about this topic:  Bruun's FFT Algorithm

Famous quotes containing the word approach:

    There is no calm philosophy of life here, such as you might put at the end of the Almanac, to hang over the farmer’s hearth,—how men shall live in these winter, in these summer days. No philosophy, properly speaking, of love, or friendship, or religion, or politics, or education, or nature, or spirit; perhaps a nearer approach to a philosophy of kingship, and of the place of the literary man, than of anything else.
    Henry David Thoreau (1817–1862)