will be elaborated in chapter 8.
5.6. Discrete-Time Signals*
Although the discrete-time signal x( n) could be any ordered sequence of numbers, they are usually
samples of a continuous-time signal. In this case, the real or imaginary valued mathematical
function x( n) of the integer n is not used as an analogy of a physical signal, but as some
representation of it (such as samples). In some cases, the term digital signal is used
interchangeably with discrete-time signal, or the label digital signal may be use if the function is
not real valued but takes values consistent with some hardware system.
Indeed, our very use of the term “discrete-time" indicates the probable origin of the signals when,
in fact, the independent variable could be length or any other variable or simply an ordering index.
The term “digital" indicates the signal is probably going to be created, processed, or stored using
digital hardware. As in the continuous-time case, the Fourier transform will again be our primary
Notation has been an important element in mathematics. In some cases, discrete-time signals are
best denoted as a sequence of values, in other cases, a vector is created with elements which are
the sequence values. In still other cases, a polynomial is formed with the sequence values as
coefficients for a complex variable. The vector formulation allows the use of linear algebra and
the polynomial formulation allows the use of complex variable theory.
The Discrete Fourier Transform
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.
Definition of the DFT
It is assumed that the signal x( n) to be analyzed is a sequence of N real or complex values which
are a function of the integer variable n. The DFT of x( n), also called the spectrum of x( n), is a length N sequence of complex numbers denoted C( k) and defined by
(5.8)
using the usual engineering notation:
. The inverse transform (IDFT) which retrieves x( n)
from C( k) is given by
(5.9)
which is easily verified by substitution into Equation 5.8. Indeed, this verification will require
using the orthogonality of the basis function of the DFT which is
(5.10)
The exponential basis functions,
, for k∈{0, N–1}, are the N values of the N th roots of unity
(the N zeros of the polynomial ( s–1) N). This property is what connects the DFT to convolution and
allows efficient algorithms for calculation to be developed 4. They are used so often that the
following notation is defined by
(5.11)
with the subscript being omitted if the sequence length is obvious from context. Using this
notation, the DFT becomes
(5.12)
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
transform values can be calculated exactly (within the accuracy of the computer or calculator
used) from the N signal values with a finite number of arithmetic operations.
Matrix Formulation of the DFT
There are several advantages to using a matrix formulation of the DFT. This is given by writing
Equation 5.8 or Equation 5.12 in matrix operator form as
(5.13)
or
(5.14)
The orthogonality of the basis function in Equation 5.8 shows up in this matrix formulation by the
columns of F being orthogonal to each other as are the rows. This means that
, where k is
a scalar constant, and, therefore,
. This is called a unitary operator.
The definition of the DFT in Equation 5.8 emphasizes the fact that each of the N DFT values are the sum of N products. The matrix formulation in Equation 5.13 has two interpretations. Each k-th DFT term is the inner product of two vectors, k-th row of F and x; or, the DFT vector, C is a
weighted sum of the N columns of F with weights being the elements of the signal vector x. A
third view of the DFT is the operator view which is simply the single matrix equation
It is instructive at this point to write a computer program to calculate the DFT of a signal. In
Matlab 18, 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
(5.15)
to explicitly calculate the real and imaginary part of 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) 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 9.
The independent index variable n of the signal x( n) is an integer, but it is usually interpreted as
time or, occasionally, as distance. The independent index variable k of the DFT 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.
Extensions of x(n)
Although the finite length signal x( n) is defined only over the interval {0≤ n≤( N–1)}, the IDFT of
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) to –∞ and +∞ and work with this new signal. A second more general
way is evaluate all indices n and k modulo N. Rather than considering the periodic extension of
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, 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 is a more general definition and
can be better utilized to develop efficient algorithms for calculating the DFT 4.
Since the indices are evaluated only over the basic interval, any values could be assigned 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 20. An interesting possibility is to
artificially create a length 2 N sequence by appending x(– n) to the end of x( n). This would remove the discontinuities of periodic extensions of this new length 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) 15.
We will assume the implicit periodic extensions to x( n) with no special notation unless this
characteristic is important, then we will use the notation
.
Convolution
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
(5.16)
where x( n) is the perhaps infinitely long input discrete-time signal, h( n) is the perhaps infinitely long impulse response of the system, and 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
(5.17)
where either all of the indices or independent integer variables are evaluated modulo N or all of
the signals are periodically extended outside their length N domains.
This cyclic (sometimes called circular) convolution can be expressed as a matrix operation by
converting the signal h( n) into a matrix operator as
(5.18)
The cyclic convolution can then be written in matrix notation as
(5.19)
where X and 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 sequence with a length M sequence yields a length 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.
Properties of the DFT
The properties of the DFT are extremely important in applying it to signal analysis and to
interpreting it. The main properties are given here using the notation that the DFT of a length- N
complex sequence x( n) is
.
1. Linear Operator:
2. Unitary Operator:
3. Periodic Spectrum:
4. Periodic Extensions of x( n):
5. Properties of Even and Odd Parts:
and
Table 5.2.
u
v
A
B
| C|
θ
even 0
even 0
even 0
odd 0
0
odd
even π/2
0
even 0
even even π/2
0
odd
odd 0
even 0
6. Cyclic Convolution:
7. Multiplication:
8. Parseval:
9. Shift:
10. Modulate:
11. Down Sample or Decimate:
where N= LK
12. Up Sample or Stretch: If
for integer n and zero otherwise, then
, for
k=0,1,2,...,2 N–1
13. N Roots of Unity:
for
14. Orthogonality:
(5.20)
15. Diagonalization of Convolution: If cyclic convolution is expressed as a matrix operation by
y=Hx with H given by Equation 5.18, the DFT operator diagonalizes the convolution operator H, or FTHF=Hd where Hd is a diagonal matrix with the N values of the DFT of h( n) on the diagonal. This is a matrix statement of Property 6. Note the columns of F are the N
eigenvectors of H, independent of the values of h( n).
One can show that any “kernel" of a transform that would support cyclic, length-N convolution
must be the N roots of unity. This says the DFT is the only transform over the complex number
field that will support convolution. However, if one considers various finite fields or rings, an
interesting transform, called the Number Theoretic Transform, can be defined and used because
the roots of unity are simply two raised to a powers which is a simple word shift for certain binary
Examples of the DFT
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) is defined by
(5.21)
The discrete-time pulse ⊓ M( n) is defined by
(5.22)
Several examples are:
, The DFT of an impulse is a constant.
, The DFT of a constant is an impulse.
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.
The Discrete-Time Fourier Transform
In addition to finite length signals, there are many practical problems where we must be able to
analyze and process essentially infinitely long sequences. For continuous-time signals, the Fourier
series is used for finite length signals and the Fourier transform or integral is used for infinitely
long signals. For discrete-time signals, we have the DFT for finite length signals and we now
present the discrete-time Fourier transform (DTFT) for infinitely long signals or signals that are
longer than we want to specify 20. The DTFT can be developed as an extension of the DFT as N
goes to infinity or the DTFT can be independently defined and then the DFT shown to be a special
case of it. We will do the latter.
Definition of the DTFT
The DTFT of a possibly infinitely long real (or complex) valued sequence f( n) is defined to be
(5.23)
and its inverse denoted IDTFT is given by
(5.24)
Verification by substitution is more difficult than for the DFT. Here convergence and the
interchange of order of the sum and integral are serious questions and have been the topics of
research over many years. Discussions of the Fourier transform and series for engineering
applications can be found in 21, 5. It is necessary to allow distributions or delta functions to be used to gain the full benefit of the Fourier transform.
Note that the definition of the DTFT and IDTFT are the same as the definition of the IFS and FS
respectively. Since the DTFT is a continuous periodic function of ω, its Fourier series is a discrete
set of values which turn out to be the original signal. This duality can be helpful in developing
properties and gaining insight into various problems. The conditions on a function to determine if
it can be expanded in a FS are exactly the conditions on a desired frequency response or spectrum
that will determine if a signal exists to realize or approximate it.
Properties
The properties of the DTFT are similar to those for the DFT and are important in the analysis and
interpretation of long signals. The main properties are given here using the notation that the DTFT
of a complex sequence x( n) is
.
1. Linear Operator:
2. Periodic Spectrum:
3. Properties of Even and Odd Parts:
and
Table 5.3.
u
v
A
B
| X|
θ
even 0
even 0
even 0
odd
0
0
odd
even 0
0
even 0
even even π/2
0
odd
odd
0
even π/2
4. Convolution: If non-cyclic or linear convolution is defined by:
then
5. Multiplication: If cyclic convolution is defined by:
<