2.9b.1 Discrete-Time Fourier Series

Discrete-Time Fourier Series (DTFS)

The discrete-time Fourier series is a Fourier transform method that provides a frequency-domain representation of a discrete-time signal defined over all integers. It results in a continuous frequency spectrum. Any $p$-periodic discrete-time signal $x:\mathbb{Z}\to \mathbb{C}$ can be written in the frequency domain, such that
$x(n)={\sum }_{k=0}^{p-1}{X}_k{e}^{j{\omega }_{0}kn}⟺X_k=\frac{1}{p}{\sum }_{n=0}^{p-1}x(n)e^{-j{\omega }_{0}kn}.$

The synthesis (left) equation can be transformed into matrix-vector form, such that the formula for the DTFS of a $p$-periodic discrete signal $x(n)$ with eigenvector components ${\psi }_k(n)=e^{j\omega kn}$ is

$$\vec{x}=\Psi \vec{X}⟺\left[\begin{array}{c}x(0)\\ x(1)\\ ⋮\\ x(p-1)\end{array}\right]=\left[\begin{array}{ccccc}{\psi }_0(0)& \dots & {\psi }_k(0)& \dots & {\psi }_{p-1}(0)\\ {\psi }_0(1)& \ddots & {\psi }_k(1)& \ddots & {\psi }_{p-1}(1)\\ ⋮& \ddots & ⋮& \ddots & ⋮\\ {\psi }_0(p-1)& \dots & {\psi }_k(p-1)& \dots & {\psi }_{p-1}(p-1)\end{array}\right]\left[\begin{array}{c}{X}_0\\ ⋮\\ X_k\\ ⋮\\ X_{p-1}\end{array}\right]$$

where $\Psi \in {\mathbb{C}}^{p\times p}$ is an orthogonal matrix called the Fourier kernel representing a Fourier basis with each of its columns ${\Psi }_k$ being the basis vectors, $\vec{X}\in {\mathbb{C}}^p$ is the vector of Fourier coefficients, and $\vec{x}\in {\mathbb{C}}^p$ is the signal output for each $n\in \{0,1,\dots ,(p-1)\}$.

Then, the solution to the discrete-time Fourier series for $x(n)$ is the projection
$\vec{X}(\omega )=\frac{1}{p}\Psi \text{textasteriskcentered}\vec{x},$
where $\frac{1}{p}\Psi \text{textasteriskcentered}={\Psi }^{-1}$ is known as the Fourier matrix.

Intuition

