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:

    “Let me approach at least, and touch thy hand.
    [Samson:] Not for thy life, lest fierce remembrance wake
    My sudden rage to tear thee joint by joint.
    At distance I forgive thee, go with that;
    Bewail thy falsehood, and the pious works
    It hath brought forth to make thee memorable
    Among illustrious women, faithful wives:
    Cherish thy hast’n’d widowhood with the gold
    Of Matrimonial treason: so farewel.”
    —John Milton (1608–1674)