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:
Finite-dimensional error-correcting code (ECC).
Parent of:
Anticode, Batch code, Best code, Binary Varshamov-Tenengolts (VT) code, Convolutional code, Gray code, Levenshtein code, Linear binary code.
Cousin of:
Binary antipodal code, Fock-state bosonic code, Group-based code, Movassagh-Ouyang Hamiltonian code.

Justesen code[1]
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.

Tanner code[2]
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.

Anticode[3][4]
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. [5][6][7] for more details.
Parents:
Binary code.
Cousins:
Griesmer code.
Cousin of:
Antipode lattice code, Projective geometry code.

Batch code[8]
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).

Best code[9]
Binary nonlinear \((10,40,4)\) code that is unique [10]. Codewords can be obtained by applying the Gray map to a set of vectors over \(\mathbb{Z}_4\) [11].
Parents:
Binary code.
Cousins:
Lattice-based code.

Binary Varshamov-Tenengolts (VT) code[12][13]
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[14]
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.

Gray code[15][16][17]
The first Gray code [15], now called the binary reflected Gray code, is a trivial code that orders length-\(n\) binary strings such that nearest-neighbor strings differ by only one digit.
Parents:
Binary code.
Cousin of:
Phase-shift keyring (PSK) code, Quadrature-amplitude modulation (QAM) code, Rank-modulation Gray code (RMGC).

Levenshtein code[18]
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 [7].
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:
Binary linear LTC, Cyclic linear binary code, Fibonacci code, Fountain code, Graph homology code, Justesen code, Reed-Muller (RM) code, Ta-Shma zigzag code, Tanner code, Tornado code, Weight-two code.
Cousins:
Binary linear LTC.
Cousin of:
Binary PSK (BPSK) code, Binary Varshamov-Tenengolts (VT) code, Calderbank-Shor-Steane (CSS) stabilizer code, Entanglement-assisted (EA) QECC, Entanglement-assisted (EA) stabilizer code, Linear code over \(G\), Mod-2 lattice code, Qubit stabilizer code, Single parity-check (SPC) code, Slepian group-orbit code.

Binary linear LTC
A binary linear code \(C\) of length \(n\) that is a \((u,R)\)-LTC with query complexity \(u\) and soundness \(R>0\). More technically, the code is a \((u,R)\)-LTC if the rows of its parity-check matrix \(H\in GF(2)^{r\times n}\) have weight at most \(u\) and if \begin{align}
\frac{1}{r}|H x| \geq \frac{R}{n} D(x,C)
\end{align} holds for any bitstring \(x\), where \(D(x,C)\) is the Hamming distance between \(x\) and the closest codeword to \(x\) [19; Def. 11].
Parents:
Linear binary code, Locally testable code (LTC).
Parent of:
Ben-Sasson-Goldreich-Harsha-Sudan-Vadhan (BGHSV) code, Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code, Dinur code, Goldreich-Sudan code, Hadamard code, Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code, Left-right Cayley complex code, Long code.
Cousin of:
Cyclic linear binary code, Linear binary code, Reed-Muller (RM) 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 [20] gives a lower bound on the distance of cyclic binary codes.
Parents:
Cyclic code, Linear binary code, Group-algebra code.
Parent of:
Binary BCH code, Binary duadic code, One-hot code, Repetition code, Single parity-check (SPC) code, Zetterberg code.
Cousins:
Binary linear LTC.
Cousin of:
Majorana stabilizer code, Reed-Muller (RM) code.

Expander code[21]
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:
Left-right Cayley complex code, Quantum expander code.

Fibonacci code[22]
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[23]
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[24]
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.

Reed-Muller (RM) code[25][26][27]
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.

Ta-Shma zigzag code[28]
Member of a family of \(\epsilon\)-balanced codes that nearly achieves the asymptotic Gilbert-Varshamov bound. The codes have relative distance \(\frac{1}{2}-\frac{\epsilon}{2}\) and rate of order \(\Omega (\epsilon^{2+\beta})\) for \(\beta\to 0\) as \(n\to\infty\) [29].
Parents:
Linear binary code.
Cousins:
Balanced code.

Tornado code[23][30][31]
Stub.
Parents:
Linear binary code, Low-density parity-check (LDPC) code.
Cousins:
Fountain code, Low-density parity-check (LDPC) code.
Cousin of:
Raptor (RAPid TORnado) code.

Weight-two code[32]
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.

Ben-Sasson-Goldreich-Harsha-Sudan-Vadhan (BGHSV) code[33]
Locally testable \([[n,k,d]]\) code with \(n = k^{1+\epsilon}\) and query complexity of order \(O(1/\epsilon)\) for any \(\epsilon > 0\).
Parents:
Binary linear LTC.

Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code[34]
Locally testable \([[n,k,d]]\) code with \(n = k \cdot 2^{\tilde{O}(\sqrt{\log k})}\) and asymptotically constant query complexity.
Parents:
Binary linear LTC.

