Citizendia
Your Ad Here

In mathematics and information theory, a linear code is an important type of block code used in error correction and detection schemes. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Information theory is a branch of Applied mathematics and Electrical engineering involving the quantification of Information. In Computer science, a block code is a type of Channel coding. In Mathematics, Computer science, Telecommunication, and Information theory, error detection and correction has great practical importance in Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome decoding). In Communication theory and Coding theory, decoding is the process of translating received messages into Codewords of a given Code.

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. A bit is a binary digit, taking a value of either 0 or 1 Binary digits are a basic unit of Information storage and communication Channel, in communications (sometimes called communications channel) refers to the medium used to convey Information from a 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 Telecommunication, a Hamming code is a linear Error-correcting code named after its inventor Richard Hamming. 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 size of the (7,4) Hamming code is sixteen.

Contents

Formal definition

A linear code of length n and rank k is a linear subspace C with dimension k of the vector space \mathbb{F}_q^n where \mathbb{F}_q is the finite field with q elements. The concept of a linear subspace (or vector subspace) is important in Linear algebra and related fields of Mathematics. In Mathematics, the dimension of a Vector space V is the cardinality (i In Mathematics, a vector space (or linear space) is a collection of objects (called vectors) that informally speaking may be scaled and added In Abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains only finitely many 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 respectively.

Remark: We want to give \mathbb{F}_q^n the usual standard basis because each coordinate represents a "bit" which is transmitted across a "noisy channel" with some small probability of transmission error (please see the binary symmetric channel (BSC) for more details). A binary symmetric channel (or BSC is a common Communications channel model used in Coding theory and Information theory. If some other basis is used then this BSC model cannot be used and the Hamming metric (defined next) does not measure the number of errors in transmission, as we want it to.

Properties

As a linear subspace of \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). The concept of a linear subspace (or vector subspace) is important in Linear algebra and related fields of Mathematics. In the mathematical subfield of Linear algebra, the linear span, also called the linear hull, of a set of vectors in a Vector Basis vector redirects here For basis vector in the context of crystals see Crystal structure. Linear algebra is the branch of Mathematics concerned with These basis codewords are often collated in the rows of a matrix G known as a generating matrix for the code C. In Coding theory, a generator matrix is a basis for a Linear code, generating all its possible codewords When G has the block matrix form G = (Ik | A), where Ik denotes the k \times k identity matrix and A is some k \times (n-k) matrix, then we say G is in standard form.

A matrix H : \mathbb{F}_q^n\to \mathbb{F}_q^{n-k} whose kernel is C is called a check matrix of C (or sometimes a parity check matrix). In Linear algebra, the kernel or null space (also nullspace) of a matrix A is the set of all vectors x for which In Coding theory, a parity-check matrix of a linear block code C is a Generator matrix of the Dual code. If C is a code with a generating matrix G in standard form, G = (Ik | A), then H = (-At | In-k) is a check matrix for C.

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

\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)=d.

Nearest Neighbor Algorithm

The parameter d is closely related to the error correcting ability of the code. In Mathematics, the elements or members of a set (or more generally a class) are all those objects which when collected together make up the The following construction/algorithm illustrates this (called the nearest neighbor decoding algorithm):

Input: A "received vector" v in \mathbb{F}_q^n .

Output: A codeword c in C closest to v. 

   * Enumerate the elements of the ball of (Hamming) radius t about v, denoted Bt(v), where v is the received word.  Set c="fail. 
   * For each w in Bt(v), check if w in C.  If so, put c = w and break to the next step; otherwise, discard w and move to the next element. 
   * Return c.

Note: "fail is not returned unless t> (d-1)/2. . We say that a linear C is t-error correcting if there is at most one codeword in Bt(w), for each w in \mathbb{F}_q^n.

Popular notation

Codes in general are often denoted by the letter C. In Communications a code is a rule for converting a piece of Information (for example a letter, Word, Phrase, or A linear code of length n, of rank k (i. In Mathematics, the dimension of a Vector space V is the cardinality (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, M, d) notation used to denote a non-linear code of length n, size M (i. e. , having M code words), and minimum Hamming distance d.

Singleton bound

Lemma (Singleton bound): Every linear [n,k,d] code C satisfies k+d \leq n+1.

A code C whose parameters satisfy k+d=n+1 is called maximum distance separable or MDS. Such codes, when they exist, are in some sense best possible.

If C1 and C2 are two codes of length n and if there is a permutation p in the symmetric group Sn for which (c1,. In Mathematics, the symmetric group on a set X, denoted by S X or Sym( X) is the group whose underlying . . ,cn) in C1 if and only if (cp(1),. . . ,cp(n)) in C2, then we say C1 and C2 are permutation equivalent. In more generality, if there is an n\times n monomial matrix M : \mathbf{F}_q^n\to \mathbf{F}_q^n which sends C1 isomorphically to C2 then we say C1 and C2 are equivalent. In Mathematics, a generalized permutation matrix (or monomial matrix) is a matrix with the same nonzero pattern as a Permutation matrix, i

Lemma: Any linear code is permutation equivalent to a code which is in standard form.

Examples

Some examples of linear codes include:

Uses

Binary linear codes (refer to formal definition above) are ubiquitous in electronic devices and digital storage media. Repetition code is an (r1 coding scheme that repeats the bits across a channel to achieve error free communication (r is the number of bits in each codeword for A cyclic redundancy check (CRC is a type of function that takes as input a data stream of any length and produces as output a value of a certain space commonly a 32-bit integer In Telecommunication, a Hamming code is a linear Error-correcting code named after its inventor Richard Hamming. Golay code may refer to Binary Golay code Ternary Golay code SpecialShortpages In Mathematics and Computer science, a binary Golay code is a type of Error-correcting code used in Digital communications The binary Golay code There are two closely related Error-correcting codes known as ternary Golay codes. In Coding theory, a polynomial code is a type of Linear code whose set of valid Code words consists of those Polynomials (usually of some fixed Reed-Solomon error correction is an Error-correcting code that works by Oversampling a Polynomial constructed from the data Reed-Muller codes are a family of linear Error-correcting codes used in communications In Mathematics, an algebraic geometric code (AG-code, otherwise known as a Goppa code, is a general type of Linear code constructed by using an Algebraic For example the Reed-Solomon code is used to store digital data on a compact disc. Reed-Solomon error correction is an Error-correcting code that works by Oversampling a Polynomial constructed from the data A Compact Disc (also known as a CD) is an Optical disc used to store digital data, originally developed for storing digital audio

External links

Footnotes

  1. ^ Thomas M. Cover and Joy A. Thomas (1991). Elements of Information Theory. John Wiley & Sons, Inc, 210-211.  
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic