Error-Control Coding

Introduction and Context

A digital communication system is never perfectly reliable. Thermal noise, interference, fading, nonlinear distortion, synchronization errors, and hardware limitations can alter transmitted symbols. Error-control coding improves reliability by adding structured redundancy to the information before transmission. The receiver uses this redundancy to detect or correct errors.

Coding is therefore a central design mechanism for trading data rate and bandwidth against reliability, delay, energy, and implementation complexity. In modern systems, coding is used in optical fibre links, satellite communication, cellular networks, wireless local-area networks, storage devices, and deep-space communication.

The fundamental distinction is between error detection, in which the receiver identifies that a codeword is corrupted, and error correction, in which it estimates the transmitted codeword. Automatic repeat request (ARQ) uses detection followed by retransmission; forward error correction (FEC) corrects errors without retransmission. Hybrid ARQ combines both approaches.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Explain redundancy, code rate, Hamming distance, and minimum distance.
2. Derive the principal bounds for error detection and correction.
3. Analyse block codes, cyclic codes, convolutional codes, and modern capacity-approaching codes.
4. Apply parity checks, syndrome decoding, CRCs, and Viterbi decoding.
5. Compare ARQ, FEC, and hybrid strategies using reliability, delay, and throughput considerations.
6. Evaluate coding schemes for practical communication channels and recognize their limitations.

1. Fundamental Coding Model

Let a message contain k information bits. An encoder maps it into an n-bit codeword. The code is therefore an (n,k) code, and its code rate is

where R is dimensionless and satisfies 0 < R ≤ 1. The remaining n-k bits are redundancy bits. A lower rate generally permits stronger error protection but increases bandwidth, transmission time, or required signal energy per information bit.

For a binary block code, the Hamming weight w_H(c) of a binary vector c is the number of ones in it. The Hamming distance between two vectors is

where ⊕ denotes bitwise exclusive OR. The minimum distance of a code is

The minimum distance determines worst-case error performance under hard-decision decoding. A code can detect up to d_min-1 errors in every codeword. It can correct up to

errors in every codeword, provided nearest-neighbour decoding is used and the received word is within the guaranteed correction radius.

These are guaranteed bounds, not necessarily average performance. If more errors occur, decoding may fail or may produce an undetected, incorrect codeword.

Linear Block Codes

A binary linear (n,k) code is a k-dimensional subspace of the vector space of all n-bit vectors. It is described by a generator matrix G and a parity-check matrix H. If the message is represented by a row vector m, encoding is

All operations are over the binary field GF(2), so addition is modulo 2. A valid codeword satisfies

For a received vector r = c ⊕ e, the syndrome is

where e is the error pattern. The syndrome depends on the error, not directly on the transmitted codeword. A syndrome table can map likely syndromes to error patterns.

A systematic code places the information bits explicitly in the codeword, commonly in the form c = [m p], where p contains parity bits. Systematic form is convenient for implementation, although nonsystematic codes can have identical distance properties.

2. Error Detection and Retransmission

Parity Checks

A single parity bit makes the total number of ones even or odd. Even parity detects every odd number of bit errors but cannot detect an even number of errors. Thus, parity is simple but weak for burst and multiple random errors.

A two-dimensional parity scheme arranges bits in rows and columns and adds parity to both dimensions. It can locate many single-bit errors at the intersection of a failed row and column, although some multiple-error patterns remain undetected.

Cyclic Redundancy Check

A CRC treats a bit sequence as a polynomial over GF(2). Let the transmitted polynomial be T(x), the message be M(x), and the generator polynomial be G(x) of degree r. The CRC encoder forms

where P(x) is the remainder obtained when x^rM(x) is divided by G(x) modulo 2. Consequently,

The receiver divides the received polynomial by G(x). A nonzero remainder indicates an error. The CRC does not normally correct errors; it detects them with a probability determined by the generator and error model.

