Welcome to the Binary Kingdom.

Binary code Encodes \(K\) states (codewords) in \(n\) binary coordinates and has distance \(d\). Usually denoted as \((n,K,d)\). The distance is the minimum Hamming distance between a pair of distinct codewords. Protection: A binary code \(C\) corrects \(t\) errors in the Hamming distance if \begin{align} \forall x \in C~,~D(x,x+y) < D(x' , x+y) \end{align} for all codewords \(x' \neq x\) and all \(y\) such that \(|y|=t\), where \(D\) is the Hamming distance and \(|y| = D(y,0) \). A code corrects \(t\) errors if and only if \(d \geq 2t+1\), i.e., a code corrects errors on \(t \leq \left\lfloor (d-1)/2 \right\rfloor\) coordinates. In addition, a code detects errors on up to \(d-1\) coordinates, and corrects erasure errors on up to \(d-1\) coordinates. Parents: Error-correcting code (ECC). Parent of: Anticode, Batch code, Binary Varshamov-Tenengolts (VT) code, Convolutional code, Levenshtein code, Linear binary code. Cousin of: Fock-state bosonic code, Group-based code, Movassagh-Ouyang Hamiltonian code.
Anticode[1][2] Code for which the distance between any two codewords is less than or equal to some value \(\delta\) called the maximum distance. Anticodes can be used to construct codes that saturate the Griesmer bound; see Refs. [3][4][5] for more details. Parents: Binary code. Cousins: Griesmer code. Cousin of: Projective geometry code.
Batch code[6] Binary code designed for minimizing the total amount of storage and the worst-case maximal load on any devices in a distributed system. Parents: Binary code, Locally recoverable code (LRC).
Binary Varshamov-Tenengolts (VT) code[7][8] Nearly optimal binary deletion-correcting code. Given integers \(n\geq 1\) and \(a\in\{0,1,\dots,n\}\), the associated binary Varshamov-Tenengolts code \(C_{n,a}\) corresponds to the set Protection: Corrects a single asymmetric error (a \(0\) mapped to a \(1\)), a single deletion, or a single insertion of an arbitrary bit in an arbitrary position for any choice of \(a\). Parents: Binary code. Cousins: Linear binary code.
Convolutional code[9] Classical codes that are formed using generator polynomials over the finite field with two elements. The encoder slides across contiguous subsets of the input bit-string (like a convolutional neural network) evaluating the polynomials on that window to obtain a number of parity bits. These parity bits are the encoded information. There are many ways to formulate these codes Parents: Binary code. Cousins: Quantum convolutional code, Reed-Solomon (RS) code.
Levenshtein code[10] Binary codes constructed from combining two codes \(A'\) constructed out of Hadamard matrices. Protection: Levenshtein codes meet the Plotkin bound \(K\leq 2\left\lfloor\frac{d}{2d-n}\right\rfloor\), where \(K\) is the number of codewords, \(d\) is the distance, and \(n\) is the length, and with the assumption that the Hadamard matrices for such parameters exist. The general proof depends on the correctness of Hadamard's conjecture [5]. Parents: Binary code.
Linear binary code An \((n,2^k,d)\) linear code is denoted as \([n,k]\) or \([n,k,d]\), where \(d\) is the code's distance. Its codewords form a linear subspace, i.e., for any codewords \(x,y\), \(x+y\) is also a codeword. A code that is not linear is called nonlinear. Protection: Distance \(d\) of a linear code is the number of nonzero entries in the (nonzero) codeword with the smallest such number. Corrects any error set for which no two elements of the set add up to a codeword. Parents: Binary code, Linear code. Parent of: Cyclic linear binary code, Fibonacci code, Fountain code, Graph homology code, Hadamard code, Justesen code, Polar code, Reed-Muller (RM) code, Tanner code, Tornado code, Weight-two code. Cousin of: Binary Varshamov-Tenengolts (VT) code, Calderbank-Shor-Steane (CSS) stabilizer code, Entanglement-assisted (EA) QECC, Entanglement-assisted (EA) stabilizer code, Parity-check code, Qubit stabilizer code.
Justesen code[11] Binary linear code resulting from generalized concatenation of a Reed-Solomon (RS) outer code with multiple inner codes sampled from the Wozencraft ensemble, i.e., \(N\) distinct binary inner codes of dimension \(m\) and length \(2m\). Justesen codes are parameterized by \(m\), with length \(n=2mN\) and dimension \(k=mK\), where \((N=2^m-1,K)\) is the RS outer code over \(GF(2^m)\). Parents: Linear binary code, Generalized concatenated code. Cousins: Reed-Solomon (RS) code, Wozencraft ensemble code, Random code.
Polar code[12] In its basic version, a binary linear polar code encodes \(K\) message bits into \(N=2^n\) bits. The linear transformation that defines the code is given by the matrix \(G^{(n)}=B_N G^{\otimes n}\), where \(B_N\) is a certain \(N\times N\) permutation matrix, and \(G^{\otimes n}\) is the \(n\)th Kronecker power of the \(2\times 2\) kernel matrix \(G=\left[\begin{smallmatrix}1 & 0\\ 1 & 1 \end{smallmatrix}\right]\). To encode \(K\) message bits, one forms an \(N\)-vector \(u\) in which \(K\) coordinates represent the message bits. The remaining \(N-K\) coordinates are set to some fixed values and are said to be frozen. The codeword \(x \in \{0,1\}^N\) is obtained as \(x=u G^{\otimes n}\). Protection: Protects against various types of noise in the communication channel, for instance, errors, erasures, or other types of noise. Distance plays no role in the analysis of its properties, and is much lower than the largest possible value given \(K,N\). Parents: Linear binary code, Generalized concatenated code. Cousins: Reed-Muller (RM) code. Cousin of: Quantum polar code.
Tanner code[13] Binary linear code defined on edges on a regular graph \(G\) such that each subsequence of bits corresponding to edges in the neighborhood any vertex belong to some short binary linear code \(C_0\). Expansion properties of the underlying graph can yield efficient decoding algorithms. Protection: Tanner Codes protect against noise on classical bit strings. If \(C_0\) is an \([d, d-t,d'> d(\gamma_0 +\frac{\lambda}{d})]_2\) code and G is an \((N, M, 2, d, \rho,\alpha)\)- expander where \(\rho = \gamma_0 (\gamma_0 +\frac{\lambda}{d})\), then the Tanner Code \(T(G, C_0)\) has rate \(1-\frac{M}{N}t\) and relative distance \(\geq \gamma_0(\gamma_0+\frac{\lambda}{d})\). Parents: Linear binary code, Parallel concatenated code. Parent of: Expander code. Cousin of: Dinur-Hsieh-Lin-Vidick (DHLV) code, Expander lifted-product code, Quantum Tanner code.
Cyclic linear binary code A binary code of length \(n\) is cyclic if, for each codeword \(c_1 c_2 \cdots c_n\), the cyclically shifted string \(c_n c_1 \cdots c_{n-1}\) is also a codeword. A cyclic code is called primitive when \(n=2^r-1\) for some \(r\geq 2\). A shortened cyclic code is obtained from a cyclic code by taking only codewords with the first \(j\) zero entries, and deleting those zeroes. Protection: Shift bound [14] gives a lower bound on the distance of cyclic binary codes. Parents: Cyclic code, Linear binary code, Group code. Parent of: Binary BCH code, Binary duadic code, One-hot code, Parity-check code, Repetition code, Zetterberg code. Cousin of: Majorana stabilizer code, Reed-Muller (RM) code.
Fibonacci code[15] The code is defined on an \(L\times L/2\) lattice with one bit on each site, where \(L=2^N\) for an integer \(N\geq 2\). The codewords are defined to satisfy the condition that, for each lattice site \((x,y)\), the bits on \((x,y)\), \((x+1,y)\), \((x-1,y)\) and \((x,y+1)\) (where the lattice is taken to be periodic in both directions) contain an even numbers of \(1\)'s. The codewords can be generated using a one-dimensional cellular automaton of length \(L\) (periodic). The \(2^L\) possible initial states correspond to the \(2^L\) codewords. For each generation, the state of each cell is the xor sum of that cell and its two neighbors in the previous generation. After \(L/2-1\) generations, the entire history generated by the automaton corresponds to a codeword, where the initial state is the first row of the lattice, the first generation is the second row, etc. Protection: Protects against small weight errors and string-like errors. The code distance is more than \(L\), but the exact value is unknown. Parents: Linear binary code. Cousins: Haah cubic code.
Fountain code[16] Code based on the idea of generating an endless stream of custom encoded packets for the receiver. The code is designed so that the receiver can recover the original transmission of size \(Kl\) bits after receiving at least \(K\) packets each of \(l\) bits. Protection: Designed to protect against erasures during broadcasting of information by a sender to multiple receivers. Parents: Linear binary code, Low-density generator-matrix (LDGM) code. Parent of: Raptor (RAPid TORnado) code. Cousins: Random code, Distributed-storage code. Cousin of: Tornado code.
Graph homology code[17] This code's properties are derived from the size two chain complex associated with a particular graph. Given a connected simplicial (no self loops or muliedges) graph \(G = (V, E)\), which is not a tree, with incidence matrix \(\Gamma\) we can construct a code by choosing a parity check matrix which consists of all the linearly independent rows of \(\Gamma\). This is a \([n,k,d]\) code with \(n = |E|\), \(k = 1 - \mathcal{X}(G) = 1-|V|+|E|\), where \( \mathcal{X}(G)\) is the euler characteristic of the graph. The code distance is equal to the shortest size of a cycle, guaranteed to exist since \(G\) is not a tree. Parents: Linear binary code. Cousins: Perfect code, Calderbank-Shor-Steane (CSS) stabilizer code.
Hadamard code An \([2^k,k,2^{k-1}]\) balanced binary code dual to an extended Hamming Code. Parents: Linear binary code, Balanced code. Cousins: Dual linear code, Hamming code, Reed-Muller (RM) code.
Reed-Muller (RM) code[18][19][20] 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\). 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 code. Parent of: Hamming code. Cousins: Binary BCH code, Dual linear code, Binary duadic code, Cyclic linear binary code, Parity-check code. Cousin of: Generalized RM (GRM) code, Hadamard code, Majorana stabilizer code, Polar code, Quantum Reed-Muller code, Quantum divisible code, Simplex code.
Weight-two code[23] A length-\(n\) binary code whose codewords all have Hamming weight two. Such codes provide slightly extra redundancy for storage of small-scale information such as ZIP codes or decimal digits. Parents: Constant-weight code, Linear binary code.
Parity-check 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, 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: Reed-Muller (RM) code.
Zetterberg code[24] Family of binary cyclic \([2^{2s}+1,2^{2s}-4s+1]\) codes with distance \(d>5\) generated by the minimal polynomial \(g_s(x)\) of \(\alpha\) over \(GF(2)\), where \(\alpha\) is a primitive \(n\)th root of unity in the field \(GF(2^{4s})\). They are quasi-perfect codes and are one of the best known families of double-error correcting binary linear codes Protection: Correct at least all weight-2 errors. Parents: Cyclic linear binary code, Quasi-perfect code.
Expander code[25] Expander codes are binary linear codes whose parity check matrices are derived from the adjacency matrix of bipartite expander graphs. In particular, the rows of the parity check matrix correspond to the right nodes of the bipartite graph and the columns correspond to the left nodes. The codespace is equivalent to all subsets of the left nodes in the graph that have an even number of edges going into every right node of the graph. Since the expander graph is only left regular, these codes do not qualify as LDPC codes. Protection: Bit flip errors of weight at most \((d-1)/2\) where \(d\) is the distance of the code and is linear in \(n\), the number of physical bits. Parents: Tanner code. Cousin of: Quantum expander code.
Binary BCH code[26][27][28] Cyclic binary code of odd length \(n\) whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\) (see Cyclic-to-polynomial correspondence). More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=2^r-1\) for some \(r\geq 2\). Protection: By the BCH bound, BCH code with designed distance \(\delta\) has true distance \(d\geq\delta\). BCH codes with different designed distances may coincide, and the largest possible designed distance for a given code is the Bose distance; the true distance may still be larger than that. Parents: Cyclic linear binary code. Parent of: Golay code, Hamming code. Cousins: Quasi-perfect code, Bose–Chaudhuri–Hocquenghem (BCH) code, Generalized RS (GRS) code, Griesmer code. Cousin of: Qubit BCH code, Reed-Muller (RM) code, \(q\)-ary Hamming code.
Binary duadic code[29] Member of a pair of cyclic linear binary codes that satisfy certain relations, depending on whether the pair is even-like or odd-like duadic. Duadic codes exist for lengths \(n\) that are products of powers of primes, with each prime being \(\pm 1\) modulo \(8\) [30]. Protection: Since duadic codes are cyclic, the BCH bound can be used to determine their minimum distance. Parents: Cyclic linear binary code. Parent of: Binary quadratic-residue (QR) code. Cousins: \(q\)-ary duadic code. Cousin of: Reed-Muller (RM) code.
One-hot code Also known as an \(1\)-in-\(n\) code. A length-\(n\) binary code whose codewords are those with Hamming weight one. The reverse of this code, where all codewords have Hamming weight \(n-1\) is called a one-cold code. Parents: Constant-weight code, Cyclic linear binary 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. Cousins: Perfect code, Quantum repetition code, Hamming code. Cousin of: Parity-check code, Simplex code.
Golay code[31] A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [32] and sporadic simple groups [5]. Adding a parity bit to the code results in the \([24, 12, 8]\) extended Golay code. Up to equivalence, both codes are unique for their respective parameters. Parents: Perfect code, Binary quadratic-residue (QR) code, Binary BCH code. Cousins: Nearly perfect code, Dual linear code. Cousin of: Hexacode, Ternary Golay Code.
Hamming code[33][34][31] 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, Steane \([[7,1,3]]\) code, \([[2^r-1, 2^r-2r-1, 3]]\) Hamming-based CSS code.
Tetracode[32] 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 [32]. Parents: Simplex code, Hamming code, Maximum distance separable (MDS) code. Cousins: Dual linear code, Ternary Golay Code.
Raptor (RAPid TORnado) code[35][36] Raptor codes are concatenated erasure codes with two layers: an outer pre-code and a Luby-Transform (LT) inner code. The pre-code is a linear binary erasure code, which is applied first to the input to create some redundant data. The LT code is then applied to the intermediate symbols from the pre-code to generate final output symbols to be transmitted. Protection: As a type of fountain code, a Raptor code is designed to correct erasures. The error probability of Raptor codes is measured in terms of its overhead, which is how many additional symbols are received above the dimension of the input \(k\). This relationship can vary widely depending on the input pre-code and degree distribution. For a well-designed degree distribution, the error probability of a Raptor code is directly related to the error probability of the pre-code's decoder. In other words, if there is a linear time decoder for the pre-code that has subexponentially small error probability, then the Raptor code's error probability will decrease exponentially with increasing overhead (past the \(n-k\) overhead symbols necessary for the pre-code). Parents: Fountain code. Parent of: Luby transform (LT) code. Cousins: Tornado code.
Binary quadratic-residue (QR) code Member of a quadruple of cyclic binary codes of prime length \(n=8m\pm 1\) for \(m\geq 1\) constructed using quadratic residues and nonresidues of \(n\). Parents: Binary duadic code. Parent of: Golay code. Cousins: \(q\)-ary quadratic-residue (QR) code. Cousin of: Hamming code.
Luby transform (LT) code[37] Erasure codes based on fountain codes. They improve on random linear fountain codes by having a much more efficient encoding and decoding algorithm. Parents: Raptor (RAPid TORnado) code.

