Information Theory and Source Coding

Introduction and Context

Communication systems are fundamentally concerned with representing, storing, transmitting, and recovering information. A message may be a speech waveform, an image, a sensor record, a genomic sequence, or a computer file. Information theory provides a mathematical framework for quantifying uncertainty and information, while source coding develops efficient representations of messages. Together, they establish the limits and methods for reducing redundancy before transmission or storage.

The central engineering distinction is between source coding and channel coding. Source coding removes statistical redundancy from a message; channel coding deliberately adds structured redundancy so that errors introduced by a noisy channel can be detected or corrected. This chapter focuses on the former, while relating it to the broader communication-system architecture.

A typical digital communication chain is:

Figure: Functional relationship between source coding, channel coding, and transmission.

Learning Objectives

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

1. Explain uncertainty, information, entropy, joint entropy, conditional entropy, and mutual information.
2. Apply entropy measures to discrete and continuous sources and interpret their limitations.
3. Distinguish lossless from lossy source coding and evaluate compression performance.
4. Derive and apply the noiseless coding theorem and Kraft inequality.
5. Construct Huffman and Shannon–Fano codes and calculate their average length and efficiency.
6. Explain arithmetic coding, dictionary methods, transform coding, and predictive coding.
7. Analyze rate–distortion trade-offs and select coding methods for practical systems.
8. Evaluate source-coding designs in relation to latency, complexity, robustness, privacy, and energy use.

1. Information as a Quantifiable Resource

1.1 Uncertainty and self-information

Suppose a discrete random variable X can take outcomes xᵢ with probabilities p(xᵢ). An outcome that is unlikely conveys more surprise than a highly likely outcome. The self-information of xᵢ is defined as

The unit is bits because the logarithm is to base 2. If natural logarithms are used, the unit is nats; if base 10 is used, the unit is hartleys. The formula assumes p(xᵢ) > 0. A certain event has p = 1 and therefore zero information. Independent observations have additive information because logarithms convert multiplication of probabilities into addition.

For example, an outcome with probability 1/8 has self-information I = −log₂(1/8) = 3 bits. This does not mean that every physical event requires exactly three transmitted bits; it is a measure of information content under the selected probabilistic model.

1.2 Entropy

Entropy is the expected self-information of a source. For a discrete memoryless source (DMS), whose successive symbols are statistically independent and governed by the same distribution,

Entropy measures average uncertainty, not the information of a particular symbol. If a source has M equally likely symbols, then

For a binary source with P(X = 1) = p and P(X = 0) = 1 − p,

with the convention 0 log₂ 0 = 0. Binary entropy is maximum at p = 0.5, where H_b(p) = 1 bit, and approaches zero as p approaches 0 or 1.

Entropy satisfies 0 ≤ H(X) ≤ log₂ M. The upper bound occurs only when all M symbols are equiprobable. Thus, an eight-symbol alphabet does not necessarily require three bits per symbol on average; unequal probabilities may permit compression below three bits.

1.3 Entropy rate and memory

Real sources generally possess memory. English text, speech, images, and sensor streams exhibit dependencies between neighbouring samples. The entropy rate of a stationary source is

when the limit exists. Equivalently, for a stationary process,

The conditional-entropy form shows that entropy rate is the uncertainty of a new symbol after all preceding symbols are known. For a first-order Markov source,

where πᵢ is the stationary probability of state i and Pⱼᵢ denotes the probability of transitioning from i to j. Index conventions must be stated because some texts write transition probabilities as Pᵢⱼ for a transition from i to j.

2. Joint, Conditional, and Mutual Information

For two random variables X and Y with joint probability p(x,y), joint entropy is

Conditional entropy is

The chain rule states

Conditioning cannot increase entropy: H(Y|X) ≤ H(Y). Equality holds when X and Y are independent. Mutual information measures the reduction in uncertainty about one variable caused by observing the other:

It can also be written as

Mutual information is non-negative and is zero if and only if X and Y are independent. It is symmetric, although the phrase “information about Y provided by X” may suggest an asymmetric interpretation.

These quantities are useful in communications, feature selection, predictive modelling, privacy analysis, and estimation. However, mutual information alone does not specify a practical code: code design also depends on alphabet constraints, delay, computational resources, and distortion criteria.

3. Source Models and Redundancy

A source model assigns probabilities to symbols or sequences. A poor model produces inefficient codes even if the coding algorithm is optimal for that model. Modelling and coding are therefore related but distinct tasks.

