In this module, we will derive an expansion for discrete-time, periodic functions, and in doing so, derive the Discrete Time Fourier Series (DTFS), or the Discrete Fourier Transform (DFT).

Since complex exponentials are eigenfunctions of linear time-invariant (LTI) systems, calculating the output of an LTI system $\mathscr{H}$ given ${e}^{i\omega n}$ as an input amounts to simple multiplication, where ${\omega}_{0}=\frac{2\pi k}{N}$ , and where $H\left[k\right]\in \mathbb{C}$ is the eigenvalue corresponding to k. As shown in the figure, a simple exponential input would yield the output

$$y\left[n\right]=H\left[k\right]{e}^{i\omega n}$$

1

Using this and the fact that $\mathscr{H}$ is linear, calculating $y\left[n\right]$ for combinations of complex exponentials is also straightforward.

$${c}_{1}{e}^{i{\omega}_{1}n}+{c}_{2}{e}^{i{\omega}_{2}n}\to {c}_{1}H\left[{k}_{1}\right]{e}^{i{\omega}_{1}n}+{c}_{2}H\left[{k}_{2}\right]{e}^{i{\omega}_{1}n}$$ $$\sum _{l}^{}{c}_{l}{e}^{i{\omega}_{\mathrm{l}}n}\to \sum _{l}^{}{c}_{l}H\left[{k}_{l}\right]{e}^{i{\omega}_{\mathrm{l}}n}$$

The action of $H$ on an input such
as those in the two equations above is easy to explain.
** $\mathscr{H}$ independently
scales** each exponential component
${e}^{i{\omega}_{\mathrm{l}}n}$
by a different complex number
$H\left[{k}_{l}\right]\in \mathbb{C}$. As such, if we can write a function
$y\left[n\right]$
as a combination of complex exponentials it allows us to easily calculate the output of a system.

It can be demonstrated that an arbitrary Discrete Time-periodic function $f\left[n\right]$ can be written as a linear combination of harmonic complex sinusoids

$$f\left[n\right]=\sum _{k=0}^{N-1}{c}_{k}{e}^{i{\omega}_{0}kn}$$

2

The
${c}_{n}$ - called the Fourier coefficients -
tell us "how much" of the sinusoid
${e}^{j{\omega}_{0}kn}$ is in
$f\left[n\right]$.
The formula shows
$f\left[n\right]$ as a sum of complex exponentials, each of which is easily processed by an
LTI system (since it is an eigenfunction of
**every** LTI system). Mathematically,
it tells us that the set of
complex exponentials
$\left\{\forall k,k\in \mathbb{Z}:\left({e}^{j{\omega}_{0}kn}\right)\right\}$ form a basis for the space of N-periodic discrete
time functions.

Say
we have the following set of numbers that describe a periodic,
discrete-time signal, where
$N=4$:
$$\left\{\dots ,3,2,-2,1,3,\dots \right\}$$
Such a periodic, discrete-time signal (with period
$N$) can be thought of as a
**finite** set of numbers. For example,
we can represent this signal as either a periodic signal or as
just a single interval as follows:

Note:

The cardinalsity of the set of discrete time signals with period
$N$ equals
${\mathbb{C}}^{N}$.
If you are familiar with the basic sinusoid signal and with complex exponentials then you should not have any problem understanding this section. In most texts, you will see the the discrete-time, complex sinusoid noted as: $${e}^{i\omega n}$$

Example 1

Example 2

The complex sinusoid can be directly mapped onto our complex plane, which allows us to easily visualize changes to the complex sinusoid and extract certain properties. The absolute value of our complex sinusoid has the following characteristic:

$$\forall n,n\in \mathbb{R}:\left(\left|{e}^{i\omega n}\right|=1\right)$$

3

$$\angle \left({e}^{i\omega n}\right)=wn$$

4

Now that we have looked over the concepts of complex sinusoids, let us turn our attention back to finding a basis for discrete-time, periodic signals. After looking at all the complex sinusoids, we must answer the question of which discrete-time sinusoids do we need to represent periodic sequences with a period $N$.

Equivalent Question:

Find a set of vectors
$\forall n,n=\left\{0,\dots ,N-1\right\}:\left({b}_{k}={e}^{i{\omega}_{k}n}\right)$
such that
$\left\{{b}_{k}\right\}$
are a basis for
${\u2102}^{n}$
Harmonic Sinusoid

$${e}^{i\frac{2\pi}{N}kn}$$

5

${e}^{i\frac{2\pi}{N}kn}$ is periodic with period $N$ and has $k$ "cycles" between $n=0$ and $n=N-1$.

Theorem 1

If we let $$\forall n,n=\left\{0,\dots ,N-1\right\}:\left({b}_{k}\left[n\right]=\frac{1}{\sqrt{N}}{e}^{i\frac{2\pi}{N}kn}\right)$$ where the exponential term is a vector in ${\mathbb{C}}^{N}$, then $\left\{{b}_{k}\right\}{|}_{k=\left\{0,\dots ,N-1\right\}}$ is an orthonormal basis for ${\mathbb{C}}^{N}$.

Proof

First of all, we must show $\left\{{b}_{k}\right\}$ is orthonormal, i.e. $\u27e8{b}_{k},{b}_{l}\u27e9={\delta}_{kl}$ $$\u27e8{b}_{k},{b}_{l}\u27e9=\sum _{n=0}^{N-1}{b}_{k}\left[n\right]\overline{{b}_{l}\left[n\right]}=\frac{1}{N}\sum _{n=0}^{N-1}{e}^{i\frac{2\pi}{N}kn}{e}^{-(i\frac{2\pi}{N}ln)}$$

