Cryptography Reference
In-Depth Information
sions (binary symmetric channel), ML decoding relies on the Hamming distance,
whereas in the case of a Gaussian channel, it relies on the Euclidean distance
(see Chapter 2). An exhaustive search for codewords associated with the differ-
ent paths in the trellis leads to
2
ν
+
k
paths being taken into account. In practice,
searching for the path with the minimum distance on a working window with a
width
l
lower than
k
, limits the search to
2
ν
+
l
paths.
The Viterbi algorithm enables a notable reduction in the complexity of the
computation. It is based on the idea that, among the set of paths of the trellis
that converge in a node at a given instant, only the most probable path can be
retained for the following search steps. Let us denote
s
i
=(
s
(1
i
,s
(2
i
,...,s
(
ν
i
)
the state of the encoder at instant
i
and
T
(
i,
s
i−
1
,
s
i
)
the branch of the trellis
corresponding to the emission of data
d
i
and associated with the transition
between nodes
s
i−
1
and
s
i
. Applying the Viterbi algorithm involves performing
the set of operations described below.
•
At each instant i, for i ranging from 1 to k:
•
Calculate for each branch of a
branch metric
,
d
(
T
(
i,
s
i−
1
,
s
i
))
. For a binary
output channel, this metric is defined as the Hamming distance between
the symbol carried by the branch of the trellis and the received symbol,
d
(
T
(
i,
s
i−
1
,
s
i
)) =
d
H
(
T
(
i,
s
i−
1
,
s
i
))
.
For a Gaussian channel, the metric is equal to the square of the Euclidean
distance between the branch considered and the observation at the input
of the decoder (see also Section 1.3):
2
+
2
d
(
T
(
i,
s
i−
1
,
s
i
))
=
X
i
−
x
i
Y
i
−
y
i
x
(
j
)
i
2
y
(
j
)
i
2
j
=1
m
j
=1
n
X
(
j
)
i
Y
(
j
)
i
=
−
+
−
•
Calculate the
accumulated metric
associated with each branch
T
(
i,
s
i−
1
,
s
i
)
defined by:
λ
(
T
(
i,
s
i−
1
,
s
i
)) =
μ
(
i
−
1
,
s
i−
1
)+
d
(
T
(
i,
s
i−
1
,
s
i
))
where
μ
(
i
−
1
,
s
i−
1
)
is the accumulated metric associated with node
s
i−
1
.
•
For each no de
s
i
, select the branch of the trellis corresponding to the
minimum accumulated metric and memorize this branch in memory (in
practice, it is the value of
d
i
associated with the branch that is stored).
The path in the trellis made up of the branches successively memorized at
the instants between 0 and
i
is the
survivor path
arriving in
s
i
.Ifthetwo
paths that converge in
s
i
have identical accumulated metrics, the survivor
is then chosen arbitrarily between these two paths.
