Linear code

In mathematics and information theory, a linear code is an important type of block code used in error correction and detection schemes. Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome decoding).

Formal definition

A linear code of length ${\displaystyle n}$  and rank ${\displaystyle k}$  is a linear subspace ${\displaystyle C}$  with dimension ${\displaystyle k}$  of the vector space ${\displaystyle {\mathbb {F} _{q}}^{n}}$  where ${\displaystyle \mathbb {F} _{q}}$  is the finite field with ${\displaystyle q}$  elements. Such a code with parameter ${\displaystyle q}$  is called a q-ary code (eg when ${\displaystyle q=5}$ , the code is a 5-ary code). Notable exceptions to this are the cases ${\displaystyle q=2}$  and ${\displaystyle q=3}$ , when the code is described as binary and ternary (respectively).

Properties

By virtue of the fact that the code is a subspace of ${\displaystyle \mathbb {F} _{2}^{n}}$ , the sum ${\displaystyle c_{1}+c_{2}}$  of two codewords in ${\displaystyle C}$  is also a codeword (ie an element of the subspace ${\displaystyle C}$ ). Thus the entire code (which may be very large) may be represented as the span of a minimal set of codewords (known as a basis in linear algebra). These basis codewords are often collated in the rows of a matrix known as a generating matrix for the code ${\displaystyle 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:

${\displaystyle d(c_{1},c_{2})=d(c_{1}+c_{2},0)\,}$ 

implying:

${\displaystyle \min _{c_{1},c_{2}\in C}d(c_{1},c_{2})=\min _{c_{1},c_{2}\in C}d(c_{1}+c_{2},0)=\min _{c_{1}\in C}d(c_{1},0).}$ 

Popular notation

Codes in general are often denoted by the letter ${\displaystyle C}$ . A linear code of length ${\displaystyle n}$ , rank ${\displaystyle k}$  (ie having ${\displaystyle k}$  codewords in its basis and ${\displaystyle k}$  rows in its generating matrix) and minimum Hamming weight ${\displaystyle d}$  is referred to as an ${\displaystyle (n,k,d)}$  code.

Remark. This is not to be confused with the notation ${\displaystyle [n,r,d]}$  to denote a non-linear code of length ${\displaystyle n}$ , size ${\displaystyle r}$  (ie having ${\displaystyle r}$  codewords) and minimum Hamming distance ${\displaystyle d}$ .

Examples

Some examples of linear codes include:

• Repetition codes
• Parity codes
• Cyclic codes
• Hamming code
• Golay code, both the binary and ternary versions
• Reed-Solomon codes
• BCH code
• Reed-Muller codes
• Perfect codes

Uses

Binary linear codes (refer to formal definition above) are ubiquitous in electronic devices and digital storage media. For example the Reed-Solomon code is used to store digital data on a compact disc.

Sphere packings and lattices

Block codes are tied to the sphere packing problem which has received some attention over the years. In two dimensions, it is easy to visualize. Take a bunch of pennies flat on the table and push them together. The result is a hexagon pattern like a bee's nest. But block codes rely on more dimensions which cannot easily be visualized. The powerful Golay code used in deep space communications uses 24 dimensions. If used as a binary code (which it usually is,) the dimensions refer to the length of the codeword as defined above.

The theory of coding uses the N-dimensional sphere model. For example, how many pennies can be packed into a circle on a tabletop or in 3 dimensions, how many marbles can be packed into a globe. Other considerations enter the choice of a code. For example, hexagon packing into the constraint of a rectangular box will leave empty space at the corners. As the dimensions get larger, the percentage of empty space grows smaller. But at certain dimensions, the packing uses all the space and these codes are the so called perfect codes. There are very few of these codes.

Another item which is often overlooked is the number of neighbors a single codeword may have. Again, lets use pennies as an example. First we pack the pennies in a rectangular grid. Each penny will have 4 near neighbors (and 4 at the corners which are farther away). In a hexagon, each penny will have 6 near neighbors. When we increase the dimensions, the number of near neighbors increases very rapidly.

The result is the number of ways for noise to make the receiver choose a neighbor (hence an error) grows as well. This is a fundamental limitation of block codes, and indeed all codes. It may be harder to cause an error to a single neighbor, but the number of neighbors can be large enough so the total error probability actually suffers.