## Description

## 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.

Performance of binary codes can also be measured with respect to deletions and insertions of bits into the codewords. In this case, the metric measuring distance of an error word to the nearest codeword is the deletion distance: given vectors \(u,v\), this distance is one-half the smallest number of deletions and insertions needed to change \(u\) to \(v\). A code \(C\) corrects \(e\) delections if all codewords are separated by at least \(e+1\) in the deletion distance [1].

## Rate

## Decoding

## Parent

## Children

## Cousins

- 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.
- 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]
- N. J. A. Sloane, “On Single-Deletion-Correcting Codes”, (2002) arXiv:math/0207197
- [2]
- 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
- [3]
- M. Navon and A. Samorodnitsky, “Linear Programming Bounds for Codes via a Covering Argument”, Discrete & Computational Geometry 41, 199 (2008) DOI
- [4]
- J. Friedman and J.-P. Tillich, “Generalized Alon--Boppana Theorems and Error-Correcting Codes”, SIAM Journal on Discrete Mathematics 19, 700 (2005) DOI
- [5]
- A. Samorodnitsky, “One more proof of the first linear programming bound for binary codes and two conjectures”, (2021) arXiv:2104.14587
- [6]
- N. Linial and E. Loyfer, “An Elementary Proof of the First LP Bound on the Rate of Binary Codes”, (2023) arXiv:2303.16619

## 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.