4.5 BLOCK CODES

The repetition code introduced in the previous section demonstrated the fundamental principle of channel coding: by adding redundancy, transmission errors can be detected and corrected. Although repetition codes are conceptually simple, they are highly inefficient because they require large amounts of additional bandwidth or transmission time to achieve relatively modest improvements in reliability. Practical communication systems therefore employ much more sophisticated coding techniques that provide significantly greater error protection while introducing far less redundancy.

One of the earliest and most important families of error-control codes is the block code. Rather than treating each transmitted bit independently, a block code processes groups of information bits as a single unit. Each block of source data is transformed into a longer coded block by adding carefully selected redundancy according to well-defined mathematical rules. The resulting redundancy is far more efficient than simple repetition because every parity bit contributes simultaneously to the protection of multiple information bits.

The principal advantage of block coding is that the encoding and decoding processes are performed independently for each block of data. This simplifies both the mathematical analysis and the implementation of practical systems. By carefully selecting the relationships between the information bits and the parity bits, engineers can design codes capable of detecting or correcting predictable numbers of transmission errors while using relatively little additional bandwidth. Many of the most influential developments in coding theory—including Hamming code (Section 4.5.10.1), cyclic redundancy check (CRC) codes (Section 4.5.10.2), BCH codes (Section 4.5.10.3), Golay codes (Section 4.5.10.4), and Reed–Solomon codes (Section 4.5.10.5)—are based on the principles of block coding.

Block codes remain widely used because they combine strong error-control capability with relatively straightforward implementation. They are found in computer memories, data-storage devices, optical media, digital broadcasting, wireless networks, satellite communications, mobile systems, and numerous computer communication protocols. Even many modern coding schemes incorporate block-coding concepts as part of more sophisticated compound coding structures.

In a block code, the source data is divided into fixed-length blocks of k bits. The encoder translates each k-bit input block into an n-bit output block, where n > k, by adding (r = n-k) redundant bits, also called parity-check bits or simply parity bits. The resulting n-bit output sequence is called a codeword.

A linear block code is one in which the modulo-2 sum (exclusive-OR)—see Appendix E—of any two valid codewords is itself a valid codeword. This property, known as closure, makes linear codes especially useful for algebraic manipulation and for the design of efficient decoders.

A block code is commonly denoted by (n,k) and the code rate is given by k/n. Typical practical code rates range from approximately 1/4 to 7/8, with block lengths ranging from only a few bits to many hundreds or even thousands of bits, depending on the application and the desired balance between reliability, latency, complexity, and bandwidth efficiency.

At the receiver, the decoder attempts to recover the original information from the received codeword. In doing so, it generates a syndrome—a pattern that indicates whether errors have occurred and, where the code permits, helps identify their location (the term syndrome is borrowed from medicine, where it refers to a characteristic pattern of symptoms associated with a disease).

In the following sections we examine the principal concepts that determine the performance of block codes, beginning with the concept of Hamming distance. Richard W. Hamming (1918–1998), a colleague of Claude Shannon, introduced the first practical error-correcting block codes in 1950. His work demonstrated how carefully chosen parity relationships could detect and correct transmission errors efficiently, laying the foundation for much of modern coding theory.

The effectiveness of any block code depends not simply on the number of parity bits that are added, but on how those parity bits are chosen. This relationship is captured by the concept of Hamming distance, which provides the principal measure of a code's error-control capability.