# Peeter Joot's (OLD) Blog.

• 333,075

## Discrete Fourier transform

Posted by peeterjoot on October 11, 2013

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)

Summary

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)

# References

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