Information Theory and Error-Control Coding

Introduction and Context

Modern computing systems communicate, store, and process information in environments that are uncertain, noisy, and resource constrained. A wireless channel may introduce interference; an optical link may suffer from attenuation; a memory device may experience bit flips; and a distributed storage system may lose symbols because of failed nodes. Information theory provides mathematical limits and design principles for representing, transmitting, and storing information. Error-control coding converts these principles into algorithms that detect and correct corruption.

The subject has two complementary concerns. Source coding removes statistical redundancy so that data can be represented efficiently. Channel coding deliberately adds structured redundancy so that data can be recovered reliably. The apparent contradiction is resolved by distinguishing useful redundancy from unnecessary redundancy: source coding removes predictable structure, whereas channel coding introduces controlled structure for protection.

This chapter develops entropy, mutual information, channel capacity, source and channel coding, linear block codes, cyclic codes, convolutional codes, decoding, and contemporary applications such as data centres, wireless systems, satellite links, and machine-learning-assisted communication.

Learning Objectives

After studying this chapter, a learner should be able to:

1. Define self-information, entropy, conditional entropy, and mutual information.
2. Apply the source-coding and channel-coding viewpoints.
3. Explain and use the binary symmetric channel and Shannon capacity.
4. Construct and analyse linear block codes using generator and parity-check matrices.
5. Compute syndromes and perform single-error correction with Hamming codes.
6. Explain cyclic, convolutional, and modern capacity-approaching codes.
7. Evaluate coding designs with respect to rate, latency, complexity, reliability, and ethical constraints.

1. Information as Uncertainty Reduction

If an event with probability p occurs, its information content should increase as p decreases. The standard measure of self-information is

where p(x) is the probability of event x. The unit is the bit when the logarithm is base 2. An event of probability 1 carries zero information; an event of probability 1/2 carries one bit.

For a discrete random variable X with possible outcomes x, the average information is its entropy:

The sum is over all outcomes having nonzero probability. Entropy is measured in bits per symbol. For a binary variable with P(X = 1) = p, the binary entropy function is

with the convention 0 log₂ 0 = 0. It is maximal at p = 1/2, where h₂(p) = 1, and zero at p = 0 or 1. Thus, a fair binary source is maximally uncertain, while a deterministic source has no uncertainty.

1.1 Joint, Conditional, and Mutual Information

For two discrete random variables X and Y, joint entropy is

Conditional entropy measures the remaining uncertainty in X after observing Y:

Mutual information measures the reduction in uncertainty about X obtained from Y:

It is always nonnegative and equals zero precisely when X and Y are statistically independent. The chain rule states

These identities are foundational in compression, feature selection, privacy analysis, and channel modelling.

Worked Example 1: Entropy

Suppose a source emits A with probability 1/2, B with probability 1/4, and C with probability 1/4. Its entropy is

A fixed-length binary representation would require 2 bits per symbol. The entropy indicates that variable-length coding can approach 1.5 bits per symbol, though an actual finite code may use slightly more.

2. Source Coding and the Limits of Compression

A source code assigns a finite binary string to each source symbol. A code is uniquely decodable if every encoded sequence has only one possible source interpretation. A prefix code has no codeword that is the prefix of another; every prefix code is instantaneously decodable and uniquely decodable.

For a binary prefix code with codeword lengths lᵢ and source probabilities pᵢ, Kraft's inequality is

Conversely, any positive integer lengths satisfying this inequality can be assigned to a binary prefix code. A central result of source coding is that, for an optimally designed code for a memoryless source,

where L = ∑ᵢ pᵢlᵢ is the expected code length in bits per symbol. The theorem assumes discrete symbols, a known probability model, and a binary prefix-code setting.

Huffman coding constructs an optimal binary prefix code for known symbol probabilities. Arithmetic coding represents an entire message as a subinterval of [0,1) and can approach entropy more closely, especially when probabilities are skewed or adaptive models are used. Dictionary methods such as LZ77 and LZ78 exploit repeated strings rather than requiring an explicit probability table.

Compression is not the same as encryption. Compression removes predictable redundancy; encryption should conceal statistical structure. In a secure system, compression and encryption must be designed carefully because side-channel leakage can arise from compressed lengths.

3. Communication Channels and Capacity