We start with a very simple change of basis. Consider two discrete functions ${\psi }_0(n)=1$ and ${\psi }_1(n)=\{\begin{array}{llc}1& & (n\mathrm{mod}2\equiv 0)\\ -1& & (n\mathrm{mod}2\equiv 1)\end{array}$.

The functions can equivalently be written as ${\psi }_0(n)=e^{i0n}$ and ${\psi }_1(n)=e^{i\pi n}$, which you can find for yourself by solving the complex exponential for the given frequency with any $n\in \mathbb{Z}$. The two functions can also be written as two vectors ${\psi }_0=\left[\begin{array}{c}1\\ 1\end{array}\right]$ and ${\psi }_1=\left[\begin{array}{c}1\\ -1\end{array}\right]$.

Since the fundamental period of the function is $p=2$ (you can find this using periodicity of discrete signals), this means that any two-periodic signal $x(n)$ can be decomposed as

x(n) &= X_0\psi_0(n) + X_1\psi_1(n) \\ &= X_0e^{i0n}+X_1e^{i \pi n}. \end{align}$$ Additionally, since $\omega_0=\frac{2\pi}{p}=\pi$, only the frequencies $0, \pi$ may contribute to the signal. This can be generalized for a $P$-periodic signal $x(n)$, such that the only frequencies that contribute to that signal are contained in the set $\set{0, \omega_0, 2\omega_0, \ldots, (P-1)\omega_0}$. Proceeding in the 2-period realm, we can find $X_0$ and $X_1$ by solving for their respective vectors' dot products, $$\begin{align} \vec{x} \cdot \psi_0 = X_0(\psi_0 \cdot \psi_0) + X_1 \times 0 \iff X_0=\frac{\vec{x} \cdot \psi_0}{\psi_0 \cdot \psi_0} \\ \vec{x} \cdot \psi_1 = X_0 \times 0 +X_1(\psi_1 \cdot \psi_1) \iff X_1=\frac{\vec{x} \cdot \psi_1}{\psi_1 \cdot \psi_1} \end{align}$$ where $\psi_0 \cdot \psi_1 = 0$ is automatically omitted since the two vectors are orthogonal, and $x$ is the vector of the signal $x(n)$. Note that this was a very simplified example, since ==a 2-period signal is always real== (the sine component of the complex number is always 0). We can now continue our $p$-periodic signal generalization by saying that a $p$-periodic signal can be generalized into a $p$-element vector, such that $\vec{x}=\begin{bmatrix}x(0) & x(1) & \ldots & x(p-1)\end{bmatrix}^T$. We will also define a $p$-dimensional orthogonal basis $\set{\psi_0, \psi_1, \ldots, \psi_{p-1}}$. The vector $\vec{x}$ can then be decomposed using $$\begin{align} \vec{x} &= X_0\psi_0+X_1\psi_1+\ldots+X_{p-1}\psi_{p-1} \\ &= \sum^{p-1}_{k=0}X_k\psi_k \\ &= \sum^{p-1}_{k=0}X_ke^{jk\omega_0n} \end{align}$$ Then, we can find any $X_n$ by projecting $\vec{x}$ onto the coefficient's respective basis vector $\psi_n$:

\begin{align}
\langle \vec{x}, \psi_n \rangle &= \langle \sum^{p-1}{k=0}X_k\psi_k, \psi_n \rangle \
&= \sum^{p-1}{k=0}X_k\langle \psi_k, \psi_n \rangle \
&= X_n\langle \psi_n, \psi_n \rangle \
&= X_n \times p.
\end{align}

Here, we use the fact that the inner product of two orthogonal vectors is always $0$, as well as the fact that $\langle \vec{x}, \vec{x} \rangle = p$. The latter comes from the relation of the basis vectors to the periodicity of $x(n)$. Finally, by dividing both sides by $\langle \psi_n, \psi_n \rangle = p$ we can define any Fourier series coefficient $X_n$ as $$X_n = \frac{1}{p} \langle \vec{x}, \psi_n \rangle.$$ In the signal realm, we can equivalently state that for $\omega_0 \in \set{0, \omega_0, 2\omega_0, \ldots, (p-1)\omega_0}$, $$x(n)=\sum^{p-1}_{k=0}X_k\psi_k(n)=\sum^{p-1}_{k=0}X_ke^{jk\omega_0n} \iff X_k=\frac{1}{p}\sum^{p-1}_{k=0}x(n)(e^{jk\omega_0n})\textasteriskcentered =\frac{1}{p}\sum^{p-1}_{k=0}x(n)e^{-jk\omega_0n}$$ where in the second equation $(e^{jk\omega_0n})\textasteriskcentered = e^{-jk\omega_0n}$. Therefore, we get our discrete-time Fourier series for $p$-periodic signals with frequency $\omega_0 \in \set{0, \omega_0, 2\omega_0, \ldots, (p-1)\omega_0}$, $$x(n)=\sum^{p-1}_{k=0}X_ke^{jk\omega_0n} \iff X_k=\frac{1}{p}\sum^{p-1}_{k=0}x(n)e^{-jk\omega_0n}.$$ Let's try to solve this for a $3$-period signal. We have $p=3$, and therefore an orthogonal basis of $\set{\psi_0, \psi_1, \psi_2}$. Let's define our basis vectors to follow the rule $\psi_k(n) = e^{jk\omega_0n}$. Since $\psi_k = \begin{bmatrix}\psi_k(0) & \psi_k(1) & \psi_k(2)\end{bmatrix}^T$ and $\omega_0 = \frac{2\pi}{p} = \frac{2\pi}{3}$, then $$\begin{align} \psi_0 &= \begin{bmatrix}1 & 1 & 1\end{bmatrix}^T \\ \psi_1 &= \begin{bmatrix}1 & e^{j\frac{2\pi}{3}} & e^{j\frac{4\pi}{3}}\end{bmatrix}^T \\ \psi_2 &= \begin{bmatrix}1 & e^{j\frac{4\pi}{3}} & e^{j\frac{8\pi}{3}}\end{bmatrix}^T = \begin{bmatrix}1 & e^{j\frac{4\pi}{3}} & e^{j\frac{2\pi}{3}}\end{bmatrix}^T. \end{align}$$ We can plot our 3 [[7.4 Roots of Unity|roots of unity]] for our 3-periodic orthogonal basis as ```tikz \usepackage{tikz} \usepackage{pgfplots} \begin{document} \begin{tikzpicture}[scale=1.5] % draw the coordinates \draw[->] (-1.5, 0) -- (1.5, 0) node[right] {$Re$}; \draw[->] (0,-1.5) -- (0,1.5) node[above] {$Im$}; \pgfsetfillopacity{0.25} % draw the unit circle \draw[thick] (0, 0) circle(1); \draw plot[mark=x, mark options={scale=1.5}, thick] coordinates { (1,0) } node[above right]{$e^{j0}$}; \draw plot[mark=x, mark options={scale=1.5}, thick] coordinates { (-0.5,0.866) } node[above left]{$e^{j\frac{2\pi}{3}}$}; \draw plot[mark=x, mark options={scale=1.5}, thick] coordinates { (-0.5,-0.866) } node[below left]{$e^{j\frac{4\pi}{3}}$}; \end{tikzpicture} \end{document} ``` # Properties #### *(Orthogonal Bases)* $\langle \psi_k, \psi_\ell \rangle = p\delta(k - \ell)$ #### $\Psi^T\Psi\textasteriskcentered = pI$ #### $\Psi^{-1}=\frac{1}{p}\Psi\textasteriskcentered$ >[!example] Discrete-Time Fourier Series by Inspection > >Consider the $p$-periodic discrete signal >$$x(n)=1+\sin(\frac{2\pi}{p}n)+3\cos(\frac{2\pi}{p}n)+\cos(\frac{2\pi}{p}n+\frac{\pi}{2}).$$ >As a sum of complex exponentials, we can equivalently express it as >$$x(n)=e^{j\frac{2\pi}{p}0}+\frac{1}{2j}(e^{j\frac{2\pi}{p}n}-e^{-j\frac{2\pi}{p}n})+\frac{3}{2}(e^{j\frac{2\pi}{p}n} + e^{-j\frac{2\pi}{p}n}) + \frac{1}{2}(e^{j\frac{\pi}{2}}e^{j\frac{4\pi}{p}n} - e^{-j\frac{\pi}{2}}e^{-j\frac{4\pi}{p}n}).$$ >Using the Fourier series decomposition $x(n)=\sum^{p-1}_{k=0}X_k\psi_k(n)$, we can reorder the complex exponentials by matching their frequencies, such that >$$x(n) = >\underbrace{(1)}_{X_0}e^{j\frac{2\pi}{p}0} + >\underbrace{\left(\frac{1}{2j} + \frac{3}{2} \right)}_{X_1}e^{j\frac{2\pi}{p}n} + >\underbrace{\left(\frac{3}{2} - \frac{1}{2j} \right)}_{X_{-1}}e^{-j\frac{2\pi}{p}n} + >\underbrace{\frac{j}{2}}_{X_2}e^{j\frac{4\pi}{p}n} + >\underbrace{-\frac{j}{2}}_{X_{-2}}e^{-j\frac{4\pi}{p}n} >$$ >The coefficients $X_{-1}$ and $X_{-2}$ come from seeing that $-1\omega_0=-\frac{2\pi}{p}$, and $-2\omega_0=-\frac{4\pi}{p}$ for $k\omega_0$. From the above, we can infer that $X_{-1}=X_{p-1}$ and $X_{-2}=X_{p-2}$, since we are trying to keep $k \in \set{0, 1, \ldots, (p-1)}$. Therefore, we have 5 coefficients: $X_0, X_1, X_2, X_{p-2}, X_{p-1}$. >[!example] A DTFS Puzzle > >Consider a signal $x: \mathbb{Z} \to \mathbb{R}$ with the following properties: >1. $x(n+4\ell)=x(n),$ $\forall\ell,n \in \mathbb{Z}.$ >2. $\sum^{2}_{n=-1}x(n)=4.$ >3. $\sum^{2}_{n=-1}x(n)(-1)^n=8.$ >4. $\sum^{2}_{n=-1}x(n)\cos(\frac{\pi}{2}n)=\sum^{2}_{n=-1}x(n)\sin(\frac{\pi}{2}n)=0.$ > >==(1)== We begin with the first equation, which implies that $n$ is periodic with period $p=\frac{4}{k}$ and fundamental frequency $\omega_{0} = \frac{2\pi}{p}=\frac{k\pi}{2}$. It also implies that we should be looking for 4 Fourier coefficients: $X_{-1}, X_{0}, X_{1}, \text{ and }X_{2}$. > >==(2)== Meanwhile, the second equation can be manipulated into >$$\sum^{2}_{n=-1}x(n) \cdot 1= \sum^{2}_{n=-1}x(n) e^{j 0 n} = 4.$$ >Dividing the rightmost side by $p$ (assuming $k=1$ such that $\frac{p}{k}=4$), we get >$$\frac{1}{4}\sum^{2}_{n=-1}x(n) e^{j 0 n} = \frac{1}{4} \cdot 4 = 1.$$ >Therefore, $X_{0} = 1$. > >==(3)== To proceed, we observe that equation 3 can also be manipulated, such that >$$\sum^{2}_{n=-1}x(n)(-1)^n=\sum^{2}_{n=-1}x(n)e^{j\pi n}=8.$$ >This implies that $k\omega_{0}=\pi$, or equivalently, $k=2$. As such, >$$X_{2} = \frac{1}{4}\sum^{2}_{n=-1}x(n)e^{j\pi n}=\frac{1}{4} \cdot 8.$$ >Therefore, $X_{2}=2$. > >==(4)== What does the fourth equation entail? We can proceed by manipulating it just like the previous two, such that >$$\frac{1}{4}\sum^{2}_{k=-1}x(n)\cos(\frac{\pi}{2}n) = \frac{1}{4} \cdot \frac{1}{2}\sum^{2}_{k=-1}[x(n)e^{j \frac{\pi}{2} n} + x(n)e^{-j \frac{\pi}{2}n}] = 0.$$ >We observe that the right side can be simplified into $\frac{1}{2}X_{1}+\frac{1}{2}X_{-1}=0$, or equivalently $X_{1}=-X_{-1}$. > >Similarly, >$$\frac{1}{4}\sum^{2}_{k=-1}x(n)\sin(\frac{\pi}{2}n) = \frac{1}{4} \cdot \frac{1}{2j}\sum^{2}_{k=-1}[x(n)e^{j \frac{\pi}{2} n} - x(n)e^{-j \frac{\pi}{2}n}] = 0,$$ >which can be simplified into $\frac{1}{2j}X_{1}-\frac{1}{2j}X_{-1}=0$, or $X_{1}=X_{-1}$. Therefore, $X_{1}$ and $X_{-1}$ need to meet the conditions >$$X_{1}=-X_{-1} \text{ and } X_{1} = X_{-1},$$ >which is only true for $X_{1}=X_{-1}=0$. > >We found the coefficients to be $X_{-1}=0$, $X_{0}=1$, $X_{1}=0$, $X_{2}=2$. We can now find $x(n)$ accordingly: >$$\begin{align} >x(n) &= X_{0}e^{j\frac{\pi}{2}0n}+X_{1}e^{j\frac{\pi}{2}2n} \\ >&= 1 + 2e^{j\pi n}. >\end{align}$$ >Let's go a little further. We were given the initial condition of $p=4$ in (1). However, a quick look at the above signal gives us a $p=2$! Why? Well, $p=4$ is still a valid period of $x$. However, the fundamental period $p_{0}=2$. This means that the fundamental frequency is actually $$