Dinur code[35]
Member of infinite family of locally testable \([[n,n/\text{polylog}(n),d]]\) codes with vanishing rate. Code construction relies on a construction utilizing tensor-product codes [36].
Parents:
Binary linear LTC.

Goldreich-Sudan code[37]
Locally testable \([[n,k,d]]\) code with \(n = k^{1+O(1/u)}\) and distance \(\Omega(n)\) for query complexity \(u\). The same work also presented a probabilistic construction of codes of size \(k^{1+o(1)}\).
Parents:
Binary linear LTC.
Cousins:
Random code.

Hadamard code
Also known as a Walsh code or Walsh-Hadamard code. An \([2^k,k,2^{k-1}]\) balanced binary code dual to an extended Hamming Code.
Parents:
Binary linear LTC, Long code, Balanced code.
Cousins:
Dual linear code, Hamming code, Reed-Muller (RM) code.
Cousin of:
Simplex code.

Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code[38][39]
Member of a family of locally testable binary linear codes with constant rate, constant relative distance, and subpolynomial query complexity \(u = (\log n)^{O(\log \log n)}\)). Later work by Gopi, Kopparty, Oliveira, Ron-Zewi, and Saraf [39] showed that related concatenated codes achieve the Gilbert-Varshamov bound.
Parents:
Binary linear LTC.

Left-right Cayley complex code[40]
Binary code constructed on a left-right Cayley complex using a pair of base codes \(C_A,C_B\) and an expander graph such that codewords for a fixed graph vertex are codewords of the tensor code \(C_A \otimes C_B\). A family of such codes is one of the first \(c^3\)-LTCs.
Parents:
Binary linear LTC.
Cousins:
Tensor-product code, Expander code, Balanced product code, Quantum Tanner code.

Long code[41][42]
Locally testable \([[2^{2^k},k,d]]\) code. The encoder maps a \(k\)-bit string into a codeword that consists of the values of all Boolean functions on the \(k\)-bit string. The code is not practical, but is useful for certain probabilistically checkable proof (PCP) constructions [43].
Parents:
Binary linear LTC.
Parent of:
Hadamard code.

Binary BCH code[44][45][46]
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[47]
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\) [48].
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, 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.

Zetterberg code[49]
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.

Golay code[50]
A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [51] and sporadic simple groups [7]. 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, Group-algebra code.
Cousin of:
Hexacode, Ternary Golay Code, \(\Lambda_{24}\) Leech lattice code.

Hamming code[52][53][50]
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[51]
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 [51].
Parents:
Simplex code, Hamming code, Maximum distance separable (MDS) code.
Cousins:
Dual linear code, Ternary Golay 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, Group-algebra code.
Cousin of:
Hamming code.

Raptor (RAPid TORnado) code[54][55]
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.

