## 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. The table below lists the most common alphabets used in block codes, along with names of the corresponding codewords.

alphabet \(\Sigma\) | codewords |
---|---|

\(\mathbb{Z}_{2}=GF(2)\) | bitstrings |

\(GF(q)\) | \(q\)-ary strings |

\(\mathbb{Z}_{q}\) | \(q\)-ary strings over \(\mathbb{Z}_{q}\) |

\(\mathbb{R}\) | sphere packings |

\(G\) | group elements |

An alternative more stringent definition (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.

### Finite-field alphabet

Finite fields: The most common alphabets used in block codes Galois or finite fields \(GF(q)=\mathbb{F}_q\), which are sets of \(q\) elements closed under addition and multiplication. They are finite analogues of the real or complex numbers, and a unique field exists for every power \(q=p^m\) of a prime \(p\). The prime-field case reduces to \(\mathbb{Z}_p\), a group under addition that is promoted to a field by defining multiplication modulo \(p\); the case \(p=2\) yields the binary field \(\mathbb{Z}_2\). Every finite field comes with a 0 element (additive identity), a 1 element (multiplicative identity), and additive (multiplicative) inverses for all (nonzero) elements. An element whose powers exhaust all nonzero field elements is called primitive. Fields come with a trace operation, the field trace, which maps elements \(\gamma \in GF(q)\) to elements of \(GF(p)\) as \begin{align} \text{tr}(\gamma)=\sum_{k=0}^{m-1}\gamma^{p^{k}}~. \tag*{(1)}\end{align} The field trace can be thought of as an averaging over the field's Galois group, which is the cyclic group generated by \(\gamma\to\gamma^p\) [2; pg. 113]. Fields also come with a field norm, \begin{align} N(\gamma)=\prod_{k=0}^{m-1}\gamma^{p^{k}}=\gamma^{(p^{m}-1)/(p-1)}~. \tag*{(2)}\end{align} In the case of the complex numbers, analogues of the field trace and field norm are the real part and norm squared of a complex number, respectively.

Any field \(GF(q)\) can be thought of as an \(m\)-dimensional vector space over \(GF(p)\) a.k.a. the \(m\)th extension of \(GF(p)\) (similar to the complex numbers being an extension of the reals). Conversely, \(GF(p)\) is an example of a subfield of \(GF(q)\). Certain field elements are chosen to be the basis of \(GF(q)\) over \(GF(p)\), and all other elements are expressed as linear combinations of these basis elements. More generally, elements of fields such as \(GF(p^{ml})\) can be written as \(m\)-dimensional vectors over \(GF(p^l)\) or \((m\times l)\)-dimensional matrices over \(GF(p)\). This idea is used to convert between ordinary block codes and matrix-based codes such as disk array codes and rank-metric codes. The field norm and field trace can likewise be defined for fields \(GF(q^m)\) that are extensions of \(GF(q)\) for non-prime \(q\).

An example of a field is the quaternary Galois field \(GF(4) = \{0,1,\omega, \omega^2=\bar{\omega}\}\) with \(p=m=2\). In this case, \(\omega\) can be interpreted as a third root of unity, but more formally it is defined as a solution to the polynomial equation \(1+x+x^2=0\). Field elements can be represented as two-dimensional vectors with binary elements, \(GF(4)=GF(2^2)\), using the basis \(1\cong(1,0)\) and \(\omega\cong(0,1)\): \begin{align} 0&\leftrightarrow(0,0)\cong0\cdot1+0\cdot\omega\tag*{(3)}\\1&\leftrightarrow(0,1)\cong0\cdot1+1\cdot\omega\tag*{(4)}\\\omega&\leftrightarrow(1,1)\cong1\cdot1+1\cdot\omega\tag*{(5)}\\\bar{\omega}&\leftrightarrow(1,0)\cong1\cdot1+0\cdot\omega~. \tag*{(6)}\end{align} In this way, the field elements form the Klein four group \(\mathbb{Z}_2\times\mathbb{Z}_2\) under addition. One can check that the trace operation, \(\text{tr}(\gamma) = \gamma + \gamma^2\), outputs either 0 or 1 for any element \(\gamma\in GF(4)\).

## Protection

## Rate

## Decoding

## 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 [7]. 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}\) |

## Parent

## Children

- Sphere packing
- Linear code over \(G\) — Linear codes over \(G\) are linear block codes with \(\Sigma=G\).
- Matrix-based code
- Constant-weight code
- Frameproof (FP) code
- Distributed-storage code
- Locally decodable code (LDC)
- Locally testable code (LTC)
- Error-correcting output code (ECOC)
- Batch code
- Private information retrieval (PIR) code
- Quantum-inspired classical block code
- Small-distance block code
- Reversible code
- Skew-cyclic code
- Quasi-twisted code
- \(t\)-design
- Universally optimal code
- Convolutional code — Convolutional codes for infinite block size are block codes consisting of infinite blocks.
- Ring code — Ring codes are block codes with \(\Sigma=R\).

## Cousin

## References

- [1]
- J. H. van Lint, Introduction to Coding Theory (Springer Berlin Heidelberg, 1999) DOI
- [2]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [3]
- C. E. Shannon, “Probability of Error for Optimal Codes in a Gaussian Channel”, Bell System Technical Journal 38, 611 (1959) DOI
- [4]
- 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
- [5]
- Fano, Robert M. The transmission of information. Vol. 65. Cambridge, MA, USA: Massachusetts Institute of Technology, Research Laboratory of Electronics, 1949.
- [6]
- N. Sourlas, “Spin-glass models as error-correcting codes”, Nature 339, 693 (1989) DOI
- [7]
- 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