Cryptography Reference
In-Depth Information
(
t
1
+1)
(
t
2
+1)
errors (even if it might decode certain patterns having more
errors) and there are words having exactly
(
t
1
+1)
·
·
(
t
2
+1)
errors that will not
be decoded.
Indeed, assume that we have a pattern with a number of errors strictly lower
than
(
t
1
+1)
(
t
2
+1)
. Since the algorithm decoding in rows corrects up to
t
1
errors, after the first decoding step, any row with errors contains at least
t
1
+1
errors. There are therefore at least
t
2
rows with errors after row decoding. Each
column therefore contains at least
t
2
errors and column decoding then eliminates
all the errors.
There are undecodable patterns having exactly
(
t
1
+1)
·
·
(
t
2
+1)
errors. Take
acodewordof
C
1
⊗
C
2
for which we choose
(
t
2
+1)
rows and
(
t
1
+1)
columns at
random. At each intersection between a row and a column, we insert an error in
the initial codeword. By construction, for the word thus obtained, there exists
a codeword for the product code at a distance of
(
t
1
+1)
·
(
t
2
+1)
errors, but
row decoding and column decoding fail.
We can note that row-column decoding is less powerful than syndrome decod-
ing for a product code. Indeed, a product code is a linear code whose minimum
distance is
d
1
d
2
. Therefore syndrome decoding allows us to correct all the words
having at least
t
errors with
t
=
(
d
1
d
2
)
/
2
. But row-column decoding allows
only all the words having less than
(
t
1
+1)
+1)
errors to be corrected. We therefore lose around a factor 2 in error correction
capability.
·
(
t
2
+1)=(
d
1
/
2
+1)(
d
2
/
2
Example 8.2
We assume that we have a product code whose row code and column code both
have a minimum distance equal to 5. They are therefore both 2-correcting. The
row-column decoding of the product code, according to the above, can thus
correct any word having at most 8 errors. Figure 8.1 illustrates a word having
10 errors (shown as points) but that can be corrected by row-column decoding.
Figure 8.2 shows a pattern having the same number of errors but not correctable.
8.3.2 The Reddy-Robinson algorithm
The Reddy-Robinson algorithm [8.15] is a more sophisticated iterative algorithm
which, now, assumes that for codes
C
1
and
C
2
we have decoders with errors and
erasures. An erasure is an unreliable position in the frame received, whose
symbol we think might be erroneous. The difference with a standard error is
that the position of the erasure is known at the moment of decoding. For an
MHD code equal to
d
, syndrome decoding can be adapted to take into account
the erasures and then it is possible to decode any frame with
t
errors and
e
erasures as long as we have
2
t
+
e<d
(8.1)