For a well-selected generator polynomial, all single-bit errors are detected if G(x) has at least two nonzero terms. All burst errors of length no greater than r are detected. For longer random error patterns, the undetected-error probability is approximately 2^-r, assuming uniformly distributed error patterns and suitable generator properties. This approximation is not a universal guarantee.

ARQ Protocols

In stop-and-wait ARQ, the sender transmits a frame and waits for an acknowledgement. A negative acknowledgement or timeout causes retransmission. Go-back-N permits several outstanding frames but retransmits from the first missing frame. Selective-repeat ARQ retransmits only frames believed to be lost or corrupted.

ARQ is bandwidth-efficient when the channel is usually reliable and feedback delay is small. It performs poorly on long-delay links, rapidly varying channels, and applications that cannot tolerate retransmission delay. Sequence numbers, timers, acknowledgements, and duplicate suppression are essential for correctness.

3. Classical Error-Correcting Codes

Hamming Codes

A binary Hamming code places parity bits at positions that are powers of two. A Hamming code with m parity bits has length

and dimension

Its minimum distance is three, so it corrects one bit error and detects two errors. The parity-check syndrome identifies the position of a single erroneous bit.

For example, the (7,4) Hamming code uses four information bits and three parity bits. It has rate 4/7 and can correct one error per seven-bit codeword. If stronger detection is needed, an overall parity bit produces an extended Hamming code with minimum distance four. Such a code corrects one error and detects up to three errors, but it does not correct two errors.

Reed–Solomon Codes

Reed–Solomon (RS) codes operate on symbols rather than individual bits. An (n,k) RS code over GF(q) has minimum distance

and corrects up to

symbol errors. Here a symbol is an element of the finite field, often an 8-bit byte. RS codes are particularly effective against burst errors because a burst affecting several bits may correspond to only a few corrupted symbols. They are used in optical media, digital broadcasting, and concatenated coding systems.

The Singleton bound states that any (n,k,d) code satisfies

Codes attaining this bound are called maximum-distance separable codes; Reed–Solomon codes are important examples under their field-size constraints.

BCH Codes

Bose–Chaudhuri–Hocquenghem codes are cyclic algebraic codes designed to provide a specified minimum distance. They offer flexible binary and nonbinary constructions and support algebraic decoding. Their advantages include predictable distance and structured implementation; their disadvantages include decoder complexity and less favourable performance than modern soft-decision codes at comparable rates in many applications.

4. Convolutional Codes and Trellis Decoding

A block encoder processes a finite message block. A convolutional encoder instead produces output symbols continuously from current and previous input bits. Its memory creates a trellis of states. A rate-k/n convolutional code produces n output bits for every k input bits, often with termination bits that return the encoder to a known state.

The Viterbi algorithm performs maximum-likelihood sequence decoding on the trellis. It assigns a path metric to each candidate path and retains the best path entering each state. For hard decisions, the metric is usually Hamming distance; for soft decisions, it is related to Euclidean distance or log-likelihood.

For a memoryless binary symmetric channel with crossover probability p, maximum-likelihood decoding selects the codeword nearest to the received sequence in Hamming distance. For an additive white Gaussian noise channel, soft information is more valuable because the magnitude of the received sample indicates confidence. A decoder that uses soft metrics generally outperforms one restricted to hard decisions, at the cost of quantization and computational complexity.

5. Turbo, LDPC, and Polar Codes

Turbo Codes

Turbo codes use two or more recursive systematic convolutional encoders separated by an interleaver. Iterative decoders exchange extrinsic information between component decoders. Their performance can approach the Shannon limit, but error floors, interleaver design, latency, and iterative complexity must be considered.

LDPC Codes

Low-density parity-check codes are defined by sparse parity-check matrices. Their Tanner graphs contain variable nodes and check nodes. Iterative belief-propagation or min-sum decoding passes reliability messages between these nodes.

For a binary-input additive white Gaussian noise channel, the received log-likelihood ratio for a bit can be written as