A communication channel is modelled by an input random variable X and output random variable Y with transition probabilities p(y|x). The mutual information I(X;Y) quantifies the information conveyed by one channel use. The channel capacity is

where the maximum is over all permitted input distributions. Capacity is measured in bits per channel use. For a memoryless channel, uses are assumed statistically independent conditioned on the transmitted sequence.

Shannon's channel coding theorem states that if the transmission rate R is below C, codes can be designed whose probability of decoding error approaches zero as block length increases. If R exceeds C, reliable communication is impossible under the channel model. The theorem is asymptotic: it does not by itself specify a practical block length, decoder, latency, or computational cost.

3.1 Binary Symmetric Channel

A binary symmetric channel (BSC) transmits 0 or 1 and flips the bit with probability ε, where 0 ≤ ε ≤ 1. For 0 ≤ ε ≤ 1/2, its capacity is

The formula assumes a memoryless channel, equal cost for both input symbols, and an optimally chosen input distribution, which is uniform for the BSC.

Worked Example 2: BSC Capacity

For ε = 0.10,

Therefore,

A code operating at 0.4 information bits per channel use may, in principle, achieve arbitrarily small error with sufficiently long and well-designed codes. A rate of 0.6 cannot be made reliably error-free for this channel model.

3.2 Gaussian Channels

For an additive white Gaussian noise (AWGN) channel with bandwidth B hertz, average signal power S watts, and noise power N watts over that bandwidth, Shannon capacity is

The ratio S/N is dimensionless. The formula assumes an ideal band-limited channel, Gaussian noise, average-power constraint, and sufficiently long codes. Practical systems operate below capacity because of finite block length, coding complexity, fading, channel estimation errors, and implementation losses.

4. Error-Control Coding Principles

Error-control coding adds redundancy to a message before transmission or storage. At the receiver, redundancy is used to identify or correct corruption.

Important parameters of a block code are:

The Hamming distance d(x,y) is the number of positions in which strings x and y differ. A code with minimum distance d_min can detect up to d_min − 1 errors. It can correct up to

errors under nearest-neighbour decoding, assuming errors do not create an ambiguous tie. These are guaranteed worst-case bounds; probabilistic performance may be better or worse depending on the channel and decoder.

There is a trade-off among rate, redundancy, correction capability, latency, and complexity. Stronger protection generally requires more redundancy or longer blocks, although modern code design can approach theoretical limits efficiently.

5. Linear Block Codes

A binary linear (n,k) code is a k-dimensional subspace of the vector space GF(2)^n. Addition is modulo 2, so 1 + 1 = 0. A generator matrix G of size k × n maps a message vector u to a codeword c:

A parity-check matrix H of size (n − k) × n characterizes valid codewords:

The matrices satisfy

A received vector r is checked using its syndrome:

If s = 0, the word satisfies all parity checks. This does not prove that no error occurred: an error pattern that is itself a codeword produces zero syndrome. For a single-error pattern eᵢ, the syndrome equals the corresponding column of H, enabling location when all columns are distinct and nonzero.

Worked Example 3: A Single-Error-Correcting Code

Consider the systematic code with

A compatible parity-check matrix is

Indeed, GHᵀ = 0 over GF(2). For message u = [1 0 1],

Suppose the received vector is r = [1 0 1 1 1], with an error in position 5. Then

The fifth column of H is [0;1]ᵀ, so the decoder identifies position 5 and flips it, recovering [1 0 1 1 0]. This example illustrates syndrome decoding; it does not claim that the code corrects every multi-bit error.

Hamming Codes

The binary Hamming code with r parity bits has

It corrects one-bit errors and detects two-bit errors under standard decoding. For r = 3, the code is (7,4), with rate 4/7. Extended Hamming codes append an overall parity bit, producing d_min = 4: they correct one error and detect two errors, although decoding conventions must distinguish some higher-weight patterns.

6. Cyclic Codes and Polynomial Representation

A cyclic code is a linear block code in which every cyclic shift of a codeword is also a codeword. Binary codewords can be represented as polynomials over GF(2), with a length-n word corresponding to a polynomial of degree less than n. A cyclic code is generated by a generator polynomial g(x) that divides xⁿ − 1 over GF(2). Valid codeword polynomials have the form

