Decoding Quadratic Residue Codes via their Embedding in Cyclic Codes over Cyclotomic Fields
by
Michele Elia
Politecnico di Torino, Italy
Coauthors: J. Carmelo Interlando (University of Notre Dame, IN, USA)

Let C_q denote a q-ary quadratic residue (QR) code of length p and dimension (p+1)/2. The code length p is a prime number of the forms 8m - 1 or 8m+1, and q is any prime for which -p or p is a quadratic residue, respectively. The minimum distance d of C_q is lower bounded by the square root of p and is independent of q. Furthermore, it is well-known that for every binary QR code with a length of less than 80, an algebraic decoding algorithm exists that corrects every error pattern of weight up to e, the code error-correcting capability.

In this paper, a ``general" algebraic decoding algorithm correcting e errors is shown to exist for every p and every q not a divisor of 2m. When q divides 2m, a case which includes every binary QR code, the algorithm should be different for different p. These results are proved by embedding C_q in a cyclic code over the cyclotomic field K of the p-th roots of unity. Specifically, C_q is considered over a residue field of algebraic numbers in the ring of integers of a quadratic subfield F of K, generated by a root of x^2-x+(-1)^((p+1)/2) 2m. The decoding algorithm, based on GPZ method, obtains the error locator polynomial using a sequence of d-1 consecutive syndromes S_1, … , S_(d-1). From a received word, a set of syndromes S_j is computed for every j that is a quadratic residue modulo p. The missing syndromes in the sequence are computed using a Galois automorphism of F. The computation is effective unless q is a divisor of 2m. The situation is fully illustrated giving a complete decoding of QR codes with length p=23, d=7, and dimension 12 for every admissible q, including 2 and 3.

Date received: August 20, 2003