Principles of Error Correction

When considering the problem of limiting the effects of errors in information processing, the first task is to establish the properties of the physical systems that are available for representing and computing with information. Thus it is necessary to learn the following:

1.

The physical system to be used, in particular the structure of its state space.

2.

The available means for controlling this system.

3.

The type of information to be processed.

4.

The nature of the errors, that is, the error model.

With this information, the approaches used to correct errors in the three examples provided in the previous section involve the following:

1.

Determine a code, which is a subspace of the physical system that can represent the information to be processed.

2.a

Identify a decoding procedure that can restore the information represented in the code after any one of the most likely errors occurred.

2.b

Or, determine a pair of syndrome and information-carrying subsystems such that the code corresponds to a ``base'' state of the syndrome subsystem and the primary errors act only on the syndrome.

3.

Analyze the error behavior of the code and subsystem.

The tasks of determining a code and of identifying decoding procedures or subsystems are closely related. As a result, the following questions are at the foundation of the theory of error-correction: What properties must a code satisfy so that it can be used to protect well against a given error model? How does one obtain the decoding or subsystem identification that achieves this protection? In many cases, the answers can be based on choosing a fixed set of error operators that represents well the most likely errors and then determining whether these errors can be protected against without any loss of information. Once an error set is fixed, determining whether it is ``correctable'' can be cast in terms of the idea of ``detectable'' errors. This idea works equally well for both classical and quantum information. We introduce it using classical information concepts.