An Introduction to Information Theory by John R. Pierce

Author:John R. Pierce
Language: eng
Format: epub, mobi, pdf
ISBN: 9780486134970
Publisher: Dover Publications
Published: 2012-07-17T16:00:00+00:00

Fig. VIII-5

Codes can be devised which can be used to correct larger numbers of errors in a block of transmitted characters. Of course, more check digits are needed to correct more errors. A final code, however we may devise it, will consist of some set of 2M blocks of 0’s and 1’s representing all of the blocks of digits M digits long which we wish to transmit. If the code were not error correcting, we could use a block just M digits long to represent each block of M digits which we wish to transmit. We will need more digits per block because of the error-correcting feature.

When we receive a given block of digits, we must be able to deduce from it which block was sent despite some number n of errors in transmission (changes of 0 to 1 or 1 to 0). A mathematician would say that this is possible if the distance between any two blocks of the code is at least 2n + 1.

Here distance is used in a queer sense indeed, as defined by the mathematician for his particular purpose. In this sense, the distance between two sequences of binary digits is the number of 0’s or 1’s that must be changed in order to convert one sequence into the other. For instance, the distance between 0 0 1 0 and 1111 is 3, because we can convert one sequence into the other only by changing three digits in one sequence or in the other.

When we make n errors in transmission, the block of digits we receive is a distance n from the code word we sent. It may be a distance n digits closer to some other code word. If we want to be sure that the received block will always be nearer to the correct code word, the one that was sent, than to any other code word, then the distance from any code word to any other code word must be at least 2n + 1.

Thus, one problem of block coding is to find 2M equal length code words (longer than M binary digits) that are all at least a distance 2n + 1 from one another. The code words must be as short as possible. The codes of Hamming and Golay are efficient, and other efficient codes have been found.

Another problem of block coding is to provide a feasible scheme for encoding and, especially, for decoding. Simply listing code words won’t do. The list would be too long. Encoding blocks of 20 binary digits (M = 20) requires around a million code words. And, finding the code word nearest to some received block of digits would take far too long.

Algebraic coding theory provides means for coding and decoding with the correction of many errors. Slepian was a pioneer in this field and important contributors can be identified by the names of types of algebraic codes: Reed-Solomon codes and Bose-Chaudhuri-Hocquenghem codes provide examples. Elwin Berlekamp contributed greatly to mathematical techniques for calculating the nearest code word more simply.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.