Quadratic-Residue Codes and Cyclotomic Fields
- PDF / 294,489 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 112 Downloads / 244 Views
Quadratic-Residue Codes and Cyclotomic Fields Michele Elia · J. Carmelo Interlando
Published online: 1 August 2006 © Springer Science + Business Media B.V. 2006
Abstract We present an exposition of quadratic-residue codes through their embedding in codes over the quadratic subfield of the pth cyclotomic field, the algebraic number field of pth roots of unity. This representation allows the development of effective syndrome decoding algorithms that can fully exploit the code’s errorcorrecting capability. This is accomplished via Galois automorphisms of cyclotomic fields. For each fixed p, the general results hold for all pairs ( p, q), with a finite number of exceptions that depends on p. A complete discussion of the set of quadratic-residue codes of length 23 and dimension 12 illustrates these results. This set includes the Golay code, the only perfect binary three-error-correcting code. Mathematics Subject Classifications (2000) 11R18 · 94B15. Key words quadratic-residue codes · algebraic decoding · cyclotomic fields · lattices · Galois automorphism.
Quadratic-residue codes, abbreviated QR codes, are cyclic codes of odd prime length p over a field GF(q) where q is a prime that is a quadratic-residue modulo p, that is, q ≡ r 2 (mod p) for some nonzero integer r [19, 29]. Several classes of quadratic-residue codes over finite fields have been studied extensively. Particular attention is given to the cases q = 2 and q = 3, both for theoretical appeal and
A preliminary version of this paper was presented at the International Conference on Statistics, Combinatorics and Related Areas, October 3–5, 2003, University of Southern Maine, Portland, ME, USA. M. Elia (B) Politecnico di Torino, Corso Duca degli Abruzzi 24, I-10129 Torino, Italy e-mail: [email protected] J. C. Interlando Department of Mathematics and Statistics, San Diego State University, San Diego, CA, USA e-mail: [email protected]
238
Acta Appl Math (2006) 93: 237–251
practical importance as they are at the crossroads of number theory and coding theory [9, 15, 25, 28]. This paper presents an exposition of quadratic-residue codes over p finite fields GF(q) through their embedding in codes over the quadratic subfield Q( (−1)( p−1)/2 p) of the prime cyclotomic field Q(ζ p ) where ζ p ∈ C is a primitive pth root of unity. This apparently esoteric approach allows us to present a unified description of quadraticresidue codes and to develop a common decoding algorithm up to their error-correcting capability. Any cyclic code ( p, k, d)q of length p, dimension k, and minimum Hamming distance d, over the field GF(q) will be described using the standard polynomial representation. Therefore, any codeword c(x) is a polynomial in the indeterminate x of degree less than p: p−1
c(x) =
X
ci xi ,
i =0
with ci ∈ GF(q), i = 0, . . . , p − 1. The Hamming weight w H (c(x)) of c(x) is equal to its number of nonzero polynomial coefficients. The Hamming distance dH (a(x), b(x)) between a(x) and b(x) is equal to w H (a(x) − b(x)). An integer a that is not a multiple o
Data Loading...
