Cryptography Reference
In-Depth Information
The Reddy-Robinson algorithm is thus the following:
•
Step 1: Find the errors in each row
i
by applying the decoder of code
C
1
without erasures and assign them a weight
l
i
equal to the number of errors
detected. If the decoding fails, the weight assigned is
l
i
=
d
1
/
2
.Therows
are passed without correction to step 2.
•
Step 2: Decode the columns by the decoder of code
C
2
with erasures.
For each column, we successively perform all the decodings by erasing the
least reliable symbols (
i.e.
those that have the highest row weight). We
therefore have at least
decodings per row. At each decoding we
assign a weight
W
such that
W
=
d
1
/
2
i
=1
w
i
where
w
i
=
l
i
if the symbol of
row
i
is unchanged by the decoding and
w
i
=
n
d
2
/
2
otherwise.
•
Step 3: At the final decoding, for each column we choose the decoded word
giving the smallest weight
W
.
Reddy-Robinson decoding allows any pattern of errors to be corrected whose
weight is strictly lower than
d
1
d
2
[8.15].
Example 8.3
Let us again take the above example with the word of Figure 8.2. During the
first step, those rows with 3 errors will not be able to be corrected by the row
code since the latter can correct only a maximum of 2 errors (MHD 5). They
will therefore be assigned an equal weight 2.5. The row with one error will have
a weight equal to 1, while all the remaining rows will have a weight equal to 0.
The configuration is then as shown in Figure 8.3.
At the second step, the correction becomes effective. Only three columns
have errors. Concerning the most left-hand column with errors, according to
the weights provided by step 1, three symbols in this column have a weight
equal to 2.5, one symbol with a weight equal to 1 and all the others have a
null weight. The second step of the algorithm for this column will therefore
involve three successive decodings: decoding without erasure, decoding with
three erasures (the symbols having a weight equal to 2.5) and decoding with
four erasures (the three previous symbols plus the symbol having a weight of 1).
The first decoding fails since the code is only 2-correcting. The second decoding
succeeds. Indeed, the column code has a minimum distance of 5. It can thus
correct
t
errors and
e
erasures when
2
t
+
e<
5
. Now, for this decoding, we have
e
=3
(since 3 erasures are placed) and
t
=0
(since there are no additional errors
in the column). The weight associated with the second decoding is the sum of the
weights of the symbols erased, that is, 7.5. Likewise, the third decoding (with
4 erasures) succeeds and the weight associated with the word decoded is thus
8.5. The algorithm then chooses from among the decodings having succeeded
the one whose weight is the lowest, that is, the second decoding in this case.
