Information Theory: A Tutorial Introduction

James V Stone

Source-linked AI summary

Information Theory: A Tutorial Introduction

James V Stone

arXiv:1802.05968v3Feb 16, 2018cs.ITstat.ML

TL;DR

The paper introduces Shannon’s theory as a framework for understanding measurable information and the limits of communication, including its relevance to biological information processing. It explains entropy, channel capacity, and noisy-channel coding, showing that reliable transmission is possible below capacity but not above it. The discussion also identifies technical difficulties for continuous-variable entropy and the upper-rate boundary imposed by channel capacity.

Problem
The paper addresses how information can be defined, measured, and transmitted within definite limits across communication systems.
Method
The paper gives an informal but rigorous introduction to Shannon’s theory through entropy, channel capacity, and noisy-channel coding concepts.
Results
If H ≤ C, a coding system can transmit the source with arbitrarily small error; if H ≥ C, communication above the channel capacity is impossible.
Takeaways & Limitations
Shannon’s framework defines limits relevant to biological information processing and identifies coding as the means of approaching channel capacity.
Takeaways & Limitations
The treatment notes technical difficulties associated with entropy for continuous variables.

Abstract

from arXiv · show

Shannon's mathematical theory of communication defines fundamental limits on how much information can be transmitted between the different components of any man-made or biological system. This paper is an informal but rigorous introduction to the main ideas implicit in Shannon's theory. An annotated reading list is provided for further reading.

1 Introduction

Shannon’s theory made information measurable and established limits on communication across man-made and natural systems. Its basic framework explains how bits encode choices and how channel capacity, noise, and encoding govern reliable transmission.

Shannon’s theory treats information as a measurable quantity, much like mass or energy, rather than an undefined substance.
Information theory defines unbreachable limits on how much information can pass between components of any system.
A communication channel has a capacity limit that decreases with noise but can nearly be reached through judicious encoding.
One bit selects between two equiprobable alternatives, while n binary decisions distinguish m = 2^n destinations and require n bits.
The route example represents each left or right choice with 0 or 1, so three forks provide three bits and distinguish eight destinations.
More generally, the number of binary decisions is the base-2 logarithm of the number of possible destinations: n = log2 m.

3 Bits Are Not Binary Digits

Shannon information measures the surprise of outcomes, while entropy averages that surprise over a variable’s possible values. The examples show how probability distributions determine information, entropy, and representational capacity.

3 Bits Are Not Binary Digits: A bit measures an amount of information, whereas a binary digit is the value of a binary variable.A binary digit can convey between zero and one bit when averaged over its possible states.
Information and Entropy: Entropy is the average Shannon information of a probability distribution, so a fair coin has H(x) = 1 bit.For a biased coin with p(xh) = 0.9, the entropy is H(x) = 0.469 bits.
Information and Entropy: Less probable outcomes carry more Shannon information, with surprisal defined as log2(1/p(x)) bits.The coin example assigns 0.15 bits to a 90%-probable head and 3.32 bits to a 10%-probable tail.
Information and Entropy: Source coding links entropy to representation length, guaranteeing that each variable value can be represented with an average of just over H(x) binary digits.Dependence between consecutive values increases predictability and reduces entropy, so independence must be specified.
Information and Entropy: A pair of dice produces 11 possible sum values from 36 equiprobable ordered outcomes, yielding H(x) = 3.27 bits.This entropy corresponds to 2^3.27 = 9.65 equiprobable values.
Information and Entropy: Entropy and information share the same quantity: entropy describes uncertainty before observation, while information is uncertainty removed by receiving an outcome.The paper notes that this distinction can lead to interpretive confusion.

5 Entropy of Continuous Variables

For discrete variables, entropy is well-defined through probabilities over countable outcomes, but the analogous continuous-variable entropy becomes technically problematic. The paper notes that mutual information avoids these difficulties through differences between entropies.

5 Entropy of Continuous Variables: A continuous variable with infinitely many equally probable values has H(xc) = ∞ under the paper’s idealized argument.Each exact value is implicitly specified with infinite precision, corresponding to infinite information.
5 Entropy of Continuous Variables: The continuous entropy calculation requires ignoring infinite terms to assign different values to different variables.The resulting expression is the continuous analogue of the discrete entropy sum.
5 Entropy of Continuous Variables: Technical difficulties with continuous-variable entropy disappear for mutual information because it involves differences between two entropies.The paper uses the term entropy for both continuous and discrete variables for convenience.

