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 x_n:

The DFT can then be understood as a reduction of this polynomial; that is, X_k 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:

“F.R. Leavis’s “eat up your broccoli” approach to fiction emphasises this junkfood/wholefood dichotomy. If reading a novel—for the eighteenth century reader, the most frivolous of diversions—did not, by the middle of the twentieth century, make you a better person in some way, then you might as well flush the offending volume down the toilet, which was by far the best place for the undigested excreta of dubious nourishment.”
—Angela Carter (1940–1992)