Linear code: Difference between revisions

Revision as of 23:53, 21 June 2007

Revision as of 00:21, 22 June 2007

Line 1:

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., [[binary|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 32 bits per block.<ref name="Cover_and_Thomas">{{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}}</ref> As there are sixteen (16) distinct 4-bit values expressed in binary, the ''rank'' of the (7,4) Hamming code is sixteen.

==Formal definition==