Redundancy is the gap between a representation’s average length and the minimum theoretically attainable length. At the single-symbol level, one may define the normalized redundancy of a code as

where L̄ is the code’s average length. This quantity is non-negative for uniquely decodable codes under the usual source-coding assumptions. Relative efficiency is often written as

and expressed as a percentage. A source model may reduce redundancy by exploiting symbol probabilities, temporal correlation, spatial correlation, or semantic structure.

4. Lossless Source Coding

A lossless code permits exact reconstruction of every source sequence. It is required for text, executable programs, financial records, measurement logs where exact values matter, and compressed data that will undergo further processing.

4.1 Codewords and decodability

A code maps source symbols to finite strings over a code alphabet, normally binary. A fixed-length code assigns the same length to every symbol. A variable-length code assigns shorter words to frequent symbols and longer words to rare symbols.

A code is uniquely decodable if every encoded sequence has only one possible source interpretation. A prefix code is a code in which no codeword is the prefix of another. Every prefix code is instantaneous and uniquely decodable, although not every uniquely decodable code is prefix-free.

For a binary prefix code with codeword lengths l₁, l₂, …, l_M, Kraft’s inequality is

More generally, for a D-ary code, the condition is ∑ᵢ D^(−lᵢ) ≤ 1. Kraft’s inequality is necessary and sufficient for the existence of a binary prefix code with the specified lengths. It is not, by itself, a probability distribution and does not prove that a particular code is uniquely decodable unless the relevant code class is specified.

4.2 Noiseless coding theorem

For a discrete memoryless source with entropy H(X), any uniquely decodable binary code has average length L̄ satisfying

There exist prefix codes, including suitable block codes, for which the average length per source symbol approaches H(X) as block length increases. A common practical bound for a Huffman code applied to individual symbols is

The theorem is asymptotic and concerns average length under a known probability model. It does not guarantee low delay, resilience to bit errors, or good performance when the model is inaccurate.

4.3 Shannon–Fano coding

Shannon–Fano coding sorts symbols by decreasing probability and recursively divides them into two groups with probabilities as nearly equal as possible. A 0 is assigned to one group and a 1 to the other. The method is simple but is not always optimal.

4.4 Huffman coding

Huffman coding constructs an optimal binary prefix code for a known finite alphabet when the objective is minimum expected codeword length and symbols are coded independently. The procedure is:

1. List symbols in increasing order of probability.
2. Combine the two least-probable nodes.
3. Replace them by a node whose probability is their sum.
4. Repeat until one tree remains.
5. Assign 0 and 1 to branches and read each symbol’s path.

Ties may produce different code trees with the same average length. Huffman coding is optimal among binary prefix codes for the specified symbol probabilities, but not necessarily optimal for a source with memory unless blocks or context-dependent models are used.

Worked Example: Huffman coding

Consider symbols A, B, C, and D with probabilities 0.50, 0.25, 0.125, and 0.125. Combine C and D to obtain 0.25; combine that node with B to obtain 0.50; finally combine the two 0.50 nodes. One valid code is A = 0, B = 10, C = 110, D = 111.

The average length is

The entropy is

Thus this particular distribution permits an integer-length prefix code whose average length equals its entropy. The efficiency is η = 1.75/1.75 = 100 percent under the assumed probabilities. This exact equality is a special result of the probabilities and should not be expected generally.

4.5 Arithmetic coding

Arithmetic coding represents an entire sequence by a subinterval of [0,1). Initially the interval is [0,1). Each new symbol narrows the current interval in proportion to its model probability. The final interval identifies the sequence; a binary representation of a number inside it becomes the compressed output.

Unlike a symbol-by-symbol prefix code, arithmetic coding can achieve an average rate close to the sequence’s ideal self-information, often performing well when probabilities are fractional or context-dependent. Practical implementations use finite precision, renormalization, termination rules, and protection against underflow. The decoder must have the same probability model or an exactly synchronized adaptive model.

4.6 Dictionary and context methods

Dictionary methods replace repeated strings by references to earlier strings or to a maintained dictionary. LZ77 uses a sliding window; LZ78 builds an explicit dictionary. These methods underpin many general-purpose compression systems because they do not require a separately transmitted probability table and adapt to local repetition.