where y is the received observation. The exact expression depends on signal mapping and noise variance. In iterative decoding, these likelihoods are combined with messages generated by parity constraints.

LDPC codes provide excellent performance and parallelizable decoding. However, short cycles in the Tanner graph can reduce iterative-decoding effectiveness, and finite block length may produce an error floor. Hardware design must address memory access, routing, power, and latency.

Polar Codes

Polar codes exploit channel polarization: a transform creates synthetic bit channels that become either highly reliable or highly unreliable as block length increases. Information bits are placed in reliable positions, while frozen bits occupy unreliable positions. Successive-cancellation decoding is simple, whereas list decoding with a cyclic redundancy check substantially improves finite-length performance. Polar codes are important in control-channel components of contemporary cellular standards.

6. Shannon Perspective and Performance Measures

For a discrete memoryless channel, reliable communication is theoretically possible when the information rate is below channel capacity. For a binary symmetric channel with crossover probability p, capacity in bits per channel use is

where

is the binary entropy function, with 0 ≤ p ≤ 1. At p=0, capacity is one bit per use; at p=0.5, capacity is zero. Shannon’s theorem does not specify a practical finite-length code or decoder; it establishes an asymptotic limit.

Important engineering measures include:

• Bit-error rate (BER): erroneous bits divided by transmitted bits.
• Frame-error rate (FER): erroneous or undecodable frames divided by transmitted frames.
• Packet-error rate (PER): corrupted packets divided by transmitted packets.
• Code rate: information bits per coded channel bit.
• Coding gain: reduction in required signal-to-noise ratio for a specified error rate, relative to an uncoded reference.
• Latency: time from information availability to successful decoding.
• Throughput: successfully delivered information per unit time.

Energy efficiency is often described using E_b/N₀, the energy per information bit divided by one-sided noise spectral density. Coding changes the relation between energy per coded symbol and energy per information bit because redundancy changes the number of transmitted symbols.

7. Worked Example: Syndrome Decoding

Consider a binary linear code with parity-check matrix

Suppose the transmitted codeword is corrupted in position 3, so the error vector is e = (0,0,1,0). The syndrome is the third column of H:

A syndrome table containing this column identifies position 3 as the likely error location. The decoder flips the third received bit. This procedure is valid when the code is designed for single-error correction and the received word contains no more errors than the guaranteed correction capability.

8. Worked Design Example: Choosing Redundancy

An engineer must protect 1000 information bits against a channel whose independent bit-error probability is approximately 10^-3. A single parity bit is inadequate because it detects only odd-weight errors and cannot correct them. A Hamming-type code can correct one error, but its guaranteed capability does not address multiple errors in the block. A practical design might use a concatenated or LDPC code with interleaving and soft-decision decoding.

The design process is not simply “choose the largest redundancy.” The engineer must specify target FER, block length, available E_b/N₀, decoder throughput, latency, and whether retransmission is possible. Simulation or density-evolution analysis is then used to select a code and operating point. This illustrates a central principle: code selection is a system optimization problem, not an isolated algebraic decision.

9. Applied Case: Reliable Telemetry over a Fading Satellite Link

Background

Consider an illustrative satellite telemetry link carrying spacecraft health data. The return path has long propagation delay, intermittent fading, and limited transmitter power. Retransmission is undesirable because a delayed control response may have operational consequences.

Problem

The link must maintain low frame-error probability while preserving battery life. Fading produces bursts of errors rather than independent isolated errors, so a code optimized only for random errors may perform poorly.

Analysis

An FEC architecture is preferable to pure ARQ. A strong outer Reed–Solomon code can correct symbol-level bursts, while an inner LDPC or convolutional code handles random errors and provides soft-decision gain. An interleaver spreads a burst across multiple codewords, converting a concentrated disturbance into approximately independent errors from the decoder’s perspective. Pilot symbols and channel estimation provide reliability information for soft decoding.

