Cryptography Reference
In-Depth Information
d
(1)
d
(1)
d
(2)
,
,
r
i
d
(2)
Mux
r
i
D
D
D
Figure 5.5 - Example of a recursive systematic double-binary convolutional encoder.
5.2.2 Polynomial representation
Let us first consider a classical (non-systematic and non-recursive) binary code:
c
=0
, all the coecients
b
j
are null and
m
=1
. The knowledge of
g
(
k
)
k
=1
..n
j
then suces to describe the code. The coecients
g
(
k
)
j
j
=0
..ν
j
=0
..ν
therefore define
n
generator polynomials
G
(
k
)
in
D
(
Delay
)algebra:
G
(
k
)
(
D
)=
j
=0
...ν
g
(
k
)
j
D
j
(5.1)
Let us take the case of the encoder defined in Figure 5.2. The outputs
r
(1)
i
and
r
(2)
i
are expressed as functions of the successive data
d
as follows:
r
(1)
i
=
d
i
+
d
i−
2
+
d
i−
3
(5.2)
which can also be written, via the transform in
D
:
r
(1)
(
D
)=
G
(1)
(
D
)
d
(
D
)
(5.3)
with
G
(1)
(
D
)=1+
D
2
+
D
3
, the first generator polynomial of the code and
d
(
D
)
the transform in
D
of the message to be encoded. Likewise, the second
generator polynomial is
G
2
(
D
)=1+
D
+
D
3
.
These generator polynomials can also be resumed by the series of their coe-
cients, (1011) and (1101) respectively, generally denoted in octal representation,
(13)
octal
and
(15)
octal
respectively. In the case of a non-recursive systematic
code , like the example in Figure 5.1, the generator polynomials are expressed
according to the same principle. In this example, the encoder has generator
polynomials
G
(1)
(
D
)=1
and
G
(2)
(
D
)=1+
D
+
D
3
.
To define the generator polynomials of a recursive systematic code is not
straightforward. Let us consider the example of Figure 5.3. The first generator