where m(x) is the message polynomial and deg g(x) = n − k. Polynomial division provides efficient encoding and syndrome computation. Cyclic redundancy checks (CRCs) use this algebra primarily for high-probability error detection rather than guaranteed correction.

A CRC's effectiveness depends on the generator polynomial, message length, and error model. A well-selected polynomial detects all single-bit errors and many burst errors, but a CRC is not a substitute for cryptographic integrity: an adversary who knows the polynomial can deliberately construct modifications with a matching CRC. Authentication requires a message authentication code or digital signature.

7. Convolutional Codes and Sequential Decoding

Unlike a block code, a convolutional encoder processes a stream and produces output based on current and previous input bits. It is described by memory, rate, and generator polynomials. The encoder's states form a trellis. The Viterbi algorithm performs maximum-likelihood sequence decoding by retaining the lowest-metric path entering each state at each time step.

For hard decisions, branch metrics may be Hamming distances; for soft decisions, Euclidean or likelihood-based metrics use reliability information from the physical receiver. Soft decoding generally improves performance because a received value close to a decision threshold is less trustworthy than a value far from it.

Termination introduces known final states but adds overhead. Tail-biting avoids explicit termination by requiring the initial and final state to agree, reducing rate loss at the cost of more complex decoding.

8. Modern Codes: Turbo, LDPC, and Polar Codes

Turbo codes use concatenated constituent convolutional codes and iterative decoding. They demonstrated practical operation close to capacity but may suffer from error floors and latency.

Low-density parity-check (LDPC) codes use sparse parity-check matrices. Their factor-graph representation supports belief-propagation decoding. A variable node represents a code bit and a check node represents a parity constraint. Iterative messages carry probabilistic reliability. LDPC codes are used in wireless standards, satellite links, Ethernet, and storage systems.

Polar codes exploit channel polarization: synthetic bit channels become either highly reliable or highly unreliable as block length grows under suitable transformations. Information bits are placed in reliable positions, while frozen bits occupy unreliable positions. Successive-cancellation list decoding improves finite-length performance and is used in cellular control channels.

The engineering choice is not determined by capacity alone. Designers compare block length, decoder parallelism, memory traffic, energy, error-floor behaviour, latency, and support for variable rates.

9. A Practical Design Workflow

A robust coding design normally follows these steps:

1. Specify the channel and failure model. Identify random errors, bursts, erasures, fading, packet loss, or adversarial manipulation.
2. Set reliability targets. Define bit-error rate, block-error rate, undetected-error probability, and availability.
3. Determine resource constraints. Include bandwidth, energy, latency, memory, processing power, and allowable overhead.
4. Choose a code family. Select a block, convolutional, LDPC, polar, fountain, or product code according to the operating environment.
5. Select rate and block length. Operate below estimated capacity with an implementation margin.
6. Design the decoder. Decide between hard and soft decisions, iterative depth, stopping rules, and numerical precision.
7. Validate experimentally. Use simulations and measurements across signal-to-noise ratios, temperatures, workloads, and burst patterns.
8. Monitor deployment. Record error statistics, retransmissions, decoder failures, and changes in channel behaviour.

Automatic repeat request (ARQ) asks for retransmission when an error is detected. Forward error correction (FEC) corrects errors without retransmission. Hybrid ARQ combines both. FEC is valuable when round-trip delay is high, as in satellite communication; ARQ is attractive when retransmission is inexpensive and latency is acceptable.

10. Illustrative Case: Reliable Storage in a Distributed Data Centre

Background

Consider a fictional but technically realistic storage service that stores replicated data across disks and servers. Silent corruption, disk failures, and network packet loss threaten data integrity. Replication alone increases storage cost and does not necessarily detect silent errors.

Problem

The service requires recovery from several failed or unavailable storage fragments while limiting overhead and maintaining acceptable read latency. It must also distinguish random corruption from malicious modification.

Analysis

An erasure code is appropriate when the system knows which fragments are missing. An (n,k) maximum-distance-separable code can reconstruct the original k fragments from any k of the n fragments, with storage overhead n/k. For example, a (10,6) design tolerates up to four erasures and has rate 0.6. This statement concerns erasures, not arbitrary unknown errors.

For corruption with unknown locations, additional integrity information and error-correcting capability are needed. A cryptographic hash or authenticated tag detects intentional modification more appropriately than a CRC. The system can use checksums for accidental corruption, authenticated integrity for adversarial threats, and erasure coding for availability.