Approach and Outcome

The system can use adaptive coding and modulation. Under favourable channel conditions it selects a higher-rate code to increase throughput; during fading it selects a lower-rate code or repeats critical control frames. Telemetry packets include a CRC so that undetected residual errors are rejected. The transmitter and receiver maintain synchronized mode information, and conservative fallback rules protect against mode-decision errors.

Learning Points

The case demonstrates that coding, interleaving, modulation, channel estimation, packetization, and link control must be designed together. A code with excellent additive-noise performance is not automatically optimal for bursty or fading channels. Reliability requirements for control information may justify lower rate and greater latency than requirements for noncritical payload data.

10. Practical Design Considerations and Limitations

Code performance depends on block length, channel model, decoder precision, termination, interleaving, and the quality of channel-state information. Theoretical distance does not alone predict practical BER. Short packets may operate far from asymptotic thresholds. Iterative decoders can exhibit an error floor caused by trapping sets, stopping sets, or other graph structures.

Coding also introduces overhead and delay. Deep interleaving improves burst protection but increases latency and memory. Soft decoding improves performance but requires quantized likelihoods, high-speed arithmetic, and substantial power. In battery-powered devices, energy spent in decoding can offset transmitter energy savings.

Security must not be confused with error control. CRCs and error-correcting codes provide integrity against accidental channel errors, not authentication against an adversary. Maliciously modified packets require cryptographic authentication, such as a message authentication code or digital signature. Standards and safety-critical systems may impose requirements for traceability, deterministic behaviour, fault logging, and validated implementations.

Contemporary systems increasingly use rate-compatible code families, incremental redundancy, neural-assisted decoding, and hardware accelerators. Machine learning may assist channel prediction, code design, or decoder scheduling, but learned decoders require careful validation under distribution shift and adversarial or rare channel conditions. Algebraic guarantees remain valuable in safety-critical and high-assurance systems.

Best-Practice Design Workflow

1. Define the channel model, including fading, burst structure, interference, and uncertainty.
2. Specify BER, FER, latency, throughput, energy, and availability targets.
3. Select block length and code family jointly with modulation and packet structure.
4. Prefer soft information when receiver estimates are reliable and complexity permits.
5. Use interleaving for burst channels, but quantify its latency and memory cost.
6. Add CRC or equivalent integrity checking when residual undetected errors are unacceptable.
7. Evaluate finite-length performance using simulation, analytical bounds, and hardware measurements.
8. Test implementation corner cases: synchronization loss, decoder failure, buffer overflow, and mode disagreement.
9. Separate accidental-error protection from cryptographic security.
10. Document assumptions, decoder failure behaviour, and standards compliance.

Chapter Summary

Error-control coding adds structured redundancy to improve the reliability of digital communication. The code rate measures efficiency, while Hamming distance determines guaranteed detection and correction capability. Linear block codes use generator and parity-check matrices; syndromes support algebraic decoding. CRCs provide efficient error detection, whereas ARQ uses feedback and retransmission. Hamming, BCH, Reed–Solomon, and convolutional codes provide classical solutions, while turbo, LDPC, and polar codes offer near-capacity performance through iterative or structured decoding. Shannon capacity establishes a theoretical limit, but practical design must account for finite block length, fading, burst errors, latency, energy, implementation complexity, and security. Successful systems select coding jointly with modulation, interleaving, channel estimation, and link control.

Key Terms

Redundancy: Additional transmitted information used to detect or correct errors.

Code rate: Ratio of information symbols to transmitted coded symbols.

Hamming distance: Number of positions in which two equal-length vectors differ.

Minimum distance: Smallest Hamming distance between distinct codewords.

Syndrome: Parity-check result used to identify an error pattern.

Linear block code: Code whose codewords form a vector subspace over a finite field.

Generator matrix: Matrix used to map information vectors into codewords.

Parity-check matrix: Matrix whose null space contains all valid codewords.

