The Gaussian Channel

Motivation: the channel that actually exists

Every channel in channel-capacity was discrete: a finite input alphabet, a finite output alphabet, a transition matrix. But the copper wire carries a voltage, and so does a radio link and a satellite downlink. The Gaussian channel is the continuous-alphabet model of that physical reality, and it is by a wide margin the most important channel in the theory.

It is a time-discrete channel with output $Y_i$ at time $i$ equal to the sum of the input $X_i$ and noise $Z_i$ :

$Y_i = X_i + Z_i, \qquad Z_i \sim \mathcal{N}(0, N)$

with $Z_i$ drawn i.i.d. and independent of the signal $X_i$ .

flowchart LR
  Xi["X_i"] --> S(("+"))
  Zi["Z_i ~ N(0, N)"] --> S
  S --> Yi["Y_i"]

IntuitionWhy Gaussian noise specifically

The additive noise in a real channel comes from a variety of causes — thermal agitation in the conductor, cosmic background, interference from countless distant sources. By the central limit theorem, the cumulative effect of a large number of small random effects is approximately normal, so the Gaussian assumption is valid in a large number of situations. It is not an arbitrary mathematical convenience; it is what physics hands you.

Why we must constrain the input

WarningWithout further conditions the capacity is infinite

Two separate ways this blows up:

Zero noise variance. The receiver gets the transmitted symbol perfectly, and since $X$ can take any real value, the channel transmits an arbitrary real number — infinitely many bits — with no error.
Nonzero noise but unconstrained input. Choose an infinite subset of inputs arbitrarily far apart. They are then distinguishable at the output with arbitrarily small error probability, and the capacity is again infinite.

So if the noise variance is zero or the input is unconstrained, capacity is infinite and the model says nothing.

The physically meaningful limitation is energy or power. We assume an average power constraint: for any codeword $(x_1, \ldots, x_n)$ ,

$\frac{1}{n}\sum_{i=1}^n x_i^2 \le P$

IntuitionWhat the power constraint is, physically

You can amplify a signal, but not for free and not without limit — the transmitter has a power supply, the regulator has a licence, the satellite has a solar panel. The constraint is what stops the “spread the codewords arbitrarily far apart” trick, and it is what makes the answer finite and interesting. Notice it constrains the average over the block, not each symbol — so a code may spend more on some symbols and less on others.

A first, suboptimal scheme

Before the theory, here is what an engineer would do naively. Suppose we want to send 1 bit in one channel use. Given the power constraint, the best we can do is send one of two levels, $+\sqrt{P}$ or $-\sqrt{P}$ — push them as far apart as the power budget allows. If both are equally likely, the optimum decoding rule is to decide $+\sqrt{P}$ if $Y > 0$ and $-\sqrt{P}$ if $Y < 0$ .

DerivationProbability of error for two-level signalling

$P_e = \frac{1}{2}\Pr\big(Y < 0 \mid X = +\sqrt{P}\big) + \frac{1}{2}\Pr\big(Y > 0 \mid X = -\sqrt{P}\big)$

Substituting $Y = X + Z$ , each event becomes a statement about the noise alone:

$= \frac{1}{2}\Pr\big(Z < -\sqrt{P}\big) + \frac{1}{2}\Pr\big(Z > \sqrt{P}\big) = \Pr\big(Z > \sqrt{P}\big)$

by symmetry of the Gaussian. Normalizing $Z$ by its standard deviation $\sqrt N$ :

$P_e = 1 - \Phi\!\left(\sqrt{\frac{P}{N}}\right)$

where $\Phi(x) = \int_{-\infty}^x \frac{1}{\sqrt{2\pi}} e^{-t^2/2}\, dt$ is the cumulative normal function.

ImportantWhat this scheme really did

It converted the Gaussian channel into a binary symmetric channel with crossover probability $P_e$ — so everything from channel-capacity now applies. Similarly a four-level input signal gives a discrete four-input channel, and practical modulation schemes use exactly these ideas.

The trade-off: the main advantage of a discrete channel is ease of processing the output for error correction. But some information is lost in the quantization — which is precisely the $\log\frac{1}{\Delta}$ story from the quantization relation. The rest of this chapter asks what is achievable without throwing that away.

Information capacity of the Gaussian channel

DefinitionInformation capacity with a power constraint

$C = \max_{f(x)\,:\, \mathbb{E}X^2 \le P} I(X;Y)$

The maximum of the mutual information over all input distributions satisfying the power constraint.

Component	Detail
What is given	The noise variance $N$ — the physics of the wire.
What is optimized	The input density $f(x)$ — the engineer’s modulation scheme.
What constrains it	$\mathbb{E}X^2 \le P$ — the transmitter’s power budget.
Difference from the discrete case	The maximization is over densities, and is restricted by a moment constraint rather than ranging over a whole simplex.

DerivationComputing the capacity

Step 1: Expand from the receiver’s side, and kill the noise term.

$I(X;Y) = h(Y) - h(Y \mid X) = h(Y) - h(X + Z \mid X) = h(Y) - h(Z \mid X) = h(Y) - h(Z)$

