The DFT

Screencast video [⯈]

Periodicity DFT and Periodic Extension (PE)

In general a discrete time signal $x[n]$ can have an infinite amount of samples from which the sampling index $n$ ranges from $-\infty$ to $+\infty$, as depicted at the left hand side of Fig. 1. However when using the $N$-point DFT, we select $N$ samples of $x[n]$, typically ranging from time index $n=0$ until $n=N-1$. The frequency indices $k$ of the DFT resulting samples $X[k]$ also range from $k=0$ until $k=N-1$. Both DFT and the Inverse DFT are periodic, or circular, operations. This periodic behavior can be shown for the Inverse DFT operation as follows: \
When increasing the index $n$ with $\lambda \times N$, in which $\lambda$ is a positive or negative integer, the Inverse DFT equation changes as follows: $$ x[n+ \lambda N]= \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N} k (n+ \lambda N)} =\frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N} k n} \cdot e^{j\frac{2\pi}{N} k \lambda N} $$ The last complex exponent is equal to one for all values of index $k$ and the result is equal to $x[n]$: $$ x[n+ \lambda N]= \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N} k n} \cdot e^{j2\pi k \lambda } = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j\frac{2\pi}{N} k n} \cdot 1 = x[n] $$ This implies that the Inverse DFT results in a periodic signal, denoted by $x_p[n]$, which has a period of $N$ samples. This periodic signal $x_p[n]$ can be constructed from the original signal $x[n]$ by first selecting the $N$ signal samples that are used in the DFT operation and then periodically repeat these samples. This Periodic Extension, abbreviated as PE, is depicted at the right hand side of Fig. 1. Obviously only one period of this period extended signal $x_p[n]$ is of importance. Typically we use the $N$ samples ranging from index $n=0$ until $n=N-1$ which is the so called Fundamental Period, abbreviated by FP.

In a similar way it can be shown that the DFT samples $X[k]$ are periodic: $$ X[k + \lambda N] = \sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{N}(k+ \lambda N) n} =\sum_{n=0}^{N-1} x[n] e^{-j\frac{2\pi}{N}k n} = X[k] \text{ } \Rightarrow \text{ } X_p[k]. $$ As a result of this periodic behavior we can redefine the DFT and IDFT operations in terms of the periodic extended notations as follows:

$$ \boxed{ \begin{eqnarray*} \text{DFT: } X_p[k] = \sum_{n=0}^{N-1} x_p[n] e^{-j\frac{2 \pi}{N} k n} \hspace{3mm} {\color{red}\bf \forall k} \qquad \text{IDFT: } x_p[n] = \frac{1}{N} \sum_{k=0}^{N-1} X_p[k] e^{j\frac{2 \pi}{N} k n} \hspace{3mm} {\color{red}\bf \forall n} \end{eqnarray*} } $$ In this definition the indices $n$ and $k$ range from $-\infty$ to $+\infty$. However we only need one period which is typically chosen in the index range from $0$ until $N-1$. In time domain this range of $N$ samples is the FP, representing the original $N$ signal samples of $x[n]$ which have been used for the DFT operation. In frequency domain this range of $N$ samples is the FI, which represents relative frequencies $\theta$ in the range $0$ until $2\pi$.

Note: To simplify the notation, we will sometimes omit the sub-index $p$ in the sequel if it is clear that we are dealing with a periodic extended signal.

Basic DFT summation or orthogonality property

In order to understand how the DFT equations can extract frequencies of a signal, we will see that the complex exponent $W_N=e^{j\frac{2\pi}{N}}$, the so called twiddle factor, plays a very important role. This can be shown by evaluating the following summation: $$ S[k]= \sum_{n=0}^{N-1} \{ W_N^k \} ^n = \sum_{n=0}^{N-1} \{ e^{j\frac{2 \pi}{N} k} \} ^n $$ which adds ,for each index $k$, $N$ terms of a discrete time phasor with relative frequency $\theta = k \cdot \frac{2\pi}{N}$. For this evaluation we shown that $S[k]$ is periodic with period $N$. With $\lambda$ a positive or negative integer this can be proven as follows: $$ \begin{eqnarray*} S[k + \lambda \cdot N ] &=& \sum_{n=0}^{N-1} \left \{ e^{j\frac{2 \pi}{N} (k + \lambda \cdot N)} \right \} ^n = \sum_{n=0}^{N-1} \left \{ e^{j\frac{2 \pi}{N} k} \cdot e^{j\frac{2 \pi}{N} \lambda \cdot N} \right \} ^n \newline &=& \left \{ e^{j\frac{2 \pi}{N} k} \cdot e^{j2 \pi \lambda } \right \} ^n = \left \{ e^{j\frac{2 \pi}{N} k} \cdot 1 \right \} ^n = S[k] \end{eqnarray*} $$ Because of this periodic behavior, we only need to evaluate $S[k]$ for one period, e.g. for $k=0, 1, \cdots , N-1$. For $k=0$ the result is: $$ S[k]|_{k=0}= \sum_{n=0}^{N-1} \{ e^{j\frac{2 \pi}{N} 0} \} ^n = \sum_{n=0}^{N-1} \{ 1\} ^n = N $$ To evaluate $S[k]$ for $k \neq 0$ we use the following general geometric series: $$ \sum_{n=0}^{N-1} a^n = \frac{1-a^N}{1-a} $$ which results into the following: $$ \begin{eqnarray*} S[k]|_{k\neq0}&=& \sum_{n=0}^{N-1} \{ e^{j\frac{2 \pi}{N} k} \} ^n = \frac{1-e^{j\frac{2 \pi}{N} k N}}{1-e^{j\frac{2 \pi}{N} k}} = \frac{1-e^{j2 \pi k}}{1-e^{j\frac{2 \pi}{N} k}} = \frac{1-1}{1-e^{j\frac{2 \pi}{N} k}}=0 \end{eqnarray*} $$ This leads to the following basic DFT summation or orthogonality property:

