Hard Viterbi Decoding
J = 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
’0’ ’1’
0, 0, 1, 1, 0, 1, 1, 0, 0, 0
bi s1 s2 bi bp s1 s2
bi s1 s2 bp 00
next 00 00
z }| {
bi , s1 , s2 11
| {z }
current 01
01 01
Given the received bits sequence, 10
we use Viterbi decoding to retrieve 01
the original information bits.
10 10
I Hard decoding
10
I Soft decoding
00
Below example assumes all zero in- 11 11
11
put sequence.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 1/3
’0’
HD ’1’ J=1J=2J=3J=4J=5J=6J=7J=8
00 1 00 1 00 2 2 2 2 2 2
00 4 4 4
11 11 01 01 01
01 2 5
3 3
01 01
00 00
10 1 3
10 10
3
11 2 11 3 11 5
Received 10 00 10 00 00 00 00 00
Decoded 0 0 0 0 0 0 0 0
Branch Metric (γ): At J = 1, we move from state ’00’ to two states
{’00’, ’10’} when input ’0’ and ’1’. Branch metric is the Hamming
distance between the received symbol and the branch words.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 2/3
’0’
HD ’1’ J=1J=2J=3J=4J=5J=6J=7J=8
00 1 00 1 00 2 2 2 2 2 2
00 4 4 4
11 11 01 01 01
01 2 5
3 3
01 01
00 00
10 1 3
10 10
3
11 2 11 3 11 5
Received 10 00 10 00 00 00 00 00
Decoded 0 0 0 0 0 0 0 0
I at J = 1, input ’0’, output ’00’, received ’10’, γ00−00 (1) = 1
I at J = 1, input ’1’, output ’11’, received ’10’, γ00−10 (1) = 1
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 2/3
’0’
HD ’1’ J=1J=2J=3J=4J=5J=6J=7J=8
00 1 00 1 00 2 2 2 2 2 2
00 4 4 4
11 11 01 01 01
01 2 5
3 3
01 01
00 00
10 1 3
10 10
3
11 2 11 3 11 5
Received 10 00 10 00 00 00 00 00
Decoded 0 0 0 0 0 0 0 0
Path Metric (Γ): At J = 2, we move from state ’00’ (’10’) to two states
{’00’, ’10’} ({’01’, ’11’}) when input ’0’ and ’1’ - a total of four states.
The path metric is obtained as accumulated branch metrics.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 2/3
’0’
HD ’1’ J=1J=2J=3J=4J=5J=6J=7J=8
00 1 00 1 00 2 2 2 2 2 2
00 4 4 4
11 11 01 01 01
01 2 5
3 3
01 01
00 00
10 1 3
10 10
3
11 2 11 3 11 5
Received 10 00 10 00 00 00 00 00
Decoded 0 0 0 0 0 0 0 0
I at J = 2, γ00−00 (2) = 0 → Γ00 (2) = γ00−00 (1) + γ00−00 (2) = 1.
I at J = 2, γ00−10 (2) = 2 → Γ10 (2) = γ00−10 (1) + γ00−10 (2) = 3.
I similarly, we have Γ01 (2) = 2 and Γ11 (2) = 2.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 2/3
’0’
HD ’1’ J=1J=2J=3J=4J=5J=6J=7J=8
00 1 00 1 00 2 2 2 2 2 2
00 4 4 4
11 11 01 01 01
01 2 5
3 3
01 01
00 00
10 1 3
10 10
3
11 2 11 3 11 5
Received 10 00 10 00 00 00 00 00
Decoded 0 0 0 0 0 0 0 0
Merging Path: At J = 3, when two paths merge, the one with smaller
path metric is survived or a random choice if two path metrics are the
same.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 2/3
’0’
HD ’1’ J=1J=2J=3J=4J=5J=6J=7J=8
00 1 00 1 00 2 2 2 2 2 2
00 4 4 4
11 11 01 01 01
01 2 5
3 3
01 01
00 00
10 1 3
10 10
3
11 2 11 3 11 5
Received 10 00 10 00 00 00 00 00
Decoded 0 0 0 0 0 0 0 0
I state ’00’, path A: input {0, 0, 0} and ΓA (3) = 2; path B: input
00
{1, 0, 0} and ΓB00 (3) = 4 → Γ00 (3) = ΓA00 (3) = 2.
I state ’11’, path A: input {0, 1, 1} and ΓA (3) = 3; path B: input
11
{1, 1, 1} and ΓB11 (3) = 3 → Γ11 (3) = 3.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 2/3
’0’
HD ’1’ J=1J=2J=3J=4J=5J=6J=7J=8
00 1 00 1 00 2 2 2 2 2 2
00 4 4 4
11 11 01 01 01
01 2 5
3 3
01 01
00 00
10 1 3
10 10
3
11 2 11 3 11 5
Received 10 00 10 00 00 00 00 00
Decoded 0 0 0 0 0 0 0 0
Final Decision: At J = 8, the decoding procedures are to select the
smallest path metric amongst {Γ00 (8), Γ01 (8), Γ10 (8), Γ11 (8)} and find
out which input sequence results into the finally selected path metric.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 2/3
’0’
HD ’1’ J=1J=2J=3J=4J=5J=6J=7J=8
00 1 00 1 00 2 2 2 2 2 2
00 4 4 4
11 11 01 01 01
01 2 5
3 3
01 01
00 00
10 1 3
10 10
3
11 2 11 3 11 5
Received 10 00 10 00 00 00 00 00
Decoded 0 0 0 0 0 0 0 0
I Errors occur when two or more paths metrics have the same value.
I Or when two or more paths have the same final path metric.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 2/3
Appendix A
’0’
’1’ J=1 J=2 J=3 J=4 J=5 J=6 J=7 J=8
00 1 00 1 00 2 00 2 00 2 00 2 00 2 00 2
00 4 4 4 4 6 6
11 11 11 11 11 11 11 11
01 01 01 01 01 01
2 5 3 5 5 5 5
01 3 3 3 5 5 5
10 10 10 10 10 10
01 01 2
01 4
01 4
01 4
01 4
01 4
10 1 3 2 4 4 4 6 6
10 10 10 10 10 10 10
00 00 00 00 00 00
3 3 5 5 5 5
11 2 3 5 5 7 7 7
11 11 11 11 11 11
Received 10 00 10 00 00 00 00 00
Decoded 0 0 0 0 0 0 0 0
Figure: Full trellis of error-free hard Viterbi decoding. Assume all zero was
transmitted.
Dr Rong ZHANG (Soton) ELEC3203: DCT October 10, 2014 3/3
