ELEN E4810: Digital Signal Processing

Topic 1: Introduction
1. Course overview
2. Digital Signal Processing
3. Basic operations & block diagrams
4. Classes of sequences

Dan Ellis 2013-09-04 1

 1. Course overview
 Digital signal processing:
Modifying signals with computers
 Web site:
http://www.ee.columbia.edu/~dpwe/e4810/
 Book:
Mitra “Digital Signal Processing”
(3rd ed., 2005)
 Instructor: dpwe@ee.columbia.edu

Dan Ellis 2013-09-04 2

 Grading structure
 Homeworks: 20%
 Mainly from Mitra
 Wednesday-Wednesday schedule
 Collaborate, don’t copy
 Midterm: 20%
 One session
 Final exam: 30%
 Project: 30%

Dan Ellis 2013-09-04 3

 Course project
 Goal: hands-on experience with DSP
 Practical implementation
 Work in pairs or alone
 Brief report, optional presentation
 Recommend MATLAB
 Ideas on website
 Don’t copy! Cite your sources!

Dan Ellis 2013-09-04 4

 Example past projects
Solo Singing Detection
on web site

 Guitar Chord Classifier

 Speech/Music Discrimination
 Room sonar
 Construction equipment monitoring
 DTMF decoder
 Reverb algorithms
 Compression algorithms
Dan Ellis 2013-09-04 5 W
 MATLAB
 Interactive system for numerical
computation
 Extensive signal processing library
 Focus on algorithm, not implementation
 Access:
 Columbia Site License:
https://portal.seas.columbia.edu/matlab/
 Student Version (need Sig. Proc. toolbox)
 Engineering Terrace 251 computer lab
Dan Ellis 2013-09-04 6
 Course at a glance
DSP
wk11
x[n]
wk1/2
Discrete time Continuous time
signals + systems n

X(ω)
Fourier Systems wk5
wk3 domain ω

DTFT z-transform Filters ω

wk4 Filter
FIR IIR design
DFT/FFT
wk10 wk6 wk7
FIR wk8 IIR wk9

Dan Ellis 2013-09-04 7

 2. Digital Signal Processing
 Signals:
Information-bearing function
 E.g. sound: air pressure variation at a
point as a function of time p(t)
 Dimensionality:
Sound: 1-Dimension
Greyscale image i(x,y) : 2-D
Video: 3 x 3-D: {r(x,y,t) g(x,y,t) b(x,y,t)}

Dan Ellis 2013-09-04 8

 Example signals
 Noise - all domains
 Spread-spectrum phone - radio
 ECG - biological
 Music
 Image/video - compression
 ….

Dan Ellis 2013-09-04 9

 Signal processing
 Modify a signal to extract/enhance/
rearrange the information
 Origin in analog electronics e.g. radar
 Examples…
 Noise reduction
 Data compression
 Representation for recognition/
classification…

Dan Ellis 2013-09-04 10

 Digital Signal Processing
 DSP = signal processing on a computer
 Two effects: discrete-time, discrete level
x(t)

x[n]

Dan Ellis 2013-09-04 11

 DSP vs. analog SP
 Conventional signal processing:

p(t) Processor q(t)

 Digital SP system:
p[n] q[n]
p(t) A/D Processor D/A q(t)

Dan Ellis 2013-09-04 12

 Digital vs. analog
 Pros
 Noise performance - quantized signal
 Use a general computer - flexibility, upgrde
 Stability/duplicability
 Novelty
 Cons
 Limitations of A/D & D/A
 Baseline complexity / power consumption

Dan Ellis 2013-09-04 13

 DSP example
 Speech time-scale modification:
extend duration without altering pitch

M
Dan Ellis 2013-09-04 14
 3. Operations on signals
 Discrete time signal often obtained by
sampling a continuous-time signal

 Sequence {x[n]} = xa(nT), n=…-1,0,1,2…

 T= samp. period; 1/T= samp. frequency
Dan Ellis 2013-09-04 15
 Sequences
Can write a sequence by listing values:
{x[n]} = {. . . , 0.2, 2.2, 1.1, 0.2, 3.7, 2.9, . . .}
↑
 Arrow indicates where n=0
 Thus,