Approach and Outcome

The service divides an object into six data fragments, computes four parity fragments, and distributes all ten across failure domains. A read first verifies authenticated checksums. If fragments are missing, the decoder reconstructs them from any six valid fragments. If a fragment fails integrity verification, it is treated as unusable and reconstruction proceeds from the remaining fragments. Background repair restores redundancy after a failure.

The approach improves durability without ten full replicas, but it introduces encoding/decoding CPU cost, metadata management, repair traffic, and privacy concerns if fragments are distributed across administrative boundaries.

Learning Points

1. The error model determines whether correction, erasure recovery, or authentication is needed.
2. Coding rate is a storage and bandwidth decision, not merely a mathematical parameter.
3. A checksum detects accidental faults; cryptographic authentication addresses adversarial tampering.
4. Repair traffic and correlated failures must be included in system-level reliability analysis.

11. Limitations, Governance, and Ethical Issues

Information-theoretic results depend on models. A capacity computed for independent noise may be misleading when errors are bursty, correlated, or affected by an attacker. Finite-blocklength performance can differ substantially from asymptotic predictions. Decoder implementations can also create timing, power, or memory side channels.

Engineers should report assumptions, confidence intervals from experiments, decoder versions, and error definitions. Safety-critical systems require traceability, independent validation, fault injection, and conservative operating margins. In privacy-sensitive applications, coding and compression should not inadvertently expose user information through lengths, retransmission patterns, or error logs.

Coding choices can also affect digital inclusion. Stronger reliability may require more energy or expensive hardware, while aggressive compression may reduce accessibility or interoperability. Standards compliance, export controls, spectrum regulation, and data protection law may constrain deployment. In AI-enabled communication systems, learned decoders should be tested against distribution shift and adversarial inputs; empirical performance does not replace a clear channel model or formal safety argument.

12. Contemporary Directions

Current research includes short-blocklength coding for ultra-reliable low-latency communication, rate-compatible codes for adaptive networks, nonbinary and spatially coupled LDPC codes, codes for DNA and molecular storage, and joint source-channel coding for multimodal sensors. Neural decoders and learned belief-propagation schedules can reduce complexity or adapt to unknown channels, but they raise questions about generalization, interpretability, certification, and robustness.

A promising systems perspective treats coding as part of a cross-layer design. Modulation, channel estimation, scheduling, compression, coding, retransmission, and application-level quality should be optimized together rather than independently. Nevertheless, fundamental bounds remain essential: learning-based methods can improve implementation for a model, but they cannot repeal information-theoretic limits.

Chapter Summary

Information theory quantifies uncertainty and the information conveyed through a channel. Entropy measures average uncertainty; conditional entropy measures residual uncertainty; mutual information measures dependence and information transfer. Source coding removes statistical redundancy and approaches entropy, while channel coding adds structured redundancy to combat noise.

Channel capacity is the maximum reliable information rate under a channel model. For a BSC it is 1 − h₂(ε), and for an ideal AWGN channel it is B log₂(1 + S/N). Shannon's theorem separates possible rates from impossible rates, but practical systems must account for finite length, complexity, latency, and implementation loss.

Linear codes use generator and parity-check matrices. Syndromes support error detection and location, while minimum distance determines guaranteed detection and correction capability. Cyclic, convolutional, LDPC, turbo, and polar codes provide different compromises among performance and complexity. Real deployments combine coding with checksums, cryptographic authentication, retransmission, and system-level monitoring. Correct design begins with an accurate failure model and ends with empirical validation and responsible governance.

Key Terms

Entropy: Average uncertainty of a discrete random variable, measured in bits when base-2 logarithms are used.

Self-information: Information associated with one event, equal to −log₂ of its probability.

Mutual information: Reduction in uncertainty about one variable obtained from another.

Source coding: Representation of data using fewer bits by exploiting statistical redundancy.

Channel coding: Addition of structured redundancy to detect or correct transmission errors.

Prefix code: A code in which no codeword is a prefix of another.

Kraft inequality: Condition ∑2^(−lᵢ) ≤ 1 for binary prefix-code lengths.

Channel capacity: Maximum information rate allowing arbitrarily small error in the asymptotic idealized model.