Context models estimate the probability of a symbol given preceding symbols. A context of order k estimates p(xₙ | xₙ₋₁, …, xₙ₋ₖ). Larger contexts can exploit more structure but require more memory, training data, and mechanisms for handling unseen contexts. Context mixing and prediction by partial matching combine predictions from several context lengths.

5. Lossy Source Coding and Rate–Distortion Theory

Lossy coding permits controlled reconstruction error to obtain substantially lower rates. It is used for speech, images, video, and perceptual sensor data. The encoder maps X to a reproduction X̂, and a distortion measure d(x, x̂) quantifies the cost of reconstruction error.

The rate–distortion function is

where the minimization is over all conditional distributions p(x̂|x) satisfying E[d(X,X̂)] ≤ D. R(D) is the theoretical minimum rate, in bits per source symbol, required to achieve average distortion no greater than D for sufficiently long blocks under the assumed source and distortion model.

For a memoryless Gaussian source X with variance σ² and mean-square error distortion, the rate–distortion function is

and R(D) = 0 for D ≥ σ². This result assumes an ideal Gaussian source, long blocks, and mean-square error. It must not be applied automatically to images or speech, whose perceptual distortion is not adequately represented by ordinary squared error.

5.1 Quantization

A quantizer maps a continuous or high-resolution discrete value to one of a finite set of reconstruction levels. A scalar quantizer partitions the input axis into intervals; a vector quantizer maps blocks of samples to codebook vectors. Uniform scalar quantization with step size Δ has approximately Δ²/12 mean-square quantization error for a uniformly distributed input within each cell, assuming sufficiently fine quantization and neglecting overload distortion.

A practical quantizer must balance granular distortion, overload distortion, bit rate, computational complexity, and robustness. Companding systems, such as logarithmic quantizers used in telephony, allocate more resolution to low-amplitude signals where the ear is often more sensitive.

5.2 Transform and predictive coding

Transform coding applies a reversible or approximately reversible transform to decorrelate samples. The transformed coefficients are quantized and entropy coded. The discrete cosine transform (DCT), for example, concentrates much of the energy of correlated image blocks into a few low-frequency coefficients. Quantization of small or perceptually unimportant coefficients then produces compression.

Predictive coding estimates the current sample from past samples and encodes the prediction error. Differential pulse-code modulation (DPCM) is an early example. If the predictor is accurate, the error has lower variance and entropy than the original signal. Adaptive predictive coding updates predictor parameters as signal statistics change.

6. Practical Design Measures

A source-coding design should be evaluated using more than compression ratio. Important measures include:

The nominal compression ratio can be misleading when metadata, framing, padding, encryption tags, or error-protection overhead are omitted. For a finite message, total rate is

where all N values are measured in bits and N_source is the number of source symbols or samples. This expression is a system-level accounting identity, not a universal entropy bound.

7. Illustrative Applied Case: Low-Power Environmental Monitoring

Background

Consider a battery-powered wireless node measuring temperature, humidity, and vibration in an industrial plant. Measurements are periodic, correlated over time, and transmitted over a low-data-rate link. Battery replacement is expensive, but safety decisions require reliable data.

Problem

Raw 16-bit measurements consume 48 bits per time instant for three sensors, before packet headers and error-control overhead. The system must reduce energy consumption without concealing abnormal vibration events or creating unacceptable reconstruction error.

Analysis

Temperature and humidity vary slowly, so consecutive samples are strongly correlated. Vibration has a wider bandwidth and may contain rare, high-amplitude transients. A single lossy method for all three streams would be inappropriate: smoothing vibration could remove evidence of equipment failure. The source model is also nonstationary because operating states change.

Approach and solution

The node uses differential prediction for temperature and humidity. It transmits small prediction errors with an adaptive entropy coder and periodically sends absolute synchronization samples. For vibration, it retains lossless coding during alarm windows and uses a carefully bounded near-lossless mode during ordinary operation. A packet includes a compact model identifier, sequence number, and integrity check. The receiver monitors reconstruction quality and requests a synchronization packet when model mismatch becomes significant.

The design separates source coding from channel protection. Entropy coding reduces average payload size; a forward-error-correcting code and cyclic redundancy check address channel errors. Synchronization points limit error propagation from a corrupted variable-length codeword.

Outcome

Under normal operation, slowly varying channels require substantially fewer bits than fixed 16-bit samples. During vibration events, the system automatically sacrifices compression efficiency to preserve diagnostic information. The resulting design is not optimal for one stationary probability distribution, but it is robust across operating regimes and aligns coding behaviour with engineering risk.

