1 January 2014

There's a good deal of information about the Discrete Fourier Transform online, and you can certainly learn from what exists. However, a long time ago I saw a nice characterization of it that I can no longer find, and think is worth writing about.

Consider a sequence $$(a_0, a_1, \ldots, a_{N-1})$$ of length $$N$$. Think of these as the coefficients of a polynomial $$f(x) = \sum_{k=0}^{N-1}a_kx^k$$. Clearly the coefficients determine the polynomial, but as we know we can also define $$f$$ uniquely by specifying its value at $$N$$ points, since we know it has degree $$N-1$$. The Discrete Fourier Transform of $$(a_0, a_1, \ldots, a_{N-1})$$ is the sequence $$(f(1), f(\zeta), f(\zeta^2), \ldots, f(\zeta^{N-1}))$$ where $$\zeta$$ is a primitive $$N$$th root of unity (generally $$e^{\frac{2i\pi}{N}}$$).

This formulation makes the circular convolution theorem almost trivial. If we have two sequences $$(a_0, \ldots, a_{N-1})$$ and $$(b_0, \ldots, b_{N-1})$$ and we consider their associated polynomials $$f(x) = \sum_{k=0}^{N-1} a_kx^k$$ and $$g(x) = \sum_{k=0}^{N-1} b_kx^k$$, then their product is of the form $$f(x)g(x) = \sum_{k=0}^{2N-2}\sum_{j=0}^{k}a_jb_{k-j}x^{k}$$. The coefficients are almost the circular convolution of the two sequences -- to get there we just need to combine the terms for $$x^k$$ with the terms for $$x^{k+N}$$. In other words, we need to take $$f(x)g(x)$$ modulo $$x^N - 1$$.

This means that $$h(x) = f(x)g(x) - r(x)(x^N - 1)$$ is the polynomial whose coefficients are the circular convolution of $$(a_0, \ldots, a_{N-1})$$ and $$(b_0, \ldots, b_{N-1})$$. Remember that to determine $$h$$, we just need to determine its value at $$N$$ distinct points, and whenever $$x^N - 1 = 0$$, we have $$h(x) = f(x)g(x)$$. As $$x^N - 1$$ has the $$N$$ distinct roots $$1, \zeta, \zeta^2, \ldots, \zeta^{N-1}$$, if we know the values of $$f$$ and $$g$$ at these points, we also know the value of $$h$$ there, and can therefore know all of $$h$$. In other words, we're just looking for the sequence $$(f(1)g(1), f(\zeta)g(\zeta), \ldots, f(\zeta^{N-1})g(\zeta^{N-1}))$$.