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).

Linear codes are applied in methods of transmitting symbols (e.g., bits) on a communications channel so that, if errors occur in the communication, some errors can be detected by the recipient of a message block. The "codes" in the linear code are blocks of symbols which are encoded using more symbols than the original value to be sent. A linear code of length n transmits blocks containing n symbols. For example, the "(7,4)" Hamming code is a binary linear code which represents 4-bit values each using 7-bit values. In this way, the recipient can detect errors as severe as 2 bits per block.^[1] As there are sixteen (16) distinct 4-bit values expressed in binary, the rank of the (7,4) Hamming code is sixteen.

Formal definition

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

Properties

As a linear subspace of ${\displaystyle \mathbb {F} _{q}^{n}}$ , the entire code C (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 C.

The subspace definition also guarantees that the minimum Hamming distance d between any given codeword c₀ and the other codewords c ≠ c₀ is constant. Since the difference c − c₀ of two codewords in C is also a codeword (i.e., an element of the subspace C), and d(c, c₀) = d(c − c₀, 0), we see that

${\displaystyle \min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,c\neq 0}d(c,0).}$ 

Popular notation

Codes in general are often denoted by the letter C. A linear code of length n, of rank k (i.e., having k code words in its basis and k rows in its generating matrix), and of minimum Hamming weight d is referred to as an (n, k, d) code.

Remark. This (n, k, d) notation should not be confused with the [n, r, d] notation used to denote a non-linear code of length n, size r (i.e., having r code words), and minimum Hamming distance d.

Examples

Some examples of linear codes include:

• Repetition codes
• Parity codes
• Cyclic codes
• Hamming codes
• Golay code, both the binary and ternary versions
• Reed-Solomon codes
• BCH codes
• Reed-Muller codes
• Goppa 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.

External links

• q-ary Code Generator Program
• Compute parameters of linear codes - an on-line interface for generating and computing parameters (e.g. minimum distance, covering radius) of linear error-correcting codes.

Footnotes

1. Thomas M. Cover and Joy A. Thomas (1991). Elements of Information Theory. John Wiley & Sons, Inc. pp. 210–211. ISBN 0-471-06259-5. {{cite book}}: Check |isbn= value: checksum (help)