References

[1]
P. G. Farrell, “Linear binary anticodes”, Electronics Letters 6, 419 (1970). DOI
[2]
P. G. Farrell and A. Farrag, “Further properties of linear binary anticodes”, Electronics Letters 10, 340 (1974). DOI
[3]
J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016). DOI
[4]
I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000). DOI
[5]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[6]
Y. Ishai et al., “Batch codes and their applications”, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04 (2004). DOI
[7]
R. R. Varshamov and G. M. Tenengolts, Codes which correct single asymmetric errors (translated to English), Autom. Remote Control, 26(2), 286-290 (1965)
[8]
V. I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals (translated to English), Soviet Physics Dokl., 10(8), 707-710 (1966).
[9]
Peter Elias. Coding for noisy channels. IRE Convention Records, 3(4):37–46, 1955.
[10]
V.I. Levenshtein, Application of Hadamard matrices to a problem in coding theory, Problems of Cybernetics, vol. 5, GIFML, Moscow, 1961, 125–136.
[11]
J. Justesen, “Class of constructive asymptotically good algebraic codes”, IEEE Transactions on Information Theory 18, 652 (1972). DOI
[12]
E. Arikan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels”, IEEE Transactions on Information Theory 55, 3051 (2009). DOI
[13]
R. Tanner, “A recursive approach to low complexity codes”, IEEE Transactions on Information Theory 27, 533 (1981). DOI
[14]
J. van Lint and R. Wilson, “On the minimum distance of cyclic codes”, IEEE Transactions on Information Theory 32, 23 (1986). DOI
[15]
G. M. Nixon and B. J. Brown, “Correcting Spanning Errors With a Fractal Code”, IEEE Transactions on Information Theory 67, 4504 (2021). DOI; 2002.11738
[16]
J. W. Byers et al., “A digital fountain approach to reliable distribution of bulk data”, ACM SIGCOMM Computer Communication Review 28, 56 (1998). DOI
[17]
H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, 052105 (2007). DOI; quant-ph/0605094
[18]
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
[19]
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
[20]
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.
[21]
M. G. Luby et al., “Practical loss-resilient codes”, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 (1997). DOI
[22]
M. G. Luby et al., “Efficient erasure correcting codes”, IEEE Transactions on Information Theory 47, 569 (2001). DOI
[23]
R. W. Hamming, Letter, April 5, 1978.
[24]
L.-H. Zetterberg, “Cyclic codes from irreducible polynomials for correction of multiple errors”, IEEE Transactions on Information Theory 8, 13 (1962). DOI
[25]
M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996). DOI
[26]
R. C. Bose and D. K. Ray-Chaudhuri, “On a class of error correcting binary group codes”, Information and Control 3, 68 (1960). DOI
[27]
R. C. Bose and D. K. Ray-Chaudhuri, “Further results on error correcting binary group codes”, Information and Control 3, 279 (1960). DOI
[28]
A. Hocquenghem, Codes correcteurs d'Erreurs, Chiffres (Paris), vol.2, pp.147-156, 1959.
[29]
J. Leon, J. Masley, and V. Pless, “Duadic Codes”, IEEE Transactions on Information Theory 30, 709 (1984). DOI
[30]
V. Pless, “Duadic Codes and Generalizations”, Eurocode ’92 3 (1993). DOI
[31]
M. J. E. Golay, Notes on digital coding, Proc. IEEE, 37 (1949) 657.
[32]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999). DOI
[33]
C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948). DOI
[34]
R. W. Hamming, “Error Detecting and Error Correcting Codes”, Bell System Technical Journal 29, 147 (1950). DOI
[35]
A. Shokrollahi, “Raptor codes”, IEEE Transactions on Information Theory 52, 2551 (2006). DOI
[36]
Petar Maymounkov, Online codes, Technical report, New York University, 2002.
[37]
M. Luby, “LT codes”, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.. DOI