Foundations

Mutual information measures statistical dependence in bits.

Entropy bounds asymptotic compression for an iid source.

Capacity is the maximal asymptotically reliable rate.

Separated codewords permit bounded symbol-error recovery.

Protocol layers divide communication responsibilities.

TCP orders bytes and retransmits detected losses.

For finite X,Y, H(X|Y)=Σy p(y)H(X|Y=y) and H(X,Y)=H(Y)+H(X|Y).

For finite distributions p,q, D(p‖q)=Σx p(x)log₂[p(x)/q(x)]≥0, with equality exactly when p=q.

If finite X→Y→Z form a Markov chain, meaning Z is conditionally independent of X given Y, then I(X;Z)≤I(X;Y).

A binary prefix code has no whole codeword as another's initial segment, permitting immediate sequential decoding.

Repeatedly merge the two least-probable source symbols or accumulated nodes, then label the two branches 0 and 1; root-to-leaf labels are codewords.

For iid finite-alphabet X₁,…,Xₙ, −n⁻¹log₂p(X₁,…,Xₙ) converges in probability to H(X₁).

The entropy rate is limₙ H(X₁,…,Xₙ)/n when the limit exists.

For a real density f with defined integral, h(X)=−∫f(x)log₂f(x)dx.

For Y=X+Z with iid real Gaussian noise Z∼N(0,N), N>0, independent of input, and average input power E[X²]≤P, capacity is C=(1/2)log₂(1+P/N) bits per channel use.

Over F₂ take H=[A|Iₘ] and G=[Iₙ₋ₘ;A].

For received r=c+e with Hc=0, syndrome Hr=He.

For a two-sender discrete memoryless MAC with independent messages, the capacity region is the closure of rates bounded by I(X1;Y|X2,Q), I(X2;Y|X1,Q) and I(X1,X2;Y|Q), over laws p(q)p(x1|q)p(x2|q)p(y|x1,x2).

For a physically degraded memoryless broadcast channel X→Y1→Y2, independent private-message rates are achieved by superposition with R2≤I(U;Y2) and R1≤I(X;Y1|U), unioned over p(u,x).

For a discrete memoryless relay law p(y2,y3|x1,x2), decode-forward achieves the maximum over p(x1,x2) of min{I(X1,X2;Y3),I(X1;Y2|X2)}.

Decode-forward asks a relay to recover a message or layer before forwarding cooperative codewords; a weak source-to-relay link can bottleneck it.

With iid correlated (X,Y), an encoder observing X and a decoder observing Y have rate-distortion function min[I(X;U)−I(Y;U)] over U−X−Y and reconstruction x-hat(U,Y) meeting the distortion bound.

Two-user interference channels require two messages decoded at their respective receivers under a joint law p(y1,y2|x1,x2).

For a binary symmetric channel with crossover probability 0<p<1/2 and fixed target block error 0<epsilon<1, the best rate has normal approximation C−sqrt(V/n) Q-inverse(epsilon)+O(log(n)/n).

For independent repetitions of a finite-alphabet joint law p(x,y), an encoder observing X and a decoder possessing Y can recover X with vanishing block error at rates above H(X|Y); rates below it are impossible.

For an iid source with law p(x) and specified distortion d(x,x-hat), R(D) minimizes mutual information over reconstruction laws meeting expected distortion D.

Arıkan's transform recursively turns a binary-input memoryless channel into synthetic channels with polarized reliabilities.

For a stationary finite-alphabet process the block entropy per symbol tends to an entropy rate, while correlations can make it smaller than single-symbol entropy.

IP addresses identify network destinations; IP does not guarantee delivery.

UDP exchanges addressed messages without adding reliable stream delivery.