Error-Correcting Codes--A Linear Programming Approach

This paper is concerned with the problem of transmitting binary signals over a noisy channel. Some situations in which this problem occurs are: when telephone lines are being used to transmit data in binary form; when an imperfect medium such as magnetic tape or a photographic emulsion is used to store binary data; or when operations on binary signals are being carried out by means of circuits constructed of devices such as relays, diodes or transistors, which have a probability of error. It has been shown by Shannon 1 that it is possible to add redundant bits to the transmitted messages so as to reduce the probability of error in the received messages to an arbitrarily small quantity. Since Shannon did not exhibit efficient codes for achieving this reduction in error probability, considerable attention has been devoted to the search for useful coding schemes. The usefulness of a coding scheme is determined by the number of redundant bits that must be added, by the complexity of the equipment required for inserting the redundant bits before transmission and for removing the redundant bits and correcting errors after transmission, and by the error-correcting capabilities. 1485