DISCRETE TIME FOURIER TRANSFORMS
Similarly to continuous-time fourier transformations, discrete-time fourier transforms is the expansion of a discrete signal $X[n]$ into a complex exponential basis $D$, which is defined as:
\begin{eqnarray}
D: \{ \quad \vec{V_{\Omega}}=e^{i\Omega n} \quad | \quad \Omega \in \mathbb{R}, \quad 0<\Omega<2\pi, \qquad n \in \mathbb{I} \quad \}
\end{eqnarray}
$D$, like $B$ contains uncountably infinite basis vectors. But unlike the $\omega$ in $B$ which can take values in $(-\infty,\infty)$, $\Omega$ in $D$ is limited to an interval of $(0,2\pi)$. This is because in the set of continuous basis vectors $C$, each different $\omega \in (-\infty,\infty)$ gives us a different basis vector $\vec{u}_{\omega}$. But in the set of discrete basis vectors $D$, $\Omega$ and $\Omega+2\pi$ will give us the same basis vector $\vec{V}_{\Omega+2\pi} = \vec{V}_{\Omega}$. Therefore, it is sufficient to limit $\Omega$’s to a finite interval $(0, 2\pi)$.
Also, we can define $\Omega$ in any $2\pi$-long interval, as $e^{i\Omega n}$ is periodic in $\Omega$ with $2\pi$. Any $(A,A+2\pi)$ interval will do. $A$ here is an arbitrary real number. $(-\pi,\pi)$ or $(6\pi, 8\pi)$ will do as well as $(0,2\pi)$. But we will use $(0,2\pi)$ for convenience.
Before expanding any function $X[n]$ into it, we must check that the vectors of $D$ is orthonormal.
Orthonormality of the basis $B$
\begin{eqnarray}
\vec{V_{\Omega_1}}.\vec{V_{\Omega_2}} &=& \sum_{k=-\infty}^{\infty} e^{i\Omega_1 k} (e^{i\Omega_2 k})^* \\
&=& \sum_{k=-\infty}^{\infty} e^{i\Omega_1 k} e^{-i\Omega_2 k} \\
&=& \sum_{k=-\infty}^{\infty} e^{i(\Omega_1–\Omega_2) k} \\
\end{eqnarray}
Using a previous result with the substitutions $ \Omega_1–\Omega_2 \rightarrow 2\pi t $, we arrive at
\begin{eqnarray}
&=& \lim_{N \rightarrow \infty}\frac{\sin[\frac{(2N+1)}{2}(\Omega_1–\Omega_2)]}{\sin[\frac{1}{2}(\Omega_1–\Omega_2)]}
&=&\sum_{k=-\infty}^{\infty}\delta(\frac{\Omega_1–\Omega_2}{2\pi}-k)
\end{eqnarray}
Using the scaling property
\begin{eqnarray}
&=&2\pi\sum_{k=-\infty}^{\infty}\delta(\Omega_1–\Omega_2-2\pi k)
\end{eqnarray}
What does this equation tells us? It says that the vectors $V_{\Omega_1}=e^{i\Omega_1 n}$ and $V_{\Omega_2}=e^{i\Omega_2 n}$ are orhogonal to each other as long as the difference between $\Omega_1$ and $\Omega_2$ is not an exact mutliple of $2\pi$. But note that when we have defined $D$ we have limited our $\Omega$’s to a $2\pi$-long interval. Therefore the vectors in $D$ are orthogonal.
Discrete Fourier and its inverse
Now we can expand the expansion of $X[n]$ in the basis $D$ as
\begin{eqnarray}
\vec{X}&=& \int_{\Omega=0}^{2\pi} (\vec{X}.\vec{V}_{\Omega}) \vec{V_{\Omega}} d\Omega
\end{eqnarray}
Define $X(\Omega)=\vec{X}.\vec{V}_{\Omega}$. The equation above becomes
\begin{eqnarray}
\vec{X }&=& \int_{\Omega=0}^{2\pi} X(\Omega) \vec{V}_{\Omega} d\Omega
\end{eqnarray}
or,
\begin{eqnarray}
X[n] &=& \int_{\Omega=0}^{2\pi} X(\Omega) \frac{e^{i\Omega n}}{\sqrt{2\pi}} d\Omega
\end{eqnarray}
where
\begin{eqnarray}
X(\omega) &=& \vec{X }.\vec{V}_{\Omega}\\
&=& \sum_{n=-\infty}^{\infty} X[n] \left(\frac{e^{i\Omega n}}{\sqrt{2\pi}}\right)^* \\
&=& \sum_{n=-\infty}^{\infty} X[n] \frac{e^{-i\Omega n}}{\sqrt{2\pi}} \qquad(2)\\
\end{eqnarray}
(2) is known as the fourier transformation and (1) is known as the inverse fourier transformation. Note that $X(\Omega)$ is the same vector with $X[n]$, just written in a different basis.
More traditionally, Fourier transform – Inverse transform pair is written as follows:
\begin{eqnarray}
X[n] &=& \frac{1}{2\pi}\int_{0}^{2\pi} X(\Omega) e^{i\Omega n}d\Omega \qquad(3)\\
X(\Omega) &=& \sum_{n=-\infty}^{\infty} X[n] e^{-i\Omega n} \qquad(4)
\end{eqnarray}
And this is the final form we’ll use them. Note that
- (3) passes from frequency representation $X(\Omega)$ to time representation $X[n]$
- (4) passes from time representation $x(t)$ to frequency representation $X(\omega)$
Some examples
0) Consider the discrete signal $X[n] =$ 2 -1 0 $\underline{4}$ 6 2 1. Its DFT is
\begin{eqnarray}
X(\Omega) &=& 2e^{3i\Omega}-e^{2i\Omega} + 4 + 6e^{-i\Omega} + 2e^{-2i\Omega} + e^{-3i\Omega}
\end{eqnarray}
1) Find the DFT of $x[n]=e^{-\alpha n}U[n]$ where $ 0<|\alpha|<1$
\begin{eqnarray}
X(\Omega) &=& \sum_{n=-\infty}^{\infty} e^{-\alpha n}U[n]e^{-i\Omega n} \\
&=& \sum_{n=0}^{\infty} e^{-\alpha n}e^{-i\Omega n} \\
&=& \sum_{n=0}^{\infty} e^{-(\alpha+i\Omega) n} \\
&=& \frac{1}{1-e^{-(\alpha+i\Omega) }}
\end{eqnarray}
2) Find the DFT of kronecker delta $\delta[n]$.
\begin{eqnarray}
DFT(\delta[n]) &=& \sum_{n=-\infty}^{\infty} \delta[n] e^{-i\Omega n} \\
&=& e^{-i\Omega 0} \\
&=& 1
\end{eqnarray}
3) Find the DFT of shifted kronecker delta $\delta[n-a]$, $a\in \mathbb{I}$.
\begin{eqnarray}
DFT(\delta[n-a]) &=& \sum_{n=-\infty}^{\infty} \delta[n-a] e^{-i\Omega n} \\
&=& e^{-i\Omega a}
\end{eqnarray}
4) Find the DFT of $\chi_{(-N,N)}[n]$, where $N\in \mathbb{I}$.
\begin{eqnarray}
DFT(\chi_{(-N,N)}[n]) &=& \sum_{n=-\infty}^{\infty} \chi_{(-N,N)}[n] e^{-i\Omega n} \\
&=& \sum_{n=-N}^{N} e^{-i\Omega n}\\
&=& e^{-i\Omega N}\sum_{n=0}^{2N} e^{i\Omega n}\\
&=& e^{-i\Omega N} \frac{1-e^{i\Omega (2N+1)}}{1-e^{i\Omega}}\\
&=& e^{-i\Omega N} \frac{e^{i\Omega (N+\frac{1}{2})}(e^{-i\Omega (N+\frac{1}{2})}-e^{i\Omega (N+\frac{1}{2})})}{e^{i\frac{\Omega}{2}}(e^{-i\frac{\Omega}{2}}-e^{i\frac{\Omega}{2}})} \\
&=& \frac{e^{-i\Omega (N+\frac{1}{2})}-e^{i\Omega (N+\frac{1}{2})}}{e^{-i\frac{\Omega}{2}}-e^{i\frac{\Omega}{2}}}\\
&=& \frac{\sin(\Omega (N+\frac{1}{2}))}{\sin(\frac{\Omega}{2})}
\end{eqnarray}
5) Find the DFT of 1.
\begin{eqnarray}
DFT(1) &=& DFT(\lim_{N \rightarrow \infty} \chi_{(-N,N)}[n])\\
&=& \lim_{N \rightarrow \infty}\frac{\sin(\Omega (N+\frac{1}{2}))}{\sin(\frac{\Omega}{2})}
\end{eqnarray}
In eq (..), if we place $\frac{\Omega}{2\pi}\rightarrow t$, we get
\begin{eqnarray}
DFT(1) &=& \lim_{N \rightarrow \infty} \frac{\sin(\Omega (N+\frac{1}{2}))}{\sin(\frac{\Omega}{2})} = \sum_{n=-\infty}^{\infty} \delta\left( \frac{\Omega}{2\pi} – n \right) =2\pi \sum_{n=-\infty}^{\infty} \delta\left( \Omega – 2\pi n \right)
\end{eqnarray}
6) Find the DFT of $U[n]$.
\begin{eqnarray}
DFT(U[n]) &=& \sum_{n=-\infty}^{\infty} U[n] e^{-i\Omega n} \\
&=& \sum_{n=0}^{\infty} e^{-i\Omega n} \\
&=& \lim_{N \rightarrow \infty} \frac{1-e^{-i\Omega (N+1)}}{1-e^{-i\Omega}}\\
&=& \frac{1}{1-e^{-i\Omega}} – \lim_{N \rightarrow \infty} \frac{e^{-i\Omega (N+1)}}{1-e^{-i\Omega}} \frac{e^{i\frac{\Omega}{2}}}{e^{i\frac{\Omega}{2}}}\\
&=& \frac{1}{1-e^{-i\Omega}} – \lim_{N \rightarrow \infty} \frac{e^{-i\Omega (N+\frac{1}{2})}}{e^{i\frac{\Omega}{2}}-e^{-i\frac{\Omega}{2}}}\\
&=& \frac{1}{1-e^{-i\Omega}} – \frac{1}{2i}\lim_{N \rightarrow \infty} \frac{\cos({-\Omega (N+\frac{1}{2}))}+i\sin({-\Omega (N+\frac{1}{2}))}}{\sin(\frac{\Omega}{2})}\\
&=& \frac{1}{1-e^{-i\Omega}} – \frac{1}{2i}\lim_{N \rightarrow \infty} \frac{\cos({\Omega (N+\frac{1}{2}))}}{\sin(\frac{\Omega}{2})} + \frac{1}{2}\lim_{N \rightarrow \infty} \frac{\sin({\Omega (N+\frac{1}{2}))}}{\sin(\frac{\Omega}{2})}
\end{eqnarray}
Using the results from the section “periodic dirac delta functions” (with the substitution $\frac{\Omega}{2\pi} \rightarrow t$), we get
\begin{eqnarray}
DFT(U[n]) &=& \frac{1}{1-e^{-i\Omega}} +\sum_{k=-\infty}^{\infty}\pi \delta(\Omega-2\pi k)
\end{eqnarray}
Periodic case: Fourier series and Fourier representation
$$
\begin{eqnarray}
X(\Omega)&=& \sum_{n=-\infty}^{\infty} x[n] e^{-i \Omega n}\\
&=& \sum_{k=-\infty}^{\infty} \sum_{n=0}^{N-1}x[kN+n] e^{-i \Omega (kN+n)}\\
&=& \sum_{k=-\infty}^{\infty} \sum_{n=0}^{N-1}x[n] e^{-i \Omega n}e^{-i \Omega kN}\\
&=& \left(\sum_{n=0}^{N-1}x[n] e^{-i \Omega n}\right)\left(\sum_{k=-\infty}^{\infty}e^{-i \Omega kN}\right)
\end{eqnarray}
$$
Recall that we had already proven in a previous chapter
$$
\sum_{k=-\infty}^{\infty}e^{{2 \pi i} kt}=\sum_{n=-\infty}^{\infty}\delta(t-n)
$$
In this formula, if we substitute $t \rightarrow \frac{N}{2\pi}\Omega$
\begin{eqnarray}
\sum_{k=-\infty}^{\infty} e^{ik \Omega N} &=& \sum_{n=-\infty}^{\infty}\delta(\frac{N}{2\pi}\Omega-n) &=& \sum_{n=-\infty}^{\infty}\delta\left( \frac{N}{2\pi} \left( \Omega-\frac{2\pi}{N}n \right)\right)
\end{eqnarray}
Note that $\sum_{k=-\infty}^{\infty}e^{-i \Omega kN}=\sum_{k=-\infty}^{\infty}e^{i \Omega kN}$, and using the scaling property of dirac deltas, we arrive at
\begin{eqnarray}
\sum_{k=-\infty}^{\infty} e^{-ik \Omega N} &=& \frac{2\pi}{N} \sum_{n=-\infty}^{\infty}\delta\left( \Omega-\frac{2\pi}{N}n \right)
\end{eqnarray}
Substituting
\begin{eqnarray}
X(\Omega)&=& \left(\sum_{n=0}^{N-1}x[n] e^{-i \Omega n}\right)\left(\frac{2\pi}{N}\sum_{k=-\infty}^{\infty} \delta(\Omega – \frac{2 \pi k}{N})\right)\\
&=& \frac{2\pi}{N}\sum_{k=-\infty}^{\infty} \left(\sum_{n=0}^{N-1}x[n] e^{-i \Omega n}\right) \delta(\Omega – \frac{2 \pi k}{N})\\
&=& \frac{2\pi}{N}\sum_{k=-\infty}^{\infty} \left(\sum_{n=0}^{N-1}x[n] e^{-i \frac{2 \pi k}{N} n}\right) \delta(\Omega – \frac{2 \pi k}{N})\\
&=& \frac{2\pi}{N}\sum_{k=-\infty}^{\infty} Na_k \delta(\Omega – \frac{2 \pi k}{N})\\
&=& 2\pi\sum_{k=-\infty}^{\infty} a_k \delta(\Omega – \frac{2 \pi k}{N})
\end{eqnarray}
Some Examples
1) Find the DFT of the periodic signal $\ldots$ 1,2, 0, $\underline{1}$, 2, 0, 1, 2, 0,1, $\ldots$ with period 3.
As this signal is periodic, we have to compute $a_k$’s as a first step:
\begin{eqnarray}
a_0 &=& \frac{1}{3} (1e^{i\frac{2\pi}{3}0.0}+2e^{i\frac{2\pi}{3}0.1}+0e^{i\frac{2\pi}{3}0.2}) = \frac{1}{3}(1+2+0)=1\\
a_1 &=& \frac{1}{3} (1e^{i\frac{2\pi}{3}1.0}+2e^{i\frac{2\pi}{3}1.1}+0e^{i\frac{2\pi}{3}1.2}) = \frac{1+2e^{i\frac{2\pi}{3}}}{3}\\
a_2 &=& \frac{1}{3} (1e^{i\frac{2\pi}{3}2.0}+2e^{i\frac{2\pi}{3}2.1}+0e^{i\frac{2\pi}{3}2.2}) = \frac{1+2e^{i\frac{4\pi}{3}}}{3}
\end{eqnarray}
Note that because of the periodicity $a_i = a_{3m+i}$, $m \in \mathbb{I}$ hence $a_i$ is well-defined for all $i$.
\begin{eqnarray}
X(\Omega) =2\pi \sum_{m=-\infty}^{\infty} \left[ \delta\left( \Omega-\frac{2\pi}{3}3m \right) + \frac{1+2e^{i\frac{2\pi}{3}}}{3} \delta\left( \Omega-\frac{2\pi}{3}(3m+1) \right)+ \frac{1+2e^{i\frac{4\pi}{3}}}{3} \delta\left( \Omega-\frac{2\pi}{3}(3m+2) \right) \right]
\end{eqnarray}
2) Find the DFT of $e^{i\frac{2\pi}{N}kn}$, $a \in \mathbb{R}$, $k<N$. Note that this is a periodic signal with period $N$, and the fourier coefficients $a_n$ can be found by observation: All the fourier coefficients are zero except $a_{3+kN}=1$ Therefore
\begin{eqnarray}
X(\Omega) =2\pi \sum_{k=-\infty}^{\infty} \delta\left( \Omega-\frac{2\pi}{N}(3+kN) \right)
\end{eqnarray}
3) Find the DFT of $\cos\left( \frac{2\pi}{7}n \right)$
Appendix:Deriving fourier transforms from fourier series
Let us rewrite the equations for the discrete Fourier series:
$$
\begin{eqnarray}
x[n]&=& \sum_{k=<N>} a[k] e^{ik \frac{2\pi}{N}n}\\
a[k]&=& \frac{1}{N}\sum_{n=<N>} x[n] e^{-ik \frac{2\pi}{N}n}
\end{eqnarray}
$$
In order to deal with non-periodic functions, we have to bring \(N\rightarrow \infty\). But before that, we have to do define a new quantity, \(X(.)\), as \(X(\Omega_0 k)=Na[k]\). Note that \(X(\Omega_0 k)\) is not a discrete signal, as its argument is not an integer. When we write the DFS equations with \(X(\Omega_0 k)\) we get
$$
\begin{eqnarray}
x[n]&=& \sum_{k=<N>} \frac{X(\Omega_0 k)}{N} e^{ik \Omega_0 n}&=&\frac{1}{2\pi} \sum_{k=<N>} X(\Omega_0 k) e^{ik \Omega_0 n} \Omega_0\\
X(\Omega_0 k)&=& \sum_{n=<N>} x[n] e^{-ik \Omega_0 n}
\end{eqnarray}
$$
As \(N \rightarrow \infty\), \(\Omega_0 \rightarrow 0\), \(\Omega_0 k\) becomes the continuous variable \(\Omega\), and \(\Omega_0\) becomes \(d\Omega\). The first sum becomes an integral. As the summation in the first integral is carried out over (\N\) consecutive intervals of width \(\Omega_0=\frac{2\pi}{N}\), the integral is taken over an interval of \(2\pi\).
\begin{eqnarray}
N &\Rightarrow& \infty\\
\Omega_0 = \frac{2\pi}{N} \Rightarrow d\Omega &\Rightarrow& 0\\
\Omega_0 k &\Rightarrow& \Omega\\
\sum_{<N>} f(\Omega_0 k) \Omega_0 &\Rightarrow& \int_{<2\pi>} f(\Omega)d\Omega
\end{eqnarray}
Therefore, DFS equations are converted into
$$
\begin{eqnarray}
x[n]&=& \frac{1}{2\pi}\int_{2\pi} X(\Omega) e^{i \Omega n}d\Omega\\
X(\Omega)&=& \sum_{n=-\infty}^{\infty} x[n] e^{-i \Omega n}
\end{eqnarray}
$$
Note that $X(\Omega)$ is a continuous function periodic with period \(2\pi\).