Cryptography Reference
In-Depth Information
described in this topic since, for turbo decoding, we prefer another family of
algorithms relying on the minimization of the error probability of each symbol
transmitted. Thus, the Maximum
A Posteriori
(MAP) algorithm enables the
calculation of the exact value of the
a posteriori
probability associated with each
symbol transmitted using the received sequence [5.1]. The MAP algorithm and
its variants are described in Chapter 7.
Figure 5.19 - Model of the transmission chain studied.
5.4.1 Model of the transmission chain and notations
Viterbi and MAP algorithms are used in the transmission chain shown in Fig-
ure 5.19. The convolutional code considered is systematic and, for each data
sequence of information
d
=
d
1
=
{
d
1
,
···
,
d
N
}
, calculates a redundant se-
quence
r
=
r
1
=
. The code is
m
-binary with rate
R
=
m/
(
m
+
n
)
:
each vector of data
d
i
at the input of the encoder is thus made up of
m
bits,
d
i
=(
d
(1)
i
{
r
1
,
···
,
r
N
}
,d
(2)
i
,d
(
m
)
i
,
···
)
, and the corresponding redundancy vector at the out-
put is written
r
i
=(
r
(1)
,r
(2)
i
,r
(
n
)
i
,
···
)
.Thevalueof
d
i
can also be represented
i
l
=1
m
2
l−
1
d
(
l
)
i
, between 0 and
2
m
by the scalar integer variable
j
=
−
1
,andwecan
then write
d
i
≡
j
.
The systematic
d
and redundant
r
data sequences are transmitted after a
binary/antipodal conversion making an antipodal value (-1 or +1) transmitted
towards the channel correspond to each value binary (0 or 1) coming from the
encoder.
X
and
Y
represent the noisy systematic and redundant symbol se-
quences received at the input of the decoder and
d
the decoded sequence that
can denote either a binary sequence in the case of the Viterbi algorithm, or a
sequence of weighted decisions associated with the
d
i
at the output of the MAP
algorithm.
5.4.2 The Viterbi algorithm
The Viterbi algorithm is the most widely used method for the maximum-
likelihood (ML) decoding of convolutional codes with low constraint length (typ-
ically
ν
8
). Beyond this limit, its complexity of implementation means that
we have to resort to a sequential decoding algorithm, like Fano's [5.6].
ML decoding is based on a search for the codeword c that is the shortest
distance away from the received word. In the case of a channel with binary deci-
≤
