A Polynomial Approach To The DFT
Recall that the DFT is defined by the formula:
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:
“Genuine polemics approach a book as lovingly as a cannibal spices a baby.”
—Walter Benjamin (18921940)