A quadratic residue code is a type of cyclic code.
Examples Examples of quadratic residue codes include the ( 7 , 4 ) {\displaystyle (7,4)} Hamming code over G F ( 2 ) {\displaystyle GF(2)} , the ( 23 , 12 ) {\displaystyle (23,12)} binary Golay code over G F ( 2 ) {\displaystyle GF(2)} and the ( 11 , 6 ) {\displaystyle (11,6)} ternary Golay code over G F ( 3 ) {\displaystyle GF(3)} .
Constructions There is a quadratic residue code of length p {\displaystyle p}
over the finite field G F ( l ) {\displaystyle GF(l)} whenever p {\displaystyle p}
and l {\displaystyle l} are primes, p {\displaystyle p} is odd, and
l {\displaystyle l} is a quadratic residue modulo p {\displaystyle p} . Its generator polynomial as a cyclic code is given by
f ( x ) = ∏ j ∈ Q ( x − ζ j ) , {\displaystyle f(x)=\prod _{j\in Q}(x-\zeta ^{j}),}
where Q {\displaystyle Q} is the set of quadratic residues of
p {\displaystyle p} in the set { 1 , 2 , … , p − 1 } {\displaystyle \{1,2,\ldots ,p-1\}} and
ζ {\displaystyle \zeta } is a primitive p {\displaystyle p} th root of unity in some finite extension field of G F ( l ) {\displaystyle GF(l)} . The condition that l {\displaystyle l} is a quadratic residue of p {\displaystyle p} ensures that the coefficients of f {\displaystyle f}
lie in G F ( l ) {\displaystyle GF(l)} . The dimension of the code is
( p + 1 ) / 2 {\displaystyle (p+1)/2} . Replacing ζ {\displaystyle \zeta } by another primitive p {\displaystyle p} -th root of unity ζ r {\displaystyle \zeta ^{r}} either results in the same code or an equivalent code, according to whether or not r {\displaystyle r}
is a quadratic residue of p {\displaystyle p} . An alternative construction avoids roots of unity. Define
g ( x ) = c + ∑ j ∈ Q x j {\displaystyle g(x)=c+\sum _{j\in Q}x^{j}}
for a suitable c ∈ G F ( l ) {\displaystyle c\in GF(l)} . When l = 2 {\displaystyle l=2}
choose c {\displaystyle c} to ensure that g ( 1 ) = 1 {\displaystyle g(1)=1} . If l {\displaystyle l} is odd, choose c = ( 1 + p ∗ ) / 2 {\displaystyle c=(1+{\sqrt {p^{*}}})/2} , where p ∗ = p {\displaystyle p^{*}=p} or − p {\displaystyle -p} according to whether
p {\displaystyle p} is congruent to 1 {\displaystyle 1} or 3 {\displaystyle 3}
modulo 4 {\displaystyle 4} . Then g ( x ) {\displaystyle g(x)} also generates a quadratic residue code; more precisely the ideal of
F l [ X ] / ⟨ X p − 1 ⟩ {\displaystyle F_{l}[X]/\langle X^{p}-1\rangle } generated by g ( x ) {\displaystyle g(x)}
corresponds to the quadratic residue code.
Weight The minimum weight of a quadratic residue code of length p {\displaystyle p}
is greater than p {\displaystyle {\sqrt {p}}} ; this is the square root bound.
Extended code Adding an overall parity-check digit to a quadratic residue code gives an extended quadratic residue code. When
… excerpt ends here. Continue reading the full article.