CRC: Polynomial-based error-detection technique.

ARQ: Error-control method using acknowledgements and retransmissions.

FEC: Error correction performed without requiring retransmission.

Hamming code: Single-error-correcting family based on parity positions.

Reed–Solomon code: Symbol-oriented maximum-distance separable code family.

Convolutional code: Code whose output depends on current and previous input symbols.

Trellis: State-transition representation used in sequence decoding.

Viterbi algorithm: Maximum-likelihood trellis decoding algorithm.

LDPC code: Code defined by a sparse parity-check matrix.

Polar code: Code based on channel polarization.

Coding gain: Reliability improvement expressed as reduced required signal-to-noise ratio.

Interleaving: Reordering that spreads burst errors across codewords.

Review Questions

Short Answer Questions

1. Define code rate and explain the effect of lowering it.
2. What is the relationship between minimum distance and guaranteed error correction?
3. Distinguish error detection from error correction.
4. What information does a syndrome provide?
5. Why are Reed–Solomon codes effective against burst errors?

Long Answer Questions

1. Explain the encoding and decoding principles of a binary linear block code using generator and parity-check matrices.
2. Compare CRC, ARQ, and FEC with respect to reliability, delay, bandwidth, and retransmission requirements.
3. Describe convolutional coding and the Viterbi algorithm, including hard- and soft-decision decoding.
4. Compare turbo, LDPC, and polar codes in terms of structure, decoding, performance, and implementation.
5. Explain how Shannon capacity guides, but does not completely determine, practical code selection.

Analytical / Application Questions

1. A binary code has minimum distance seven. Determine its guaranteed error-detection and error-correction capabilities, and explain the assumptions.
2. Design an error-control architecture for a low-power wireless sensor network experiencing burst interference and intermittent feedback. Justify the code, interleaving, and retransmission choices.
3. A satellite link has long propagation delay and limited power. Compare pure ARQ, pure FEC, and hybrid ARQ, and recommend a strategy for safety-critical telemetry.

Multiple Choice Questions with Answers

Question 1

For a code with minimum Hamming distance 5, what is the maximum number of errors it can guarantee to correct?

A. 1

B. 2

C. 3

D. 4

Correct Answer: B. 2

Question 2

The code rate of a (15,11) block code is:

A. 0.25

B. 0. fifty

C. 11/15

D. 15/11

Correct Answer: C. 11/15

Question 3

For a valid linear block-code word c, which condition holds?

A. Gc^T = 1

B. Hc^T = 0

C. Hc = 1

D. cG^T = 0 always

Correct Answer: B. Hc^T = 0

Question 4

A CRC primarily performs which function?

A. Error detection

B. Source compression

C. Encryption

D. Carrier recovery

Correct Answer: A. Error detection

Question 5

A binary Hamming code with m parity bits has length:

A. m^2−1

B. 2m−1

C. 2^m−1

D. m+2

Correct Answer: C. 2^m−1

Question 6

Which decoder is associated with convolutional-code trellis decoding?

A. Euclidean algorithm

B. Viterbi algorithm

C. Newton algorithm

D. K-means algorithm

Correct Answer: B. Viterbi algorithm

Question 7

For a binary symmetric channel, capacity is zero when the crossover probability is:

A. 0

B. 0.1

C. 0.25

D. 0.5

Correct Answer: D. 0.5

Question 8

Which technique spreads a burst of errors across multiple codewords?

A. Interleaving

B. Sampling

C. Quantization

D. Multiplexing

Correct Answer: A. Interleaving

Question 9

Reed–Solomon codes operate primarily on:

A. Individual analogue samples

B. Symbols in a finite field

C. Carrier frequencies only

D. Uncoded acknowledgements

Correct Answer: B. Symbols in a finite field

Question 10

Which approach combines error detection with retransmission?

A. FEC

B. ARQ

C. PSK

D. PCM

Correct Answer: B. ARQ