nLab
binary linear code

Contents

Contents

Definitions and framework

Linear codes

A (qq-ary) linear code of length nn and rank kk is a kk-dimensional subspace of the nn-dimensional vector space 𝔽 q n\mathbb{F}_q^n over a finite field 𝔽 q\mathbb{F}_q with qq elements, or of any nn-dimensional space over 𝔽 q\mathbb{F}_q that comes equipped with a β€œstandard” basis. A principal application is in the construction of error-correcting code?s.

There is a Joyal species Code q,k:Core(FinSet)β†’SetCode_{q, k}: Core(FinSet) \to Set of qq-ary linear codes of rank kk, which assigns to a finite set Ξ©\Omega the set of kk-dimensional subspaces of the free 𝔽 q\mathbb{F}_q-vector space generated by Ξ©\Omega as basis. The corresponding groupoid of qq-linear codes is the category of elements of Code q,kCode_{q, k}. This gives one notion of isomorphism of linear codes, where an isomorphism (S,VβŠ†π”½ qS)β†’(T,WβŠ†π”½ qT)(S, V \subseteq \mathbb{F}_q S) \to (T, W \subseteq \mathbb{F}_q T) is a bijection Ο•:Sβ†’T\phi: S \to T such that the linear map 𝔽 qΟ•\mathbb{F}_q \phi carries VV onto WW. 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 VV onto WW.

Each assigned basis {e 1,…,e n}\{e_1, \ldots, e_n\} of a vector space UU can be construed as a self-dual basis with respect to a bilinear form, so that ⟨e i,e j⟩=Ξ΄ ij\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