6 Maximum Entropy Distributions

Maximum-entropy distributions maximize information under stated constraints, making them useful for transmission and modeling. The paper summarizes Gaussian, exponential, and uniform cases and relates channel capacity to input, output, and noise entropies.

6 Maximum Entropy Distributions: With fixed variance and no other constraint, the Gaussian distribution is maximum entropy.Its mean sets the center, while its variance, the square of standard deviation, sets the bell curve’s width.
6 Maximum Entropy Distributions: Maximum entropy is desirable for information transmission because no other distribution provides as much information at a lower energy cost per bit.The precise maximum-entropy form depends on the constraints imposed on the variable.
6 Maximum Entropy Distributions: With nonnegative values and a fixed mean but no other constraint, the exponential distribution is maximum entropy and has var(x) = µ^2.The paper identifies this case in Figure 5b.
6 Maximum Entropy Distributions: With fixed lower and upper bounds but no other constraint, the uniform distribution is maximum entropy and has variance (xmax − xmin)^2/12.This case is shown in Figure 5c.
Information Channels: Channel capacity is the maximum information a channel can provide at its output about its input, and it decreases as noise increases.Capacity is expressed in bits per usage or bits per second and depends on input, output, and noise entropies.

8 Shannon’s Source Coding Theorem

Shannon’s source coding theorem gives the limiting average transmission rate for encoding a source over a noiseless channel, while channel noise reduces usable information capacity.

Channel Capacity: A noiseless channel communicating R binary digits per second has capacity C numerically equal to R, although correlated outputs communicate at a lower rate R < C.Each binary digit can carry at most one bit, and correlation can make the information per digit less than one bit.
Shannon’s Source Coding Theorem: A source with entropy H bits per symbol can be encoded for transmission at an average rate arbitrarily close to C/H symbols per second, but not above C/H.Here C is channel capacity in bits per second, and the theorem applies to noiseless channels.
Shannon’s Source Coding Theorem: For the sum of two dice, source coding reduces the average representation from 3.46 binary digits to just over 3.27 per value.The latter is described as an average rate arbitrarily close to the source entropy.
Channel Capacity: Channel capacity is achieved by the input distribution p(x) that maximizes the entropy H(x), subject to constraints such as power limits.The distribution determines the maximum information carried by each input.
Noise Reduces Channel Capacity: For noisy channels, output entropy includes uncertainty caused by noise, so it does not all represent information about the input.Conditional entropy H(y|x) measures residual output uncertainty given the input and equals the entropy of the channel noise.
Noise Reduces Channel Capacity: A noise entropy H(η) = H(Y|X) means each input may produce 2^H(Y|X) equally probable outputs, while H(X|Y) counts possible inputs per output.The fan-diagram interpretation expresses conditional entropy as an equivalent number of equiprobable possibilities.

10 Mutual Information

Mutual information measures how much one variable reveals about another, while channel capacity is the maximum information rate compatible with noise. Shannon’s noisy-channel theorem shows that coding can approach this capacity with arbitrarily small error, but cannot exceed it.

10 Mutual Information: Mutual information I(x, y) is the average information that an input value provides about the output, and it is symmetric between input and output.The figure relates mutual information to entropy and conditional entropy under channel noise.
10 Mutual Information: Noise creates conditional uncertainty about both output given input and input given output, reducing the information communicated through a practical channel.Telephone signals illustrate how electrical components introduce spurious noise, while error-correcting codes reduce errors at a rate cost.
11 Shannon’s Noisy Channel Coding Theorem: If source entropy H is at most channel capacity C, coding can transmit the source with arbitrarily small error or equivocation.When H is at least C, the remaining equivocation is bounded below by H − C + ϵ.
11 Shannon’s Noisy Channel Coding Theorem: Shannon’s noisy-channel theorem permits transmission at rates arbitrarily close to channel capacity C with arbitrarily small error, but not above C.The theorem characterizes both reliable communication below capacity and the upper limit imposed by the channel.
10 Mutual Information: Channel capacity is defined by maximizing mutual information over input distributions, and the data processing inequality prevents output information from exceeding input information.With no noise, the capacity expression reduces to the noiseless-channel case.

12 The Gaussian Channel

The Gaussian channel models output as signal plus Gaussian noise and derives its maximum information rate from entropy and mutual information. Gaussian inputs maximize this rate, yielding Shannon’s capacity equation in terms of signal and noise power.

