Cryptography Reference
In-Depth Information
We obtain:
d
(
x
)
c
(
x
)
1 1
x
+
x
3
x x
+
x
2
+
x
4
x
2
1+
x
+
x
2
+
x
5
x
3
1+
x
2
+
x
6
and thus the generator matrix in a systematic form:
⎡
⎣
⎤
⎦
1101000
0110100
1110010
1010001
G
=
We can verify that for
d
=
1011
,
the matrix product
dG
does give
c
=
1001011
.
Implementation of an encoder
We have just seen that the encoder must carry out the division of
x
n−k
d
(
x
)
by the generator polynomial
g
(
x
)
then add the remainder
v
(
x
)
of this division
to
x
n−k
d
(
x
)
. This operation can be done using only shift registers and adders
in field
F
2
. As the most dicult operation to carry out is the division of
x
n−k
d
(
x
)
by
g
(
x
)
, let us first examine the schematic diagram of a divisor by
g
(
x
)
shown in Figure 4.2. The circuit divisor is realized from a shift register
with (
n
k
) memories denoted
R
i
and the same number of adders. The shift
register is initialized to zero and the
k
coecients of the polynomial
x
n−k
d
(
x
)
are introduced sequentially into the circuit divisor. After
k
clock pulses, we
can verify that the result of the division is available at the output of the cir-
cuit divisor, as well as the remainder
v
(
x
)
which is in the shift register memories.
−
The schematic diagram of the encoder shown in Figure 4.3, uses the circuit
divisor of Figure 4.2. The multiplication of
d
(
x
)
by
x
n−k
, corresponding to a
simple shift, is realized by introducing polynomial
d
(
x
)
at the output of the shift
register of the divisor.
The
k
data coming from the information source are introduced sequentially
into the encoder (switch I in position 1) that carries out the division of
x
n−k
d
(
x
)
by
g
(
x
)
. Simultaneously, the
k
data coming from the information source are also
transmitted. Once this operation is finished, the remainder
v
(
x
)
of the division
is in the (
n
−
k
) shift register memories. Switch I then moves to position 2, and
the (
n
−
k
) redundancy symbols are sent to the output of the encoder.
