<< Chapter < Page | Chapter >> Page > |

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}$$

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

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

which tells that our complex sinusoid only takes values onthe unit circle. As for the angle, the following
statement holds true:
$\angle (e^{i\omega n})=wn$

For more information, see the section on the
Discrete Time Complex Exponential to learn about
Aliasing ,
Negative Frequencies , and the formal definition of the
Complex Conjugate .
Now that we have looked over the concepts of complex sinusoids, let us turn our attention back to finding a basisfor discrete-time, periodic signals. After looking at all the complex sinusoids, we must answer the question of whichdiscrete-time sinusoids do we need to represent periodic sequences with a period $N$ .

Find a set of vectors
$\forall n, n=\{0, \dots , N-1\}\colon {b}_{k}=e^{i{\omega}_{k}n}$ such that
$\{{b}_{k}\}$ are a
basis for
${\u2102}^{n}$

In answer to the above question, let us try the "harmonic"
sinusoids with a fundamental frequency
${\omega}_{0}=\frac{2\pi}{N}$ :
$e^{i\frac{2\pi}{N}kn}$ is periodic with period
$N$ and has
$k$ "cycles"
between
$n=0$ and
$n=N-1$ .

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

First of all, we must show
$\{{b}_{k}\}()$ is orthonormal,

$${b}_{k}\cdot {b}_{l}=\frac{1}{N}\sum_{n=0}^{N-1} e^{i\frac{2\pi}{N}(l-k)n}$$

If
$l=k$ ,
then
$${b}_{k}\cdot {b}_{l}=\frac{1}{N}\sum_{n=0}^{N-1} 1()=1$$

If
$l\neq k$ ,
then we must use the "partial summation formula" shownbelow:
$$\sum_{n=0}^{N-1} \alpha ^{n}=-\sum $$∞
${b}_{k}\cdot {b}_{l}=\begin{cases}1 & \text{if $k=l$}\\ 0 & \text{if $k\neq l$}\end{cases}()$

Therefore:
$\{{b}_{k}\}$ is an orthonormal set.
$\{{b}_{k}\}$ is also a
basis , since there
are
$N$ vectors which are
linearly independent (orthogonality
implies linear independence).
And finally, we have shown that the harmonic sinusoids $\{\frac{1}{\sqrt{N}}e^{i\frac{2\pi}{N}kn}\}$ 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(k)$ (the Discrete-time Fourier coefficients).
[link] shows a simple illustration of how we can represent
a sequence as a periodic signal mapped over an infinite numberof intervals.

Why does a periodic extension to the DTFS coefficients $c(k)$ make sense?

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

${b}_{k+N}=e^{i\frac{2\pi}{N}(k+N)n}=e^{i\frac{2\pi}{N}kn}e^{i\times 2\pi n}=e^{i\frac{2\pi}{N}n}={b}_{k}$

→ DTFS coefficients are also periodic with
period
$N$ . Calculate the DTFS $c(k)$ using:

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

Just like continuous time Fourier series, we can take the summation
over any interval, so we have
${c}_{k}=\frac{1}{N}\sum_{n=-{N}_{1}}^{{N}_{1}} e^{-(i\frac{2\pi}{N}kn)}$

Let
$m=n+{N}_{1}$ (so we can get a geometric series starting at 0)
${c}_{k}=\frac{1}{N}\sum_{m=0}^{2{N}_{1}} e^{-(i\frac{2\pi}{N}(m-{N}_{1})k)}=\frac{1}{N}e^{i\frac{2\pi}{N}k}\sum_{m=0}^{2{N}_{1}} e^{-(i\frac{2\pi}{N}mk)}$

Now, using the "partial summation formula"
$\sum_{n=0}^{M} a^{n}=\frac{1-a^{(M+1)}}{1-a}$

${c}_{k}=\frac{1}{N}e^{i\frac{2\pi}{N}{N}_{1}k}\sum_{m=0}^{2{N}_{1}} e^{-(i\frac{2\pi}{N}k)}^{m}=\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})}}$

Manipulate to make this look like a sinc function (distribute):
${c}_{k}=\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})})}=\frac{1}{N}\frac{\sin \left(\frac{2\pi k({N}_{1}+\frac{1}{2})}{N}\right)}{\sin \left(\frac{\pi k}{N}\right)}=\text{digital sinc}$

It's periodic!
[link] ,
[link] , and
[link] show our
above function and coefficients for various values of
${N}_{1}$ .

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, periodicsignal (vector in ${\u2102}^{n}$ ) $f(n)$ , we can write:

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

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

Note: Most people collect both the
$\frac{1}{\sqrt{N}}$ terms into the expression for
${c}_{k}$ .
Here is the common form of the DTFS with the above note
taken into account:
$$f(n)=\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(n)e^{-(i\frac{2\pi}{N}kn)}$$ This is what the

`fft`

command in MATLAB does.-
100% Free
*Android Mobile*Application - Complete Textbook by OpenStax
- Multiple Choices Questions (MCQ)
- Essay Questions Flash Cards
- Key-Terms Flash Cards

Source:
OpenStax, Signals and systems. OpenStax CNX. Aug 14, 2014 Download for free at http://legacy.cnx.org/content/col10064/1.15

Google Play and the Google Play logo are trademarks of Google Inc.

*Notification Switch*

Would you like to follow the *'Signals and systems'* conversation and receive update notifications?