1 - Error-correcting Codes

Summary

The idea of redundant information is a well-known phenomenon in reading a newspaper. Misspellings usually go unnoticed for a casual reader, while the meaning is still grasped. In Semitic languages such as Hebrew, and even older in the hieroglyphics in the tombs of the pharaohs of Egypt, only the consonants are written while the vowels are left out so that we do not know for sure how to pronounce these words nowadays. The letter “e” is the most frequent occurring symbol in the English language, and leaving out all these letters would still give in almost all cases an understandable text to the expense of greater attention of the reader.

The science of deleting redundant information in a clever way such that it can be stored in less memory or space and still can be expanded to the original message is called data compression or source coding. It is not the topic of this book. So we can compress data, but an error made in a compressed text would give a different message that is most of the time utterly meaningless.

The idea in error-correcting codes is the converse. One adds redundant information in such a way that it is possible to detect or even correct errors after transmission. In radio contacts between pilots and radar controls the letters in the alphabet are spoken phonetically as “Alpha, Bravo, Charlie, …” but “Adams, Boston, Chicago, …” is more commonly used for spelling in a telephone conversation. The addition of a parity check symbol enables one to detect an error, such as on the former punch cards that were fed into a computer, in the ISBN code for books, the European Article Numbering (EAN) and the Universal Product Code (UPC) for articles. Error-correcting codes are common in numerous modern applications where data are required to be stored, processed and transmitted in a reliable manner, such as in audiovisual media, quick response (QR) codes, fault-tolerant computer systems and deep space telecommunication, to name but a few.

In this chapter, we present an introduction to error-correcting codes focusing on the most commonly used codes, namely, block codes and linear codes, including fundamental concepts and procedures for code construction, encoding and decoding.