Dan Ellis 2013-09-04 16

 Left- and right-sided
 x[n] may be defined only for certain n:
 N1 ≤ n ≤ N2: Finite length (length = …)
 N1 ≤ n: Right-sided (Causal if N1 ≥ 0)
 n ≤ N2: Left-sided (Anticausal)
 Can always extend with zero-padding

Left-sided Right-sided

Dan Ellis 2013-09-04 17

 Operations on sequences
 Addition operation:
 Adder x[n] y[n]

w[n] y[n] = x[n] + w[n]

 Multiplication operation
A
 Multiplier x[n] y[n]
y[n] = A x[n]

Dan Ellis 2013-09-04 18

 More operations
 Product (modulation) operation:
x[n] y[n]
 Modulator
w[n] y[n] = x[n] w[n]

 E.g. Windowing:
Multiplying an infinite-length sequence
by a finite-length window sequence
to extract a region

Dan Ellis 2013-09-04 19

 Time shifting
 Time-shifting operation:
where N is an integer
 If N > 0, it is delaying operation
 Unit delay x[n] y[n]

 If N < 0, it is an advance operation

 Unit advance
x[n] y[n]

Dan Ellis 2013-09-04 20

Combination of basic operations
 Example

y[n] = 1 x[n] +  2 x[n  1]

+  3 x[n  2] +  4 x[n  3]

Dan Ellis 2013-09-04 21

 Up- and down-sampling
 Certain operations change the effective
sampling rate of sequences by adding
or removing samples
 Up-sampling = adding more samples
= interpolation
 Down-sampling = discarding samples
= decimation

Dan Ellis 2013-09-04 22

 Down-sampling
 In down-sampling by an integer factor
M > 1, every M-th sample of the input
sequence is kept and M - 1 in-between
samples are removed:
xd [n] = x[nM ]

M xd [n]

Dan Ellis 2013-09-04 23

 Down-sampling
 An example of down-sampling

3 y[n] = x[3n]
Dan Ellis 2013-09-04 24
 Up-sampling
 Up-sampling is the converse of down-
sampling: L-1 zero values are inserted
between each pair of original values.
x[n/L] n = 0, ±L, 2L, . . .
xu [n] =
0 otherwise

Dan Ellis 2013-09-04 25

 Up-sampling
 An example of up-sampling

3
not inverse of downsampling!

Dan Ellis 2013-09-04 26

 Complex numbers
 .. a mathematical convenience that lead
to simple expressions
 A second “imaginary” dimension (j≡√-1)
is added to all values.
 Rectangular form: x = xre + j·xim
where magnitude |x| = √(xre2 + xim2)
and phase θ = tan-1(xim/xre)
 Polar form: x = |x| ejθ = |x|cosθ + j· |x|sinθ
! (! e =! cos ! + j sin  )
j

Dan Ellis 2013-09-04 27

 Complex math
 When adding, real
imag and imaginary parts
xim x+y
+yim add: (a+jb) + (c+jd)
x·y = (a+c) + j(b+d)
|y| yim
F
|x|·|y|
xim x  When multiplying,
yre
QF |x| magnitudes multiply
Q
xre xre
real and phases add:
+yre
rejθ·sejφ = rsej(θ+φ)
 Phases modulo 2π
Dan Ellis 2013-09-04 28
 Complex conjugate
 Flips imaginary part / negates phase:
Conjugate x* = xre – j·xim = |x| ej(–µ)
 Useful in resolving to real quantities:
x + x* = xre + j·xim + xre – j·xim = 2xre
x·x* = |x| ej(µ) |x| ej(–µ) = |x|2
imag
x
|x|
x+x*
= 2xre
Q
real

x*
Dan Ellis 2013-09-04 29
 Classes of sequences
 Useful to define broad categories…

 Finite/infinite (extent in n)

 Real/complex:
x[n] = xre[n] + j·xim[n]

Dan Ellis 2013-09-04 30

 Classification by symmetry
 Conjugate symmetric sequence:

Imag
xim[n]
if x[n] = xre[n] + j·xim[n]
Real

then xcs[n] = xcs*[-n]