$$\u27e8{b}_{k},{b}_{l}\u27e9=\frac{1}{N}\sum _{n=0}^{N-1}{e}^{i\frac{2\pi}{N}(l-k)n}$$

6

$$\begin{array}{rcl}\hfill \u27e8{b}_{k},{b}_{l}\u27e9& \hfill =\hfill & \frac{1}{N}\sum _{n=0}^{N-1}1\hfill \\ \hfill & \hfill =\hfill & 1\hfill \end{array}$$

7

$$\u27e8{b}_{k},{b}_{l}\u27e9=\{\begin{array}{l}1\text{if}k=l\\ 0\text{if}k\ne l\end{array}$$

8

And finally, we have shown that the harmonic sinusoids $\left\{\frac{1}{\sqrt{N}}{e}^{i\frac{2\pi}{N}kn}\right\}$ form an orthonormal basis for ${\u2102}^{n}$

Now that we have an understanding of the discrete-time Fourier series
(DTFS), we can consider the **periodic
extension** of
$c\left[k\right]$ (the Discrete-time Fourier coefficients). Figure 7 shows a simple illustration of how we can represent
a sequence as a periodic signal mapped over an infinite number
of intervals.

Exercise 1

Why does a periodic extension to the DTFS coefficients $c\left[k\right]$ make sense?

Solution

Aliasing: ${b}_{k}={e}^{i\frac{2\pi}{N}kn}$

$$\begin{array}{rcl}\hfill {b}_{k+N}& \hfill =\hfill & {e}^{i\frac{2\pi}{N}(k+N)n}\hfill \\ \hfill & \hfill =\hfill & {e}^{i\frac{2\pi}{N}kn}{e}^{i2\pi n}\hfill \\ \hfill & \hfill =\hfill & {e}^{i\frac{2\pi}{N}n}\hfill \\ \hfill & \hfill =\hfill & {b}_{k}\hfill \end{array}$$

9

Example 3: Discrete time square wave

Calculate the DTFS $c\left[k\right]$ using:

$$c\left[k\right]=\frac{1}{N}\sum _{n=0}^{N-1}f\left[n\right]{e}^{-(i\frac{2\pi}{N}kn)}$$

10

$${c}_{k}=\frac{1}{N}\sum _{n=-{N}_{1}}^{{N}_{1}}{e}^{-(i\frac{2\pi}{N}kn)}$$

11

$$\begin{array}{rcl}\hfill {c}_{k}& \hfill =\hfill & \frac{1}{N}\sum _{m=0}^{2{N}_{1}}{e}^{-(i\frac{2\pi}{N}(m-{N}_{1})k)}\hfill \\ \hfill & \hfill =\hfill & \frac{1}{N}{e}^{i\frac{2\pi}{N}k}\sum _{m=0}^{2{N}_{1}}{e}^{-(i\frac{2\pi}{N}mk)}\hfill \end{array}$$

12

$$\sum _{n=0}^{M}{a}^{n}=\frac{1-{a}^{M+1}}{1-a}$$

13

$$\begin{array}{rcl}\hfill {c}_{k}& \hfill =\hfill & \frac{1}{N}{e}^{i\frac{2\pi}{N}{N}_{1}k}\sum _{m=0}^{2{N}_{1}}{\left({e}^{-(i\frac{2\pi}{N}k)}\right)}^{m}\hfill \\ \hfill & \hfill =\hfill & \frac{1}{N}{e}^{i\frac{2\pi}{N}{N}_{1}k}\frac{1-{e}^{-(i\frac{2\pi}{N}(2{N}_{1}+1))}}{1-{e}^{-(ik\frac{2\pi}{N})}}\hfill \end{array}$$

14

$$\begin{array}{rcl}\hfill {c}_{k}& \hfill =\hfill & \frac{1}{N}\frac{{e}^{-(ik\frac{2\pi}{2N})}({e}^{ik\frac{2\pi}{N}({N}_{1}+\frac{1}{2})}-{e}^{-(ik\frac{2\pi}{N}({N}_{1}+\frac{1}{2}))})}{{e}^{-(ik\frac{2\pi}{2N})}({e}^{ik\frac{2\pi}{N}\frac{1}{2}}-{e}^{-(ik\frac{2\pi}{N}\frac{1}{2})})}\hfill \\ \hfill & \hfill =\hfill & \frac{1}{N}\frac{\mathrm{sin}\left(\frac{2\pi k({N}_{1}+\frac{1}{2})}{N}\right)}{\mathrm{sin}\left(\frac{\pi k}{N}\right)}\hfill \\ \hfill & \hfill =\hfill & \text{digital sinc}\hfill \end{array}$$

15

Using the steps shown above in the derivation and our previous understanding of Hilbert Spaces and Orthogonal Expansions, the rest of the derivation is automatic. Given a discrete-time, periodic signal (vector in ${\u2102}^{n}$) $f\left[n\right]$, we can write:

$$f\left[n\right]=\frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}{c}_{k}{e}^{i\frac{2\pi}{N}kn}$$

16

$${c}_{k}=\frac{1}{\sqrt{N}}\sum _{n=0}^{N-1}f\left[n\right]{e}^{-(i\frac{2\pi}{N}kn)}$$

17

Discrete Time Fourier Series:

Here is the common form of the DTFS with the above note
taken into account:
$$f\left[n\right]=\sum _{k=0}^{N-1}{c}_{k}{e}^{i\frac{2\pi}{N}kn}$$
$${c}_{k}=\frac{1}{N}\sum _{n=0}^{N-1}f\left[n\right]{e}^{-(i\frac{2\pi}{N}kn)}$$
This is what the `fft`

command in MATLAB does.