Outline
• Transmitters (Chapters 3 and 4, Source Coding and Modulation)
(week 1 and 2)
• Receivers (Chapter 5) (week 3 and 4)
• Received Signal Synchronization
(Chapter 6) (week 5)
• Channel Capacity (Chapter 7) (week 6)
• Error Correction Codes (Chapter 8) (week 10 and 11)
• Equalization (Bandwidth Constrained Channels) (Chapter 10)
• Adaptive Equalization (Chapter 11)
• Spread Spectrum (Chapter 13)
• Fading and multi path (Chapter 14)
Error Correction Codes (Chapter 8)
• Trellis/Convolution Codes
• Trellis Codes and QAM NRZI code with memory L=1
Trellis for NRZI
Convolution Code Generator
Viterbi Algorithm
QAM set partition via convolution code 8 state Trellis for rectangular QAM
Trellis/Convolution Codes
• Modulation with Memory
– Example: NRZI NRZI code with memory L=1
• Trellis diagram
• Maximum likelihood sequence
detectors Trellis for NRZI
– Viterbi Algorithm
Viterbi Algorithm
Modulation with Memory
• Example: NRZI (non return to zero invert)
– Binary PAM
NRZI code with memory L=1
Modulation with Memory
• Example: NRZI (non return to zero invert)
– Encoded by:
ak
bk 1
Modulo 2 addition
bk
Has one memory and 1/1 code rate
(No error correction)
Trellis diagram
• Indicates state transitions for various inputs
ak
bk 1
bk
Trellis Diagram for NRZI
Maximum likelihood sequence
detectors
• Consider NRZI matched filter decoder
output:
rk b nk
1 ( rk b ) 2 / 2 n2
p (rk | s1 ) e
2 n
1 ( rk b ) 2 / 2 n2
p (rk | s2 ) e
2 n
Maximum likelihood sequence
detectors
• Consider joint pdf of a matched filter
decoder output sequence and a transmitted
(m )
sequence s : m = 1,2,…M (M symbols)
K
1
)
(m) ( rk b ) 2 / 2 n2
p (r1 , r2 , rK | s e
k 1 2 n
K K
1 ( rk sk( m ) ) 2 / 2 n2
e k 1
2
n
Maximum likelihood sequence
detectors
• Now find maximum likely hood:
(m)
max( p(r1 , r2 , rK | s ))
K
min( D(r, s (m)
) (rk s (m) 2
k )
k 1
Minimizes Euclidean distance
Maximum likelihood sequence
detectors
• Viterbi algorithm
– Eliminates sequences as data is collected
1. compute distances as you go
2. Keep only the smallest distances for each
trellis state at each symbol time
3. After some number of symbols K decide
what the first symbol was by:
a) Consensus or b) Minimum D path
4. Do this for each time step
Maximum likelihood sequence
detectors ak
bk 1
• Viterbi algorithm for NRZI
k s r s0 s1 K bk
b s r shat D(r, s bhat bhat shat bhat bhat ( m)
) (rk sk( m ) ) 2
1 0 0.00 0 0 1 1 0 1
k 1
1 0.00 s= 0
0.99
1
0.00
0.99 s= 1
0.99
0
1.98 The example
1 1 1.00 0 0 1 1 0 1
2 0.99 s= 0 1 0.00 s= 1 0 shows how
1 0 -0.01 0
0.99
0
2.01
1 1
1.02
0
0.00
1
the Viterbi
3 0.00 s= 0
1.02
1
0.00
1.02 s= 1
1.02
0
2.04
algorithm by
1 1 1.01 0 0 1 1 0 1 trying all
4 1.02 s= 0
1.02
1
2.03
0.00 s= 1
1.01
0
0.00
possible
0 0 -0.01 0 0 1 1 0 1 states and
5 0.00 s= 0
0.00
1
0.98
1.01 s= 1
2.00
0
1.01
digital inputs
0 0 0.01 0 0 1 1 0 1 can correctly
6 0.00 s= 0
0.00
1
1.00
0.98 s= 1
1.98
0
0.98
estimate the
1 0 0 0 1 digital inputs
7 0.00 0.99
(green)
Maximum likelihood sequence
detectors ak
bk 1
• Viterbi algorithm for NRZI
k s r s0 s1 K bk
b s r shat D(r, s bhat bhat shat bhat bhat ( m)
) (rk sk( m ) ) 2
0 1 1.01 0 0 1 1 0 1
k 1
1 1.02 s= 0
2.02
1
1.02
0.00 s= 1
0.00
0
1.00 Try it again
1 1 1.00 0 0 1 1 0 1
2 1.00 s= 0 1 0.00 s= 1 0 with different
1 0 0.00 0
1.00
0
2.01
1 1
1.01
0
0.00
1
initial state
3 0.00 s= 0
1.00
1
0.00
1.01 s= 1
1.01
0
2.00
and data.
0 1 1 0 0 1 1 0 1
4 1.00 s= 0
1.98
1
1.00
0.00 s= 1
0.00
0
0.98
The trellis to
0 1 0.99 0 0 1 1 0 1 the right
5 0.98 s= 0
2.00
1
0.98
0.00 s= 1
0.00
0
1.02
matches the
1 1 1.01 0 0 1 1 0 1 Excel
6 1.02 s= 0
1.02
1
2.01
0.00 s= 1
0.99
0
0.00
spreadsheet
1 0 0.01 0 1
7 0.00 0.98
Trellis/Convolution Codes
• The general Convolution Code
K=number of stages
k=number of input bits per stage
n=number of output bits
The code rate
Rc k n
Represents how much faster data must be
sent
Trellis/Convolution Codes
• The general Convolution Code
– The code is described by the “generators”
• i.e., the weights on each mod 2 adder
– e.g., for K = 3, k = 1, n = 3, Rc k n 1 3
g1 1 0 0 4 (octal) 1
0
1
g 2 1 0 1 5 (octal) 1
g 3 1 1 1 7 (octal) 1 1
Trellis/Convolution Codes
• The general Convolution Code
– There are better codes
– K = 3, k = 1, n = 3, Rc k n 1 3
– With generator 5 7 7 is optimal
g1 1 0 1 5 (octal)
g 2 1 1 1 7 (octal)
g 3 1 1 1 7 (octal)
Trellis/Convolution Codes
• The general Convolution Code
– Trellis and Transfer function
• Tell us dfree = minimum hamming distance between
paths through the Trellis
– Coding gain:
Coding gain 10 log10 ( Rc d free )
e.g., Rc 1 3 , d free 6
Coding gain 10 log10 (1 3 6) 3dB
e.g., Rc 1 3 , d free 8
Coding gain 10 log10 (1 3 8) 4.3dB
Maximum likelihood sequence
detector
• Viterbi algorithm for K = 3, k = 1, n = 3,with generator 5 7 7
b in s b in b o u t s ig m a0=. 0 1 r shat shat shat shat s hat shat shat shat
1 1 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1
g1 1 0 1 0 -0 . 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0
g2 1 1 1 1 0 .9 9 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
g3 1 1 1 1 1 .0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
m e t ric = 1 .9 8 1 .0 1 1 .0 1 1 .9 8 0 .0 0 2 .9 9 2 .9 9 0 .0 0
n e x t s ta te = 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1
2 1 1 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1
g1 1 0 1 0 0 .0 3 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0
g2 1 1 1 1 1 .0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
g3 1 1 1 1 1 .0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
m e t ric = 3 .0 1 1 .9 5 0 .9 4 2 .0 0 1 .0 1 3 .9 5 2 .9 4 0 .0 0
n e x t s ta te = 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1
3 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1
g1 1 0 1 1 0 .9 9 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0
g2 1 1 1 0 -0 . 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
g3 1 1 1 0 -0 . 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
m e t ric = 1 .9 2 2 .9 9 3 .0 6 1 .9 9 4 .9 8 1 .9 5 0 .0 0 3 .0 3
n e x t s ta te = 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1
4 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1
g1 1 0 1 1 1 .0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0
g2 1 1 1 1 1 .0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
g3 1 1 1 1 1 .0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
m e t ric = 4 .9 5 1 .9 2 0 .0 0 3 .0 3 3 .0 1 4 .0 1 3 .9 7 2 .9 7
n e x t s ta te = 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1
Maximum likelihood sequence
detector
• Viterbi algorithm for K = 3, k = 1, n = 3,with generator 5 7 7
• Example of error correction? sigma = 0.5
• Decision at step 11 corrects bit error at step 2
b in s b in b o u t s ig m a =0 . 5 r shat shat shat shat shat shat shat shat
1 1 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1
g1 1 0 1 0 0 .1 7 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0
g2 1 1 1 1 1 .0 6 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
g3 1 1 1 1 0 .8 5 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
m e t ric = 1 .8 6 0 .7 2 0 .7 2 1 .8 6 0 .0 5 2 .5 3 2 .5 3 0 .0 5
n e x t s ta te = 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1
2 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1
g1 1 0 1 1 0 .8 8 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0
g2 1 1 1 0 0 .4 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
g3 1 1 1 0 0 .7 4 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
m e t ric = 2 .2 2 1 .1 5 0 .4 8 1 .5 5 1 .9 0 1 .4 6 0 .7 9 1 .2 3
n e x t s ta te = 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1
3 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1
g1 1 0 1 1 1 .6 5 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0
g2 1 1 1 1 1 .5 8 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
g3 1 1 1 1 0 .9 8 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
m e t ric = 6 .6 8 1 .2 4 1 .5 6 6 .9 9 4 .2 2 5 .0 4 5 .1 3 4 .3 0
n e x t s ta te = 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1
4 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1
g1 1 0 1 1 0 .9 4 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0
g2 1 1 1 1 1 .6 7 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
g3 1 1 1 1 1 .3 8 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1
m e t ric = 7 .1 3 2 .1 6 4 .8 1 9 .7 9 2 .7 2 5 .9 4 9 .0 0 5 .7 8
n e x t s ta te = 0 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1
Trellis Codes and QAM
• Bandwidth Constrained Channels
– Use set partitioning to combine code with M-ary bandwidth constrained
signaling Ungerboeck (1982)
– Three rules:
• Use all subsets with equal frequency in trellis
• Use Transitions that join use maximum distance subsets
• Parallel transitions are assigned max Euclidean distance (unencoded bit transitions)
QAM set partition via convolution code
8 state Trellis for rectangular QAM
Set Partitioning
• Chop up the Constellations to increase Euclidean distance
between points
• In rectangular QAM case each partition increases d by 2
64 QAM Set Partitioning
• Each 4 x 4 block of 64 QAM constellation is
sm2
replaced by 16 QAM partition
sm1
64 QAM Set Partitioning
• Examples:
Decide between these in Real decoder
D0 D2
Trellis Codes and QAM
• Eight state trellis for QAM
Contains no overlapping locations
Trellis Codes and QAM
• The code generator
Trellis Codes and QAM
• The code generator
– Alternate = essentially a kind of parity bit
Trellis Codes and QAM
• The code generator
– Alternate = essentially a kind of parity bit
– The weights = “parity matrix” not generator
matrix
– Ungerboeck IEEE Communications Magazine February 1987-Vol. 25. No. 2
Trellis Codes and QAM
• The code generator
g1 0 0 1 0 0 0
g 2 0 1 0 0 1 0
g 3 1 0 0 1 0 0
Trellis Codes and QAM
• The code generator
Memory = 3, thus 8 states
g1 0 0 1 0 0 0
g 2 0 1 0 0 1 0
g 3 1 0 0 1 0 0
Trellis Codes and QAM
• The code generator
g1 0 0 1 0 0 0
g 2 0 1 0 0 1 0
g 3 1 0 0 1 0 0
0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0
b in s b in bout 0 .0 1 r
1 1 1 1 1 1 1 s ig m a =
g1 0 0 1 0 0 0 1 1 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
g2 0 1 0 0 1 0 0 0 .0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1
g3 1 0 0 1 0 0 0 0 .0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1
m e t ric = 1 .0 0 1 .9 7 2 .0 0 2 .9 7 1 .9 7 1 .0 0 2 .9 7 2 .0 0 2 .0 0 2 .9 7 1 .0 0 1 .9 7 2 .9 7 2 .0 0 1 .9 7 1 .0 0 0 .0 0 0 .9 7 1 .0 0 1 .9 8 0 .
n e x t s ta te =
2 1 0 0 0 1 1 1 1
g1 0 0 1 0 0 0 1 1 .0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
g2 0 1 0 0 1 0 1 1 .0 2 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1
g3 1 0 0 1 0 0 1 1 .0 1 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1
m e t ric = 4 .0 5 3 .0 2 3 .0 4 2 .0 1 2 .0 3 3 .0 6 1 .0 1 2 .0 4 3 .0 4 2 .0 1 4 .0 5 3 .0 2 1 .0 1 2 .0 4 2 .0 3 3 .0 6 3 .0 4 2 .0 1 2 .0 3 1 .0 0 1 .
n e x t s ta te =
3 1 1 0 1 0 0 1 1
g1 0 0 1 0 0 0 0 0 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
g2 0 1 0 0 1 0 0 -0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1
g3 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1
Trellis Codes and 64 QAM
• Send 64 QAM but only 5 bits per symbol
– 6 bits = 3 data bits + 3 encoded bits
– The 3 encoded bits come from 2 data bits
One of eight subsets – 3 bits
Select the levels for each dimension
2 bits in, 3 bits out
One of eight symbols – 3 bits
4 levels per dimension
Trellis Codes and QAM
• Trellis seems not the same?
– Maybe books trellis is parity realization
0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1
bout 0 .0 1 r
s ig m a =
1 1 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 -0 . 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1
0 0 .0 0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1
m e t ric = 1 .0 0 2 .0 3 2 .0 0 3 .0 3 2 .0 3 1 .0 0 3 .0 3 2 .0 0 2 .0 0 3 .0 3 1 .0 0 2 .0 3 3 .0 3 2 .0 0 2 .0 3 1 .0 0 0 .0 0 1 .0 3 1 .0 0 2 .0 3 1 .0 3 0 .0 0 2 .0 3 1 .0 0 1 .0 0 2 .0 3
n e x t s ta te =
1 0 .9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
1 1 .0 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1
1 0 .9 9 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1
m e t ric = 3 .9 8 2 .9 7 2 .9 9 1 .9 9 1 .9 7 2 .9 8 0 .9 8 1 .9 9 2 .9 9 1 .9 9 3 .9 8 2 .9 7 0 .9 8 1 .9 9 1 .9 7 2 .9 8 3 .0 0 1 .9 9 2 .0 1 1 .0 0 0 .9 9 1 .9 9 0 .0 0 1 .0 1 2 .0 1 1 .0 0
n e x t s ta te =
0 0 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 0 .0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1
0 -0 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1
m e t ric = 0 .9 8 1 .9 7 2 .0 1 3 .0 0 0 .9 9 0 .0 0 2 .0 1 1 .0 2 3 .0 1 4 .0 0 1 .9 9 2 .9 8 3 .0 2 2 .0 3 1 .9 9 1 .0 0 1 .9 9 2 .9 8 3 .0 1 4 .0 0 1 .9 9 1 .0 1 3 .0 2 2 .0 3 4 .0 1 5 .0 0
n e x t s ta te =
