Overview

Information media, such as communication systems and storage devices of data, are not absolutely reliable in practice because of noise or other forms of introduced interference. One of the tasks in coding theory is to detect, or even correct, errors. Usually, coding is defined as source coding and channel coding. Source coding involves changing the message source to a suitable code to be transmitted through the channel. An example of source coding is the ASCII code, which converts each character to a byte of 8 bits. A simple communication model can be represented by Fig. 1.1.

Fig. 1.1

Example 1.0.1

Consider the source encoding of four fruits, apple, banana, cherry, grape, as follows:

Suppose the message apple , which is encoded as 00, is transmitted over a noisy channel. The message may become distorted and may be received as 01 (see Fig. 1.2). The receiver may not realize that the message was corrupted. This communication fails.

Fig. 1.2

The idea of channel coding is to encode the message again after the source coding by introducing some form of redundancy so that errors can be detected or even corrected. Thus, Fig. 1.1 becomes Fig. 1.3.

Fig. 1.3

Example 1.0.2

In Example 1.0.1, we perform the channel encoding by introducing a redundancy of 1 bit as follows:

Suppose that the message apple , which is encoded as 000 after the source and channel encoding, is transmitted over a noisy channel, and that there is only one...