12 The Gaussian Channel: Gaussian inputs maximize H(x), which maximizes H(y) and therefore mutual information I(x, y).The argument relies on the sum of independent Gaussian variables remaining Gaussian.
12 The Gaussian Channel: Gaussian input, output, and noise variables make the average information per output value equal to channel capacity C.The output remains Gaussian because it is the sum of independent Gaussian signal and noise variables.
12 The Gaussian Channel: The Gaussian-channel capacity curve increases slowly with signal power when noise power is fixed at N = 1.Figure 9 describes the resulting diminishing increase in capacity as signal power grows.
12 The Gaussian Channel: The channel output y = x + η has variance v_y = v_x + v_η when signal and noise are independent Gaussian variables.This variance relation supports the entropy calculation used to derive capacity.
12 The Gaussian Channel: Gaussian channel capacity is expressed using signal power S and noise power N through their signal-to-noise ratio S/N.For zero-mean variables, variance equals power, so S = v_x and N = v_η.

13 Fourier Analysis

Fourier analysis represents a signal as weighted sine and cosine components, with coefficients describing each frequency’s amplitude, power, and phase. For Gaussian noisy signals, independent frequency components allow mutual information and channel capacity to be analyzed by summing across frequencies.

13 Fourier Analysis: Fourier analysis represents any signal as a weighted sum of sinusoidal components across its bandwidth.A signal containing frequencies from 0 Hz to W Hz has bandwidth W Hz.
13 Fourier Analysis: Each Fourier coefficient specifies the amount of cosine or sine at a frequency, while coefficient pairs determine that component’s power and phase.The coefficients are obtained from integrals against cosine and sine functions.
13 Fourier Analysis: Fourier components are mutually uncorrelated for any variable and mutually independent for Gaussian variables.For Gaussian variables, this permits entropy to be estimated by adding the entropies of the components.
13 Fourier Analysis: A bandwidth-W Gaussian channel sampled at the Nyquist rate has capacity 2WC bits per second.The Nyquist rate is 2W samples per second, with C defined as the capacity per sample.
13 Fourier Analysis: Mutual information between Gaussian signals can be obtained by summing the information carried by their frequency components.The per-frequency contribution depends on the signal-to-noise ratio S(f)/N(f).
13 Fourier Analysis: When peak total power is fixed, mutual information is maximized when S(f) + N(f) = k, producing a flat power spectrum.Sculpting the signal-plus-noise spectrum to be flat yields improved but diminishing returns.

14 A Very Short History of Information Theory

The paper presents Shannon’s information theory as a mathematical resolution to a longstanding problem of defining and measuring information. It places Shannon’s achievement within earlier work on entropy, signal processing, sampling, and information.

14 A Very Short History of Information Theory: The account emphasizes that major scientific theories depend on prior contributions rather than emerging independently.The paper connects Shannon’s work to earlier developments in the same way it connects Einstein to Newton.
14 A Very Short History of Information Theory: Shannon’s theory built on earlier work by Boltzmann, Gibbs, Wiener, Nyquist, and Hartley.These predecessors contributed work on thermodynamic entropy, signal processing, sampling, and information.
14 A Very Short History of Information Theory: Shannon produced a complete mathematical theory of information while addressing how information could be defined and measured.The paper describes this as a key scientific problem of his time.
14 A Very Short History of Information Theory: The paper portrays Shannon’s contribution as accelerating scientific progress on information theory.It says the theory might otherwise have taken decades to construct.

15 Key Equations

The paper collects equations for discrete and continuous entropy, joint and conditional information, and Gaussian-channel capacity. These equations connect probability distributions and signal-to-noise structure to information measured in bits or bits per second.

15 Key Equations: The equations define discrete and continuous entropy using probability masses or densities and logarithms with base 2 unless stated otherwise.The resulting information quantities are measured in bits.
15 Key Equations: Joint entropy, conditional entropy, and mutual information are expressed through joint and conditional probability distributions.The equations include both discrete sums and continuous integrals.
15 Key Equations: The chain rule for entropy follows from decomposing joint probability into conditional and marginal terms.The section explicitly introduces the chain rule after the joint-entropy expressions.
15 Key Equations: For an additive Gaussian channel, capacity depends on bandwidth W and the frequency-dependent signal-to-noise ratio S(f)/N(f).Data are transmitted at the Nyquist rate of 2W samples per second.
15 Key Equations: When input and noise variances are S and N and both are iid, the Gaussian-channel mutual information equals the capacity expression.The ratio S/N is identified as the signal-to-noise ratio.