Binary code
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 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.
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
Cousins
- Group-based code — Group-based codes whose alphabet is based on the group \(\mathbb{Z}_2\) are binary codes.
- Movassagh-Ouyang Hamiltonian code — Movassagh-Ouyang codes are constructed from classical binary codes.
Zoo code information
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/tree/main/codes/classical/bits/bits_into_bits.yml.