8.11 Redundant Coding

Redundant coding is the deliberate addition of extra bits, symbols, or structural elements to a transmitted message beyond the minimum number required to represent the information, with the purpose of enabling the receiver to detect, locate, and correct errors introduced by the channel, without requiring retransmission. The fundamental trade-off in redundant coding is between code rate (the fraction of transmitted symbols that carry original information) and error correction capability (the maximum number of errors per codeword that the code can correct): lower code rates provide more redundancy and therefore greater error correction power, while higher code rates are more efficient but more vulnerable to uncorrected transmission errors. The science of redundant coding—known as coding theory or channel coding—concerns the design of coding schemes that achieve the best possible combination of these properties for a given channel.

The simplest redundant code is the repetition code: the transmitter sends each information bit multiple times, and the receiver uses majority voting to decide which bit was most likely transmitted. A triple repetition code (sending each bit three times) converts a 1-bit message into a 3-bit codeword:

If the channel introduces at most one error per 3-bit codeword, the receiver can decode correctly by choosing the bit value (0 or 1) that appears in the majority of the three received positions. The code rate is 1/3 (one information bit per three transmitted bits), and the minimum Hamming distance is 3, enabling correction of 1 error per codeword. Repetition codes are simple to understand and implement but are extremely inefficient: they spend most of their capacity on redundancy and are not used in practice for high-rate data transmission, where more sophisticated codes provide much better tradeoffs.

The Hamming (7,4) code is a historically important example of a more efficient redundant code that encodes 4 information bits into a 7-bit codeword using 3 parity check bits. The 3 parity bits are placed at positions 1, 2, and 4 of the codeword; each parity bit covers a different subset of the information bit positions and is set to make the XOR of the covered bits equal to 0. The minimum Hamming distance of the (7,4) code is 3, enabling single-error correction and double-error detection (SECDED in its extended form). The code rate is 4/7 ≈ 0.57, significantly more efficient than a triple repetition code, while providing the same single-error correction capability. The parity check matrix H for the (7,4) Hamming code satisfies:

Reed-Solomon (RS) codes are a class of redundant codes that operate on symbols rather than individual bits, making them particularly effective against burst errors. An RS(n, k) code encodes k data symbols into n codeword symbols over a finite field GF(2^m), where each symbol consists of m bits. The minimum distance of an RS code is d_min = n − k + 1, the maximum possible distance for a code with these parameters (Reed-Solomon codes are maximum distance separable, or MDS, codes). An RS(255, 223) code, for example, uses 32 redundancy bytes to encode 223 data bytes into a 255-byte codeword, correcting up to 16 symbol errors per codeword regardless of the pattern of bit errors within each corrupted symbol. RS codes are used in CD-ROM error correction, QR codes, deep-space communication (the Voyager and Cassini probes), and RAID-6 storage systems.

Convolutional codes are a class of redundant codes that do not process information in discrete blocks but as a continuous stream, using a finite-state encoder with memory: the output symbols at any time depend not only on the current input bits but also on a number of preceding input bits. The constraint length K of a convolutional code specifies how many input bits the encoder remembers; the code rate is m/n, meaning m input bits generate n output bits at each step. Convolutional codes are decoded using the Viterbi algorithm, which finds the maximum likelihood transmitted sequence by dynamic programming through the encoder's state trellis. Combined with puncturing—selectively deleting some output bits to increase the code rate—convolutional codes provide efficient, flexible redundant coding for applications from cellular voice coding (GSM, CDMA) to satellite communication.

Turbo codes and low-density parity-check (LDPC) codes are modern capacity-approaching redundant coding schemes that use iterative decoding to achieve bit error rates within a fraction of a dB of the Shannon limit. Turbo codes use two parallel convolutional encoders connected by an interleaver, and the decoder iterates between two corresponding soft-output decoders, passing reliability information (extrinsic information) between them until the estimates converge. LDPC codes use sparse parity check matrices where each bit participates in only a small number of parity checks and each check involves only a small number of bits; the iterative belief propagation decoder passes probability messages along the edges of a bipartite factor graph connecting bits to checks. Both code families allow communication systems to approach the theoretical Shannon capacity limit, enabling the high spectral efficiency needed for modern broadband wireless (LTE, 5G) and satellite communication systems.

In human communication, redundant coding is ubiquitous and serves analogous functions to formal error-correcting codes. The use of check digits—a single calculated digit appended to identification numbers such as ISBN, IBAN, national identity numbers, and credit card numbers—is a simple form of redundant coding that allows immediate detection of the most common data entry errors (single digit transpositions, single-digit substitutions) at the cost of one extra symbol per number. Aviation and military communication protocols use phonetic alphabets (Alpha, Bravo, Charlie...) and number pronunciation conventions ("niner" for 9 to distinguish it from "no" and "five" from "nine") that are explicitly designed to be maximally distinct when spoken over noisy radio channels—a form of symbol-level redundant coding that increases the Hamming distance between acoustic representations of potentially confused symbols. Legal contracts use both formal and informal redundant language ("null and void," "cease and desist," "goods and chattels") partly as a historical artifact but also because the dual expression reduces the risk that one term alone will be misinterpreted due to technical ambiguity in legal interpretation.