Extended Quadratic Residue Code

Let s denote a prime number and let b be prime and a quadratic residue modulo s. Then Q(s, b) and Qʹ(s, b) are the cyclic linear codes defined by the polynomials

$\displaystyle \prod_{{r\in Q}}^{}$(X – αr)

and

(X – 1)$\displaystyle \prod_{{r\in Q}}^{}$(X – αr)

over ℤb, respectively, where Q denotes the set of all quadratic residues modulo s, and α is a primitive sth root of unity in some extension field of ℤb. The code Q(s, b) is called the augmented quadratic residue code, whereas Qʹ(s, b) is called the expurgated quadratic residue code. It can be shown that Q(s, b) is an [s,(s + 1)/2]-code and Qʹ(s, b) is an [s,(s−1)/2]-code.

The extended quadratic residue code Qe(s + 1, b) is obtained by applying standard lengthening (i.e., construction X with a [1, 1, 1]-code) to Qʹ(s, b) ⊂ Q(s, b). It is a linear [s + 1,(s + 1)/2]-code over ℤb.

Bounds on the minimum distance of Qe are available, but the actual minimum distance of quadratic residue codes is usually much higher. It can be shown that the minimum distance of Qe is actually given by the following values. These tables are based on the tables in [1, page 318], but contain some additional entries.

Over ℤ2

s + 1d 
84[2]
186[3]
248[3], extended Golay code
328[2]
4210[2]
4812[2]
7212[2]
7414[2]
8016[2]
9018[2]
9816[2]
10420[4]
11416[5]
12820[4]
13822[6]
15220[4]

Over ℤ3

s + 1d 
126[3], extended Golay code
146[3]
249[3]
3811[7], [5]
4815[3]
6018[8]
6212[5]
7218[5]
7418[5]
8421[9]

Over F4

s + 1d 
64[8], hexacode
126[3]
146[3]
208[8]
3012[3]
3812[8]
4210[8]
4414[10]
5414[10]
6014[10]

Over ℤ5

s + 1d 
126[3]
208[11]
3012[11]
3210[11]

Over ℤ7

s + 1d 
209[11]
3012[11]
3213[11]

Over F9

s + 1d 
85[8]
188[11]
2010[11]
3012[11]
3212[11]

Over F25

s + 1d 
85[8]
148[11]
1810[11]
2412[11]

Over F49

s + 1d 
64[8]
127[8]
148[11]
1810[11]
2412[11]

See also

References

[1]Andries E. Brouwer.
Bounds on the size of linear codes.
In Vera S. Pless and W. Cary Huffman, editors, Handbook of Coding Theory, volume 1, pages 295–461. Elsevier Science, 1998.
[2]Elwyn R. Berlekamp.
Algebraic Coding Theory.
McGraw-Hill, New York, 1968.
MR0238597 (38 #6873)
[3]Edward F. Assmus, Jr. and Harold F. Mattson, Jr.
New 5-designs.
Journal of Combinatorial Theory, Series A, 6:122–151, 1969.
MR0272647 (42 #7528)
[4]F. Jessie MacWilliams and Neil J. A. Sloane.
The Theory of Error-Correcting Codes.
North-Holland, Amsterdam, 1977.
[5]Donald Coppersmith and Gadiel Seroussi.
On the minimum distance of some quadratic residue codes.
IEEE Transactions on Information Theory, 30(2):407–411, March 1984.
[6]Nigel Boston.
The minimum distance of the [137, 69] binary quadratic residue code.
IEEE Transactions on Information Theory, 45(1):282, January 1999.
doi:10.1109/18.746813 MR1677868 (99k:94052)
[7]J. C. C. M. Remijn and Cornelis de Vroedt.
The minimum distance of the [38, 19] ternary extended QR-code is 11.
IEEE Transactions on Information Theory, 30(2):405–407, March 1984.
[8]Edward F. Assmus, Jr. and Harold F. Mattson, Jr.
On weights in quadratic-residue codes.
Discrete Mathematics, 3(1–3):1–20, 1972.
doi:10.1016/0012-365X(72)90021-0 MR0305905 (46 #5033)
[9]Doug Kuhlman.
The minimum distance of the [83, 42] ternary quadratic residue code.
IEEE Transactions on Information Theory, 45(1):282, January 1999.
doi:10.1109/18.746814
[10]Maurice Karlin, Vijay K. Bhargava, and Stafford E. Tavares.
A note on extended quaternary quadratic residue codes and their binary images.
Information and Control, 38(2):148–153, August 1978.
doi:10.1016/S0019-9958(78)90158-4
[11]Donald W. Newhart.
On minimum weight codewords in QR codes.
Journal of Combinatorial Theory, Series A, 48(1):104–119, May 1988.
doi:10.1016/0097-3165(88)90078-7

Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Extended Quadratic Residue Code.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CQuadraticResidue.html

Show usage of this method