Say
we have the following set of numbers that describe a periodic,
discretetime signal, where
N=4
N
4
:
…32213…
…
3
2
2
1
3
…
Such a periodic, discretetime signal (with period
NN) 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:
The cardinalsity of the set of discrete time signals with period
NN equals
CN
N
.
Here, we are going to form a basis
using
harmonic sinusoids. Before we look into
this, it will be worth our time to look at the discretetime,
complex sinusoids in a little more detail.
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 discretetime,
complex sinusoid noted as:
eiωn
ω
n
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:
∀
n
,n∈R:eiωn=1
n
n
ω
n
1
(3)
which tells that our complex sinusoid only takes values on
the unit circle. As for the angle, the following
statement holds true:
∠eiωn=wn
∠
ω
n
w
n
(4)
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 basis
for discretetime, periodic signals. After looking at all the
complex sinusoids, we must answer the question of which
discretetime sinusoids do we need to represent periodic
sequences with a period NN.
Find a set of vectors
∀
n
,n=0…N−1:
b
k
=ei
ω
k
n
n
n
0
…
N
1
b
k
ω
k
n
such that
b
k
b
k
are a basis for
ℂ
n
ℂ
n
In answer to the above question, let us try the "harmonic"
sinusoids with a fundamental frequency
ω
0
=2πN
ω
0
2
N
:
ei2πNkn
2
N
k
n
is periodic with period N
N and has kk "cycles"
between
n=0
n
0
and
n=N−1
n
N
1
.
If we let
∀
n
,n=0…N−1:
b
k
n=1Nei2πNkn
n
n
0
…
N
1
b
k
n
1
N
2
N
k
n
where the exponential term is a vector in
CN
N
, then
b
k

k=0…N−1
k
0
…
N
1
b
k
is an orthonormal basis for
CN
N
.
First of all, we must show
b
k
b
k
is orthonormal, i.e.
〈
b
k
,
b
l
〉=
δ
k
l
b
k
b
l
δ
k
l
〈
b
k
,
b
l
〉=∑
n
=0N−1
b
k
n
b
l
n¯=1N∑
n
=0N−1ei2πNkne−(i2πNln)
b
k
b
l
n
N
1
0
b
k
n
b
l
n
1
N
n
N
1
0
2
N
k
n
2
N
l
n
〈
b
k
,
b
l
〉=1N∑
n
=0N−1ei2πN(l−k)n
b
k
b
l
1
N
n
N
1
0
2
N
l
k
n
(6)
If
l=k
l
k
,
then
〈
b
k
,
b
l
〉=1N∑
n
=0N−11=1
b
k
b
l
1
N
n
N
1
0
1
1
(7)
If
l≠k
l
k
,
then we must use the "partial summation formula" shown
below:
∑
n
=0N−1αn=∑
n
=0∞αn−∑
n
=N∞αn=11−α−αN1−α=1−αN1−α
n
N
1
0
α
n
n
0
α
n
n
N
α
n
1
1
α
α
N
1
α
1
α
N
1
α
〈
b
k
,
b
l
〉=1N∑
n
=0N−1ei2πN(l−k)n
b
k
b
l
1
N
n
N
1
0
2
N
l
k
n
where in the above equation we can say that
α=ei2πN(l−k)
α
2
N
l
k
, and thus we can see how this is in the form
needed to utilize our partial summation formula.
〈
b
k
,
b
l
〉=1N1−ei2πN(l−k)N1−ei2πN(l−k)=1N1−11−ei2πN(l−k)=0
b
k
b
l
1
N
1
2
N
l
k
N
1
2
N
l
k
1
N
1
1
1
2
N
l
k
0
So,
〈
b
k
,
b
l
〉={1 if k=l0 if k≠l
b
k
b
l
1
k
l
0
k
l
(8)
Therefore:
b
k
b
k
is an orthonormal set.
b
k
b
k
is also a
basis, since there
are
NN vectors which are
linearly independent (orthogonality
implies linear independence).
And finally, we have shown that the harmonic sinusoids
1Nei2πNkn
1
N
2
N
k
n
form an orthonormal basis for
ℂ
n
ℂ
n
Now that we have an understanding of the discretetime Fourier series
(DTFS), we can consider the periodic
extension of
ck
c
k
(the Discretetime 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.
Why does a periodic
extension to the DTFS coefficients
ck
c
k
make sense?
Aliasing:
b
k
=ei2πNkn
b
k
2
N
k
n
b
k
+
N
=ei2πN(k+N)n=ei2πNknei2πn=ei2πNn=
b
k
b
k
+
N
2
N
k
N
n
2
N
k
n
2
n
2
N
n
b
k
(9)
→ DTFS coefficients are also periodic with
period
NN.
Calculate the DTFS
ck
c
k
using:
ck=1N∑n=0N−1fne−(i2πNkn)
c
k
1
N
n
0
N
1
f
n
2
N
k
n
(10)
Just like continuous time Fourier series, we can take the summation
over any interval, so we have
c
k
=1N∑n=−
N
1
N
1
e−(i2πNkn)
c
k
1
N
n
N
1
N
1
2
N
k
n
(11)
Let
m=n+
N
1
m
n
N
1
(so we can get a geometric series starting at 0)
c
k
=1N∑m=02
N
1
e−(i2πN(m−
N
1
)k)=1Nei2πNk∑m=02
N
1
e−(i2πNmk)
c
k
1
N
m
0
2
N
1
2
N
m
N
1
k
1
N
2
N
k
m
0
2
N
1
2
N
m
k
(12)
Now, using the "partial summation formula"
∑n=0Man=1−aM+11−a
n
0
M
a
n
1
a
M
1
1
a
(13)
c
k
=1Nei2πN
N
1
k∑m=02
N
1
e−(i2πNk)m=1Nei2πN
N
1
k1−e−(i2πN(2
N
1
+1))1−e−(ik2πN)
c
k
1
N
2
N
N
1
k
m
0
2
N
1
2
N
k
m
1
N
2
N
N
1
k
1
2
N
2
N
1
1
1
k
2
N
(14)
Manipulate to make this look like a sinc function (distribute):
c
k
=1Ne−(ik2π2N)(eik2πN(
N
1
+12)−e−(ik2πN(
N
1
+12)))e−(ik2π2N)(eik2πN12−e−(ik2πN12))=1Nsin2πk(
N
1
+12)NsinπkN=
digital sinc
c
k
1
N
k
2
2
N
k
2
N
N
1
1
2
k
2
N
N
1
1
2
k
2
2
N
k
2
N
1
2
k
2
N
1
2
1
N
2
k
N
1
1
2
N
k
N
digital sinc
(15)
"My introduction to signal processing course at Rice University."