Proofs of Existence and Optimality · Application: Error Correcting Codes (Optional)

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

In this section, we will look at an important application: error-correcting codes. While analyzing such codes, we will prove existence, correctness, and optimality. At the same time, we only briefly touch on this topic: we will see several beautiful and classical examples, but this will only be the tip of the iceberg (there are separate courses and books dedicated to error-correcting codes).

Such codes are needed so that we can recover data even when this data is somehow corrupted. The nature of the damage can be very different:

  • When transmitting data over a network, some packets may be lost or corrupted.

  • The disk on which the data is stored may be physically damaged (e.g., scratched).

  • A QR code in which the data is encoded may be smudged or poorly photographed.

In all these situations it is important for us to be able to recover the data despite possible damage. The methods of such recovery may vary. For example, if we are afraid of losing data from the disk, we can store one or several backups — and this is often done, although it is highly redundant. Or if some packets did not reach the network, we can resend them. Below we will be interested in how redundant the encoding must be so that it still allows effective error correction.