A bineary linear code is a linear code over the prime field .
A (-ary) linear code of length and rank is a -dimensional subspace of the -dimensional vector space over a prime field with elements, or of any -dimensional space over that comes equipped with a βstandardβ basis. A principal application is in the construction of error-correcting codes.
There is a Joyal species of -ary linear codes of rank , which assigns to a finite set the set of -dimensional subspaces of the free -vector space generated by as basis. The corresponding groupoid of -linear codes is the category of elements of . This gives one notion of isomorphism of linear codes, where an isomorphism is a bijection such that the linear map carries onto . 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 onto .
Each assigned basis of a vector space can be construed as a self-dual basis with respect to a bilinear form, so that . In terms of coordinates with respect to the chosen basis, this bilinear form is the usual dot product
and this bilinear form is used to define the notion of dual code (see below).
The following is largely adapted from Frenkel, Lepowsky, Meurman.
A (binary linear) code is a -ary code with . 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 , a binary linear code is typically construed as a subspace of a finite power set , considered as an -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 -bilinear pairing on the Boolean ring given by
where is the cardinality of a set . In the sequel, we let .
To each code there is a dual code :
Notice that . A code is self-dual if . In this case is even and .
Now suppose is a set with an even number of elements. The collection of subsets of even cardinality is a vector subspace of of dimension , and we have
where is the multiplicative unit of (the subset ), under the assumption is even. On we may define a quadratic form
taking to ; this gives rise to the bilinear form on via
A code is of type II if
and of type I if
Notice that the quadratic form (hence the bilinear form) vanishes on a type II code , so that we have (i.e., is isotropic). If is maximal isotropic β has half the dimension of β then it follows that is self-dual.
(Hamming code) Up to isomorphism, there is a unique type II self-dual code where is an 8-element set. Such a code may be constructed as follows: let be the projective line , so as a set . Let be the set of squares and let be its complement in . The span of the set of elements (where for each ) is a 4-dimensional space consisting of 16 elements:
For this subspace , every element is a set that is of cardinality , , or . It is clearly of type II, and self-dual because it is maximal isotropic.
There is a second Hamming code (isomorphic to ) that is spanned by the elements . This is βcomplementaryβ to the first in an appropriate sense: we have
so that is complementary to in the 6-dimensional space .
In the theory of error-correcting codes, this is related to the Hamming code, but with an extra parity bit. The Hamming code is one of an infinite family of Hamming codes of type .
(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 denote the disjoint union of three copies of . Construct a code that is spanned by elements of the form
where ranges over elements of the Hamming code and ranges over elements of the Hamming code . Any three elements , , and are mutually orthogonal in , so evidently is an orthogonal direct sum of three 4-dimensional isotropic spaces, making an isotropic subspace of dimension 12, hence maximal isotropic. Each element of has cardinality a multiple of , making it self-dual type II.
To see that has no elements of weight 4, argue as follows. Note that combinations are of the form such that . Now suppose we had
Since all the summands are even, one must be zero, so say . Since , we must have . But then and are multiples of , and therefore one is zero, so say . But now we have
whence we infer that is a multiple of , and we have reached a contradiction.
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)
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:
Last revised on May 5, 2021 at 09:14:47. See the history of this page for a list of all contributions to it.