(xβ†’,yβ†’)↦x 1y 1+…+x ny n(\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 Frankel, Lepowsky, Meurman.

A (binary linear) code is a qq-ary code with q=2q = 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(Ξ©)P(\Omega), considered as an 𝔽 2\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 𝔽 2\mathbb{F}_2-bilinear pairing on the Boolean ring P(Ξ©)P(\Omega) given by

P(Ξ©)Γ—P(Ξ©)β†’βŸ¨βˆ’,βˆ’βŸ©π”½ 2 P(\Omega) \times P(\Omega) \stackrel{\langle -, - \rangle}{\to} \mathbb{F}_2
\,
(S,T)↦|S∩T|(mod2)(S, T) \mapsto {|S \cap T|} \pmod 2

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

To each code CβŠ‚P(Ξ©)\mathbf{C} \subset P(\Omega) there is a dual code C βŠ₯\mathbf{C}^\perp:

C βŠ₯={S∈P(Ξ©):βˆ€T∈C⟨S,T⟩=0}.\mathbf{C}^\perp = \{S \in P(\Omega): \forall T \in \mathbf{C} \; \langle S, T \rangle = 0\}.

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

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

E(Ξ©)=1 βŠ₯,E(\Omega) = 1^\perp,

where 11 is the multiplicative unit of P(Ξ©)P(\Omega) (the subset Ξ©\Omega), under the assumption nn is even. On E(Ξ©)E(\Omega) we may define a quadratic form

q:E(Ξ©)→𝔽 2q: E(\Omega) \to \mathbb{F}_2

taking S∈E(Ξ©)S \in E(\Omega) to |S|2(mod2)\frac{{|S|}}{2} \pmod 2; this qq gives rise to the bilinear form βŸ¨βˆ’,βˆ’βŸ©\langle -, - \rangle on E(Ξ©)E(\Omega) via

⟨S,T⟩=q(S+T)βˆ’q(S)βˆ’q(T).\langle S, T \rangle = q(S + T) - q(S) - q(T).

A code CβŠ‚P(Ξ©)\mathbf{C} \subset P(\Omega) is of type II if

  • 44 divides |C|{|C|} for every C∈CC \in \mathbf{C} and Ω∈C\Omega \in \mathbf{C},

and of type I if

  • CβŠ‚E(Ξ©)\mathbf{C} \subset E(\Omega) and Ω∈C\Omega \in \mathbf{C}, but C\mathbf{C} is not of type II.

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

Examples

Example

(Hamming (8,4)(8, 4) code) Up to isomorphism, there is a unique type II self-dual code CβŠ‚P(Ξ©)\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 β„™ 1𝔽 7\mathbb{P}^1 \mathbb{F}_7, so as a set Ξ©={0,1,2,3,4,5,6,∞}\Omega = \{0, 1, 2, 3, 4, 5, 6, \infty\}. Let QQ be the set of squares 0,1,2,40, 1, 2, 4 and let NN be its complement in Ξ©\Omega. The span of the set of elements {N+i:iβˆˆπ”½ 7}\{N + i: i \in \mathbb{F}_7\} (where ∞+i=∞\infty + i = \infty for each ii) is a 4-dimensional space consisting of 16 elements:

βˆ…, {3,5,6,∞}, {0,4,6,∞}, {0,1,5,∞} {1,2,6,∞}, {0,2,3,∞}, {1,3,4,∞}, {2,4,5,∞} {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}, Ξ©.\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 CβŠ‚P(Ξ©)\mathbf{C} \subset P(\Omega), every element is a set that is of cardinality 00, 44, or 88. It is clearly of type II, and self-dual because it is maximal isotropic.

There is a second Hamming code Cβ€²\mathbf{C}' (isomorphic to C\mathbf{C}) that is spanned by the elements {βˆ’Nβˆ’i:iβˆˆπ”½ 7}\{-N - i: i \in \mathbb{F}_7\}. This is β€œcomplementary” to the first in an appropriate sense: we have

C+Cβ€²=E(Ξ©),C∩Cβ€²=𝔽 2Ξ©,\mathbf{C} + \mathbf{C}' = E(\Omega), \qquad \mathbf{C} \cap \mathbf{C}' = \mathbb{F}_2 \Omega,

so that C/𝔽 2Ξ©\mathbf{C}/\mathbb{F}_2 \Omega is complementary to Cβ€²/𝔽 2Ξ©\mathbf{C}'/\mathbb{F}_2 \Omega in the 6-dimensional space E(Ξ©)/𝔽 2Ξ©E(\Omega)/\mathbb{F}_2 \Omega.

In the theory of error-correcting codes, this is related to the Hamming (7,4)(7, 4) code, but with an extra parity bit. The Hamming (7,4)(7, 4) code is one of an infinite family of Hamming codes of type (2 rβˆ’1,2 rβˆ’rβˆ’1)(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Ξ©3 \Omega denote the disjoint union of three copies of Ξ©\Omega. Construct a code DβŠ‚P(3Ξ©)\mathbf{D} \subset P(3\Omega) that is spanned by elements of the form

SβŠ”SβŠ”βˆ…,SβŠ”βˆ…βŠ”S,TβŠ”TβŠ”TS \sqcup S \sqcup \emptyset, \qquad S \sqcup \emptyset \sqcup S, \qquad T \sqcup T \sqcup T

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

To see that D\mathbf{D} has no elements of weight 4, argue as follows. Note that combinations (SβŠ”SβŠ”βˆ…)+(Sβ€²βŠ”βˆ…βŠ”Sβ€²)(S \sqcup S \sqcup \emptyset) + (S' \sqcup \emptyset \sqcup S') are of the form S 1βŠ”S 2βŠ”S 3S_1 \sqcup S_2 \sqcup S_3 such that S 1+S 2+S 3=0S_1 + S_2 + S_3 = 0. Now suppose we had

|S 1+T|+|S 2+T|+|S 3+T|=4.{|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=0S_3 + T = 0. Since C∩Cβ€²=𝔽 2Ξ©\mathbf{C} \cap \mathbf{C}' = \mathbb{F}_2 \Omega, we must have Tβˆˆπ”½ 2Ξ©T \in \mathbb{F}_2 \Omega. But then |S 1+T|{|S_1 + T|} and |S 2+T|{|S_2 + T|} are multiples of 44, and therefore one is zero, so say S 2+T=0S_2 + T = 0. But now we have

S 1=S 1βˆ’2T=S 1+S 2+S 3=0S_1 = S_1 - 2 T = S_1 + S_2 + S_3 = 0

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

References

  • Igor Frankel, James Lepowsky, Arne Meurman, Vertex Operator Algebras and the Monster, Academic Press 1988.
  • 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)

category: combinatorics

Last revised on September 13, 2018 at 04:24:53. See the history of this page for a list of all contributions to it.