Linear code

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.cite book|title=Elements of Information Theory|author=Thomas M. Cover and Joy A. Thomas|pages=210-211|year=1991|publisher=John Wiley & Sons, Inc|ISBN=0-471-06259-5] As there are sixteen (16) distinct 4-bit values expressed in binary, the "size" 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 mathbb{F}_q^n where 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 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). 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). 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 G = (Ik | A), where Ik denotes the k imes k identity matrix and A is some k imes (n-k) matrix, then we say G is in standard form.

A matrix H : mathbb{F}_q^n o mathbb{F}_q^{n-k} whose kernel is C is called a check matrix of C (or sometimes a parity check matrix). 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 "c"0 and the other codewords "c" ≠ "c"0 is constant. Since the difference "c" − "c"0 of two codewords in "C" is also a codeword (i.e., an element of the subspace "C"), and "d"("c", c0) = "d"("c" − "c"0, 0), we see that

:min_{c in C, c eq c_0}d(c,c_0)=min_{c in C, c eq c_0}d(c-c_0, 0)=min_{c in C, c eq 0}d(c, 0)=d.

Nearest Neighbor Algorithm

The parameter d is closely related to the error correcting ability of the code. 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". 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", "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".

ingleton 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,...,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 imes n monomial matrix M : mathbf{F}_q^n o mathbf{F}_q^n which sends C1 isomorphically to C2 then we say C1 and C2 are equivalent.

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

Examples

Some examples of linear codes include:


* Repetition codes
* Parity codes
* Cyclic codes
* Hamming codes
* Golay code, both the binary and ternary versions
* Polynomial codes, of which BCH codes are an example
* Reed-Solomon 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

* [http://jason.mchu.com/QCode/index.html q-ary Code Generator Program]
* [http://ipsit.bu.edu/comp.html 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.
* [http://www.codetables.de/ Code Tables: Bounds on the parameters of various types of codes] , "IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)] ". Online, up to date table of the optimal binary codes, includes non-binary codes.

Footnotes


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Code coverage — is a measure used in software testing. It describes the degree to which the source code of a program has been tested. It is a form of testing that inspects the code directly and is therefore a form of white box testing.[1] Code coverage was among …   Wikipedia

  • Linear (disambiguation) — Definition: The word linear comes from the Latin word linearis, which means created by lines. Usage in mathematics: * Linear, a property; * Linear code; * Linear equation; * Linear function; * Linear programming, a type of optimization problem; * …   Wikipedia

  • Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia

  • Code-excited linear prediction — (CELP) is a speech coding algorithm originally proposed by M.R. Schroeder and B.S. Atal in 1985. At the time, it provided significantly better quality than existing low bit rate algorithms, such as residual excited linear prediction and linear… …   Wikipedia

  • Linear timecode — Linear (or Longitudinal) Timecode (LTC) encodes SMPTE timecode data as a Manchester Biphase encoded audio signal. The audio signal is commonly recorded on a VTR track or other storage media. Each frame is terminated by a sync word which has a… …   Wikipedia

  • Code excited linear prediction — (CELP) is a speech coding algorithm originally proposed by M.R. Schroeder and B.S. Atal in 1985. At the time, it provided significantly better quality than existing low bit rate algorithms, such as RELP and LPC vocoders (e.g. FS 1015). Along with …   Wikipedia

  • Code-book Excited Linear Prediction — Code( book) Excited Linear Prediction (CELP) ist ein hybrides Audiokompressionsverfahren, das die Vorteile der Signalformkodierung mittels Vektorquantisierung und der parametrischen Verfahren vereint. Das Ergebnis ist eine gute Sprachqualität,… …   Deutsch Wikipedia

  • Code Excited Linear Prediction — Code( book) Excited Linear Prediction (CELP) ist ein hybrides Audiokompressionsverfahren, das die Vorteile der Signalformkodierung mittels Vektorquantisierung und der parametrischen Verfahren vereint. Das Ergebnis ist eine gute Sprachqualität,… …   Deutsch Wikipedia

  • Linear discriminant analysis — (LDA) and the related Fisher s linear discriminant are methods used in statistics, pattern recognition and machine learning to find a linear combination of features which characterize or separate two or more classes of objects or events. The… …   Wikipedia

  • Linear pulse code modulation — (LPCM) is a method of encoding audio information digitally. The term also refers collectively to formats using this method of encoding. The term PCM, though strictly more general, is often used to describe data encoded as LPCM. Description LPCM… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”