Concepts and Examples

Communication is the prototypical application of error-correction methods. To communicate, a sender needs to convey information to a receiver over a noisy ``communication channel''. Such a channel can be thought of as a means of transmitting an information-carrying physical system from one place to another. During transmission, the physical system is subject to disturbances that can affect the information carried. To use a communication channel, the sender needs to ``encode'' the information to be transmitted in the physical system. After transmission, the receiver ``decodes'' the information. The procedure is shown in Fig. 1.

FIG. 1: A typical application of error-correction methods: The illustration shows the three main steps required for communication. Information is first encoded in a physical system, then transmitted over the noisy communication channel and finally decoded. The combination of encoding and decoding is chosen so that errors have no effect on the transmitted information.

The protection of stored information is an other important application of error-correction methods. In this case, the user encodes the information in a storage system and retrieves it at a later time. Provided that there is no communication from the receiver to the sender, any error-correction method applicable to communication is also applicable to storage and vice versa. In Sect. 7 we discuss the problem of fault-tolerant computation, which requires enhancing error-correction methods in order to enable applying operations to encoded information without losing protection against errors.

To illustrate the different features of error-correction methods we consider three examples. We begin by describing them for classical information, but in each case, there is a quantum analogue that will be introduced later.