4.2.1 Redundancy And Codewords

In digital communication, redundancy is introduced deliberately by restricting transmission to a carefully selected subset of all possible bit sequences. This subset is called a code, and each permitted sequence within it is called a codeword.

Without redundancy, every possible bit sequence is valid. In that case, a corrupted message is indistinguishable from a legitimate one. For example, if all eight possible three-bit combinations are valid, the received sequence "101" cannot be checked for error because every three-bit pattern is acceptable. There is no basis upon which the receiver can determine whether an error has occurred.

By contrast, if only a subset of sequences is permitted, then any received sequence lying outside that subset immediately indicates that an error has occurred. Channel coding therefore transforms the communication problem from transmitting arbitrary bit patterns to transmitting only carefully selected, mathematically related patterns.

As a simple example, suppose only the four codewords 00000, 00111, 11001 and 11110 are permitted. Although there are (2⁵ = 32) possible five-bit sequences, only four are considered valid. If the receiver obtains the sequence 01011, it can immediately conclude that an error has occurred because the received sequence is not one of the permitted codewords.

The receiver must then determine which valid codeword was most likely transmitted. This is accomplished by comparing the received sequence with every valid codeword and selecting the one that differs in the fewest bit positions. The underlying assumption is that only a small number of bits are likely to have been corrupted during transmission.

The effectiveness of a code therefore depends not simply on the amount of redundancy that is added, but on how the codewords are arranged within the space of all possible bit sequences. Ideally, valid codewords should be separated by as many differing bits as possible. The greater the separation, the more errors can occur before one valid codeword is mistaken for another.

An intuitive way to visualize this is to imagine every possible n-bit sequence occupying a point within an n-dimensional “code space”. The valid codewords occupy only a small fraction of these points. During transmission, noise may move the received sequence away from the transmitted codeword by changing one or more bits. If the codewords are widely separated, small movements caused by noise are unlikely to carry the received sequence into the neighbourhood of another valid codeword. Instead, the receiver can correctly identify the nearest valid codeword and thereby recover the original message.

This geometric interpretation forms the basis of almost all modern channel coding. Whether the code is a simple parity check, a Hamming code, a Reed–Solomon code, a convolutional code, an LDPC code, or a polar code, the underlying objective is essentially the same: arrange valid codewords so that they are sufficiently far apart for the receiver to distinguish them reliably in the presence of noise.

The measure used to quantify the separation between codewords is called the Hamming distance. Because it is so fundamental to channel coding, it is introduced in the next section.