Section 1. An Introduction to Coding

Richard W. Hamming's encounter with the Bell Telephone Laboratories' mechanical relay computer in 1947 (quoted in the Preface) initiated what has come to be known as coding theory. In this chapter we will trace these origins of coding theory and develop enough of the theory itself to prepare for Leech's work in sphere packing which appears in Chapter 2.

Communication is imperfect. Even if a message is accurately stated, it may be garbled during transmission; and the consequences of a mistake in the interpretation of a financial, diplomatic, military or other message may be unfortunate. (Hamming's work was goaded by mistakes which occurred internally in a computer.) As a result, when a message travels from an information source to a destination, both the sender and the receiver would like assurance that the received message either is free of errors or, if it contains errors, those errors will be detectable. Ideally, in case an error is detected, the receiver would like to be able to correct it and recover the original message.

Our interest will lie mainly in the transmission of strings of 0's and 1's of length n, which are called (binary) n-blocks. This may, at first glance, seem an artificial restriction. But in fact the entire twenty-six letters of the alphabet can be coded using 5-blocks since there are thirty-two arrangements of five 0's and 1's.