Cryptography Reference
In-Depth Information
1
/
2
since, at each instant
i
, it receives data
d
i
and delivers two elements at the
output:
d
i
(systematic part) and
r
i
(redundant part).
It was not until 1957 that the first algorithm capable of decoding such codes
appeared. Invented by Wozencraft [5.15], this algorithm, called sequential de-
coding, was then improved by Fano [5.6] in 1963. Four years later, Viterbi
introduced a new algorithm that was particularly interesting when the length of
the shift register of the encoder is not too large [5.14]. Indeed, the complexity
of the Viterbi algorithm increases exponentially with the size of this register
whereas the complexity of the Fano algorithm is almost independent of it.
In 1974, Bahl, Cocke, Jelinek and Raviv presented a new algorithm [5.1]
capable of associating a probability with the binary decision. This property is
very widely used in the decoding of concatenated codes and more particularly
turbocodes, which have brought this algorithm back into favour. It is now
referred to in the literature in one of these three ways: BCJR (initials of the
inventors), MAP (Maximum
A Posteriori
)orAPP(
A Posteriori
Probability).
The MAP algorithm is rather complex to implement in its initial version,
and it exists in simplified versions, the most common ones being presented in
Chapter 7.
In parallel with these advances in decoding algorithms, a number of works
have treated the construction of convolutional encoders. The aim of these stud-
ies has not been to decrease the complexity of the encoder, since its implantation
is trivial. The challenge is to find codes with the highest possible error correction
capability. In 1970, Forney wrote a reference paper on the algebra of convolu-
tional codes [5.7]. It showed that a
good
convolutional code is not necessarily
systematic and suggested a construction different from that of Figure 5.1. For a
short time, that paper took systematic convolutional codes away from the field
of research on channel coding.
Figure 5.2 gives an example of a non-systematic convolutional encoder. Un-
like the encoder in Figure 5.1, the data are not present at the output of the
encoder and are replaced by a modulo 2 sum of the data at instant
i
,
d
i
,and
of the data present at instants
i
3
(
d
iā
2
and
d
iā
3
). Therateof
the encoder remains unchanged at
1
/
2
since the encoder always provides two
elements at the output:
r
(1)
ā
2
and
i
ā
i
and
r
(2
i
,atinstant
i
.
When Berrou
et al.
presented their work on turbocodes [5.4], they rehabil-
itated systematic convolutional codes by using them in a recursive form. The
interest of recursive codes is presented in Sections 5.2 and 5.3. Figure 5.3 gives
an example of an encoder for recursive systematic convolutional codes. The
original message being transmitted (
d
i
), the code is therefore truly systematic.
A feedback loop appears, the structure of the encoder now being similar to that
of pseudo-random sequence generators.
This brief overview has allowed us to present the three most commonly used
families of convolutional codes: systematic, non-systematic, and recursive sys-
tematic codes. The next two sections tackle the representation and performance
