Ph.D Thesis | |

Ph.D Student | Ruckenstein Gitit |
---|---|

Subject | Error Decoding Strategies for Algebraic Codes |

Department | Department of Computer Science |

Supervisor | PROF. Ronny Roth |

Error
correcting codes are used to detect and correct errors that occur in data when
transmitted through noisy channels. The channels considered are usually
communication channels or storage devices. An (*n*,*M*,*d*)
block code over an alphabet *F* is an *M*-subset of *F ^{n}*
with minimum Hamming distance

A list decoder
with a decoding radius *τ* for an (*n*,*M*,*d*) block
code *C* over *F* maps words in *F ^{n}* into sets
(lists) of codewords in

An [*n*,*k*,*d*]
linear code over the finite field *F*=GF(*q*) is an (*n*,*q ^{k}*,

A
polynomial-time list decoding algorithm for [*n*,*k*] RS codes has
been presented by Sudan in 1996. For codes of rate *k*/*n* not
greater than 1/3, his algorithm corrects more than *τ*_{1}
errors. In 1998, Guruswami and Sudan presented an improved algorithm which
enables the polynomial-time correction of more than *τ*_{1 }errors
for every [*n*,*k*] RS code at any code rate.

In this work,
a list decoding algorithm is presented for [*n*,*k*] RS codes over
GF(*q*), which is capable of correcting more than *τ*_{1}
errors. Based on the previous work of Sudan, an extended key equation (EKE) is
derived for RS codes, which reduces to the classical key equation when the
number of errors is limited to *τ*_{1}. Generalizing Massey's
algorithm which finds the shortest recurrence that generates a given sequence,
an algorithm is obtained for solving the EKE in time complexity *O*(*l*·(*n*-*k*)^{2}),
where *l* is a design parameter, typically a small constant, which is an
upper bound on the size of the list of decoded codewords (the case *l*=1
corresponds to classical decoding of up to *τ*_{1} errors
where the decoding ends with at most one codeword). This improves on the time
complexity *O*(*n*^{3}) needed for solving the equations of
Sudan's algorithm by a naive Gaussian elimination. The polynomials found by
solving the EKE are then used for reconstructing the codewords in time
complexity *O*((*l *log^{2 }*l*) k (n + *l* log *q*))
using root-finders of degree-*l* univariate polynomials. An extension of
the algorithm into an efficient implementation of Guruswami-Sudan's algorithm
is outlined as well.

Techniques are presented for computing upper and lower bounds on the number of errors that can be corrected by list decoders for general block codes and, specifically, for RS codes. The list decoder of Guruswami and Sudan implies such a lower bound (referred to here as the GS bound) for RS codes. It is shown that this lower bound, given by means of the code length, the minimum Hamming distance, and the maximal allowed list size, applies in fact to all block codes. Ranges of code parameters are identified where the GS bound is tight for worst-case RS codes, in which case the list decoder of Guruswami and Sudan provably corrects the largest possible number of errors.

On the other hand, ranges of parameters are provided for which the GS lower bound can be strictly improved. In some cases, the improvement applies to all block codes with a given minimum Hamming distance, while in others it applies only to RS codes.

Upper bounds
are derived on the average number of incorrect codewords (i.e., codewords
different from the transmitted one) that are included in the output list of a
decoder with radius *τ* for any [*n*,*k*] MDS code, where *τ*_{1}
< *τ* <*d*.