Welcome to the Ring Kingdom.
Ring code
Encodes \(K\) states (codewords) in \(n\) coordinates over a ring \(R\).
Parents:
Finite-dimensional error-correcting code (ECC).
Parent of:
\(R\)-linear code.
Cousin of:
Group-based code.
\(R\)-linear code
A code of length \(n\) over a ring \(R\) is \(R\)-linear if it is a submodule of \(R^n\).
Parents:
Ring code, Linear code.
Parent of:
\(q\)-ary code over \(\mathbb{Z}_q\).
Cousin of:
Linear code over \(G\).
\(q\)-ary code over \(\mathbb{Z}_q\)
A linear code encoding \(K\) states (codewords) in \(n\) coordinates over the ring \(\mathbb{Z}_q\) of integers modulo \(q\).
Parents:
\(R\)-linear code.
Parent of:
Quaternary code over \(\mathbb{Z}_4\).
Cousin of:
Polyphase code.
Reed-Muller (RM) code[1][2][3]
Member of the RM\((r,m)\) family of linear binary codes derived from multivariate polynomials. The code parameters are \([2^m,\sum_{j=0}^{r} {m \choose j},2^{m-r}]\), where \(r\) is the order of the code satisfying \(0\leq r\leq m\). First-order RM codes are also called biorthogonal codes, while \(m\)th order RM codes are also called universe codes. Punctured RM codes RM\(^*(r,m)\) are obtained from RM codes by deleting one or more coordinates from each codeword.
Parents:
Polynomial evaluation code, Linear binary code, Quaternary code over \(\mathbb{Z}_4\), Divisible code, Group-algebra code.
Parent of:
Hamming code, Repetition code, Single parity-check (SPC) code.
Cousins:
Binary BCH code, Dual linear code, Binary duadic code, Cyclic linear binary code, Binary linear LTC.
Cousin of:
Barnes-Wall (BW) lattice code, Biorthogonal spherical code, Generalized RM (GRM) code, Hadamard code, Majorana stabilizer code, Polar code, Quantum Reed-Muller code, Quantum divisible code, Simplex code.
Repetition code
\([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. The idea is to increase the code distance by repeating the logical information several times. It is a \((n,1)\)-Hamming code.
Protection: Detects errors on up to \(\frac{n-1}{2}\) coordinates, corrects erasure errors on up to \(\frac{n-1}{2}\) coordinates. The generator matrix is \(G=\left[\begin{smallmatrix}1 & 1&\cdots& 1 & 1 \end{smallmatrix}\right]\).
Parents:
Cyclic linear binary code, Nearly perfect code, Reed-Muller (RM) code.
Cousins:
Perfect code, Quantum repetition code, Hamming code.
Cousin of:
Self-correcting quantum code, Simplex code, Single parity-check (SPC) code, \(D_4\) lattice code.
Single parity-check (SPC) code
Also known as a sum-zero or even-weight code. An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check bit such that the parity (i.e., sum over all coordinates of each codeword) is zero. If the Hamming weight of a message is odd (even), then the parity bit is one (zero). This code requires only one extra bit of overhead and is therefore inexpensive.
Protection: This code cannot protect information, it can only detect 1-bit error.
Parents:
Cyclic linear binary code, Reed-Muller (RM) code, Nearly perfect code, Maximum distance separable (MDS) code, Divisible code.
Cousins:
Repetition code, \(q\)-ary parity-check code, Linear binary code, Low-density generator-matrix (LDGM) code.
Cousin of:
CSS classical product code, \(D_4\) lattice code.
Quaternary code over \(\mathbb{Z}_4\)
A linear code encoding \(K\) states (codewords) in \(n\) coordinates over the ring \(\mathbb{Z}_4\) of integers modulo 4.
Parents:
\(q\)-ary code over \(\mathbb{Z}_q\).
Parent of:
Octacode, Reed-Muller (RM) code.
Cousin of:
Niemeier lattice code.
Hamming code[4][5][6]
An infinite family of perfect linear codes with parameters \((2^r-1,2^r-r-1, 3)\) for \(r \geq 2\). Their \(r \times (2^r-1) \) parity check matrix \(H\) has all possible non-zero \(r\)-bit strings as its columns.
Protection: Can detect 1-bit and 2-bit errors, and can correct 1-bit errors.
Parents:
Perfect code, Reed-Muller (RM) code, Binary BCH code.
Parent of:
Tetracode.
Cousins:
Projective geometry code, Binary quadratic-residue (QR) code, \([[2^r, 2^r-r-2, 3]]\) quantum Hamming code, \(q\)-ary Hamming code, Nearly perfect code.
Cousin of:
Hadamard code, Octacode, Repetition code, \(E_8\) Gosset lattice code, \([[2^r, 2^r-r-2, 3]]\) quantum Hamming code, \([[2^r-1, 2^r-2r-1, 3]]\) Hamming-based CSS code, \([[7,1,3]]\) Steane code.
Tetracode[7]
The \([4,2,3]_{GF(3)}\) self-dual MDS code with generator matrix \begin{align}
\begin{pmatrix}1 & 0 & 1 & 1\\
0 & 1 & 1 & 2
\end{pmatrix}~,
\end{align} where \(GF(3) = \{0,1,2\}\). Has connections to lattices [7].
Parents:
Simplex code, Hamming code, Maximum distance separable (MDS) code.
Cousins:
Dual linear code, Ternary Golay Code.
Octacode[8][7][9]
The unique self-dual linear code of length 8 over \(\mathbb{Z}_4\) with generator matrix \begin{align}
\begin{pmatrix}
3 & 3 & 2 & 3 & 1 & 0 & 0 & 0\\
3 & 0 & 3 & 2 & 3 & 1 & 0 & 0\\
3 & 0 & 0 & 3 & 2 & 3 & 1 & 0\\
3 & 0 & 0 & 0 & 3 & 2 & 3 & 1
\end{pmatrix}\,.
\end{align}
Parents:
Quaternary code over \(\mathbb{Z}_4\).
Cousins:
Cyclic code, Hamming code, Dual additive code.
Cousin of:
Niemeier lattice code, \(E_8\) Gosset lattice code.
References
- [1]
- D. E. Muller, “Application of Boolean algebra to switching circuit design and to error detection”, Transactions of the I.R.E. Professional Group on Electronic Computers EC-3, 6 (1954). DOI
- [2]
- I. Reed, “A class of multiple-error-correcting codes and the decoding scheme”, Transactions of the IRE Professional Group on Information Theory 4, 38 (1954). DOI
- [3]
- N. Mitani, On the transmission of numbers in a sequential computer, delivered at the National Convention of the Inst. of Elect. Engineers of Japan, November 1951.
- [4]
- C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948). DOI
- [5]
- R. W. Hamming, “Error Detecting and Error Correcting Codes”, Bell System Technical Journal 29, 147 (1950). DOI
- [6]
- M. J. E. Golay, Notes on digital coding, Proc. IEEE, 37 (1949) 657.
- [7]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999). DOI
- [8]
- J. H. Conway and N. J. A. Sloane, “Self-dual codes over the integers modulo 4”, Journal of Combinatorial Theory, Series A 62, 30 (1993). DOI
- [9]
- E. M. Rains and N. J. A. Sloane, “Self-Dual Codes”. math/0208001