nLab binary linear code

Definitions and framework

A bineary linear code is a linear code over the prime field $\mathbb{F}_2$.

Linear codes

A ($q$-ary) linear code of length $n$ and rank $k$ is a $k$-dimensional subspace of the $n$-dimensional vector space $\mathbb{F}_q^n$ over a prime field $\mathbb{F}_q$ with $q$ elements, or of any $n$-dimensional space over $\mathbb{F}_q$ that comes equipped with a “standard” basis. A principal application is in the construction of error-correcting codes.

There is a Joyal species $Code_{q, k}: Core(FinSet) \to Set$ of $q$-ary linear codes of rank $k$, which assigns to a finite set $\Omega$ the set of $k$-dimensional subspaces of the free $\mathbb{F}_q$-vector space generated by $\Omega$ as basis. The corresponding groupoid of $q$-linear codes is the category of elements of $Code_{q, k}$. This gives one notion of isomorphism of linear codes, where an isomorphism $(S, V \subseteq \mathbb{F}_q S) \to (T, W \subseteq \mathbb{F}_q T)$ is a bijection $\phi: S \to T$ such that the linear map $\mathbb{F}_q \phi$ carries $V$ onto $W$. Thus, isomorphisms in this sense are given by permutation matrices.

An alternative notion that recurs in coding theory is that an isomorphism (often called an equivalence) of codes consists of a monomial matrix which, when interpreted as a linear isomorphism using the assigned linear bases, carries $V$ onto $W$.

Each assigned basis $\{e_1, \ldots, e_n\}$ of a vector space $U$ can be construed as a self-dual basis with respect to a bilinear form, so that $\langle e_i, e_j \rangle = \delta_{i j}$. In terms of coordinates with respect to the chosen basis, this bilinear form is the usual dot product

$$(\vec{x}, \vec{y}) \mapsto x_1 y_1 + \ldots + x_n y_n$$

and this bilinear form is used to define the notion of dual code (see below).

Binary linear codes

The following is largely adapted from Frenkel, Lepowsky, Meurman.

A (binary linear) code is a $q$-ary code with $q = 2$. In this case, isomorphisms defined by permutation matrices are the same as isomorphisms defined by monomial matrices.

As a combinatorial structure on a finite set $\Omega$, a binary linear code is typically construed as a subspace of a finite power set $P(\Omega)$, considered as an $\mathbb{F}_2$-space whose addition is given by taking the symmetric difference of sets, and with standard basis given by the atoms.

In that case, the standard dot product can be identified with the nondegenerate symmetric $\mathbb{F}_2$-bilinear pairing on the Boolean ring $P(\Omega)$ given by

$$P(\Omega) \times P(\Omega) \stackrel{\langle -, - \rangle}{\to} \mathbb{F}_2$$

$$\,$$

$$(S, T) \mapsto {|S \cap T|} \pmod 2$$

where ${|C|}$ is the cardinality of a set $C$. In the sequel, we let $n = {|\Omega|} = \dim(P(\Omega))$.

To each code $\mathbf{C} \subset P(\Omega)$ there is a dual code $\mathbf{C}^\perp$:

$$\mathbf{C}^\perp = \{S \in P(\Omega): \forall T \in \mathbf{C} \; \langle S, T \rangle = 0\}.$$

Notice that $\dim(\mathbf{C}^\perp) = n - \dim(\mathbf{C})$. A code $\mathbf{C}$ is self-dual if $\mathbf{C} = \mathbf{C}^\perp$. In this case $n$ is even and $\dim(\mathbf{C}) = n/2$.

Now suppose $\Omega$ is a set with an even number $n$ of elements. The collection $E(\Omega)$ of subsets of even cardinality is a vector subspace of $P(\Omega)$ of dimension $n-1$, and we have

$$E(\Omega) = 1^\perp,$$

where $1$ is the multiplicative unit of $P(\Omega)$ (the subset $\Omega$), under the assumption $n$ is even. On $E(\Omega)$ we may define a quadratic form

$$q: E(\Omega) \to \mathbb{F}_2$$

taking $S \in E(\Omega)$ to $\frac{{|S|}}{2} \pmod 2$; this $q$ gives rise to the bilinear form $\langle -, - \rangle$ on $E(\Omega)$ via

$$\langle S, T \rangle = q(S + T) - q(S) - q(T).$$

A code $\mathbf{C} \subset P(\Omega)$ is of type II if

• $4$ divides ${|C|}$ for every $C \in \mathbf{C}$ and $\Omega \in \mathbf{C}$,

and of type I if

• $\mathbf{C} \subset E(\Omega)$ and $\Omega \in \mathbf{C}$, but $\mathbf{C}$ is not of type II.

Notice that the quadratic form (hence the bilinear form) vanishes on a type II code $\mathbf{C}$, so that we have $\mathbf{C} \subset \mathbf{C}^\perp$ (i.e., $\mathbf{C}$ is isotropic). If $\mathbf{C}$ is maximal isotropic – has half the dimension of $P(\Omega)$ – then it follows that $\mathbf{C}$ is self-dual.

Examples

Example

