Content deleted Content added
m clean up, typo(s) fixed: Therefore → Therefore, (2) using AWB |
citing Dr David J.C. MacKay's book for "The codewords in a linear block code are blocks of symbols which are encoded using more symbols than the original value to be sent" |
||
Line 1:
In [[coding theory]], a '''linear code''' is an [[error-correcting code]] for which any [[linear combination]] of codewords is also a codeword. Linear codes are traditionally partitioned into [[block code]]s and [[convolutional code]]s, although [[turbo code]]s can be seen as a hybrid of these two types.<ref>{{cite book|title=Channel Codes: Classical and Modern|author=William E. Ryan and Shu Lin|page=4|year=2009|publisher=Cambridge University Press|isbn=978-0-521-84868-8}}</ref> 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]]s) on a [[communications channel]] 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 which are encoded using more symbols than the original value to be sent.<ref name=DrMacKayECC>{{cite book| last=MacKay | first=David, J.C.| authorlink=David J.C. MacKay| title=Information Theory, Inference, and Learning Algorithms |year=2003 | pages=540|publisher=[[Cambridge University Press]]| isbn=9780521642989|url=http://www.inference.phy.cam.ac.uk/itprnn/book.pdf | quote="In a ''linear'' block code, the extra <math>N - K</math> bits are linear functions of the original <math>K</math> bits; these extra bits are called ''parity-check bits'' (page 9)"}}</ref> A linear code of length ''n'' transmits blocks containing ''n'' symbols. For example, the [7,4,3] [[Hamming code]] is a linear [[binary code]] 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.<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-6}}</ref> This code contains 2<sup>4</sup>=16 codewords.
==Definition and parameters==
| |||