DISCRETE PERIODIC FUNCTIONS AS FINITE DIMENSIONAL VECTORS
As in continuous fourier series, we start with periodic discrete functions \(x[n]=x[n+N]\), where \(N\) is the period. We consider a single period of this function, starting from time $0$, as an \(N\)-dimensional vector, ie,
$$
\begin{eqnarray}
\vec{x}^0&= & \begin{bmatrix}
x[0]\\
x[1]\\
x[2]\\
\vdots\\
x[N-2]\\
x[N-1]
\end{bmatrix}_0
\end{eqnarray}
$$
The subscript zero indicates that we start our vector from $n=0$. We want to expand this vector into the discrete complex exponential basis
$$
\begin{eqnarray}
e^{i\frac{2\pi k n}{N}} \hspace3ex k=0,1,2,\dots,N-1
\end{eqnarray}
$$
which can also be considered as \(N\) \(N\)-dimensional vectors, \(\{ e_0^0, e_1^0, \ldots, e_{N-1}^0 \}\):
$$
\begin{eqnarray}
\vec{e}_m^0=\begin{bmatrix}
e^{i\frac{2\pi m.0}{N}}\\
e^{i\frac{2\pi m.1}{N}}\\
e^{i\frac{2\pi m.2}{N}}\\
\vdots\\
e^{i\frac{2\pi m.(N-2)}{N}}\\
e^{i\frac{2\pi m.(N-1)}{N}}
\end{bmatrix}_0
\end{eqnarray} , \quad 0\leq m < N
$$
Recall that all the signals we have considered are discrete and periodic with period \(N\), therefore the above \(N\)-dimensional vectors carry all the information about them. Also, because of the periodicity, they are not the only choice. We could equivalently choose any shifted version of them, ie,
$$
\begin{eqnarray}
\vec{x}^k &= \begin{bmatrix}
x[k]\\
x[k+1]\\
x[k+2]\\
\vdots\\
x[k+N-2]\\
x[k+N-1]
\end{bmatrix}_k; \hspace{1cm}
\vec{e}_m^k=\begin{bmatrix}
e^{i\frac{2\pi m.k}{N}}\\
e^{i\frac{2\pi m.(k+1)}{N}}\\
e^{i\frac{2\pi m.(k+2)}{N}}\\
\vdots\\
e^{i\frac{2\pi m.(k+N-2)}{N}}\\
e^{i\frac{2\pi m.(k+N-1)}{N}}
\end{bmatrix}_k
\end{eqnarray}, \quad k\leq m < k+N
$$
From now on we will carry out our computations using $\vec{x}^0$ and $\vec{e}_i^0$ and omit the superscripts, but other choices $\vec{x}^k$ and $\vec{e}_i^k$ are equivalently possible.
The expansion can be carried out as
$$
\begin{eqnarray}
\begin{bmatrix}
x[0]\\
x[1]\\
\vdots\\
x[N-1]
\end{bmatrix}
=
a_0\begin{bmatrix}
e^{i\frac{2\pi 0.0}{N}}\\
e^{i\frac{2\pi 0.1}{N}}\\
\vdots\\
e^{i\frac{2\pi 0.(N-1)}{N}}
\end{bmatrix}
+
a_1\begin{bmatrix}
e^{i\frac{2\pi 1.0}{N}}\\
e^{i\frac{2\pi 1.1}{N}}\\
\vdots\\
e^{i\frac{2\pi 1.(N-1)}{N}}
\end{bmatrix}
+
a_2\begin{bmatrix}
e^{i\frac{2\pi 2.0}{N}}\\
e^{i\frac{2\pi 2.1}{N}}\\
\vdots\\
e^{i\frac{2\pi 2.(N-1)}{N}}
\end{bmatrix}+
……. \\ …..
+a_{N-2}\begin{bmatrix}
e^{i\frac{2\pi (N-2).0}{N}}\\
e^{i\frac{2\pi (N-2).1}{N}}\\
\vdots\\
e^{i\frac{2\pi (N-2).(N-1)}{N}}
\end{bmatrix}
+
a_{N-1}\begin{bmatrix}
e^{i\frac{2\pi (N-1).0}{N}}\\
e^{i\frac{2\pi (N-1).1}{N}}\\
\vdots\\
e^{i\frac{2\pi (N-1).(N-1)}{N}}
\end{bmatrix}
\end{eqnarray}
$$
or,
$$
\vec{x}^0 = a_0\vec{e}_0^0+a_1\vec{e}_1^0 \ldots +a_{N-1}\vec{e}_{N-1}^0
$$
Note that all these complex exponentials above are periodic with \(N\), and we need to find the unknown quantities $a_j$. If we expand these vector equations we get
$$
\begin{eqnarray}
x[0]&=&a_0 e^{i\frac{2\pi 0.0}{N}}+a_1 e^{i\frac{2\pi 1.0}{N}}+a_2 e^{i\frac{2\pi 2.0}{N}}+\ldots+ a_{N-2}e^{i\frac{2\pi (N-2).0}{N}}+a_{N-1}e^{i\frac{2\pi (N-1).0}{N}}\\
x[1]&=&a_0 e^{i\frac{2\pi 0.1}{N}}+a_1 e^{i\frac{2\pi 1.1}{N}}+a_2 e^{i\frac{2\pi 2.1}{N}}+\ldots+ a_{N-2}e^{i\frac{2\pi (N-2).1}{N}}+a_{N-1}e^{i\frac{2\pi (N-1).1}{N}}\\
&\vdots&\\
x[N-1]&=&a_0 e^{i\frac{2\pi 0.(N-1)}{N}}+a_1 e^{i\frac{2\pi 1.(N-1)}{N}}+a_2 e^{i\frac{2\pi 2.(N-1)}{N}}+\ldots+ a_{N-2}e^{i\frac{2\pi (N-2).(N-1)}{N}}+a_{N-1}e^{i\frac{2\pi (N-1).(N-1)}{N}}
\end{eqnarray}
$$
which is \(N\) linear equations in \(N\) unknowns, and it is quite possible to solve this via standard gaussian elimination technique to find the unknown quantities, ie, \(a_i\)’s. But, there is a much easier way!
NORM AND ORTHOGONALITY IN DISCRETE PERIODIC FUNCTION SPACE
Unlike the geometric vector space which we have considered in the last chapter, we dont have any intuition from geometry for the discrete periodic function space. How to define the dot product between two functions? What is the angle between them? What is the length of a function?
Therefore, we directly postulate the dot product between vectors $\vec{x}$ and $\vec{y}$
$$
\vec{x} = \begin{bmatrix}
x[0]\\
x[1]\\
x[2]\\
\vdots\\
x[N-2]\\
x[N-1]
\end{bmatrix}; \hspace{1cm}
\vec{y} =\begin{bmatrix}
y[0]\\
y[1]\\
y[2]\\
\vdots\\
y[N-2]\\
y[N-1]
\end{bmatrix}
$$
as
$$
\vec{x}.\vec{y} = x[0]y[0]^*+x[1]y[1]^*+x[2]y[2]^*+ \ldots +x[N-2]y[N-2]^*+x[N-1]y[N-1]^*
$$
Note that if the vector elements $x[i]$, $y[i]$ in the above sum are complex, dot product is not commutative. Ie, $\vec{x}.\vec{y} \neq \vec{y}.\vec{x}$. Instead of commutativity, we have $\vec{x}.\vec{y} = (\vec{y}.\vec{x})^*$
With this new definition of dot product, we can have two claims about our basis vectors (proven in class)
- Each of the basis vectors has norm \(\sqrt{N}\), ie
\begin{eqnarray}
|\vec{e}_i|^2=\vec{e}_i.\vec{e}_i^* = N
\end{eqnarray} - Basis vectors are orthogonal to each other, ie, \(\vec{e}_i.\vec{e}_j^*=0\) if \( i \neq j\).
We can unite these two observations in a single formula by writing
\begin{eqnarray}
\vec{e}_i . \vec{e}_j^* = N\delta_{ij}
\end{eqnarray}
After this observations, it becomes very easy to solve the linear system: To find \(a_i\), just dot product both sides of equation (**) with \(e_i\):
\begin{eqnarray}
\vec{x}.\vec{e}_i = a_0\vec{e}_0.\vec{e}_i+a_1\vec{e}_1.\vec{e}_i+\ldots+a_ie_i.e_i+\ldots+a_{N-2}e_{N-2}.e_i+a_{N-1}e_{N-1}.e_i
\end{eqnarray}
Note that all the dot products \(e_k.e_i\) in the RHS will give zero except for one, \(e_i.e_i\). Hence the equation becomes
\begin{eqnarray}
x.e_i &=& a_ie_i.e_i &=& a_i N
\end{eqnarray}
or,
\begin{eqnarray}
a_k &=& \frac{1}{N} x.e_k &=& \frac{1}{N} \sum_{<N>} x[n]e_k[n]^*=\frac{1}{N} \sum_{n=<N>} x[n] e^{-i\frac{2\pi}{N}kn}
\end{eqnarray}
Therefore, the fourier series representation of a discrete periodic signal is
$$
\begin{eqnarray}
x[n]&=& \sum_{k=0}^{N-1} a_k e^{ik \frac{2\pi}{N}n}\\
a_k&=& \frac{1}{N}\sum_{n=0}^{N-1} x[n] e^{-ik \frac{2\pi}{N}n}
\end{eqnarray}
$$
There is one more point that requires elaboration: In the above derivations, we take the datapoints $x[0],\ldots,x[N-1]$, used the basis vectors $e_0,\ldots, e_{N-1}$ and obtained the fourier coefficients $a_0,\ldots, a_{N-1}$. We could equally well take the datapoints $x[K],\ldots,x[K+N-1]$, use the basis vectors $e_K,\ldots, e_{K+N-1}$ and obtained the fourier coefficients $a_K,\ldots, a_{K+N-1}$. In this case, the above formulas will change as
$$
\begin{eqnarray}
x[n]&=& \sum_{k=K}^{K+N-1} a_k e^{ik \frac{2\pi}{N}n}\\
a_k&=& \frac{1}{N}\sum_{n=K}^{K+N-1} x[n] e^{-ik \frac{2\pi}{N}n}
\end{eqnarray}
$$
To include all possible cases, we write the fourier series equations as
$$
\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}
$$
where $<N>$ means: “take any $N$ consecutive points”.
FOURIER TRANSFORMATIONS
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\).
PERIODIC CASE
$$
\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
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}
7) 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}
8) 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}
9) Find the DFT of $\cos\left( \frac{2\pi}{7}n \right)$