$$ \boxed{ \begin{eqnarray*} S[k]= \sum_{n=0}^{{\color{red}N}-1} \left \{ W_{{\color{red}N}}^k \right \} ^n = \sum_{n=0}^{{\color{red}N}-1} \left \{ \text{e}^{j \frac{2\pi}{{\color{red}N}} k } \right \} ^n = {\color{red}N} \delta [{\color{blue} k} \text{ mod}({\color{red}N})] \end{eqnarray*} } $$

Thus, the summation $S[k]$ is always equal to zero, except for the cases that the index $k$ is an $N$-fold, thus for $k$ equal to $0$ or $\pm N$ or $\pm 2N$ or etc. which can be described by the given delta function in which the index contains the modulo(N) operation.

How the DFT extracts a frequency

In this subsection we will show by an example, that the basic DFT summation property is used in the DFT algorithm to find the relative frequencies which are ‘hidden’ in the signal samples $x[n]$ for $n=0,1, \cdots, N-1$. In this example we use a DFT of length $N=4$, so for each resulting DFT index $k$ the result of the DFT operation describes how much of the relative frequency $k \times \frac{2 \pi}{4}$ is contained in the signal samples $x[n]$ in the range $n=0$ until $n=3$. In order to show how this works we use again the same sinusoidal example as before, namely $x[n]= \cos (\frac{\pi}{2} n)$: $$ X[k] = \sum_{n=0}^{3} x[n] e^{-j\frac{2\pi}{4} k n} = \sum_{n=0}^{3} \cos (\frac{\pi}{2} n) e^{-j\frac{\pi}{2} k n} $$ By using Euler, we can split the cosine into two discrete-time phasors, split the summation into two separate summations and combine in each of these summations the complex exponents:

\begin{eqnarray*} X[k]&=& \sum_{n=0}^{3} \frac{1}{2} \cdot \left ( e^{j\frac{\pi}{2} n} + e^{-j\frac{\pi}{2} n} \right ) e^{-j\frac{\pi}{2} k n} \newline &=& \frac{1}{2} \sum_{n=0}^{3} \left ( e^{j\frac{\pi}{2} n} \right ) e^{-j\frac{\pi}{2} k n} + \frac{1}{2} \sum_{n=0}^{3} \left ( e^{-j\frac{\pi}{2} n} \right ) e^{-j\frac{\pi}{2} k n} \newline &=& \frac{1}{2} \sum_{n=0}^{3} e^{-j\frac{\pi}{2} (k-1) n} + \frac{1}{2} \sum_{n=0}^{3} e^{-j\frac{\pi}{2} (k+1) n} \end{eqnarray*}

Now we can use for each of these individual summations the previous described basic DFT summation property. The first summation will always result into zero except for the case when the DFT frequency index $k-1$ is a 4-fold, thus for $k=1$ or $k=5$ or $k=-3$ etc. Mathematically this can be described by a delta function from which the index contains a modulo-4 operation as given in the first part of the following result: $$ X[k]= \frac{1}{2} \cdot 4 \delta[(k-1) \text{ mod}(4)]+ \frac{1}{2} \cdot 4 \delta[(k+1) \text{ mod}(4)] $$ The second summation will always result into zero except for the case when the DFT frequency index $k+1$ is a 4-fold, thus for $k=-1$ or $k=-5$ or $k=3$ etc. which also results in a delta function.

In the FI, which ranges from frequency index $k=0$ until $k=3$ in this case, this leads to the same two delta pulses as we have found before, namely: $$ \Rightarrow \hspace{2mm} \text{In FI: } X[k] = 2\delta[k-1] + 2\delta[k-3] $$ This example shows how the basic DFT summation property is used in the DFT algorithm to extract the frequency components of the $N$ signal samples $x[n]$.