Institute for Experimental Mathematics
Ellernstrasse 29
45326 Essen - Germany
The viterbi algorithm
A.J. Han Vinck
Lecture notes data communications
10.01.2009
UniversityDuisburg-Essen digitalcommunicationsgroup
content
Viterbi decoding for convolutional codes
Hidden Markov models
With contributions taken from Dan Durafsky
2
UniversityDuisburg-Essen digitalcommunicationsgroup
Problem formulation
noise
information
Finite
State
Machine
observation
What is the best estimate for the information given the observation?
Maximum Likelihood receiver:
max P( Y | X ) = max P( X+N | X ) = max P( N )
for independent transmissions = max �
i=1,L
P( N
i
)
� minimum weight noise sequence
x n
y = x + n
3
UniversityDuisburg-Essen digitalcommunicationsgroup
The Noisy Channel Model
• Search through space of all possible sentences.
• Pick the one that is most probable given the
waveform.
4
UniversityDuisburg-Essen digitalcommunicationsgroup
characteristics
the Viterbi algorithm is a standard component of tens of millions of high-speed modems. It is
a key building block of modern information infrastructure
The symbol "VA" is ubiquitous in the block diagrams of modern receivers.
Essentially:
the VA finds a path through any Markov graph, which is a sequence of states
governed by a Markov chain.
many practical applications:
convolutional decoding and channel trellis decoding.
fading communication channels,
partial response channels in recording systems,
optical character recognition,
voice recognition.
DNA sequence analysis
etc.
5