The description of signals in terms of their sinusoidal frequency content has
proven to be as powerful and informative for discrete-time signals as it has
for continuous-time signals. It is also probably the most powerful
computational tool we will use. We now develop the basic discrete-time methods
starting with the discrete Fourier transform (DFT) applied to finite length
signals, followed by the discrete-time Fourier transform (DTFT) for infinitely
long signals, and ending with the z-transform which uses the powerful tools of
complex variable theory.
It is assumed that the signal
x
(
n
)
x
(
n
)
to be analyzed is a sequence of
N
N
real or complex values which are a function of the integer variable
n
n
.
The DFT of
x
(
n
)
x
(
n
)
,
also called the spectrum of
x
(
n
)
x
(
n
)
,
is a length
N
N
sequence of complex numbers denoted
C
(
k
)
C
(
k
)
and defined by
C
(
k
)
=
∑
n
=
0
N
−
1
x
(
n
)
e
−
j
2
π
N
n
k
C
(
k
)
=
∑
n
=
0
N
−
1
x
(
n
)
e
−
j
2
π
N
n
k
(1)
using the usual engineering notation:
j
=
−
1
j
=
−
1
.
The inverse transform (IDFT) which retrieves
x
(
n
)
x
(
n
)
from
C
(
k
)
C
(
k
)
is given by
x
(
n
)
=
1
N
∑
k
=
0
N
−
1
C
(
k
)
e
j
2
π
N
n
k
x
(
n
)
=
1
N
∑
k
=
0
N
−
1
C
(
k
)
e
j
2
π
N
n
k
(2)
which is easily verified by substitution into (1). Indeed, this verification
will require using the orthogonality of the basis function of the DFT which is
∑
k
=
0
N
−
1
e
−
j
2
π
N
m
k
e
j
2
π
N
n
k
=
{
N
if
n
=
m
0
if
n
≠
m
.
∑
k
=
0
N
−
1
e
−
j
2
π
N
m
k
e
j
2
π
N
n
k
=
{
N
if
n
=
m
0
if
n
≠
m
.
(3)
The exponential basis functions,
e
−
j
2
π
N
k
e
−
j
2
π
N
k
,
for
k
∈
{
0
,
N
−
1
}
k
∈
{
0
,
N
−
1
}
,
are the
N
N
values of the
N
N
th
roots of unity (the N zeros of the polynomial
(
s
−
1
)
N
(
s
−
1
)
N
).
This property is what connects the DFT to convolution and allows efficient
algorithms for calculation to be developed
[1]. They are used
so often that the following notation is defined by
W
N
=
e
−
j
2
π
N
W
N
=
e
−
j
2
π
N
(4)
with the subscript being omitted if the sequence length is obvious from
context. Using this notation, the DFT becomes
C
(
k
)
=
∑
n
=
0
N
−
1
x
(
n
)
W
N
n
k
C
(
k
)
=
∑
n
=
0
N
−
1
x
(
n
)
W
N
n
k
(5)
One should notice that with the finite summation of the DFT, there is no
question of convergence or of the ability to interchange the order of
summation. No ``delta functions'' are needed and the
N
N
transform values can be calculated exactly (within the accuracy of the
computer or calculator used) from the
N
N
signal values with a finite number of arithmetic operations.
There are several advantages to using a matrix formulation of the DFT. This is
given by writing
(Equation 1) or
(Equation 5) in matrix
operator form as
[
C
0
C
1
C
2
⋮
C
N
−
1
]
=
[
W
0
W
0
W
0
⋯
W
0
W
0
W
1
W
2
W
0
W
2
W
4
⋮
⋮
W
0
⋯
W
(
N
−
1
)
(
N
−
1
)
]
[
x
0
x
1
x
2
⋮
x
N
−
1
]
[
C
0
C
1
C
2
⋮
C
N
−
1
]
=
[
W
0
W
0
W
0
⋯
W
0
W
0
W
1
W
2
W
0
W
2
W
4
⋮
⋮
W
0
⋯
W
(
N
−
1
)
(
N
−
1
)
]
[
x
0
x
1
x
2
⋮
x
N
−
1
]
(6)
or
C
=
F
x
.
C
=
F
x
.
(7)
The orthogonality of the basis function in
(Equation 1) shows up in
this matrix formulation by the columns of
F
F
being orthogonal to each other as are the rows. This means that
F
T
F
=
k
I
F
T
F
=
k
I
,
where
k
k
is a scalar constant, and, therefore,
F
T
=
k
F
−
1
F
T
=
k
F
−
1
.
This is called a unitary operator.
The definition of the DFT in
(Equation 1) emphasizes the
fact that each of the
N
N
DFT values are the sum of
N
N
products. The matrix formulation in
(Equation 6) has two
interpretations. Each
k
k
-th
DFT term is the inner product of two vectors,
k
k
-th
row of
F
F
and
x
x
;
or, the DFT vector,
C
C
is a weighted sum of the
N
N
columns of
F
F
with weights being the elements of the signal vector
x
x
.
A third view of the DFT is the operator view which is simply the single matrix
equation (Equation 7).
It is instructive at this point to write a computer program to calculate the
DFT of a signal. In Matlab
[2], there is a
pre-programmed function to calculate the DFT, but that hides the scalar
operations. One should program the transform in the scalar interpretive
language of Matlab or some other lower level language such as FORTRAN, C,
BASIC, Pascal, etc. This will illustrate how many multiplications and
additions and trigonometric evaluations are required and how much memory is
needed. Do not use a complex data type which also hides arithmetic, but use
Euler's relations
e
j
x
=
cos
(
x
)
+
j
sin
(
x
)
e
j
x
=
cos
(
x
)
+
j
sin
(
x
)
(8)
to explicitly calculate the real and imaginary part of
C
(
k
)
C
(
k
)
.
If Matlab is available, first program the DFT using only scalar operations. It
will require two nested loops and will run rather slowly because the execution
of loops is interpreted. Next, program it using vector inner products to
calculate each
C
(
k
)
C
(
k
)
which will require only one loop and will run faster. Finally, program it
using a single matrix multiplication requiring no loops and running much
faster. Check the memory requirements of the three approaches.
The DFT and IDFT are a completely well-defined, legitimate transform pair with
a sound theoretical basis that do not need to be derived from or interpreted
as an approximation to the continuous-time Fourier series or integral. The
discrete-time and continuous-time transforms and other tools are related and
have parallel properties, but neither depends on the other.
The notation used here is consistent with most of the literature and with the
standards given in
[3]. The independent
index variable
n
n
of the signal
x
(
n
)
x
(
n
)
is an integer, but it is usually interpreted as time or, occasionally, as
distance. The independent index variable
k
k
of the DFT
C
(
k
)
C
(
k
)
is also an integer, but it is generally considered as frequency. The DFT is
called the spectrum of the signal and the magnitude of the complex valued DFT
is called the magnitude of that spectrum and the angle or argument is called
the phase.
Although the finite length signal
x
(
n
)
x
(
n
)
is defined only over the interval
{
0
≤
n
≤
(
N
−
1
)
}
{
0
≤
n
≤
(
N
−
1
)
}
,
the IDFT of
C
(
k
)
C
(
k
)
can be evaluated outside this interval to give well defined values. Indeed,
this process gives the periodic property 4. There are two ways of formulating
this phenomenon. One is to periodically extend
x
(
n
)
x
(
n
)
to
−
∞
−
∞
and
+
∞
+
∞
and work with this new signal. A second more general way is evaluate all
indices
n
n
and
k
k
modulo
N
N
.
Rather than considering the periodic extension of
x
(
n
)
x
(
n
)
on the line of integers, the finite length line is formed into a circle or a
line around a cylinder so that after counting to
N
−
1
N
−
1
,
the next number is zero, not a periodic replication of it. The periodic
extension is easier to visualize initially and is more commonly used for the
definition of the DFT, but the evaluation of the indices by residue reduction
modulo
N
N
is a more general definition and can be better utilized to develop efficient
algorithms for calculating the DFT
[1].
Since the indices are evaluated only over the basic interval, any values could
be assigned
x
(
n
)
x
(
n
)
outside that interval. The periodic extension is the choice most consistent
with the other properties of the transform, however, it could be assigned to
zero [4]. An
interesting possibility is to artificially create a length
2
N
2
N
sequence by appending
x
(
−
n
)
x
(
−
n
)
to the end of
x
(
n
)
x
(
n
)
.
This would remove the discontinuities of periodic extensions of this new
length
2
N
2
N
signal and perhaps give a more accurate measure of the frequency content of
the signal with no artifacts caused by ``end effects". Indeed, this
modification of the DFT gives what is called the discrete cosine transform
(DCT) [5]. We will
assume the implicit periodic extensions to
x
(
n
)
x
(
n
)
with no special notation unless this characteristic is important, then we will
use the notation
x
˜
(
n
)
x
˜
(
n
)
.
Convolution is an important operation in signal processing that is in some
ways more complicated in discrete-time signal processing than in
continuous-time signal processing and in other ways easier. The basic
input-output relation for a discrete-time system is given by so-called linear
or non-cyclic convolution defined and denoted by
y
(
n
)
=
∑
m
=
−
∞
∞
h
(
m
)
x
(
n
−
m
)
=
h
(
n
)
*
x
(
n
)
y
(
n
)
=
∑
m
=
−
∞
∞
h
(
m
)
x
(
n
−
m
)
=
h
(
n
)
*
x
(
n
)
(9)
where
x
(
n
)
x
(
n
)
is the perhaps infinitely long input discrete-time signal,
h
(
n
)
h
(
n
)
is the perhaps infinitely long impulse response of the system, and
y
(
n
)
y
(
n
)
is the output. The DFT is, however, intimately related to cyclic convolution,
not non-cyclic convolution. Cyclic convolution is defined and denoted by
y
˜
(
n
)
=
∑
m
=
0
N
−
1
h
˜
(
m
)
x
˜
(
n
−
m
)
=
h
(
n
)
∘
x
(
n
)
y
˜
(
n
)
=
∑
m
=
0
N
−
1
h
˜
(
m
)
x
˜
(
n
−
m
)
=
h
(
n
)
∘
x
(
n
)
(10)
where either all of the indices or independent integer variables are evaluated
modulo
N
N
or all of the signals are periodically extended outside their length
N
N
domains.
This cyclic (sometimes called circular) convolution can be expressed as a
matrix operation by converting the signal
h
(
n
)
h
(
n
)
into a matrix operator as
H
=
[
h
0
h
L
−
1
h
L
−
2
⋯
h
1
h
1
h
0
h
L
−
1
h
2
h
1
h
0
⋮
⋮
h
L
−
1
⋯
h
0
]
,
H
=
[
h
0
h
L
−
1
h
L
−
2
⋯
h
1
h
1
h
0
h
L
−
1
h
2
h
1
h
0
⋮
⋮
h
L
−
1
⋯
h
0
]
,
(11)
The cyclic convolution can then be written in matrix notation as
Y
=
H
X
Y
=
H
X
(12)
where
X
X
and
Y
Y
are column matrices or vectors of the input and output values respectively.
Because non-cyclic convolution is often what you want to do and cyclic
convolution is what is related to the powerful DFT, we want to develop a way
of doing non-cyclic convolution by doing cyclic convolution.
The convolution of a length
N
N
sequence with a length
M
M
sequence yields a length
N
+
M
−
1
N
+
M
−
1
output sequence. The calculation of non-cyclic convolution by using cyclic
convolution requires modifying the signals by appending zeros to them. This
will be developed later.
It is very important to develop insight and intuition into the DFT or spectral
characteristics of various standard signals. A few DFT's of standard signals
together with the above properties will give a fairly large set of results.
They will also aid in quickly obtaining the DFT of new signals. The
discrete-time impulse
δ
(
n
)
δ
(
n
)
is defined by
δ
(
n
)
=
{
1
when
n
=
0
0
otherwise
δ
(
n
)
=
{
1
when
n
=
0
0
otherwise
(13)
The discrete-time pulse
⊓
M
(
n
)
⊓
M
(
n
)
is defined by
⊓
M
(
n
)
=
{
1
when
n
=
0
,
1
,
⋯
,
M
−
1
0
otherwise
⊓
M
(
n
)
=
{
1
when
n
=
0
,
1
,
⋯
,
M
−
1
0
otherwise
(14)
Several examples are:
-
D
F
T
{
δ
(
n
)
}
=
1
D
F
T
{
δ
(
n
)
}
=
1
,
The DFT of an impulse is a constant.
-
D
F
T
{
1
}
=
N
δ
(
k
)
D
F
T
{
1
}
=
N
δ
(
k
)
,
The DFT of a constant is an impulse.
-
D
F
T
{
e
j
2
π
K
n
/
N
}
=
N
δ
(
k
−
K
)
D
F
T
{
e
j
2
π
K
n
/
N
}
=
N
δ
(
k
−
K
)
-
D
F
T
{
cos
(
2
π
M
n
/
N
)
=
N
2
[
δ
(
k
−
M
)
+
δ
(
k
+
M
)
]
D
F
T
{
cos
(
2
π
M
n
/
N
)
=
N
2
[
δ
(
k
−
M
)
+
δ
(
k
+
M
)
]
-
D
F
T
{
⊓
M
(
n
)
}
=
sin
(
π
N
M
k
)
sin
(
π
N
k
)
D
F
T
{
⊓
M
(
n
)
}
=
sin
(
π
N
M
k
)
sin
(
π
N
k
)
These examples together with the properties can generate a still larger set of
interesting and enlightening examples. Matlab can be used to experiment with
these results and to gain insight and intuition.