Binary symmetric channel: A binary channel that independently flips each bit with probability ε.

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

Minimum distance: Smallest Hamming distance between distinct codewords.

Linear block code: A vector subspace of GF(2)^n used for fixed-length coding.

Generator matrix: Matrix that maps information vectors to codewords.

Parity-check matrix: Matrix whose null space is the set of valid codewords.

Syndrome: Vector Hrᵀ used to test parity constraints and locate errors.

Cyclic code: Linear code closed under cyclic shifts.

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

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

Erasure: A symbol known to be missing or unreliable, with its location identified.

CRC: Polynomial-based error-detection mechanism, not a cryptographic authenticator.

Review Questions

Short Answer Questions

1. Define entropy and explain why it is largest for a uniformly distributed finite source.
2. Distinguish source coding from channel coding.
3. What does a syndrome represent in a linear block code?
4. State the relationship between minimum distance and guaranteed error correction.
5. Why is a CRC not sufficient for adversarial integrity protection?

Long Answer Questions

1. Derive the capacity of the binary symmetric channel from mutual information and explain the role of the binary entropy function.
2. Explain generator matrices, parity-check matrices, syndromes, and their relationships in binary linear codes.
3. Compare Huffman coding, arithmetic coding, and dictionary-based compression.
4. Compare convolutional, LDPC, and polar codes in terms of structure, decoding, latency, and applications.
5. Explain Shannon's channel coding theorem and discuss why practical systems operate below theoretical capacity.

Analytical / Application Questions

1. A BSC has crossover probability ε = 0.02. Calculate its capacity using the binary entropy function and interpret the result.
2. Design a reliability strategy for a satellite link carrying compressed scientific data, considering FEC, ARQ, latency, and integrity protection.
3. A storage system has six data fragments and four parity fragments. Analyse its rate, erasure tolerance, repair implications, and the additional controls needed for malicious corruption.

Multiple Choice Questions with Answers

Question 1

For a discrete random variable X, which expression defines entropy in bits?

A. ∑ₓ p(x)

B. −∑ₓ p(x) log₂ p(x)

C. ∑ₓ log₂ p(x)

D. −log₂(maxₓ p(x))

Correct Answer: B. −∑ₓ p(x) log₂ p(x)

Question 2

What is the capacity of a binary symmetric channel with crossover probability ε?

A. h₂(ε)

B. ε log₂ ε

C. 1 − h₂(ε)

D. 1 + h₂(ε)

Correct Answer: C. 1 − h₂(ε)

Question 3

A code with minimum Hamming distance 5 can guarantee correction of how many errors?

A. 1

B. 2

C. 4

D. 5

Correct Answer: B. 2

Question 4

For a linear code, a valid codeword c satisfies which condition?

A. Hcᵀ = 1

B. Hcᵀ = c

C. Hcᵀ = 0

D. Hcᵀ = H

Correct Answer: C. Hcᵀ = 0

Question 5

What is the principal purpose of a syndrome in linear-code decoding?

A. To estimate source entropy

B. To locate or characterize an error pattern

C. To increase the channel bandwidth

D. To encrypt the message

Correct Answer: B. To locate or characterize an error pattern

Question 6

A binary Hamming code with r = 3 parity bits has which parameters?

A. (7,4)

B. (8,4)

C. (6,3)

D. (7,3)

Correct Answer: A. (7,4)

Question 7

Which technique is primarily designed to detect accidental transmission errors rather than authenticate an adversary?

A. Digital signature

B. Message authentication code

C. CRC

D. Public-key encryption

Correct Answer: C. CRC

Question 8

In an AWGN channel, increasing S/N while holding bandwidth fixed generally does what?

A. Decreases capacity

B. Leaves capacity unchanged

C. Increases capacity logarithmically

D. Makes capacity negative

Correct Answer: C. Increases capacity logarithmically

Question 9

What is a defining property of a cyclic code?

A. Every codeword has equal probability

B. Every cyclic shift of a codeword is also a codeword

C. It contains no redundancy

D. It corrects every possible error

Correct Answer: B. Every cyclic shift of a codeword is also a codeword

Question 10

For a (10,6) erasure-code design, what is the code rate k/n?

A. 0.4

B. 0.6

C. 1.67

D. 4

Correct Answer: B. 0.6