The third equality is translation invariance of differential entropy ([[differential-entropy#Behaviour under transformations| $h(X+c)=h(X)$ ]]): given $X = x$ , the variable $X + Z$ is just $Z$ shifted by the constant $x$ . The fourth uses independence of $Z$ from $X$ .

This is the crucial structural fact: $h(Z) = \tfrac12\log 2\pi e N$ is a constant the sender cannot influence, so maximizing $I$ reduces entirely to maximizing $h(Y)$ — exactly as it did for the symmetric discrete channels.

Step 2: Find the power available at the output.

$\mathbb{E}Y^2 = \mathbb{E}(X+Z)^2 = \mathbb{E}X^2 + 2\,\mathbb{E}X\,\mathbb{E}Z + \mathbb{E}Z^2 = P + N$

using independence and $\mathbb{E}Z = 0$ . The power constraint has now been converted into a variance constraint on $Y$ — which is exactly the hypothesis of the maximum-entropy theorem.

Step 3: Apply the Gaussian maximum-entropy bound. By the max-entropy theorem, a variable with second moment $P+N$ has $h(Y) \le \tfrac12\log 2\pi e(P+N)$ :

$I(X;Y) \le \frac{1}{2}\log 2\pi e(P+N) - \frac{1}{2}\log 2\pi e N = \frac{1}{2}\log\left(1 + \frac{P}{N}\right)$

Step 4: Achievability of the bound. Equality in the max-entropy step needs $Y \sim \mathcal{N}(0, P+N)$ , which is delivered by $X \sim \mathcal{N}(0,P)$ (sum of independent Gaussians is Gaussian).

FormulaCapacity of the Gaussian channel

$C = \max_{\mathbb{E}X^2 \le P} I(X;Y) = \frac{1}{2}\log\left(1 + \frac{P}{N}\right)$

attained when $X \sim \mathcal{N}(0, P)$ .

IntuitionReading the formula

$P/N$ is the signal-to-noise ratio. Capacity grows only logarithmically in it: to buy one extra bit per use you must roughly double the transmit power at high SNR. That diminishing return is the central economic fact of radio engineering. The optimal input is Gaussian — meaning a good code makes the transmitted signal look like noise, the continuous echo of the equality condition that a capacity-achieving code makes the channel output look like pure noise.

Codes for the Gaussian channel

Definition $(M, n)$ code with power constraint $P$

An index set $\{1, 2, \ldots, M\}$ .
An encoding function $x : \{1,\ldots,M\} \rightarrow \mathcal{X}^n$ yielding codewords satisfying the power constraint: for every codeword, $\sum_{i=1}^n x_i^2(w) \le nP, \qquad w = 1, \ldots, M$
A decoding function $g : \mathcal{Y}^n \rightarrow \{1, \ldots, M\}$ .

Rate and probability of error are as in the discrete case, with $P_e^{(n)} = \frac{1}{2^{nR}}\sum_i \lambda_i$ . A rate $R$ is achievable if there is a sequence of $(2^{nR}, n)$ codes whose codewords satisfy the power constraint and whose maximal error $\lambda^{(n)} \rightarrow 0$ . The capacity is the supremum of achievable rates.

TheoremCapacity of the Gaussian channel

$C = \frac{1}{2}\log\left(1 + \frac{P}{N}\right) \text{ bits per transmission}$

The sphere-packing picture

Before the proof, the geometric plausibility argument — which for this channel is unusually vivid, because the codewords really are points in $\mathbb{R}^n$ .

IntuitionCounting decoding spheres

Consider any codeword of length $n$ . The received vector is normally distributed with mean the true codeword and variance the noise variance, so with high probability it lies in a sphere of radius $\sqrt{n(N+\epsilon)}$ around the codeword. Assign everything in that sphere to that codeword; an error occurs only if the received vector escapes, which is unlikely.

How many such codewords fit? The volume of an $n$ -dimensional sphere is $C_n r^n$ . Each decoding sphere has radius $\sqrt{nN}$ . The received vectors have energy at most $n(P+N)$ , so they all live inside one big sphere of radius $\sqrt{n(P+N)}$ . The maximum number of non-intersecting decoding spheres is at most

$\frac{C_n\big(n(P+N)\big)^{n/2}}{C_n (nN)^{n/2}} = \left(\frac{P+N}{N}\right)^{n/2} = 2^{\frac{n}{2}\log\left(1 + \frac{P}{N}\right)}$

and the rate of such a code is $\tfrac12\log(1 + P/N)$ — the capacity, read straight off a volume ratio.

NoteWhat sphere packing does and does not establish

Like the preview argument in the discrete case, this indicates we cannot hope to send above $C$ with low error. It is an upper bound by counting. That we can almost achieve it is the content of the proof below.

ProofAchievability — random coding with two modifications

Same ideas as the discrete coding theorem: random codes and joint typicality decoding. Two modifications are needed: the power constraint and the fact that variables are continuous.

Step 1: Generate the codebook — with margin. We need every codeword to satisfy the power constraint. Generate each element i.i.d. $\mathcal{N}(0, P - \epsilon)$ , i.e. deliberately under-power. Since $\frac1n\sum X_i^2 \rightarrow P - \epsilon$ for large $n$ by the law of large numbers, the probability that a codeword violates the constraint is small. This $\epsilon$ of headroom is the first modification and exists purely to absorb the fluctuation of the sample power.

Step 2: Encoding. The codebook is revealed to sender and receiver; to send message $w$ , transmit codeword $X^n(w)$ .

Step 3: Decoding. Search the codebook for one codeword jointly typical with the received vector. If exactly one, declare it. Otherwise declare an error — and also declare an error if the chosen codeword violates the power constraint.

Step 4: Probability of error. Assume codeword 1 was sent, so $Y^n = X^n(1) + Z^n$ . Define

$E_0 = \left\{ \frac{1}{n}\sum_{j=1}^n X_j^2(1) > P \right\}, \qquad E_i = \left\{ (X^n(i), Y^n) \in A_\epsilon^{(n)} \right\}$

An error occurs if $E_0$ (power violated), or $E_1^c$ (true codeword not jointly typical), or $E_2 \cup \cdots \cup E_{2^{nR}}$ (a wrong codeword is). $E_0$ is the second modification — a failure mode with no discrete analogue. By the union bound,

$\Pr(\mathcal{E} \mid W=1) \le P(E_0) + P(E_1^c) + \sum_{i=2}^{2^{nR}} P(E_i)$

Step 5: Bound the three terms. $P(E_0) \rightarrow 0$ by the law of large numbers (Step 1’s margin). $P(E_1^c) \rightarrow 0$ by the joint AEP, which can be proved by the same argument as the discrete case, so $P(E_1^c) \le \epsilon$ for large $n$ . And since $X^n(1)$ and $X^n(i)$ are independent by construction, so are $Y^n$ and $X^n(i)$ , giving $P(E_i) \le 2^{-n(I(X;Y) - 3\epsilon)}$ .

Step 6: Assemble.

$P_e^{(n)} \le \epsilon + \epsilon + \big(2^{nR} - 1\big)2^{-n(I(X;Y) - 3\epsilon)} \le 2\epsilon + 2^{3n\epsilon}2^{-n(I(X;Y) - R)} \le 3\epsilon$

for $n$ sufficiently large and $R < I(X;Y) - 3\epsilon$ .

Step 7: From average to maximal error — and a bonus. Choose a good codebook and delete the worst half of the codewords, exactly as in the discrete proof. Note the happy side effect: codewords violating the power constraint have probability of error 1, so they are necessarily in the discarded half. The surviving code therefore satisfies the power constraint outright, and achieves a rate arbitrarily close to capacity.

∎

Converse for the Gaussian channel

The proof parallels the discrete converse. The main new ingredient is the power constraint, and the interesting question is where it enters.

ProofConverse — Fano, single-letterization, then Jensen on the power allocation

We must show $P_e^{(n)} \rightarrow 0$ forces $R \le \tfrac12\log(1 + P/N)$ .

Step 1: Fano. Let $W$ be uniform on $\{1, \ldots, 2^{nR}\}$ ; the uniform distribution on messages induces one on codewords and hence on the input alphabet, specifying a joint law on $W \to X^n(W) \to Y^n \to \hat{W}$ . Then

$H(W \mid \hat{W}) \le 1 + nRP_e^{(n)} = n\epsilon_n, \qquad \epsilon_n \rightarrow 0$

Step 2: The standard chain.

$nR = H(W) = I(W;\hat{W}) + H(W \mid \hat{W}) \le I(W;\hat{W}) + n\epsilon_n \le I(X^n;Y^n) + n\epsilon_n$

$= h(Y^n) - h(Y^n \mid X^n) + n\epsilon_n = h(Y^n) - h(Z^n) + n\epsilon_n$

Step 3: Single-letterize. Apply the independence bound to $h(Y^n)$ and independence of the noise samples to $h(Z^n)$ :

$\le \sum_{i=1}^n h(Y_i) - \sum_{i=1}^n h(Z_i) + n\epsilon_n = \sum_{i=1}^n I(X_i;Y_i) + n\epsilon_n$

Step 4: Here is where the power constraint enters. Define the average power of the $i$ th column of the codebook,

$P_i = \frac{1}{2^{nR}}\sum_w x_i^2(w)$

Since $Y_i = X_i + Z_i$ with $X_i, Z_i$ independent, $\mathbb{E}Y_i^2 = P_i + N$ , and by the max-entropy theorem $h(Y_i) \le \tfrac12\log 2\pi e(P_i + N)$ . Hence

$nR \le \sum_i \left[\frac{1}{2}\log 2\pi e (P_i + N) - \frac{1}{2}\log 2\pi e N\right] + n\epsilon_n = \sum_i \frac{1}{2}\log\left(1 + \frac{P_i}{N}\right) + n\epsilon_n$

Step 5: Jensen finishes it. Every codeword satisfies the power constraint, so their average does too: $\frac1n \sum_i P_i \le P$ . Since $f(x) = \tfrac12\log(1+x)$ is concave, Jensen’s inequality moves the average inside:

$\frac{1}{n}\sum_{i=1}^n \frac{1}{2}\log\left(1 + \frac{P_i}{N}\right) \le \frac{1}{2}\log\left(1 + \frac{1}{n}\sum_{i=1}^n \frac{P_i}{N}\right) \le \frac{1}{2}\log\left(1 + \frac{P}{N}\right)$

So $R \le \tfrac12\log(1 + P/N) + \epsilon_n$ with $\epsilon_n \rightarrow 0$ .

∎

IntuitionWhat Jensen is doing physically

Step 5 says spreading your power unevenly across the $n$ coordinates cannot help. Concavity of $\log(1+x)$ means the capacity gained from a watt in a quiet coordinate is less than the capacity lost by taking it from another — when all coordinates have the same noise level $N$ . Hold that thought: when the coordinates have different noise levels, uneven allocation does help, and that is exactly .

Bandlimited channels

The problem. Everything so far is time-discrete: one input per channel use. A real radio or telephone channel is continuous-time with a bandwidth limit. How do the two connect, and what is the capacity in bits per second rather than per use?

The model: the output is the convolution

$Y(t) = \big(X(t) + Z(t)\big) * h(t)$

where $X(t)$ is the signal waveform, $Z(t)$ is white Gaussian noise, and $h(t)$ is the impulse response of an ideal bandpass filter cutting out all frequencies greater than $W$ .

TheoremNyquist–Shannon sampling theorem

Suppose a function $f(t)$ is bandlimited to $W$ — its spectrum is 0 for all frequencies greater than $W$ . Then the function is completely determined by samples spaced $\frac{1}{2W}$ seconds apart.

IntuitionWhy sampling works

If a signal is bandlimited to $W$ , it cannot change by a substantial amount in a time less than half a cycle of its maximum frequency — that is, it cannot change much over intervals shorter than $\frac{1}{2W}$ seconds. The bandwidth limit is a smoothness guarantee, and smooth functions are determined by samples.

ProofSampling theorem

Step 1: The band limit truncates the inverse Fourier integral. Let $F(\omega)$ be the Fourier transform of $f(t)$ . Since $F(\omega) = 0$ outside $-2\pi W \le \omega \le 2\pi W$ ,

$f(t) = \frac{1}{2\pi}\int_{-\infty}^{\infty} F(\omega)e^{i\omega t} d\omega = \frac{1}{2\pi}\int_{-2\pi W}^{2\pi W} F(\omega)e^{i\omega t} d\omega$

Step 2: Recognize the samples as Fourier coefficients. At the sample points,

$f\!\left(\frac{n}{2W}\right) = \frac{1}{2\pi}\int_{-2\pi W}^{2\pi W} F(\omega)e^{i\omega \frac{n}{2W}} d\omega$

The right-hand side is also the definition of the Fourier series coefficients of the periodic extension of $F(\omega)$ , taking $(-2\pi W, 2\pi W)$ as the fundamental period. So the samples determine the Fourier coefficients, hence $F(\omega)$ on that interval, hence (since $F$ vanishes outside) $F$ entirely, hence $f$ .

Step 3: Explicit reconstruction. Define $\text{sinc}(t) = \frac{\sin(2\pi Wt)}{2\pi Wt}$ , which is 1 at $t=0$ , zero at $t = n/2W$ for $n \ne 0$ , and has a spectrum constant on $(-W, W)$ and zero outside. Then

$g(t) = \sum_{n=-\infty}^{\infty} f\!\left(\frac{n}{2W}\right)\text{sinc}\!\left(t - \frac{n}{2W}\right)$

is bandlimited to $W$ and matches $f$ at every sample point. Since only one function satisfies both constraints, $g(t) = f(t)$ .

∎

ImportantDegrees of freedom — the bridge to the discrete theory

A general function has an infinite number of degrees of freedom: its value at every point is free. The sampling theorem says a bandlimited function has only $2W$ degrees of freedom per second. This is the whole reason the continuous-time channel reduces to the discrete-time one we already solved.

NoteAlmost-bandlimited, almost-timelimited functions

A bandlimited function cannot be time-limited. But we can consider functions with most of their energy in bandwidth $W$ and most of it in a finite interval $(0,T)$ . These are described by a basis of prolate spheroidal functions: there are about $2TW$ orthonormal basis functions for this set. Moreover the projection of white noise on these basis vectors is an i.i.d. Gaussian process — which is what lets us reuse the i.i.d. noise model. So bandlimited, time-limited functions are vectors in a $2TW$ -dimensional space.

DerivationFrom samples to the capacity formula

Step 1: Discretize. With bandwidth $W$ , represent input and output by samples $1/2W$ seconds apart. Since the noise is white and Gaussian, each noise sample is an i.i.d. Gaussian random variable.

Step 2: Noise power per sample. If the noise has power spectral density $N_0/2$ watts/Hz and bandwidth $W$ Hz, the total noise power is $\frac{N_0}{2} \cdot 2W = N_0 W$ . Over time $T$ there are $2WT$ samples, so each has variance $\frac{N_0 W T}{2WT} = \frac{N_0}{2}$ .

Step 3: Signal energy per sample. Over $[0,T]$ the energy is $PT$ spread over $2WT$ samples, so $\frac{PT}{2WT} = \frac{P}{2W}$ per sample.

Step 4: Apply the discrete-time result.

$C = \frac{1}{2}\log\left(1 + \frac{P/2W}{N_0/2}\right) = \frac{1}{2}\log\left(1 + \frac{P}{N_0 W}\right) \text{ bits per sample}$

Step 5: Convert to bits per second. There are $2W$ samples each second.

FormulaCapacity of a bandlimited Gaussian channel

$C = W \log\left(1 + \frac{P}{N_0 W}\right) \text{ bits per second}$

ImportantOne of the most famous formulas in information theory

It gives the capacity of a bandlimited Gaussian channel with noise spectral density $N_0/2$ watts/Hz and power $P$ watts. Everything in this entire set of notes — surprise, entropy, mutual information, typical sets, joint typicality, the coding theorem, differential entropy, maximum entropy — exists to make this line true and computable.

(A more precise version involves signals with a small fraction of their energy outside band $W$ and outside $(0,T)$ ; the formula is the limit as that fraction goes to zero.)

CorollaryInfinite bandwidth

Letting $W \rightarrow \infty$ ,

$C = \frac{P}{N_0}\log_2 e \text{ bits per second}$

So for infinite-bandwidth channels, capacity grows linearly with power — the logarithmic penalty disappears once bandwidth is free. Bandwidth and power are substitutes, but not equally: you can always trade more bandwidth for less power until this floor.

ExampleThe telephone line

To allow multiplexing, telephone signals are bandlimited to 3300 Hz. With that bandwidth and an SNR of 33 dB (i.e. $P/N_0W = 2000$ ), the capacity is about 36,000 bits per second. Practical modems achieve up to 33,600 bits/s in both directions — remarkably close. Real channels also suffer crosstalk, interference, echoes, and non-flat response, which must be compensated for.

The V.90 modems reaching 56 kb/s do so in one direction only, exploiting a purely digital path from server to the final telephone switch; the only impairments are the digital-to-analog conversion at the switch and noise on the copper link to the home, reducing 64 kb/s to 56 kb/s at best.

The actual bandwidth on that copper is a few megahertz (depending on wire length), with a far-from-flat frequency response. Using the whole band allows a few megabits per second — which is what DSL does, using special equipment at both ends (unlike modems, which need no change at the switch).

Parallel Gaussian channels and water-filling

The problem. Consider $k$ independent Gaussian channels in parallel sharing one total power budget. How should the power be distributed to maximize capacity? This models a non-white additive Gaussian noise channel, where each parallel component represents a different frequency.

flowchart LR
  X1["X_1"] --> S1(("+")) --> Y1["Y_1"]
  Z1["Z_1 ~ N(0, N_1)"] --> S1
  Xk["X_k"] --> Sk(("+")) --> Yk["Y_k"]
  Zk["Z_k ~ N(0, N_k)"] --> Sk

For channel $j$ : $Y_j = X_j + Z_j$ with $Z_j \sim \mathcal{N}(0, N_j)$ , noise independent from channel to channel, and a common constraint $\mathbb{E}\sum_{j=1}^k X_j^2 \le P$ .

$C = \max_{f(x_1,\ldots,x_k)\,:\,\mathbb{E}\sum X_i^2 \le P} I(X_1, \ldots, X_k ; Y_1, \ldots, Y_k)$

DerivationDecomposing the joint mutual information

Since $Z_1, \ldots, Z_k$ are independent,

$I(X_1,\ldots,X_k; Y_1,\ldots,Y_k) = h(Y_1,\ldots,Y_k) - h(Z_1,\ldots,Z_k \mid X_1,\ldots,X_k)$

$= h(Y_1,\ldots,Y_k) - h(Z_1,\ldots,Z_k) = h(Y_1,\ldots,Y_k) - \sum_i h(Z_i)$

Applying the independence bound to the joint output entropy, then the single-channel result to each term:

$\le \sum_i \big[h(Y_i) - h(Z_i)\big] \le \sum_i \frac{1}{2}\log\left(1 + \frac{P_i}{N_i}\right)$

where $P_i = \mathbb{E}X_i^2$ and $\sum P_i = P$ . Equality is achieved by an independent Gaussian vector, $(X_1,\ldots,X_k) \sim \mathcal{N}(0, \text{diag}(P_1, \ldots, P_k))$ .

So the problem reduces to the power allotment: maximize $\sum_i \tfrac12\log(1 + P_i/N_i)$ subject to $\sum_i P_i = P$ .

DerivationLagrange multipliers and the Kuhn–Tucker correction

Write the functional

$J(P_1, \ldots, P_k) = \sum_i \frac{1}{2}\log\left(1 + \frac{P_i}{N_i}\right) + \lambda \sum_i P_i$

and differentiate with respect to $P_i$ :

$\frac{1}{2}\frac{1}{P_i + N_i} + \lambda = 0 \quad \Longrightarrow \quad P_i = \nu - N_i$

The catch: the $P_i$ must be non-negative, and for a noisy enough channel $\nu - N_i$ is negative — so a solution of this form may not exist. The Kuhn–Tucker conditions confirm that the correct solution clips at zero.

FormulaWater-filling

$P_i = (\nu - N_i)^+, \qquad \text{with } \nu \text{ chosen so that } \sum_i (\nu - N_i)^+ = P$

where $(x)^+ = x$ if $x \ge 0$ and $0$ if $x < 0$ .

IntuitionWhy it is called water-filling

Picture the noise levels $N_i$ as the uneven floor of a vessel, with one bin per channel. Pour in a volume of water equal to the total power $P$ . As the power is increased from zero, it goes first to the channels with the lowest noise; as more is added, some spills into noisier channels. The water finds a common surface level $\nu$ , and the depth over bin $i$ is exactly $P_i = (\nu - N_i)^+$ . Bins whose floor sits above the waterline get nothing at all — a channel too noisy to be worth using is simply switched off.

Contrast the converse for the single channel, where Jensen said even power allocation is optimal. That was because all coordinates shared one noise level $N$ ; here they do not, and the asymmetry is what makes uneven allocation pay.

Channels with colored Gaussian noise

The problem. In the parallel case the noise samples were independent. Now let them be dependent. This covers not only correlated parallel channels but also channels with memory: for a channel with memory, treat a block of $n$ consecutive uses as $n$ parallel channels with dependent noise.

Let $K_Z$ be the noise covariance and $K_X$ the input covariance. The power constraint $\frac1n\sum_i \mathbb{E}X_i^2 \le P$ becomes

$\frac{1}{n}\text{tr}(K_X) \le P$

WarningThe capacity now depends on $n$

Unlike the parallel case, the power constraint here depends on $n$ , so the capacity must be calculated for each $n$ separately.

DerivationReducing to a determinant maximization

Step 1: The noise entropy is fixed. As always,

$I(X_1,\ldots,X_n; Y_1,\ldots,Y_n) = h(Y^n) - h(Z^n)$

and $h(Z^n)$ depends only on the noise distribution, not on our input choice. So finding the capacity amounts to maximizing $h(Y^n)$ .

Step 2: Gaussian input is optimal. Output entropy is maximized when $Y$ is normal, which is achieved when the input is normal. Since input and noise are independent, $K_Y = K_X + K_Z$ , and by the multivariate normal entropy,

$h(Y^n) = \frac{1}{2}\log\big((2\pi e)^n \lvert K_X + K_Z \rvert\big)$

So we must maximize $\lvert K_X + K_Z \rvert$ subject to a trace constraint on $K_X$ .

Step 3: Diagonalize the noise. Decompose $K_Z = Q\Lambda Q^t$ with $QQ^t = I$ . Then

$\lvert K_X + K_Z\rvert = \lvert K_X + Q\Lambda Q^t \rvert = \lvert Q \rvert \lvert Q^t K_X Q + \Lambda \rvert \lvert Q^t \rvert = \lvert A + \Lambda \rvert$

where $A = Q^t K_X Q$ .

Step 4: The trace constraint is preserved. Since $\text{tr}(BC) = \text{tr}(CB)$ ,

$\text{tr}(A) = \text{tr}(Q^t K_X Q) = \text{tr}(QQ^t K_X) = \text{tr}(K_X)$

This is why the rotation is free — changing basis does not spend any extra power. So: maximize $\lvert A + \Lambda \rvert$ subject to $\text{tr}(A) \le nP$ .

Step 5: Hadamard forces $A$ diagonal. By Hadamard’s inequality, $\lvert A + \Lambda \rvert \le \prod_i (A_{ii} + \lambda_i)$ with equality iff $A$ is diagonal. So the optimum is diagonal, and we are maximizing a product $\prod_i(A_{ii} + \lambda_i)$ under $\frac1n\sum_i A_{ii} \le P$ , $A_{ii}\ge0$ — which is the same problem as before.

FormulaWater-filling on the noise eigenvalues

$A_{ii} = (\nu - \lambda_i)^+ \qquad \text{with } \nu \text{ chosen so that } \sum_i A_{ii} = nP$

ImportantWater-filling in the spectral domain

Consider a channel whose additive Gaussian noise is a stationary stochastic process. Then the covariance matrix is Toeplitz, and the density of eigenvalues on the real line tends to the power spectrum of the process. So the eigenvalue water-filling above translates into water-filling across frequency:

The input signal should be a Gaussian process whose spectrum is large at frequencies where the noise spectrum is small. Pour your transmit power into the quiet parts of the band, and abandon the frequencies where interference is loudest. The capacity is

$C = \int_{-\pi}^{\pi} \frac{1}{2}\log\left(1 + \frac{(\nu - N(f))^+}{N(f)}\right) df$

with $\nu$ chosen so that $\int (\nu - N(f))^+ df = P$ . This is the theoretical justification for what every modern modem, DSL line and Wi-Fi radio actually does when it probes the channel and allocates bits per subcarrier.

Gaussian channels with feedback

In channel-capacity we proved feedback does not increase capacity for discrete memoryless channels. The same holds for a memoryless Gaussian channel (white noise).

ImportantBut with memory, feedback does help

For channels with memory — noise correlated from one instant to the next — feedback does increase capacity. The capacity without feedback is computed by water-filling, but we have no simple explicit characterization of the capacity with feedback. What we can do is bound the gain, and the answer is that it is small.

The channel is $Y_i = X_i + Z_i$ with $Z_i \sim \mathcal{N}(0, K_Z^{(n)})$ , and feedback lets the input depend on past outputs.

flowchart LR
  W["W"] --> E[Encoder]
  E --> Xi["X_i(W, Y^(i-1))"]
  Xi --> S(("+")) --> Yi["Y_i"]
  Zi["Z_i"] --> S
  Yi -.->|feedback| E

DefinitionFeedback code for the Gaussian channel

A $(2^{nR}, n)$ code with feedback is a sequence of mappings $x_i(W, Y^{i-1})$ — so $x(W, \cdot)$ is a code function rather than a codeword — satisfying the power constraint

$\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^n x_i^2(w, Y^{i-1})\right] \le P, \qquad w \in \{1, \ldots, 2^{nR}\}$

where the expectation is over all possible noise sequences.

Warning $X^n$ and $Z^n$ are no longer independent

Because of the feedback, $X_i$ depends causally on past values of $Z$ . Every argument in this chapter that used independence of signal and noise must be re-examined.

FormulaCapacity with and without feedback

With feedback: $C_{n,FB} = \max_{\frac{1}{n}\text{tr}(K_X^{(n)}) \le P} \frac{1}{2n}\log \frac{\lvert K_{X+Z}^{(n)} \rvert}{\lvert K_Z^{(n)} \rvert}$ where the maximization is over all $X^n$ of the form $X_i = \sum_{j=1}^{i-1} b_{ij}Z_j + V_i$ with $V^n$ independent of $Z^n$ .

Without feedback: $C_n = \max_{\frac1n \text{tr}(K_X^{(n)}) \le P} \frac{1}{2n}\log\frac{\lvert K_X^{(n)} + K_Z^{(n)}\rvert}{\lvert K_Z^{(n)}\rvert}$ which reduces to water-filling on the eigenvalues $\{\lambda_i^{(n)}\}$ of $K_Z^{(n)}$ : $C_n = \frac{1}{2n}\sum_{i=1}^n \log\left(1 + \frac{(\lambda - \lambda_i^{(n)})^+}{\lambda_i^{(n)}}\right), \qquad \sum_i (\lambda - \lambda_i^{(n)})^+ = nP$

NoteWhy the restricted form of $X^n$ loses nothing

The distribution on $X^n + Z^n$ achieving maximum entropy is Gaussian; since $Z^n$ is Gaussian too, a jointly Gaussian $(X^n, Z^n, X^n+Z^n)$ achieves the maximum. And since $Z^n = Y^n - X^n$ , the most general jointly normal causal dependence of $X^n$ on $Y^n$ is exactly $X_i = \sum_{j<i} b_{ij}Z_j + V_i$ , with $V^n$ playing the role of the innovations process. Recast as $X = BZ + V$ , $Y = X+Z$ :

$C_{n,FB} = \max \frac{1}{2n}\log\frac{\lvert (B+I)K_Z^{(n)}(B+I)^t + K_V\rvert}{\lvert K_Z^{(n)}\rvert}$

over nonnegative definite $K_V$ and strictly lower triangular $B$ with $\text{tr}(BK_Z^{(n)}B^t + K_V) \le nP$ . Lower-triangularity is causality: $X_i$ may see only past noise. Note $B = 0$ when feedback is not allowed.

TheoremUpper bound on the feedback rate

For a Gaussian channel with feedback, any sequence of $(2^{nR_n}, n)$ codes with $P_e^{(n)} \rightarrow 0$ satisfies $R_n \le C_{n,FB} + \epsilon_n$ with $\epsilon_n \rightarrow 0$ . (This bound is in fact achievable and therefore is the capacity, though we do not prove that.)

ProofConverse with feedback

Fano gives $H(W\mid\hat W) \le 1 + nR_nP_e^{(n)} = n\epsilon_n$ . Then

$nR_n = H(W) = I(W;\hat{W}) + H(W \mid \hat W) \le I(W;Y^n) + n\epsilon_n = \sum_i I(W; Y_i \mid Y^{i-1}) + n\epsilon_n$

$\overset{(a)}{=} \sum_i \left[h(Y_i \mid Y^{i-1}) - h(Y_i \mid W, Y^{i-1}, X_i, X^{i-1}, Z^{i-1})\right] + n\epsilon_n$

$\overset{(b)}{=} \sum_i \left[h(Y_i\mid Y^{i-1}) - h(Z_i \mid W, Y^{i-1}, X_i, X^{i-1}, Z^{i-1})\right] + n\epsilon_n$

$\overset{(c)}{=} \sum_i \left[h(Y_i\mid Y^{i-1}) - h(Z_i \mid Z^{i-1})\right] + n\epsilon_n = h(Y^n) - h(Z^n) + n\epsilon_n$

where (a) holds because $X_i$ is a function of $W$ and past $Y$ ‘s, and $Z^{i-1} = Y^{i-1} - X^{i-1}$ — so all those extra conditioning variables are free; (b) uses $Y_i = X_i + Z_i$ and $h(X+Z\mid X) = h(Z\mid X)$ ; (c) uses that $Z_i$ and $(W, Y^{i-1}, X^i)$ are conditionally independent given $Z^{i-1}$ . Dividing by $n$ and applying the entropy-maximizing property of the normal,

$R_n \le \frac{1}{2n}\log\frac{\lvert K_Y^{(n)}\rvert}{\lvert K_Z^{(n)}\rvert} + \epsilon_n \le C_{n,FB} + \epsilon_n$

∎

Matrix lemmas

Four lemmas about determinants, each proved by an information-theoretic argument — a nice inversion of the usual direction.

Lemma1. Covariance identity

$K_{X+Z} + K_{X-Z} = 2K_X + 2K_Z$ .

ProofExpand both sides

$K_{X+Z} = K_X + K_{XZ} + K_{ZX} + K_Z$ and $K_{X-Z} = K_X - K_{XZ} - K_{ZX} + K_Z$ ; the cross terms cancel on addition.

∎

Lemma2. Determinant monotonicity

For nonnegative definite $A, B$ , if $A - B$ is nonnegative definite then $\lvert A \rvert \ge \lvert B \rvert$ .

ProofBuild random vectors with those covariances

Let $C = A - B$ . Since $B, C$ are nonnegative definite, treat them as covariances: take independent $X_1 \sim \mathcal{N}(0,B)$ , $X_2 \sim \mathcal{N}(0,C)$ , and set $Y = X_1 + X_2$ (so $K_Y = A$ ). Then

$h(Y) \ge h(Y \mid X_2) = h(X_1 \mid X_2) = h(X_1)$

by conditioning-reduces-entropy and independence. Substituting the normal entropy formula gives $\tfrac12\log(2\pi e)^n\lvert A\rvert \ge \tfrac12\log(2\pi e)^n \lvert B \rvert$ .

∎

Lemma3. Sum covariance bound

$\lvert K_{X+Z}\rvert \le 2^n \lvert K_X + K_Z\rvert$ .

ProofLemma 1 then Lemma 2

From Lemma 1, $2(K_X + K_Z) - K_{X+Z} = K_{X-Z} \succeq 0$ , so Lemma 2 gives $\lvert K_{X+Z}\rvert \le \lvert 2(K_X+K_Z)\rvert = 2^n\lvert K_X + K_Z\rvert$ .

∎

Lemma4. Log-concavity of the determinant

For nonnegative definite $A, B$ and $0 \le \lambda \le 1$ , $\lvert \lambda A + (1-\lambda)B \rvert \ge \lvert A\rvert^\lambda \lvert B \rvert^{1-\lambda}$ .

ProofA mixture random vector

Let $\mathbf{X}\sim\mathcal{N}_n(0,A)$ , $\mathbf{Y}\sim\mathcal{N}_n(0,B)$ , and let $\theta$ be 1 w.p. $\lambda$ and 2 w.p. $1-\lambda$ , independent of both. Define $\mathbf{Z} = \mathbf{X}$ if $\theta=1$ , else $\mathbf{Y}$ . Then $K_\mathbf{Z} = \lambda A + (1-\lambda)B$ and

$\frac12\ln(2\pi e)^n\lvert \lambda A + (1-\lambda)B\rvert \ge h(\mathbf{Z}) \ge h(\mathbf{Z}\mid\theta) = \lambda h(\mathbf{X}) + (1-\lambda)h(\mathbf{Y}) = \frac12\ln(2\pi e)^n \lvert A\rvert^\lambda\lvert B\rvert^{1-\lambda}$

The first inequality is the Gaussian max-entropy property under a covariance constraint; the second is conditioning reduces entropy.

∎

DefinitionCausally related

$X^n$ is causally related to $Z^n$ if $f(x^n, z^n) = f(z^n)\prod_{i=1}^n f(x_i \mid x^{i-1}, z^{i-1})$ Feedback codes necessarily yield causally related $(X^n, Z^n)$ .

Lemma5. Causality bound

If $X^n$ and $Z^n$ are causally related, then $h(X^n - Z^n) \ge h(Z^n)$ and hence $\lvert K_{X-Z}\rvert \ge \lvert K_Z \rvert$ .

ProofChain rule, then conditional determinism

$h(X^n - Z^n) \overset{(a)}{=} \sum_i h(X_i - Z_i \mid X^{i-1}-Z^{i-1}) \overset{(b)}{\ge} \sum_i h(X_i - Z_i \mid X^{i-1}, Z^{i-1}, X_i)$

$\overset{(c)}{=} \sum_i h(Z_i \mid X^{i-1}, Z^{i-1}, X_i) \overset{(d)}{=} \sum_i h(Z_i\mid Z^{i-1}) \overset{(e)}{=} h(Z^n)$

with (a) the chain rule, (b) conditioning reduces entropy, (c) the conditional determinism of $X_i$ plus translation invariance of $h$ , (d) the causal relationship, (e) the chain rule again. The determinant statement follows by taking a multivariate normal causally related pair with the same covariance structure and substituting the normal entropy formula.

∎

How much feedback buys

TheoremFeedback adds at most half a bit

$C_{n,FB} \le C_n + \frac{1}{2} \text{ bits per transmission}$

ProofChain the lemmas

$C_{n,FB} \le \max_{\text{tr}(K_X)\le nP} \frac{1}{2n}\log\frac{\lvert K_Y\rvert}{\lvert K_Z\rvert} \le \max \frac{1}{2n}\log\frac{2^n\lvert K_X+K_Z\rvert}{\lvert K_Z\rvert} = \max \frac{1}{2n}\log\frac{\lvert K_X+K_Z\rvert}{\lvert K_Z\rvert} + \frac{1}{2} \le C_n + \frac{1}{2}$

using the feedback converse, Lemma 3 (whose factor $2^n$ becomes the $\tfrac12$ after $\frac{1}{2n}\log 2^n$ ), and the definition of $C_n$ .

∎

TheoremFeedback at most doubles capacity (Pinsker)

$C_{n,FB} \le 2C_n$

ProofShow

\frac{1}{2}\cdot\frac{1}{2n}\log\frac{\lvert K_{X+Z}\rvert}{\lvert K_Z\rvert} \le \frac{1}{2n}\log\frac{\lvert K_X+K_Z\rvert}{\lvert K_Z\rvert}

$\frac{1}{2n}\log\frac{\lvert K_X+K_Z\rvert}{\lvert K_Z\rvert} \overset{(a)}{=} \frac{1}{2n}\log\frac{\lvert \frac12 K_{X+Z} + \frac12 K_{X-Z}\rvert}{\lvert K_Z\rvert} \overset{(b)}{\ge} \frac{1}{2n}\log\frac{\lvert K_{X+Z}\rvert^{1/2}\lvert K_{X-Z}\rvert^{1/2}}{\lvert K_Z\rvert}$

$\overset{(c)}{\ge} \frac{1}{2n}\log\frac{\lvert K_{X+Z}\rvert^{1/2}\lvert K_Z\rvert^{1/2}}{\lvert K_Z\rvert} \overset{(d)}{=} \frac{1}{2}\cdot\frac{1}{2n}\log\frac{\lvert K_{X+Z}\rvert}{\lvert K_Z\rvert}$

with (a) Lemma 1, (b) Lemma 4, and (c) Lemma 5 — the only step where causality is used. Maximizing each side in turn gives $C_{n,FB} \le 2C_n$ .

∎

ImportantThe bottom line on feedback

Gaussian channel capacity is increased by at most half a bit per transmission, and at most a factor of two. Feedback helps — but not by much. Combined with the discrete result that it helps not at all for memoryless channels, the overall picture is: feedback is enormously valuable for simplifying encoder and decoder design (recall retransmission on the erasure channel) and essentially worthless for raising the rate.

Quick reference

Object	Formula	Note
Channel model	$Y_i = X_i + Z_i$ , $Z_i \sim \mathcal{N}(0,N)$	Power constraint $\frac1n\sum x_i^2 \le P$ required or $C = \infty$ .
Two-level signalling	$P_e = 1 - \Phi(\sqrt{P/N})$	Turns the AWGN channel into a BSC.
Capacity	$C = \tfrac12\log(1 + P/N)$	Achieved by $X \sim \mathcal{N}(0,P)$ .
Sphere packing	$\big(\frac{P+N}{N}\big)^{n/2}$ spheres	Capacity as a volume ratio.
Sampling theorem	$2W$ degrees of freedom/second	Bridges continuous- to discrete-time.
Bandlimited capacity	$C = W\log\big(1 + \frac{P}{N_0W}\big)$ bits/s	The Shannon–Hartley formula.
Infinite bandwidth	$C = \frac{P}{N_0}\log_2 e$ bits/s	Capacity becomes linear in power.
Parallel channels	$P_i = (\nu - N_i)^+$ , $\sum P_i = P$	Water-filling; noisy channels switched off.
Colored noise	$A_{ii} = (\nu - \lambda_i)^+$	Water-filling on noise eigenvalues.
Stationary noise	$C = \int \tfrac12\log\big(1 + \frac{(\nu - N(f))^+}{N(f)}\big) df$	Water-filling across frequency.
Feedback	$C_{n,FB} \le C_n + \tfrac12$ and $C_{n,FB} \le 2C_n$	Helps with complexity, not with rate.

Facts to keep to hand:

The capacity derivation is three moves: $h(Y\mid X) = h(Z)$ by translation invariance $\to$ power constraint becomes a variance constraint on $Y$ $\to$ Gaussian max-entropy bound. Every capacity in this chapter, including the colored-noise one, is that same sequence.
Where the power constraint enters each argument: the codebook generation margin ( $\mathcal{N}(0, P-\epsilon)$ ) in achievability; the column powers $P_i$ plus Jensen in the converse; the trace constraint in the matrix version.
Jensen says even power allocation is optimal when noise levels are equal; water-filling says uneven allocation is optimal when they differ. Same concavity, opposite conclusions, because the constraint set changed.
Gaussian maximum entropy is used at least five times in this chapter (capacity bound, converse Step 4, parallel channels, colored noise, Lemmas 2 and 4). It is the workhorse.
Every matrix lemma in the feedback section is proved by building random vectors with the right covariance and applying an entropy inequality — determinant inequalities from information theory, as with Hadamard.

References

[[lit/cover2006-elements|Cover & Thomas, Elements of Information Theory]] — Chapter 9

Related