(Hamming $(8, 4)$ code) Up to isomorphism, there is a unique type II self-dual code $\mathbf{C} \subset P(\Omega)$ where $\Omega$ is an 8-element set. Such a code may be constructed as follows: let $\Omega$ be the projective line $\mathbb{P}^1 \mathbb{F}_7$, so as a set $\Omega = \{0, 1, 2, 3, 4, 5, 6, \infty\}$. Let $Q$ be the set of squares $0, 1, 2, 4$ and let $N$ be its complement in $\Omega$. The span of the set of elements $\{N + i: i \in \mathbb{F}_7\}$ (where $\infty + i = \infty$ for each $i$) is a 4-dimensional space consisting of 16 elements:

$$\array{ \emptyset, & \{3, 5, 6, \infty\}, & \{0, 4, 6, \infty\}, & \{0, 1, 5, \infty\} \\ \{1, 2, 6, \infty\}, & \{0, 2, 3, \infty\}, & \{1, 3, 4, \infty\}, & \{2, 4, 5, \infty\} \\ \{0, 3, 4, 5\}, & \{1, 4, 5, 6\}, & \{0, 2, 5, 6\}, & \{0, 1, 3, 6\} \\ \{0, 1, 2, 4\}, & \{1, 2, 3, 5\}, & \{2, 3, 4, 6\}, & \Omega. }$$

For this subspace $\mathbf{C} \subset P(\Omega)$, every element is a set that is of cardinality $0$, $4$, or $8$. It is clearly of type II, and self-dual because it is maximal isotropic.

There is a second Hamming code $\mathbf{C}'$ (isomorphic to $\mathbf{C}$) that is spanned by the elements $\{-N - i: i \in \mathbb{F}_7\}$. This is “complementary” to the first in an appropriate sense: we have

$$\mathbf{C} + \mathbf{C}' = E(\Omega), \qquad \mathbf{C} \cap \mathbf{C}' = \mathbb{F}_2 \Omega,$$

so that $\mathbf{C}/\mathbb{F}_2 \Omega$ is complementary to $\mathbf{C}'/\mathbb{F}_2 \Omega$ in the 6-dimensional space $E(\Omega)/\mathbb{F}_2 \Omega$.

In the theory of error-correcting codes, this is related to the Hamming $(7, 4)$ code, but with an extra parity bit. The Hamming $(7, 4)$ code is one of an infinite family of Hamming codes of type $(2^r - 1, 2^r - r - 1)$.

Example

(The binary Golay code.) Up to isomorphism, there is a unique self-dual code of type II on a 24-element set with no elements of weight (= cardinality) 4. Indeed, let $3 \Omega$ denote the disjoint union of three copies of $\Omega$. Construct a code $\mathbf{D} \subset P(3\Omega)$ that is spanned by elements of the form

$$S \sqcup S \sqcup \emptyset, \qquad S \sqcup \emptyset \sqcup S, \qquad T \sqcup T \sqcup T$$

where $S$ ranges over elements of the Hamming code $\mathbf{C}$ and $T$ ranges over elements of the Hamming code $\mathbf{C}'$. Any three elements $S \sqcup S \sqcup \emptyset$, $S' \sqcup \emptyset \sqcup S'$, and $T \sqcup T \sqcup T$ are mutually orthogonal in $P(\Omega)$, so evidently $\mathbf{D}$ is an orthogonal direct sum of three 4-dimensional isotropic spaces, making $\mathbf{D}$ an isotropic subspace of dimension 12, hence maximal isotropic. Each element of $\mathbf{D}$ has cardinality a multiple of $4$, making it self-dual type II.

To see that $\mathbf{D}$ has no elements of weight 4, argue as follows. Note that combinations $(S \sqcup S \sqcup \emptyset) + (S' \sqcup \emptyset \sqcup S')$ are of the form $S_1 \sqcup S_2 \sqcup S_3$ such that $S_1 + S_2 + S_3 = 0$. Now suppose we had

$${|S_1 + T|} + {|S_2 + T|} + {|S_3 + T|} = 4.$$

Since all the summands are even, one must be zero, so say $S_3 + T = 0$. Since $\mathbf{C} \cap \mathbf{C}' = \mathbb{F}_2 \Omega$, we must have $T \in \mathbb{F}_2 \Omega$. But then ${|S_1 + T|}$ and ${|S_2 + T|}$ are multiples of $4$, and therefore one is zero, so say $S_2 + T = 0$. But now we have

$$S_1 = S_1 - 2 T = S_1 + S_2 + S_3 = 0$$

whence we infer that ${|S_1 + T|}$ is a multiple of $8$, and we have reached a contradiction.

Properties

Relation to quantum stabilizer codes

Classical binary linear codes are closely related to quantum error correcting codes knows as stabilizer codes (e.g. Ball, Centelles & Huber 20, Sec. 2.3 & 3)

Related entries

• coding theory

• binary Golay code

• combinatorial design

• Leech lattice

• adinkra

References

• Igor Frenkel, James Lepowsky, Arne Meurman, Vertex operator algebras and the monster, Pure and Applied Mathematics 134, Academic Press, New York 1998. liv+508 pp. MR0996026

• Patrick J. Morandi, Error Correcting Codes and Algebraic Curves , lecture notes New Mexico State University 2001. (pdf)

• Jay A. Wood, Spinor groups and algebraic coding theory , J.Combinatorial Th. Series A 51 (1989) pp.277-313. (available online)

Discussion in relation to quantum stabilizer codes:

• Simeon Ball, Aina Centelles, Felix Huber, Section 2.3 & 3 of: Quantum error-correcting codes and their geometries (arXiv:2007.05992)

category: combinatorics