Error-correcting codes and information in biology

摘要

Shannon's channel coding theorem (1948), a major result of information theory, paradoxically states that errorless communication is possible using an unreliable channel. Since then, engineers developed many error-correcting codes and decoding algorithms. A performance close to the predicted one was eventually achieved no earlier than the beginning of the nineties. Many communication facilities would not exist without error-correcting codes, e.g., mobile telephony and terrestrial digital television. This article explains first how they work without mathematical formalism. An error-correcting code is a minority subset among some set of messages. Within this subset, the messages are sufficiently different from each other to be exactly identified even if a number of their symbols, up to a certain limit, are changed. Beyond this limit, another message can be erroneously identified. An error-correcting code is interpreted as a set of messages subjected to constraints which make their symbols mutually dependent. Although mathematical constraints are conveniently used in engineering, constraints of any other kind, possibly of natural origin, can generate error-correcting codes.