Block code

Finite fields: The most common alphabets used in block codes are 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=p^m)\) 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\).