In
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...
, a linear code is an
error-correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea i ...
for which any
linear combination of
codewords is also a codeword. Linear codes are traditionally partitioned into
block codes and
convolutional codes, although
turbo code
In information theory, turbo codes (originally in French ''Turbocodes'') are a class of high-performance forward error correction (FEC) codes developed around 1990–91, but first published in 1993. They were the first practical codes to closely ...
s can be seen as a hybrid of these two types. Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf.
syndrome decoding).
Linear codes are used in
forward error correction and are applied in methods for transmitting symbols (e.g.,
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented a ...
s) on a
communications channel
A communication channel refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such as a radio channel in telecommunications and computer networking. A channel is used for inform ...
so that, if errors occur in the communication, some errors can be corrected or detected by the recipient of a message block. The codewords in a linear block code are blocks of symbols that 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
,4,3Hamming code
In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the s ...
is a linear
binary code
A binary code represents text, computer processor instructions, or any other data using a two-symbol system. The two-symbol system used is often "0" and "1" from the binary number system. The binary code assigns a pattern of binary digits, als ...
which represents 4-bit messages using 7-bit codewords. Two distinct codewords differ in at least three bits. As a consequence, up to two errors per codeword can be detected while a single error can be corrected.
This code contains 2
4=16 codewords.
Definition and parameters
A linear code of length ''n'' and dimension ''k'' is a
linear subspace ''C'' with
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coor ...
''k'' of the
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but ...
where
is the
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subt ...
with ''q'' elements. Such a code is called a ''q''-ary code. If ''q'' = 2 or ''q'' = 3, the code is described as a binary code, or a ternary code respectively. The vectors in ''C'' are called ''codewords''. The size of a code is the number of codewords and equals ''q''
''k''.
The weight of a codeword is the number of its elements that are nonzero and the distance between two codewords is the
Hamming distance between them, that is, the number of elements in which they differ. The distance ''d'' of the linear code is the minimum weight of its nonzero codewords, or equivalently, the minimum distance between distinct codewords. A linear code of length ''n'', dimension ''k'', and distance ''d'' is called an
'n'',''k'',''d''code (or, more precisely,
code).
We want to give
the standard basis because each coordinate represents a "bit" that is transmitted across a "noisy channel" with some small probability of transmission error (a
binary symmetric channel). If some other basis is used then this model cannot be used and the Hamming metric does not measure the number of errors in transmission, as we want it to.
Generator and check matrices
As a
linear subspace of
, the entire code ''C'' (which may be very large) may be represented as the
span
Span may refer to:
Science, technology and engineering
* Span (unit), the width of a human hand
* Span (engineering), a section between two intermediate supports
* Wingspan, the distance between the wingtips of a bird or aircraft
* Sorbitan es ...
of a set of
codewords (known as a
basis in
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matric ...
). These basis codewords are often collated in the rows of a matrix G known as a
generating matrix for the code ''C''. When G has the block matrix form