In mathematics, a (binary) linear code of length n > 0 and rank 0 < k < n + 1 is a linear subspace C with dimension k of the vector space
- Fn2 .
Aside: F2 = {0,1} is the field with two elements and Fn2 is the set of all n-tuples of length n over F2. Occasionally some other finite field Fq containing q > 2 elements is used, in which case the code is said to be a q-ary code (rather than a binary code). Special exceptions to the adjective 'q-ary' are binary and ternary codes (corresponding to q=2 and q=3 respectively).
Properties
By virtue of the fact that the code is a subspace of Fn, the sum c1 + c2 of two codewords in C is also a codeword (ie an element of the subspace C). Thus the entire code (which may be very large) to be represented as the span of a minimal set of codewords (known as a basis in linear algebra terms). These basis codewords are often collated in the rows of a matrix known as a generating matrix for the code C.
The subspace definition also gives rise to the important property that the minimum Hamming distance between codewords is simply the minimum Hamming weight of all codewords since:
- d (c1 , c2 ) = d (c1 + c2 , 0 )
implying:
- min c1 , c2 in C { d (c1 , c2 ) } = min c1 , c2 in C { d (c1 + c2 , 0 ) } = min c1 in C { d ( c1 , 0 ) }
The motivation behind creating linear codes is to allow for syndrome decoding.
Popular notation
Codes in general are often denoted by the letter C. A linear code of length n, rank k (ie having k codewords in its basis and k rows in its generating matrix) and minimum Hamming weight d is referred to as an (n.k,d) code.
Remark: this is not to be confused with the notation [n,r,d] to denote a non-linear code of length n, size r (ie having r codewords) and minimum Hamming distance d.