xre[n]
= xre[-n] – j·xim[-n]
n

 Conjugate antisymmetric:
xca[n] = –xca*[-n] = –xre[-n] + j·xim[-n]
Dan Ellis 2013-09-04 31
Conjugate symmetric decomposition
 Any sequence can be expressed as
conjugate symmetric (CS) /
antisymmetric (CA) parts:
x[n] = xcs[n] + xca[n]
where:

xcs[n] = 1/2(x[n] + x*[-n]) = xcs*[-n]

xca[n] = 1/2(x[n] – x*[-n]) = -xca*[-n]
 When signals are real,
CS → Even (xre[n] = xre[-n]), CA → Odd
Dan Ellis 2013-09-04 32
 Basic sequences
 Unit sample sequence:
1

n
–4 –3 –2 –1 0 1 2 3 4 5 6
1
 Shift in time:
±[n - k] k–2 k–1 k
n
k+1 k+2 k+3

 Can express any sequence with ±:

{Æ0,Æ1,Æ2..}= Æ0±[n] + Æ1±[n-1] + Æ2±[n-2]..
Dan Ellis 2013-09-04 33
 More basic sequences
1, n 0
 Unit step sequence: µ[n] =
0, n<0

 Relate to unit sample:

[n] = µ[n]  µ[n 1]
µ[n] = 
n
[k]
k=

Dan Ellis 2013-09-04 34

 Exponential sequences
 Exponential sequences are
eigenfunctions of LTI systems
 General form: x[n] = A·Æn
 If A and Æ are real (and positive):

|Æ| > 1 |Æ| < 1

Dan Ellis 2013-09-04 35
 Complex exponentials

x[n] = A·Æn
 Constants A, Æ can be complex :
A = |A|ej¡ ; Æ = e(æ + j!)
→ x[n] = |A| eæn ej(!n + ¡) I
scale varying varying
R
magnitude phase
1 2
3 4
W
W n
W
per-sample
phase advance

Dan Ellis 2013-09-04 36

 Complex exponentials
 Complex exponential sequence can
‘project down’ onto real & imaginary
axes to give sinusoidal sequences
x[n] = exp{( 12 + j 6 )n} e = cos  + j sin 
1  j

xre[n] xim[n]

xre[n] = e-n/12cos(πn/6) xim[n] = e-n/12sin(πn/6) M

Dan Ellis 2013-09-04 37

 Periodic sequences
 A sequence satisfying
is called a periodic sequence with a
period N where N is a positive integer and
k is any integer.
Smallest value of N satisfying
is called the fundamental period

Dan Ellis 2013-09-04 38

 Periodic exponentials
 Sinusoidal sequence and
complex exponential sequence
are periodic sequences of period N only if
 o N = 2 r with N & r positive integers
 Smallest value of N satisfying
is the fundamental period of the
sequence
 r = 1 → one sinusoid cycle per N samples
r > 1 → r cycles per N samples M

Dan Ellis 2013-09-04 39

 Symmetry of periodic sequences
 An N-point finite-length sequence xf[n]
defines a periodic sequence:
“n modulo N” n N = n + rN
x[n] = xf [ n N]
s.t. 0 n N < N, r Z
 Symmetry of xf [n] is not defined
because xf [n] is undefined for n < 0
 Define Periodic Conjugate Symmetric:
xpcs [n] =1/2 (x[n] + x [ n N ])

=1/2 xf [n] + xf [N n] 1 n<N

Dan Ellis 2013-09-04 40
 Sampling sinusoids
 Sampling a sinusoid is ambiguous:
1

0.5

-0.5

-1
0 1 2 3 4 5 6 7 8 9 10

x1 [n] = sin(!0n)
x2 [n] = sin((!0+2πr)n) = sin(!0n) = x1 [n]

Dan Ellis 2013-09-04 41

 Aliasing
 E.g. for cos(!n), ! = 2ºr ± !0
all (integer) r appear the same after
sampling
 We say that a larger ! appears
aliased to a lower frequency
 Principal value for discrete-time
frequency: 0 ≤ !0 ≤ º
( i.e. less than 1/2 cycle per sample)
Dan Ellis 2013-09-04 42