Ph.D Thesis

Ph.D StudentRuckenstein Gitit
SubjectError Decoding Strategies for Algebraic Codes
DepartmentDepartment 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 n with minimum Hamming distance d between any two different elements (codewords).

A list decoder with a decoding radius τ for an (n,M,d) block code C over F maps words in Fn into sets (lists) of codewords in C, such that the output list corresponding to an input word y consists of all the codewords in C at Hamming distance τ or less from y. The maximal list size is 1 if and only if the decoding radius does not exceed the largest integer τ not greater than  (d-1)/2. We denote this integer by τ1.

An [n,k,d] linear code over the finite field F=GF(q) is an (n,qk,d) code which forms a linear space over F. Such a code is called [n,k] MDS if d=n-k+1. An [n,k] Reed-Solomon (RS) code over F is an MDS code in which the codewords are obtained by evaluating the various polynomials of degree less than k over F at n prescribed different elements of F. The well-known RS decoding algorithm by Berlekamp and Massey and the Euclid-based algorithm by Sugiyama et  al. correct up to τ1 errors in time complexity O(τ12)=O((n-k)2).

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(n3) 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 log2 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.