Cryptography Reference
In-Depth Information
Figure 9.5 - Representation in the lower pseudo-triangular form of the parity check
matrix H.
of rows or columns. This matrix is made up of 6 sparse sub-matrices, denoted
A,B,C,D,E
and
T
, the latter being a lower triangular sub-matrix. Once the
preprocessing of
H
is finished, the encoding principle is based on solving the
system represented by the following matrix equation:
cH
T
=0
(9.16)
The codeword searched for is decomposed into three parts:
c
=(
d
,
r
1
,
r
2
)
,
where
d
is the systematic part that is known and where the redundancy bits
searched for are split into two vectors
r
1
and
r
2
, of respective size
g
and
n
−
g
. After multiplication on the right-hand side by matrix
,
I
0
k
−
ET
−
1
−
I
Equation (9.16) becomes:
A
d
t
+
B
r
1
+
T
r
2
=0
(9.17)
−
ET
−
1
A
+
C
d
t
+
−
ET
−
1
B
+
D
r
1
=0
(9.18)
ET
−
1
B
+
D
.Then
Equation (9.17) enables
r
2
to be found by inverting
T
. Many time-consuming
operations can be done once and for all during preprocessing. All the operations
repeated during the encoding have a complexity in
O(
n
)
except the multiplica-
Equation (9.18) enables
r
1
to be found by inverting
Φ=
−
tion of
−
ET
−
1
A
+
C
d
t
by square matrix
−
Φ
−
1
of size
g
g
which after
inversion is no longer sparse, hence a complexity in
O
g
2
. It is shown in [9.49]
that we can obtain a value of
g
equal to a small fraction of
n
:
g
=
αn
where
α
×
is a suciently low coecient for
O
g
2
<<
O(
n
)
for values of
n
up to
10
5
.
