Description
A code intended to encode a piece, or block, of a data stream on a block of \(n\) symbols, with each symbol taking values from a fixed alphabet \(\Sigma\).
The overall alphabet of the code is \(\Sigma^n\), and \(n\) is called the length of the code [1; Ch. 3]. In some cases, only a subset of \(\Sigma^n\) is available to use for constructing the code. For example, in the case of spherical codes, one is constrained to \(n\)-dimensional real vectors on the unit sphere.
An alternative more stringent definition of the code (not used here) is in terms of a map encoding logical information from \(\Sigma^k\) into \(\Sigma^n\), yielding an \((n,k,d)_{\Sigma}\) block code, where \(d\) is the code distance.
Protection
Block codes protect from errors acting on a few of the \(n\) symbols. A block code with distance \(d\) detects errors acting on up to \(d-1\) symbols, and corrects erasure errors on up to \(d-1\) symbols.Rate
Ideal decoding error is suppressed exponentially with the number of subsystems \(n\), and the exponent has been studied in Ref. [2–4].Decoding
Decoding an error-correcting code is equivalent to finding the ground state of some statistical mechanical model [5].Notes
Asymptotic notation: We are often interested in how parameters of particular infinite block-code families scale with increasing block length \(n\), necessitating the use of asymptotic or Bachmann–Landau notation; see the book [6]. The table below summarizes the notation used throughout the EC Zoo for relating functions \(f,g\) that both grow with \(n\).
relation | behavior |
|---|---|
\(f(n)=O(g(n))\) | \(\phantom{c_{2}\geq}{\displaystyle \underset{n\to\infty}{\lim}\frac{|f(n)|}{|g(n)|}}\leq c\) |
\(f(n)=\Omega(g(n))\) | \(0<{\displaystyle \underset{n\to\infty}{\lim}\frac{|f(n)|}{|g(n)|}}\phantom{\leq c_{2}}\) |
\(f(n)=\Theta(g(n))\) | \(c_{1}\leq{\displaystyle \underset{n\to\infty}{\lim}\frac{|f(n)|}{|g(n)|}}\leq c_{2}\) |
Cousin
Member of code lists
Primary Hierarchy
References
- [1]
- J. H. van Lint, Introduction to Coding Theory (Springer Berlin Heidelberg, 1999) DOI
- [2]
- C. E. Shannon, “Probability of Error for Optimal Codes in a Gaussian Channel”, Bell System Technical Journal 38, 611 (1959) DOI
- [3]
- C. E. Shannon, R. G. Gallager, and E. R. Berlekamp, “Lower bounds to error probability for coding on discrete memoryless channels. I”, Information and Control 10, 65 (1967) DOI
- [4]
- Fano, Robert M. The transmission of information. Vol. 65. Cambridge, MA, USA: Massachusetts Institute of Technology, Research Laboratory of Electronics, 1949.
- [5]
- N. Sourlas, “Spin-glass models as error-correcting codes”, Nature 339, 693 (1989) DOI
- [6]
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press.
Page edit log
- Victor V. Albert (2023-02-14) — most recent
Cite as:
“Block code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/block