Cryptography Reference
In-Depth Information
After encoding the rows, the provisional codeword is therefore:
0110011
1010010
.
Each column of the final codeword must now be a codeword with parity
P
.
The final codeword is therefore obtained by adding a third row made up of the
parity bits of each column. The complete codeword is:
⎡
⎤
0110011
1010010
1100001
⎣
⎦
.
For the codeword to be valid, it must then be verified that the third row of the
word is indeed a codeword of
H
. This row vector must therefore be multiplied
by the parity control matrix of
H
:
⎡
⎤
1
1
0
0
0
0
1
⎣
⎦
⎡
⎤
⎡
⎤
1110100
1101010
1011001
0
0
0
⎣
⎦
·
⎣
⎦
=
In fact, it is not worthwhile doing this verification: it is ensured by con-
struction since codes
H
and
P
are linear. In addition, the encoding order is not
important: if we first code by columns then by rows, the codeword obtained is
the same.
8.3
Hard input decoding of product codes
8.3.1 Row-column decoding
The first decoding algorithm results directly from the construction of the code:
we successively alternate decoding the rows by a decoder of code
C
1
and decod-
ing the columns by a decoder of code
C
2
.Let
d
1
(resp.
d
2
) be the minimum
distance of code
C
1
(resp.
C
2
). Then, syndrome decoding of
C
1
(resp.
C
2
)is
t
1
-correcting (resp.
t
2
-correcting) with
t
1
=
d
1
/
2
(resp.
t
2
=
d
2
/
2
).
Property
Row-column decoding is limited by a correction capability of
(
t
1
+1)
(
t
2
+1)
errors. In other words, row-column decoding decodes any word having at least
·
