Cryptography Reference
In-Depth Information
correction capability limited to 11 error symbols, which is insucient for most
applications today. The construction of product codes allows this problem to be
circumvented: by using simple codes with low correction capability, but whose
decoding is not too costly, it is possible to assemble them to obtain a longer
code with higher correction capability.
Definition
Let
C
1
(resp.
C
2
) be a linear code of length
n
1
(resp.
n
2
) and with dimension
1
k
1
(resp.
k
2
). The product code
C
=
C
1
⊗
C
2
is the set of matrices
M
of size
n
1
×
n
2
such that:
•
Each row is a codeword of
C
1
,
•
Each column is a codeword of
C
2
.
This code is a linear code of length
n
1
×
n
2
andwithdimension
k
1
×
k
2
.
Example 8.1
Let
H
be the Hamming code of length 7 and
P
be the parity code of length 3.
The dimension of
H
is 4 and the dimension of
P
is 2. The code
C
=
H
⊗
P
is therefore of length
21 = 7
×
3
and dimension
8=4
×
2
. Let the following
information word be coded:
I
=
0110
1010
.
Each row of a codeword of
C
must be a codeword of
H
. Therefore to code
I
, we begin by multiplying each row of
I
by the generating matrix of code
H
:
⎡
⎤
1000111
0100110
0010101
0001011
0110
⎣
⎦
=
0110011
·
⎡
⎣
⎤
⎦
1000111
0100110
0010101
0001011
1010
·
=
1010010
1
or length of message