Learning points

1. Source statistics must be measured under actual operating conditions.
2. Compression objectives differ across signal classes.
3. Model overhead and resynchronization cost matter for short packets.
4. Rare events should not be discarded merely because they reduce average compression.
5. Source coding cannot replace channel coding or integrity protection.

8. Limitations, Governance, and Contemporary Directions

8.1 Model mismatch and finite data

Theoretical entropy assumes a known probability law, whereas practical systems estimate probabilities from finite data. If the model is stale or biased, compression worsens and may systematically distort particular classes of signals. Adaptive models improve performance but introduce synchronization and security requirements.

8.2 Error sensitivity and security

Variable-length codes can lose symbol boundaries after a bit error. Block framing, periodic restart markers, unequal error protection, and channel interleaving can limit damage. Compression should normally precede encryption: encrypted data is intentionally close to statistically uniform and therefore difficult to compress. However, compressed length may reveal information about content, so traffic analysis and side-channel leakage must be considered.

Sensitive data also raises governance issues. Designers should document whether compression is lossless, what distortion is permitted, whether models retain identifiable information, and how decoding is validated. In safety-critical, medical, and financial applications, reproducibility, version control, audit trails, and approved decoder implementations are essential.

8.3 AI-assisted and learned compression

Neural codecs learn an analysis transform, quantized latent representation, entropy model, and synthesis transform. Training may optimize a rate–distortion objective such as

where R is estimated rate, D is distortion, and λ ≥ 0 controls the trade-off. Learned systems can exploit complex spatial or temporal structure, but they introduce model size, training-data dependence, computational cost, possible distribution shift, and difficulty in guaranteeing behaviour on rare inputs. They are promising for images, video, point clouds, and multimodal data, but classical predictive and transform codecs remain attractive where explainability, low power, interoperability, and deterministic behaviour are priorities.

8.4 Best-practice workflow

A professional source-coding project should:

1. Define the source, alphabet, sampling process, and acceptable distortion.
2. Measure distributions, correlations, nonstationarity, and rare-event behaviour.
3. Establish an entropy or rate–distortion benchmark.
4. Select a model and code jointly, including metadata and synchronization.
5. Test compression, quality, latency, energy, memory, and error propagation.
6. Evaluate adversarial, out-of-distribution, and degraded-channel conditions.
7. Specify decoder versioning, validation, interoperability, and data-retention rules.

Chapter Summary

Information theory quantifies uncertainty through self-information and entropy. Entropy is an average property of a source, while entropy rate accounts for memory and temporal dependence. Joint and conditional entropy describe relationships among variables, and mutual information measures uncertainty reduction.

Lossless source coding reconstructs the source exactly. Prefix codes obey Kraft’s inequality, and the noiseless coding theorem establishes entropy as the fundamental lower bound on average rate. Huffman coding is optimal among binary prefix codes for a known finite symbol distribution, while arithmetic, dictionary, and context methods exploit fractional probabilities and repeated structure.

Lossy coding trades reconstruction fidelity for lower rate. Rate–distortion theory formalizes this trade-off, while quantization, transform coding, and predictive coding provide practical implementations. Real designs must consider finite block length, model overhead, delay, complexity, error propagation, privacy, and changing source statistics. AI-assisted codecs extend modelling capability but require careful evaluation of robustness and governance.

Key Terms

Self-information: Information associated with a particular outcome, measured as −log₂ p.

Entropy: Expected self-information of a random source symbol.

Entropy rate: Average uncertainty per symbol for a source with memory.

Discrete memoryless source: Source whose symbols are independent and identically distributed.

Conditional entropy: Remaining uncertainty in one variable after another is known.

Mutual information: Reduction in uncertainty produced by observing another variable.

Redundancy: Difference between a representation’s rate and a theoretical or practical lower bound.

Lossless coding: Coding that permits exact reconstruction.

Lossy coding: Coding that permits controlled reconstruction error.

Prefix code: Code in which no codeword is the prefix of another.

Uniquely decodable code: Code for which every encoded sequence has one source interpretation.

Kraft inequality: Condition governing feasible prefix-codeword lengths.

Huffman coding: Greedy construction of an optimal binary prefix code for known symbol probabilities.

Arithmetic coding: Interval-based coding of a complete sequence using probability estimates.

Dictionary coding: Replacement of repeated strings by references to stored patterns.

