Quadratic residue code

Examples of quadratic

residue codes include the $(7,4)$ Hamming code

over $GF(2)$, the $(23,12)$ binary Golay code

over $GF(2)$ and the $(11,6)$ ternary Golay code

over $GF(3)$.

There is a quadratic residue code of length $p$

over the finite field $GF(l)$ whenever $p$

and $l$ are primes, $p$ is odd, and

$l$ is a quadratic residue modulo $p$.

Its generator polynomial as a cyclic code is given by

:$f(x)=\backslash prod\_\{j\backslash in\; Q\}(x-\backslash zeta^j)$

where $Q$ is the set of quadratic residues of

$p$ in the set $\backslash \{1,2,\backslash ldots,p-1\backslash \}$ and

$\backslash zeta$ is a primitive $p$th root of

unity in some finite extension field of $GF(l)$.

The condition that $l$ is a quadratic residue

of $p$ ensures that the coefficients of $f$

lie in $GF(l)$. The dimension of the code is

$(p+1)/2$.

Replacing $\backslash zeta$ by another primitive $p$-th

root of unity $\backslash zeta^r$ either results in the same code

or an equivalent code, according to whether or not $r$

is a quadratic residue of $p$.

An alternative construction avoids roots of unity. Define

:$g(x)=c+\backslash sum\_\{j\backslash in\; Q\}x^j$

for a suitable $c\backslash in\; GF(l)$. When $l=2$

choose $c$ to ensure that $g(1)=1$.

If $l$ is odd, choose $c=(1+\backslash sqrt\{p^*\})/2$,

where $p^*=p$ or $-p$ according to whether

$p$ is congruent to $1$ or $3$

modulo $4$. Then $g(x)$ also generates

a quadratic residue code; more precisely the ideal of

$F\_l[X]/\backslash langle\; X^p-1\backslash rangle$ generated by $g(x)$

corresponds to the quadratic residue code.

The minimum weight of a quadratic residue code of length $p$

is greater than $\backslash sqrt\{p\}$; this is the square root bound.

Adding an overall parity-check digit to a quadratic residue code

gives an extended quadratic residue code. When

$p\backslash equiv\; 3$ (mod $4$) an extended quadratic

residue code is self-dual; otherwise it is equivalent but not

equal to its dual. By the Gleason–Prange theorem (named for Andrew Gleason and Eugene Prange), the automorphism group of an extended quadratic residue

code has a subgroup which is isomorphic to

either $PSL\_2(p)$ or $SL\_2(p)$.

Since late 1980, there are many algebraic decoding algorithms were developed for correcting errors on quadratic residue codes. These algorithms can achieve the (true) error-correcting capacity $\backslash lfloor(d-1)/2\backslash rfloor$ of the quadratic residue codes with the code length up to 113. However, decoding of long binary quadratic residue codes and non-binary quadratic residue codes continue to be a challenge. Currently, decoding quadratic residue codes is still an active research area in the theory of error-correcting code.

• F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977.
• {{citation

| last = Blahut | first = R. E. | author-link = R. E. Blahut

| date = September 2006

| doi = 10.1109/18.133245

| issue = 5

| journal = IEEE Trans. Inf. Theory

| location = Piscataway, NJ, USA

| pages = 1269–1273

| publisher = IEEE Press

| title = The Gleason-Prange theorem

| volume = 37}}.

• M. Elia, Algebraic decoding of the (23,12,7) Golay code, IEEE Transactions on Information Theory, Volume: 33, Issue: 1, pg. 150-151, January 1987.
• Reed, I.S., Yin, X., Truong, T.K., Algebraic decoding of the (32, 16, 8) quadratic residue code. IEEE Trans. Inf. Theory 36(4), 876–880 (1990)
• Reed, I.S., Truong, T.K., Chen, X., Yin, X., The algebraic decoding of the (41, 21, 9) quadratic residue code. IEEE Trans. Inf. Theory 38(3), 974–986 (1992)
• Humphreys, J.F. Algebraic decoding of the ternary (13, 7, 5) quadratic-residue code. IEEE Trans. Inf. Theory 38(3), 1122–1125 (May 1992)
• Chen, X., Reed, I.S., Truong, T.K., Decoding the (73, 37, 13) quadratic-residue code. IEE Proc., Comput. Digit. Tech. 141(5), 253–258 (1994)
• Higgs, R.J., Humphreys, J.F.: Decoding the ternary (23, 12, 8) quadratic-residue code. IEE Proc., Comm. 142(3), 129–134 (June 1995)
• He, R., Reed, I.S., Truong, T.K., Chen, X., Decoding the (47, 24, 11) quadratic residue code. IEEE Trans. Inf. Theory 47(3), 1181–1186 (2001)
• ….
• Y. Li, Y. Duan, H. C. Chang, H. Liu, T. K. Truong, Using the difference of syndromes to decode quadratic residue codes, IEEE Trans. Inf. Theory 64(7), 5179-5190 (2018)

Category:Quadratic residue

Category:Coding theory