Luby transform (LT) code[56]
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]
- J. Justesen, “Class of constructive asymptotically good algebraic codes”, IEEE Transactions on Information Theory 18, 652 (1972). DOI
- [2]
- R. Tanner, “A recursive approach to low complexity codes”, IEEE Transactions on Information Theory 27, 533 (1981). DOI
- [3]
- P. G. Farrell, “Linear binary anticodes”, Electronics Letters 6, 419 (1970). DOI
- [4]
- P. G. Farrell and A. Farrag, “Further properties of linear binary anticodes”, Electronics Letters 10, 340 (1974). DOI
- [5]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016). DOI
- [6]
- I. N. Landjev, “Linear codes over finite fields and finite projective geometries”, Discrete Mathematics 213, 211 (2000). DOI
- [7]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [8]
- 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
- [9]
- M. Best, “Binary codes with a minimum distance of four (Corresp.)”, IEEE Transactions on Information Theory 26, 738 (1980). DOI
- [10]
- S. Litsyn and A. Vardy, “The uniqueness of the Best code”, IEEE Transactions on Information Theory 40, 1693 (1994). DOI
- [11]
- J. H. Conway and N. J. A. Sloane, “Quaternary constructions for the binary single-error-correcting codes of Julin, Best and others”, Designs, Codes and Cryptography 4, 31 (1994). DOI
- [12]
- R. R. Varshamov and G. M. Tenengolts, Codes which correct single asymmetric errors (translated to English), Autom. Remote Control, 26(2), 286-290 (1965)
- [13]
- V. I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals (translated to English), Soviet Physics Dokl., 10(8), 707-710 (1966).
- [14]
- Peter Elias. Coding for noisy channels. IRE Convention Records, 3(4):37–46, 1955.
- [15]
- Gray, Frank. "Pulse code communication." United States Patent Number 2632058 (1953).
- [16]
- E. N. Gilbert, “Gray Codes and Paths on the n-Cube”, Bell System Technical Journal 37, 815 (1958). DOI
- [17]
- J. T. Joichi, D. E. White, and S. G. Williamson, “Combinatorial Gray Codes”, SIAM Journal on Computing 9, 130 (1980). DOI
- [18]
- V.I. Levenshtein, Application of Hadamard matrices to a problem in coding theory, Problems of Cybernetics, vol. 5, GIFML, Moscow, 1961, 125–136.
- [19]
- A. Leverrier, V. Londe, and G. Zémor, “Towards local testability for quantum coding”, Quantum 6, 661 (2022). DOI; 1911.03069
- [20]
- J. van Lint and R. Wilson, “On the minimum distance of cyclic codes”, IEEE Transactions on Information Theory 32, 23 (1986). DOI
- [21]
- M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996). DOI
- [22]
- 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
- [23]
- J. W. Byers et al., “A digital fountain approach to reliable distribution of bulk data”, ACM SIGCOMM Computer Communication Review 28, 56 (1998). DOI
- [24]
- 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
- [25]
- 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
- [26]
- 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
- [27]
- 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.
- [28]
- A. Ta-Shma, “Explicit, almost optimal, epsilon-balanced codes”, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (2017). DOI
- [29]
- Fernando Granha Jeronimo et al., “Unique Decoding of Explicit $ε$-balanced Codes Near the Gilbert-Varshamov Bound”. 2011.05500
- [30]
- 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
- [31]
- M. G. Luby et al., “Efficient erasure correcting codes”, IEEE Transactions on Information Theory 47, 569 (2001). DOI
- [32]
- R. W. Hamming, Letter, April 5, 1978.
- [33]
- E. Ben-Sasson et al., “Robust pcps of proximity, shorter pcps and applications to coding”, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04 (2004). DOI
- [34]
- E. Ben-Sasson et al., “Randomness-efficient low degree tests and short PCPs via epsilon-biased sets”, Proceedings of the thirty-fifth ACM symposium on Theory of computing - STOC '03 (2003). DOI
- [35]
- I. Dinur, “The PCP theorem by gap amplification”, Journal of the ACM 54, 12 (2007). DOI
- [36]
- Eli Ben-Sasson and Madhu Sudan, “Robust Locally Testable Codes and Products of Codes”. cs/0408066
- [37]
- O. Goldreich and M. Sudan, “Locally testable codes and PCPs of almost-linear length”, Journal of the ACM 53, 558 (2006). DOI
- [38]
- S. Kopparty et al., “High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity”, Journal of the ACM 64, 1 (2017). DOI
- [39]
- S. Gopi et al., “Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound”, IEEE Transactions on Information Theory 64, 5813 (2018). DOI
- [40]
- Irit Dinur et al., “Locally Testable Codes with constant rate, distance, and locality”. 2111.04808
- [41]
- J. Håstad, “Some optimal inapproximability results”, Journal of the ACM 48, 798 (2001). DOI
- [42]
- M. Bellare, O. Goldreich, and M. Sudan, “Free Bits, PCPs, and Nonapproximability---Towards Tight Results”, SIAM Journal on Computing 27, 804 (1998). DOI
- [43]
- Prahladh Harsha et al., “Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)”. 1002.3864
- [44]
- R. C. Bose and D. K. Ray-Chaudhuri, “On a class of error correcting binary group codes”, Information and Control 3, 68 (1960). DOI
- [45]
- R. C. Bose and D. K. Ray-Chaudhuri, “Further results on error correcting binary group codes”, Information and Control 3, 279 (1960). DOI
- [46]
- A. Hocquenghem, Codes correcteurs d'Erreurs, Chiffres (Paris), vol.2, pp.147-156, 1959.
- [47]
- J. Leon, J. Masley, and V. Pless, “Duadic Codes”, IEEE Transactions on Information Theory 30, 709 (1984). DOI
- [48]
- V. Pless, “Duadic Codes and Generalizations”, Eurocode ’92 3 (1993). DOI
- [49]
- L.-H. Zetterberg, “Cyclic codes from irreducible polynomials for correction of multiple errors”, IEEE Transactions on Information Theory 8, 13 (1962). DOI
- [50]
- M. J. E. Golay, Notes on digital coding, Proc. IEEE, 37 (1949) 657.
- [51]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999). DOI
- [52]
- C. E. Shannon, “A Mathematical Theory of Communication”, Bell System Technical Journal 27, 379 (1948). DOI
- [53]
- R. W. Hamming, “Error Detecting and Error Correcting Codes”, Bell System Technical Journal 29, 147 (1950). DOI
- [54]
- A. Shokrollahi, “Raptor codes”, IEEE Transactions on Information Theory 52, 2551 (2006). DOI
- [55]
- Petar Maymounkov, Online codes, Technical report, New York University, 2002.
- [56]
- M. Luby, “LT codes”, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.. DOI