Root code for the Binary Kingdom

## Description

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) \tag*{(1)}\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. The number of correctable errors is called the decoding radius, and it is upper bounded by half of the distance. In addition, a code detects errors on up to \(d-1\) coordinates, and corrects erasure errors on up to \(d-1\) coordinates.

## Rate

The rate of a binary code is usually defined as \(R=\frac{1}{n}\log_{2}K\) bits per symbol. The maximum rate of a binary code with linear distance is upper bounded by the McEliece, Rodemich, Rumsey and Welch (MRRW) bound [1] (see Refs. [2–5] for other proofs).

## Decoding

For few-bit codes (\(n\) is small), decoding can be based on a lookup table. For infinite code families, the size of such a table scales exponentially with \(n\), so approximate decoding algorithms scaling polynomially with \(n\) have to be used. The decoder determining the most likely error given a noise channel is called the maximum-likelihood decoder.Given a received string \(x\) and an error bound \(e\), a list decoder returns a list of all codewords that are at most \(e\) from \(x\) in Hamming distance. The number of codewords in a neighborhood of \(x\) has to be polynomial in \(n\) in order for this decoder to run in time polynomial in \(n\).

## Parent

## Children

- Binary group-orbit code
- Combinatorial design — If the number of a code is less than or equal to its dual distance, then some sets of fixed-weight codewords form a combinatorial design [6; Thm. 6.7].
- Nearly perfect code
- Unary code
- Anticode
- Batch code
- Conference code
- Hergert code
- Gray code
- Delsarte-Goethals (DG) code
- Levenshtein code
- Best \((10,40,4)\) code
- Sloane-Whitehead code
- Vasilyev code
- Binary Varshamov-Tenengolts (VT) code

## Cousins

- Orthogonal array (OA) — An \((n,K)\) binary code with dual distance \(d^{\perp}\) is an OA\(_{K/2^{d^{\perp}-1}}(d^{\perp}-1,n,2)\) [7][6; Ch. 5].
- Construction-\(A\) code — Each binary code yields a sphere packing under Construction A.
- Binary antipodal code — Binary antipodal codes are spherical codes obtained from binary codes via the antipodal mapping.
- Fock-state bosonic code — Fock-state code distance is a natural extension of Hamming distance between binary strings.
- Movassagh-Ouyang Hamiltonian code — Movassagh-Ouyang codes are constructed from classical binary codes.

## References

- [1]
- R. McEliece et al., “New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities”, IEEE Transactions on Information Theory 23, 157 (1977) DOI
- [2]
- M. Navon and A. Samorodnitsky, “Linear Programming Bounds for Codes via a Covering Argument”, Discrete & Computational Geometry 41, 199 (2008) DOI
- [3]
- J. Friedman and J.-P. Tillich, “Generalized Alon--Boppana Theorems and Error-Correcting Codes”, SIAM Journal on Discrete Mathematics 19, 700 (2005) DOI
- [4]
- A. Samorodnitsky, “One more proof of the first linear programming bound for binary codes and two conjectures”, (2021) arXiv:2104.14587
- [5]
- N. Linial and E. Loyfer, “An Elementary Proof of the First LP Bound on the Rate of Binary Codes”, (2023) arXiv:2303.16619
- [6]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [7]
- Delsarte, Philippe. "Bounds for unrestricted codes, by linear programming." (1972).

## Page edit log

- Victor V. Albert (2022-07-06) — most recent
- Victor V. Albert (2022-02-16)
- Victor V. Albert (2021-10-29)

## Cite as:

“Binary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/bits_into_bits

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/bits_into_bits.yml.