Quantization: Mapping values to a finite set of representation levels.

Rate–distortion function: Minimum achievable rate for a specified average distortion.

Transform coding: Coding that decorrelates data before quantization and entropy coding.

Predictive coding: Coding of prediction errors rather than original samples.

Model mismatch: Difference between assumed source statistics and actual statistics.

Review Questions

Short Answer Questions

1. Define self-information and explain why a less probable event carries more self-information.
2. State the entropy formula for a discrete random variable and its maximum value for an M-symbol alphabet.
3. Distinguish a prefix code from a uniquely decodable code.
4. What is the purpose of Kraft’s inequality?
5. Differentiate lossless and lossy source coding.

Long Answer Questions

1. Explain entropy rate for a source with memory and derive its relationship with conditional entropy.
2. Describe the Huffman coding algorithm and explain the conditions under which it is optimal.
3. Explain arithmetic coding and compare it with Huffman coding in terms of probability representation and implementation.
4. Discuss transform, predictive, and quantization-based coding, including their main engineering trade-offs.
5. Explain rate–distortion theory and the assumptions behind the Gaussian mean-square-error result.

Analytical / Application Questions

1. A source emits four symbols with probabilities 0.50, 0.25, 0.125, and 0.125. Construct one Huffman code, calculate its average length, and compare it with entropy.
2. Design a coding strategy for a battery-powered sensor that produces slowly varying temperature data and rare high-amplitude vibration events. Justify how the strategy handles model mismatch and error propagation.
3. A communication system uses a variable-length entropy code over a noisy wireless channel. Analyze why a single bit error can affect subsequent decoding and propose at least three synchronization or protection techniques.

Multiple Choice Questions with Answers

Question 1

For a source with M equally likely symbols, the entropy is:

A. M bits/symbol

B. log₂ M bits/symbol

C. 1/M bits/symbol

D. M log₂ M bits/symbol

Correct Answer: B. log₂ M bits/symbol

Question 2

The self-information of an event with probability 1/8 is:

A. 1/8 bit

B. 2 bits

C. 3 bits

D. 8 bits

Correct Answer: C. 3 bits

Question 3

Which statement about mutual information is correct?

A. It is always negative for dependent variables

B. It is zero only when both variables are deterministic

C. It is symmetric and non-negative

D. It always equals joint entropy

Correct Answer: C. It is symmetric and non-negative

Question 4

For a binary prefix code with codeword lengths lᵢ, Kraft’s inequality is:

A. ∑ᵢ lᵢ ≤ 1

B. ∑ᵢ 2^(−lᵢ) ≤ 1

C. ∑ᵢ 2lᵢ ≥ 1

D. ∏ᵢ 2^(−lᵢ) ≤ 1

Correct Answer: B. ∑ᵢ 2^(−lᵢ) ≤ 1

Question 5

Huffman coding is optimal, under its standard assumptions, among:

A. All lossy codes

B. Binary prefix codes for a known finite symbol distribution

C. All channel codes

D. Only fixed-length codes

Correct Answer: B. Binary prefix codes for a known finite symbol distribution

Question 6

For probabilities 0.50, 0.25, 0.125, and 0.125, the entropy is:

A. 1.00 bits/symbol

B. 1.25 bits/symbol

C. 1.75 bits/symbol

D. 3.00 bits/symbol

Correct Answer: C. 1.75 bits/symbol

Question 7

Which method represents a sequence by progressively narrowing an interval?

A. Huffman coding

B. Arithmetic coding

C. Uniform sampling

D. Parity coding

Correct Answer: B. Arithmetic coding

Question 8

In predictive coding, compression is primarily obtained by encoding:

A. The prediction error

B. Only the largest original sample

C. A random replacement sequence

D. Channel noise directly

Correct Answer: A. The prediction error

Question 9

The rate–distortion function R(D) represents:

A. Maximum channel bandwidth for a fixed code

B. Minimum rate required for a specified average distortion

C. The probability of a bit error

D. The number of source symbols in a dictionary

Correct Answer: B. Minimum rate required for a specified average distortion

Question 10

Why is channel coding still needed after source coding?

A. Source coding always adds random noise

B. Channel coding removes all source redundancy for compression

C. Channel coding adds structured redundancy to combat transmission errors

D. Source coding works only on analog signals

Correct Answer: C. Channel coding adds structured redundancy to combat transmission errors