Peeter Joot's (OLD) Blog.

Math, physics, perl, and programming obscurity.

Discrete Fourier transform

Posted by peeterjoot on October 11, 2013

[Click here for a PDF of this post with nicer formatting]

For decoupling trial solutions of lattice vibrations we have what appears to be a need for the use of a discrete Fourier transform. This is described briefly in [1], but there’s no proof of the inversion formula. Let’s work through that detail.

Let’s start given a periodic signal of the following form

\begin{aligned}a_n = \sum_{k = 0}^{N-1} A_k e^{-2 \pi i k n/N },\end{aligned} \hspace{\stretch{1}}(1.1)

and assume that there’s an inversion formula of the form

\begin{aligned}A_k' \propto \sum_{n = 0}^{N-1} a_n e^{2 \pi i k' n/N }.\end{aligned} \hspace{\stretch{1}}(1.2)

Direct substitution should show if such a transform pair is valid, and determine the proportionality constant. Let’s try this

\begin{aligned}\sum_{n = 0}^{N-1} a_n e^{2 \pi i k' n/N }=\sum_{n = 0}^{N-1} e^{2 \pi i k' n/N }\sum_{k = 0}^{N-1} A_k e^{-2 \pi i k n/N }=\sum_{k = 0}^{N-1} A_k \sum_{n = 0}^{N-1} e^{2 \pi i (k' - k)n/N }.\end{aligned} \hspace{\stretch{1}}(1.3)

Observe that the interior sum is just N when k' = k. Let’s sum this for the values k \ne k', writing

\begin{aligned}S_N(k'-k) = \sum_{n = 0}^{N-1} e^{2 \pi i (k' - k)n/N }.\end{aligned} \hspace{\stretch{1}}(1.4)

With a = \exp( 2 \pi i (k' - k)/N) we have

\begin{aligned}S_N(k'-k) = \sum_{n = 0}^{N-1} a^n= \frac{a^N - 1}{a - 1}= \frac{a^{N/2}}{a^{1/2}} \frac{a^{N/2} - a^{-N/2}}{a^{1/2} - a^{-1/2}}= e^{ \pi i (k' - k)(1 - 1/N)} \frac{ \sin \pi (k'-k) }{\sin \pi (k' - k)/N}.\end{aligned} \hspace{\stretch{1}}(1.5)

Observe that k' - k \in [-N+1, N-1], and necessarily takes on just integer values. We have terms of the form \sin \pi m, for integer m in the numerator, always zero. In the denominator, the sine argument is in the range

\begin{aligned}[ \pi \left( -1 + \frac{1}{{N}} \right), \pi \left( 1 - \frac{1}{{N}} \right)],\end{aligned} \hspace{\stretch{1}}(1.6)

We can visualize that range as all the points on a sine curve with the integer multiples of \pi omitted, as in fig. 1.1.

Fig 1.1: Sine with integer multiples of pi omitted

Clearly the denominator is always non-zero when k \ne k'. This provides us with the desired inverse transformation relationship

\begin{aligned}\sum_{n = 0}^{N-1} a_n e^{2 \pi i k' n/N }= N \sum_{k' = 0}^{N-1} A_k' \delta_{k, k'}= N A_k'.\end{aligned} \hspace{\stretch{1}}(1.7)


Now that we know the relationship between the discrete set of values a_n and this discrete transformation of those values, let’s write the transform pair in a form that explicitly expresses this relationship.

\begin{aligned}\boxed{\begin{aligned}a_n &= \sum_{k = 0}^{N-1} \tilde{a}_k e^{-2 \pi i k n/N } \\ \tilde{a}_k &= \frac{1}{{N}} \sum_{n = 0}^{N-1} a_n e^{2 \pi i k n/N }.\end{aligned}}\end{aligned} \hspace{\stretch{1}}(1.8)

We have also shown that our discrete sum of exponentials has an delta function operator nature, a fact that will likely be handy in various manipulations.

\begin{aligned}\boxed{\sum_{n = 0}^{N-1} e^{2 \pi i (k' - k)n/N } = N \delta_{k, k'}.}\end{aligned} \hspace{\stretch{1}}(1.9)


[1] S.S. Haykin. Communication systems. Wiley, 1994.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: