|
ERROR CORRECTING CODES Messages sent over electronic or other channels are prone to distortions of various sorts. Most of the time the data is stored and transmitted in bits. Distortions may cause errors and some of the bits may get inverted. Unless the received message is absurd, it is very often impossible to detect the errors. In todays information age, accuracy in transmission is vital, and so, we need a reliable method of detecting errors and, if possible, reconstructing the original message without being forced to re-send it. The transmitted information is in blocks of bits or binary digits (0 and 1). Each block is called a word. A word of length m is just a sequence of m binary digits. The set of all possible words of length m is denoted as Bm. Suppose that we wish to transmit words of length two. Each such word will be a member of the set B2 = {00,01,10,11}. (So each word could represent a direction). Now, if we transmit these words merely as they are, any error will convert one word into another. Thus errors, if they occur, cannot be detected. The way out is to attach some extra information in the form of extra digits to each word. We therefore encode each word by attaching a fixed number (three, in this example) of extra digits (called check digits or parity bits). The five digit words obtained are called codewords. It is these codewords that are transmitted.
We encode all the possible messages as follows:
The extra digits have been chosen so that any two codewords differ in at least three places (we say that the minimum distance between the codewords is three). Thus, if in transmission, one or two digits get changed, the received word is no longer one of these four codewords. Hence we can detect the occurrence of certain errors.
Further, any single error will transform the codeword into another word, differing from it in only one place but from every other codeword in at least two places. For instance, a single error converts 10110 to 11110. Note that 11110 differs from every other codeword in at least two places.
Now suppose we receive the word 11110. We correct this to the 10110 because only one error has to occur in this codeword to get the received word. On the other hand, at least two errors would have to occur in any other codeword before we get the word 11110. Since double errors are less likely to occur than single errors, we apply a general rule:
The process of obtaining the correct codeword from the received word is called error decoding. Here the original message is obtained from the corrected codeword by dropping the three check digits.
Copyright © 2022 ICICI Centre for Mathematical Sciences |
