Quadratic residue codes

Let $m>2$ be a prime number. The integers $1\leq a\leq m-1$ for which $a\equiv x^2\, ({\rm mod}\, m)$ for some $x\in \mathbb{Z}$, are called quadratic residues mod $m$ . The remaining elements of $\{1,2,...,m-1\}$ are called quadratic non-residues mod $m$.

Let $n$ be a positive integer relatively prime to $q$ and let $\alpha$ be a primitive n-th root of unity. Let $p$ and $n$ be distinct primes and assume that $p$ is a quadratic residue mod $n$. The quadratic residue code of length $n$ over $\mathbb{F}_p$ is the cyclic code whose generator polynomial has zeros

$$\{\alpha^k\ \vert\ k\ {\rm is\ a\ square\ mod}\ n\}.$$

Example 3.10.10   The binary Golay code $GC_{23}$ is the quadratic residue code of length 23 over $\mathbb{F}_2$. It is a $[23,12,7]$-code. A generating matrix for $GC_{23}$ is

$$\left( \begin {array}{ccccccccccccccccccccccc} 1&0&0&0&0&0&... ...&0&0&0&0&0&0&0&0&1&1&0&1&1&0&1&1&1&0&0&0 \end {array} \right).$$

The binary Golay code $GC_{24}$ is the code of length 24 over $\mathbb{F}_2$ obtained by appending onto $GC_{23}$ a zero-sum check digit. It is a $[24,12,8]$-code. Moreover, it is self-dual in the sense that $GC_{24}^\perp = GC_{24}$. A generating matrix for $GC_{24}$ is

$$\left(\begin {array}{cccccccccccccccccccccccc} 1&0&0&0&0&0&0&0&0... ...medskip }0&0&0&0&0&0&0&0&0&0&0&1&1&0&1&1&0&1&1&1&0&0&0&1 \end {array} \right).$$

Example 3.10.11   The ternary Golay code $GC_{11}$ is the quadratic residue code of length 11 over $\mathbb{F}_3$. It is a $[11,6,5]$-code. A generating matrix for $GC_{11}$ is

$$\left( \begin {array}{ccccccccccc} 1&0&0&0&0&0&1&1&1&1&1 \\... ...noalign{\medskip }0&0&0&0&0 &1&1&2&2&1&0 \end {array} \right).$$

The ternary Golay code $GC_{12}$ is the code of length 12 over $\mathbb{F}_3$ obtained by appending onto $GC_{11}$ a zero-sum check digit. It is a $[12,6,6]$-code. Moreover, it is self-dual in the sense that $GC_{12}^\perp = GC_{12}$. A generating matrix for $GC_{12}$ is

$$\left( \begin {array}{cccccccccccc} 1&0&0&0&0&0&0&1&1&1&1&1... ...align{\medskip }0&0&0&0 &0&1&1&1&2&2&1&0 \end {array} \right).$$

Exercise 3.10.12   Find all quadratic residues mod $m$, where

(a) $m=11$,

(b) $m=13$,

(c) $m=23$.

Exercise 3.10.13   Show that if $a,b$ are quadratic residues mod $m$ then so is $ab$.

Exercise 3.10.14   Verify the generator matrix in Example 3.10.5 above is correct.

Exercise 3.10.15   Show that the minimum distance of $C$ in Example 3.10.7 is $3$.

Exercise 3.10.16 (a)   Show that the code in Example 3.10.5 is equivalent to the Hamming $[7,4,3]$-code in §3.4.2.

(b) Find the analog of the decoding diagram in Figure 3.4.2. Fill in the following blanks: