Digital Signal Processing
Introduction
Moslem Amiri, V´aclav Pˇrenosil
Embedded Systems Laboratory
Faculty of Informatics, Masaryk University
Brno, Czech Republic
amiri@mail.muni.cz
prenosil@fi.muni.cz
February 25, 2012
The Concept of Frequency
Frequency is closely related to a specific type of periodic motion called
harmonic oscillation
Described by sinusoidal functions
Frequency has dimension of inverse time
Nature of time (continuous or discrete) would affect nature of frequency
accordingly
2 / 45
Continuous-Time Sinusoidal Signals
A simple harmonic oscillation
xa(t) = A cos(Ωt + θ), −∞ < t < ∞
Subscript a = analog signal
A = amplitude
Ω = frequency (in rad/s)
θ = phase (in radians)
Rewriting above equation using frequency F in cycles per second or
hertz (Hz)
xa(t) = A cos(2πFt + θ), −∞ < t < ∞
3 / 45
Continuous-Time Sinusoidal Signals
4 / 45
Continuous-Time Sinusoidal Signals
Properties of xa(t) = A cos(2πFt + θ), −∞ < t < ∞
1 For every fixed F, xa(t) is periodic
xa(t + Tp) = xa(t)
Tp = 1/F= fundamental period of sinusoidal signal
2 Signals with distinct frequencies are themselves distinct
3 Increasing F results in an increase in rate of oscillation of signal
Using Euler identity
e±jφ = cos φ ± j sin φ
and introducing negative frequencies
xa(t) = A cos(Ωt + θ) = A
2 ej(Ωt+θ) + A
2 e−j(Ωt+θ)
A sinusoidal signal can be obtained by adding two equal-amplitude
complex-conjugate exponential signals, called phasors
As time progresses, phasors rotate in opposite directions with angular
frequencies ±Ω radians/second
5 / 45
Discrete-Time Sinusoidal Signals
A discrete-time sinusoidal signal
x(n) = A cos(ωn + θ), −∞ < n < ∞
n = an integer called sample number
A = amplitude
ω = frequency in radians/sample
θ = phase in radians
Using ω = 2πf
x(n) = A cos(2πfn + θ), −∞ < n < ∞
frequency f is in cycles/sample
6 / 45
Discrete-Time Sinusoidal Signals
7 / 45
Discrete-Time Sinusoidal Signals
Properties of discrete-time sinusoids
1 A discrete-time sinusoid is periodic only if its frequency f is a rational
number
x(n) is periodic with period N(N > 0) if and only if
x(n + N) = x(n) for all n
Smallest value of N for which this equation is true is called fundamental
period
Proof of this property
cos[2πf0(N + n) + θ] = cos(2πf0n + θ)
2πf0N = 2kπ
f0 = k/N
To determine fundamental period N, express its frequency as f0 = k/N
and cancel common factors so that k and N are relatively prime, then N
is answer
8 / 45
Discrete-Time Sinusoidal Signals
Properties of discrete-time sinusoids (continued)
2 Discrete-time sinusoids whose frequencies are separated by an integer
multiple of 2π are identical
cos[(ω0 + 2kπ)n + θ] = cos(ω0n + 2πkn + θ) = cos(ω0n + θ)
where −π ≤ ω0 ≤ π
Discrete-time sinusoids with |ω| ≤ π or |f | ≤ 1
2
are unique
Any sequence resulting from a sinusoid with |ω| > π or |f | > 1
2
is
identical to a sequence obtained from a sinusoid with |ω| < π
Sinusoid having |ω| > π is called an alias of a corresponding sinusoid
with |ω| < π
9 / 45
Discrete-Time Sinusoidal Signals
Properties of discrete-time sinusoids (continued)
3 The highest rate of oscillation in a discrete-time sinusoid is attained
when ω = π (or ω = −π) or, equivalently, f = 1
2 (or f = −1
2 )
x(n) = cos ω0n, ω0 = 0 =⇒ N = ∞
−100 −50 0 50 100
−2
−1.5
−1
−0.5
0
0.5
1
1.5
2
x(n)
n
1
x(n) = cos ω0n, ω0 = π
8
=⇒ N = 16
−1.5
−1
−0.5
0
0.5
1
1.5
2
x(n)
n
1
10 / 45
Discrete-Time Sinusoidal Signals
Properties of discrete-time sinusoids (continued)
3 The highest rate of oscillation is when ω = π
x(n) = cos ω0n, ω0 = π
4
=⇒ N = 8
−15 −10 −5 0 5 10 15
−2
−1.5
−1
−0.5
0
0.5
1
1.5
2
x(n)
n
1
x(n) = cos ω0n, ω0 = π
2
=⇒ N = 4
−1.5
−1
−0.5
0
0.5
1
1.5
2
x(n)
n
1
11 / 45
Discrete-Time Sinusoidal Signals
Properties of discrete-time sinusoids (continued)
3 The highest rate of oscillation is when ω = π
x(n) = cos ω0n, ω0 = π =⇒ N = 2
−60 −40 −20 0 20 40 60
−2
−1.5
−1
−0.5
0
0.5
1
1.5
2
n
x(n)
1
For π ≤ ω0 ≤ 2π, if consider sinusoids with ω1 = ω0 and ω2 = 2π − ω0
x1(n) = A cos ω1n = A cos ω0n
x2(n) = A cos ω2n = A cos(2π − ω0)n
= A cos(−ω0n) = x1(n)
Hence, ω2 is an alias of ω1
Using a sine function, result would be same, except phase difference
would be π between x1(n) and x2(n)
12 / 45
Discrete-Time Sinusoidal Signals
Negative frequencies for discrete-time signals
x(n) = A cos(ωn + θ) = A
2 ej(ωn+θ) + A
2 e−j(ωn+θ)
Since discrete-time sinusoids with frequencies separated by 2kπ are
identical
Frequency range for discrete-time sinusoids is finite with duration 2π
Usually 0 ≤ ω ≤ 2π or −π ≤ ω ≤ π is called fundamental range
13 / 45
Harmonically Related Complex Exponentials
Harmonically related complex exponentials
Sets of periodic complex exponentials with fundamental frequencies that
are multiples of a single positive frequency
Properties which hold for complex exponentials, also hold for
sinusoidal signals
We confine our discussion to complex exponentials
14 / 45
Continuous-Time Exponentials
Basic signals for continuous-time, harmonically related exponentials
sk(t) = ejkΩ0t = ej2πkF0t k = 0, ±1, ±2, . . .
For each k, sk (t) is periodic with fundamental period 1/(kF0) = Tp/k
or fundamental frequency kF0
A signal that is periodic with period Tp/k is also periodic with period
k(Tp/k) = Tp for any positive integer k
Hence all sk (t) have a common period of Tp
A linear combination of harmonically related complex exponentials
xa(t) = ∞
k=−∞ cksk(t) = ∞
k=−∞ ckejkΩ0t
This is Fourier series expansion for xa(t)
ck , k = 0, ±1, ±2, . . . are arbitrary complex constants (Fourier series
coefficients)
sk (t) is kth harmonic of xa(t)
xa(t) is periodic with fundamental period Tp = 1/F0
15 / 45
Discrete-Time Exponentials
A discrete-time complex exponential is periodic if its frequency is a
rational number
Hence, we choose f0 = 1/N
Sets of harmonically related complex exponentials
sk(n) = ej2πkf0n, k = 0, ±1, ±2, . . .
Since
sk+N (n) = ej2πn(k+N)/N
= ej2πn
sk (n) = sk (n)
there are only N distinct periodic complex exponentials in the set
All members of the set have a common period of N samples
We can choose any consecutive N complex exponentials to form a set
For convenience
sk (n) = ej2πkn/N
, k = 0, 1, 2, . . . , N − 1
Fourier series representation for a periodic discrete-time sequence
x(n) = N−1
k=0 cksk(n) = N−1
k=0 ckej2πkn/N
Fundamental period = N
Fourier coefficients = {ck }
Sequence sk (n) is called kth harmonic of x(n)
16 / 45
Discrete-Time Exponentials
Example
Stored in memory is one cycle of sinusoidal signal
x(n) = sin 2πn
N + θ
where θ = 2πq/N, where q and N are integers
Obtain values of harmonically related sinusoids having the same phase
xk(n) = sin 2πnk
N + θ = sin 2π(kn)
N + θ = x(kn)
Thus xk(0) = x(0), xk(1) = x(k), xk(2) = x(2k), . . .
Obtain sinusoids of the same frequency but different phase
We control phase θ of sinusoid with fk = k/N by taking first value of
sequence from memory location q = θN/2π, where q is an integer
We wrap around table each time index (kn) exceeds N
17 / 45
Analog-to-Digital and Digital-to-Analog Conversion
Analog-to-digital (A/D) conversion
Converting analog signals to a sequence of numbers having finite
precision
Corresponding devices are called A/D converters (ADCs)
A/D conversion is a three-step process
18 / 45
Analog-to-Digital and Digital-to-Analog Conversion
A/D conversion process
1 Sampling
Taking samples of continuous-time signal at discrete-time instants
xa(t) is input −→ xa(nT) ≡ x(n) is output
T = sampling interval
2 Quantization
Conversion of a discrete-time continuous-valued signal into a
discrete-time, discrete-valued signal
Value of each sample is selected from a finite set of possible values
Quantization error: Difference between unquantized sample x(n) and
quantized output xq(n)
3 Coding
Each discrete value xq(n) is represented by a b-bit binary sequence
19 / 45
Analog-to-Digital and Digital-to-Analog Conversion
Digital-to-analog (D/A) conversion
Process of converting a digital signal into an analog signal
Interpolation
Connecting dots in a digital signal
Approximations: zero-order hold (staircase), linear, quadratic, and so on
20 / 45
Sampling of Analog Signals
Periodic or uniform sampling
x(n) = xa(nT), −∞ < n < ∞
T = sampling period or sample interval
1/T = Fs = sampling rate (samples/second) or sampling frequency
(hertz)
21 / 45
Sampling of Analog Signals
Relationship between t of continuous-time and n of discrete-time
signals
t = nT = n
Fs
To establish a relationship between F (or Ω) and f (or ω)
xa(t) = A cos(2πFt + θ)
xa(nT) ≡ x(n) = A cos(2πFnT + θ) = A cos 2πnF
Fs
+ θ
f = F/Fs
ω = ΩT
Substituting f = F/Fs and ω = ΩT into following range
−1
2 < f < 1
2
−π < ω < π
we find that F and Ω must fall in the range
− 1
2T = −Fs
2 ≤ F ≤ Fs
2 = 1
2T
− π
T = −πFs ≤ Ω ≤ πFs = π
T
22 / 45
Sampling of Analog Signals
Summary of relations among frequency variables
Continuous-time signals Discrete-time signals
Ω = 2πF ω = 2πf
radians
sec Hz radians
sample
cycles
sample
ω=ΩT,f =F/Fs
−−−−−−−−−→
−π ≤ ω ≤ π
−1
2 ≤ f ≤ 1
2
Ω=ω/T,F=f .Fs
←−−−−−−−−−−
−∞ < Ω < ∞ −π/T ≤ Ω ≤ π/T
−∞ < F < ∞ −Fs/2 ≤ F ≤ Fs/2
Since the highest frequency in a discrete-time signal is ω = π or f = 1
2
Fmax = Fs
2 = 1
2T
Ωmax = πFs = π
T
23 / 45
Sampling of Analog Signals
Example
Consider these analog sinusoids sampled at Fs = 40 Hz
x1(t) = cos 2π(10)t
x2(t) = cos 2π(50)t
Corresponding discrete-time signals
x1(n) = cos 2π 10
40 n = cos π
2 n
x2(n) = cos 2π 50
40 n = cos 5π
2 n
However
cos 5πn/2 = cos(2πn + πn/2) = cos πn/2
x2(n) = x1(n)
Given sampled values generated by cos(π/2)n, there is ambiguity as to
whether they correspond to x1(t) or x2(t)
F2 = 50 Hz is an alias of F1 = 10 Hz at Fs = 40
All cos 2π(F1 + 40k)t, k = 1, 2, . . . sampled at Fs = 40 are aliases of
F1 = 10
24 / 45
Sampling of Analog Signals
If sinusoids
xa(t) = A cos(2πFkt + θ)
where
Fk = F0 + kFs, k = ±1, ±2, . . .
are sampled at Fs, then Fk is outside the range −Fs/2 ≤ F ≤ Fs/2
x(n) ≡ xa(nT) = A cos 2π
F0 + kFs
Fs
n + θ
= A cos(2πnF0/Fs + θ + 2πkn)
= A cos(2πf0n + θ)
Frequencies
Fk = F0 + kFs, −∞ < k < ∞
are aliases of F0 after sampling
25 / 45
Sampling of Analog Signals
26 / 45
Sampling of Analog Signals
Example
Two sinusoids: F1 = −7
8 Hz and F2 = 1
8 Hz with Fs = 1 Hz
F1 = F2 + kFs, k = ±1, ±2, . . .
k = −1, F2 = F1 + Fs = (−7
8 + 1)Hz = 1
8Hz
27 / 45
Sampling of Analog Signals
Fs/2 (which corresponds to ω = π) is highest frequency that can be
represented uniquely with Fs
Use Fs/2 or ω = π as pivotal point and fold alias frequency to range
0 ≤ ω ≤ π
Fs/2 (ω = π) is called folding frequency
28 / 45
Sampling of Analog Signals
Example
xa(t) = 3 cos 100πt
1 Minimum sampling rate required to avoid aliasing
F = 50 Hz −→ Fs = 100 Hz
2 Suppose Fs = 200 Hz. Discrete-time signal obtained after sampling
x(n) = 3 cos 100π
200 n = 3 cos π
2 n
3 Suppose Fs = 75 Hz. Discrete-time signal obtained after sampling
x(n) = 3 cos 100π
75 n = 3 cos 4π
3 n = 3 cos 2π − 2π
3 n = 3 cos 2π
3 n
4 Frequency 0 < F < Fs/2 of a sinusoid that yields samples identical to
those obtained in part (3)
For Fs = 75 Hz, F = fFs = 75f
In part (3), f = 1
3 −→ F = 25 Hz
ya(t) = 3 cos 2πFt = 3 cos 50πt
Hence F = 50 Hz is an alias of F = 25 Hz for Fs = 75 Hz
29 / 45
The Sampling Theorem
Given any analog signal, how T or equivalently Fs should be selected
Knowing Fmax of general class of signals (e.g., class of speech signals),
we can specify Fs
Suppose any analog signal can be represented as
xa(t) = N
i=1 Ai cos(2πFi t + θi )
N = number of frequency components
Fmax may vary slightly from different realizations among signals of any
given class (e.g., from speaker to speaker)
To ensure Fmax does not exceed some predetermined value, pass analog
signal through a filter that attenuates frequency components above Fmax
Any frequency outside −Fs/2 ≤ F ≤ Fs/2 results in samples identical
with a corresponding frequency inside this range
To avoid aliasing
Fs > 2Fmax
This condition ensures that any frequency component (|Fi | < Fmax ) in
analog signal is mapped into a discrete-time sinusoid with a frequency
−1
2
≤ fi = Fi
Fs
≤ 1
2
30 / 45
The Sampling Theorem
Sampling theorem
If Fmax = B for xa(t) and Fs > 2Fmax ≡ 2B, then xa(t) can be exactly
recovered from its sample values using the interpolation function
g(t) =
sin 2πBt
2πBt
xa(t) =
∞
n=−∞
xa
n
Fs
g t −
n
Fs
where xa(n/Fs) = xa(nT) ≡ x(n) are samples of xa(t)
Nyquist rate = FN = 2B = 2Fmax
31 / 45
The Sampling Theorem
Example
xa(t) = 3 cos 50πt + 10 sin 300πt + cos 100πt
Nyquist rate for this signal
F1 = 25 Hz, F2 = 150 Hz, F3 = 50 Hz −→ Fmax = 150 Hz
Fs > 2Fmax = 300 Hz
FN = 2Fmax = 300 Hz
Component 10 sin 300πt sampled at FN = 300 results in 10 sin πn
which are identically zero
If θ = 0 or π, samples taken at Nyquist rate are not all zero
10 sin(πn + θ) = 10(sin πn cos θ + cos πn sin θ) = 10 sin θ cos πn =
(−1)n10 sin θ
To avoid this uncertain situation, sample analog signal at a rate higher
than Nyquist
32 / 45
The Sampling Theorem
Example
xa(t) = 3 cos 2000πt + 5 sin 6000πt + 10 cos 12000πt
Nyquist rate for this signal
F1 = 1 kHz, F2 = 3 kHz, F3 = 6 kHz −→ Fmax = 6 kHz
Fs > 2Fmax = 12 kHz
FN = 12 kHz
Assume Fs = 5000 samples/s. Signal obtained after sampling
Folding frequency = Fs
2 = 2.5 kHz
x(n) = xa(nT) = xa
n
Fs
= 3 cos 2π(1
5)n + 5 sin 2π(3
5)n +
10 cos 2π(6
5)n = 3 cos 2π(1
5)n + 5 sin 2π(1 − 2
5)n + 10 cos 2π(1 + 1
5)n =
3 cos 2π(1
5)n + 5 sin 2π(−2
5)n + 10 cos 2π(1
5)n =
13 cos 2π(1
5)n − 5 sin 2π(2
5)n
33 / 45
The Sampling Theorem
Example (continued)
Second solution:
Aliases of F0: Fk = F0 + kFs −→ F0 = Fk − kFs such that
−Fs/2 ≤ F0 ≤ Fs/2
F1 is less than Fs/2
F2 = F2 − Fs = −2 kHz
F3 = F3 − Fs = 1 kHz
f = F
Fs
−→ f1 = 1
5, f2 = −2
5, f3 = 1
5
Analog signal ya(t) reconstructed from samples using ideal
interpolation
Only frequency components at 1 kHz and 2 kHz are present in
sampled signal
ya(t) = 13 cos 2000πt − 5 sin 4000πt
This distortion was caused by aliasing effect due to low Fs used
34 / 45
Quantization of Continuous-Amplitude Signals
Quantization
Process of converting a discrete-time continuous-amplitude signal into a
digital signal
xq(n) = Q[x(n)] = sequence of quantized samples
Each sample value is expressed as a finite number of digits
Error introduced is called quantization error or quantization noise
eq(n) = xq(n) − x(n)
Example
Consider discrete-time signal
x(n) =
0.9n, n ≥ 0
0, n < 0
obtained by sampling xa(t) = 0.9t, t ≥ 0 with Fs = 1 Hz
35 / 45
Quantization of Continuous-Amplitude Signals
Example (continued)
Following table shows values of first 10 samples of x(n)
Description of sample value x(n) requires n significant digits
36 / 45
Quantization of Continuous-Amplitude Signals
Example (continued)
x(n) xq(n) xq(n) eq(n) = xq(n) − x(n)
n Discrete-time signal (Truncation) (Rounding) (Rounding)
0 1 1.0 1.0 0.0
1 0.9 0.9 0.9 0.0
2 0.81 0.8 0.8 -0.01
3 0.729 0.7 0.7 -0.029
4 0.6561 0.6 0.7 0.0439
5 0.59049 0.5 0.6 0.00951
6 0.531441 0.5 0.5 -0.031441
7 0.4782969 0.4 0.5 0.0217031
8 0.43046721 0.4 0.4 -0.03046721
9 0.387420489 0.3 0.4 0.012579511
Assume using one significant digit. To eliminate excess digits
do truncation
or do rounding
Rounding process is illustrated in next figure
37 / 45
Quantization of Continuous-Amplitude Signals
Example (continued)
Quantization step size (or resolution) = ∆ = 1−0
11−1 = 0.1
38 / 45
Quantization of Continuous-Amplitude Signals
Range of quantization error eq(n) in rounding
−
∆
2
≤ eq(n) ≤
∆
2
∆ =
xmax − xmin
L − 1
xmin and xmax = minimum and maximum value of x(n)
L = number of quantization levels
Dynamic range of signal = xmax − xmin
Quantization of analog signals always results in a loss of information
39 / 45
Quantization of Sinusoidal Signals
Sampling and quantization of xa(t) = A cos Ω0t
40 / 45
Quantization of Sinusoidal Signals
If Fs satisfies sampling theorem, quantization is the only error in A/D
process
Thus we can evaluate quantization error by quantizing xa(t) instead of
x(n) = xa(nT)
xa(t) is almost linear between quantization levels
Quantization error = eq(t) = xa(t) − xq(t)
Δ/2
-τ 0 τ t
Δ
e (t)
Δ/2
-Δ/2
-τ
0 τ t
q
τ denotes time that xa(t) stays within quantization levels
41 / 45
Quantization of Sinusoidal Signals
Mean-square error power
Pq =
1
2τ
τ
−τ
e2
q(t) dt =
1
τ
τ
0
e2
q(t) dt
since eq(t) = (∆/2τ)t, −τ ≤ t ≤ τ
Pq =
1
τ
τ
0
∆
2τ
2
t2
dt =
∆2
12
If quantizer has b bits of accuracy and covers range 2A
∆ =
2A
2b
−→ Pq =
A2/3
22b
Average power of xa(t)
Px =
1
Tp
Tp
0
(A cos Ω0t)2
dt =
A2
2
42 / 45
Quantization of Sinusoidal Signals
Quality of output of A/D converter is measured by
signal-to-quantization noise ratio (SQNR)
Provides ratio of signal power to noise power
SQNR =
Px
Pq
=
3
2
.22b
SQNR(dB) = 10 log10 SQNR = 1.76 + 6.02b
43 / 45
Coding of Quantized Samples
Coding process assigns a unique binary number to each quantization
level
L levels need at least L different binary numbers
b bits −→ 2b
different binary numbers−→ 2b
≥ L −→ b ≥ log2 L
44 / 45
References
John G. Proakis, Dimitris G. Manolakis, Digital Signal
Processing: Principles, Algorithms, and Applications, Prentice
Hall, 2006.
45 / 45