Here is a list of binary linear codes.
| Code | Description |
|---|---|
| Ben-Sasson-Goldreich-Harsha-Sudan-Vadhan (BGHSV) code | Locally testable \([[n,k,d]]\) code with \(n = k^{1+\epsilon}\) and query complexity of order \(O(1/\epsilon)\) for any \(\epsilon > 0\). |
| Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code | Locally testable \([[n,k,d]]\) code with \(n = k \cdot 2^{\tilde{O}(\sqrt{\log k})}\) and asymptotically constant query complexity. |
| Binary BCH code | 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\). |
| Binary duadic code | 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\) [1]. |
| 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) \tag*{(1)}\end{align} holds for any bitstring \(x\), where \(D(x,C)\) is the Hamming distance between \(x\) and the closest codeword to \(x\) [2; Def. 11]. |
| 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\). |
| 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. |
| Dinur code | 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 [3]. |
| Expander code | 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. |
| Fibonacci code | 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. |
| Fountain code | 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. |
| Golay code | A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [4] 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. |
| Gold code | Member of the family of \([2^r-1, 2r ]\) cyclic binary linear code characterized by the generator polynomial of degree \(r\) of two maximum-period sequences of period \(2^r-1\) with absolute cross-correlation \( \leq 2^{(r+2)/2}\). Gold codewords are generated using \(m\)-sequences \(x\) and \(y\), which are codewords of simplex codes with check polynomials of degree \(r\) [6]. |
| Goldreich-Sudan code | 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)}\). |
| Graph homology code | 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. |
| Hadamard code | Also known as a Walsh code or Walsh-Hadamard code. An \([2^m,m,2^{m-1}]\) balanced binary code dual to an extended Hamming Code. |
| Hamming code | 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. |
| Justesen code | 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)\). |
| Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code | 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 [7] showed that related concatenated codes achieve the Gilbert-Varshamov bound. |
| Left-right Cayley complex code | 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. |
| 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. |
| Long code | 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 [8]. |
| Luby transform (LT) code | Erasure codes based on fountain codes. They improve on random linear fountain codes by having a much more efficient encoding and decoding algorithm. |
| Melas code | Cyclic \([2^m -1, 2^m - 1 - 2m, 5]\) linear code with generator polynomial is \(g(x) = p(x)p(x)^{\star}\), where \(p(x)\) is a primitive polynomial of degree \(m\) that is the minimal polynomial over \(GF(2)\) of an element \(\alpha\) of order \(2^m -1\) in \(GF(2^m)\), \(m\) is odd and greater that five, and '\(\star\)' denotes reciprocation [9]. |
| 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. |
| Polar code | 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}\). |
| Raptor (RAPid TORnado) code | 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. |
| Reed-Muller (RM) code | 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. |
| 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. |
| Single parity-check (SPC) code | Also known as a sum-zero, zero-sum, 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. |
| Ta-Shma zigzag code | 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\) [10]. |
| Tanner code | 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. |
| Tornado code | Stub. |
| Weight-two code | 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. |
| Zetterberg code | 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 |
| \([7,4,3]\) Hamming code | Second-smallest member of the Hamming code family with generator matrix \begin{align} \left(\begin{array}{ccccccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right)~. \tag*{(2)}\end{align} Can be extended to yield the \([8,4,4]\) extended Hamming code. |