Cryptography Reference
In-Depth Information
Chapter 5
Convolutional codes and their
decoding
5.1
History
It was in 1955 that Peter Elias introduced the notion of convolutional code
[5.5]. The example of an encoder described is illustrated in Figure 5.1. It
is a systematic encoder, that is, the coded message contains the message to
be transmitted, to which redundant information is added. The message is of
infinite length, which at first sight limits the field of application of this type of
code. It is however easy to adapt it for packet transmissions thanks to
tail-biting
techniques.
d
i
d
i
,
r
i
d
i
d
i
1
d
i
d
i
2
3
Mux
D
D
D
r
i
Figure 5.1 - Example of a convolutional encoder.
The encoder presented in Figure 5.1 is designed around a shift register with
three memory elements. The redundancy bit at instant
i
, denoted
r
i
is con-
structed with the help of a modulo 2 sum of the information at instant
i
,
d
i
and
the data present at instants
i
3
(
d
iā
1
and
d
iā
3
). A multiplexer plays
the role of a parallel to serial converter and provides the result of the encoding
at a rate twice that of the rate at the input. The coding rate of this encoder is
ā
1
and
i
ā
