Block code: Difference between revisions

Revision as of 21:53, 2 April 2009

Revision as of 05:06, 9 April 2009

Line 1:

In [[computer science]], a '''block code''' is a type of [[channel coding]]. It adds [[redundancy (information theory)|redundancy]] to a message so that, at the receiver, one can decode with minimal (theoretically zero) errors, provided that the [[information rate]] (amount of transported [[information]] in [[bit]]s per sec) would not exceed the [[channel capacity]].

The main characterization of a block code is that it is a ''fixed length'' channel code (unlike source coding schemes such as [[Huffman coding]], and unlike channel coding methods like [[convolutional code|convolutional encoding]]). Typically, a block code takes a ''k''-digit information word, ''s,'' and transforms this into an ''n''-digit codeword, ''C(s).'' The '''block length''' of such a code would be ''n''.

Block coding was the primary type of [[channel coding]] used in earlier [[mobile communication]] systems.

Line 10:

:<math>C(W) = C(s_{k_1})C(s_{k_2})\ldots C(s_{k_m})</math>.

== A[n,d] ==

The trade-off between efficiency (large information rate) and correction capabilities can also be seen from the attempt to, given a fixed codeword length and a fixed correction capability (represented by the [[Hamming distance]] d) maximize the total amount of codewords. ''A[n,d]'' is the maximum number of codewords for a given codeword length n and Hamming distance d.

== Information rate ==

When <math>C</math> is a binary block code, consisting of <math>A</math> codewords of length ''n'' bits, then the information rate of <math>C</math> is defined as

Line 22:

:<math>\frac{\!log_{2}(2^k)}{n}=\frac{k}{n}</math>.

== Sphere packings and lattices ==

Block codes are tied to the [[sphere packing problem]] which has received some attention over the years. In two dimensions, it is easy to visualize. Take a bunch of pennies flat on the table and push them together. The result is a hexagon pattern like a bee's nest. But block codes rely on more dimensions which cannot easily be visualized. The powerful Golay code used in deep space communications uses 24 dimensions. If used as a binary code (which it usually is,) the dimensions refer to the length of the codeword as defined above.

Line 36:

total error probability actually suffers.

== References ==

{{refimprove|date=September 2008}}

* {{cite book | author=J.H. van Lint | authorlink=Jack van Lint | title=Introduction to Coding Theory | edition=2nd ed | publisher=Springer-Verlag | series=[[Graduate Texts in Mathematics|GTM]] | volume=86 | date=1992 | isbn=3-540-54894-7 | page=31 }}

Line 47:

[[es:Códigos de bloque]]

[[ja:ブロック符号]]

[[ru:Блочный код]]