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

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

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

References

[1]
N. J. A. Sloane, “On Single-Deletion-Correcting Codes”. math/0207197
Page edit log

Zoo code information

Internal code ID: bits_into_bits

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: bits_into_bits

Cite as:
“Binary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/bits_into_bits
BibTeX:
@incollection{eczoo_bits_into_bits, title={Binary code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/bits_into_bits} }
Share via:
Twitter |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/bits_into_bits

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.