Indexed text attachment
entropy-sources-and-channels-in-higher-categories.tex
Source for Entropy, Sources, and Channels in Higher Categories
View paper · Download original file
Lines 2869–2968 of 4249. Source text is displayed literally.
2869\chapter{Shannon's Theorems}\label{ch:shannon}2870 2871Everything is now in place. McMillan's theorem makes a long block from an ergodic source an approximate2872retract of a set of $2^{nH}$ points. Feinstein's lemma makes a set of $2^{nC}$ points an approximate retract of2873a long block of channel uses. If $H<C$ the first set fits inside the second, and the composite of the two2874retractions transmits the source through the channel. This is Shannon's theorem as Khinchin proves it in2875his last chapter. We present it in that form, add the converse, which Khinchin does not treat, and observe2876that the two halves of the theorem are of different kinds. The chapter ends with polar codes, where the2877martingale of \cref{ch:martingales} returns in a new role.2878 2879\section{Coding without noise}2880 2881A \term{prefix code} for a finite set $X$ is an injective map $c$ from $X$ to finite binary strings such that2882no codeword is an initial segment of another. Write $\ell(x)$ for the length of $c(x)$.2883 2884\begin{theorem}[Kraft's inequality and the noiseless coding theorem]\label{thm:noiseless}2885\Scl[\cite{Kra49,Sha48}] The lengths of a prefix code satisfy $\sum_x2^{-\ell(x)}\le1$, and every assignment of2886lengths satisfying this inequality is realized by a prefix code. For a distribution $p$ on $X$ the least2887expected length $L^*(p)$ of a prefix code satisfies2888\[ H(p)\le L^*(p)<H(p)+1. \]2889\end{theorem}2890 2891\begin{proof}2892A codeword of length $\ell$ determines a cylinder of measure $2^{-\ell}$ in the space of infinite binary2893sequences with the fair coin measure, and the prefix condition says that the cylinders are disjoint. For2894the lower bound let $K=\sum_x2^{-\ell(x)}\le1$ and $q(x)=2^{-\ell(x)}/K$; then2895$\sum_xp(x)\ell(x)-H(p)=\KL pq-\log K\ge0$ by \cref{prop:gibbs}. For the upper bound take2896$\ell(x)=\lceil-\log p(x)\rceil$.2897\end{proof}2898 2899Applied to blocks of length $n$ from a stationary source, the theorem gives codes whose expected length2900per letter lies between $H_n/n$ and $H_n/n+1/n$, and both tend to $H(\mu)$. So for codes of variable length2901judged by their expected length the entropy of the source is the optimal rate, for every stationary2902source. Ergodicity is needed for the stronger statement that the length is close to $nH$ with high2903probability, which is the form in which Khinchin states the result (his Theorem~4) and the form needed for2904transmission over a channel.2905 2906\begin{example}\label{ex:huffman}2907For $p=(0.7,0.2,0.1)$, $H(p)\approx1.157$. The optimal prefix code for single letters has expected length $1.3$.2908For blocks of $2$, $3$, $4$ and $6$ letters the optimal expected lengths per letter are $1.165$, $1.175$,2909$1.164$ and $1.162$. The convergence to $H$ is not monotone.2910\end{example}2911 2912The proof identifies an optimal code with an embedding of the source into the fair-coin source: the2913encoded stream is, as nearly as integer lengths allow, a sequence of independent fair bits. In2914\cref{ch:rates} this becomes a theorem of ergodic theory.2915 2916\section{Codes and channels}2917 2918Khinchin defines a code as a map $\theta\mapsto x(\theta)$ from sequences over a source alphabet $A_0$ to sequences2919over the channel alphabet $A$, and remarks that it can be regarded as a channel $[A_0,\rho,A]$ without noise.2920Connecting the source to the code and the code to the channel is the composite2921\[ 1\xrightarrow{\ \mu\ }A_0^{\Z}\xrightarrow{\ \rho\ }\AZ\xrightarrow{\ \nu\ }\BZ \]2922of \cref{ch:channels}. The codes he uses are block codes, which map each block of $n$ source letters to a2923block of $n+m$ channel letters, where $m$ is the memory of the channel. Such a map commutes with the2924appropriate powers of the two shifts, not with the shifts themselves, and the sources it produces are2925stationary only for the block shift. This is harmless; one either works with the block shift throughout,2926as Khinchin does, or averages over the phase.2927 2928\section{The first theorem}2929 2930\begin{lemma}[Retractions compose]\label{lem:compose}2931\Sob Let $(e_s,d_s)$ be an $(M,\varepsilon_1)$-compression of a finite probability space $(X,p)$ in the sense of2932\cref{def:compression}, and $(e_c,d_c)$ an $(M,\varepsilon_2)$-code for $W\colon U\to V$ in the sense of2933\cref{def:code}. Then for $x$ drawn from $p$, sent as $e_c(e_s(x))$ through $W$ and decoded by2934$d_s\circ d_c$, the result equals $x$ with probability at least $1-\varepsilon_1-\varepsilon_2$.2935\end{lemma}2936 2937\begin{proof}2938With probability at least $1-\varepsilon_1$ the point $x$ satisfies $d_s(e_s(x))=x$. Whatever the message2939$j=e_s(x)$ is, the channel code returns it with probability at least $1-\varepsilon_2$.2940\end{proof}2941 2942The second step is where the maximal-error criterion of \cref{def:code} is used. The compression may2943concentrate the source on a few messages, and the channel code must work for each of them. A code that is2944good only on average over messages would not compose with an arbitrary source (\cref{exer:average}). This is2945why Feinstein's formulation suits Khinchin's proof.2946 2947\begin{figure}[ht]\centering2948\begin{tikzpicture}[x=0.95cm,y=1cm]2949 \node[ogbox] (mu) at (0,0) {$\mu_n$};2950 \node[ogbox] (es) at (1.9,0) {$e_s$};2951 \node[ogbox] (ec) at (4.1,0) {$e_c$};2952 \node[ogbox] (W) at (6.7,0) {$W_n$};2953 \node[ogbox] (dc) at (9.1,0) {$d_c$};2954 \node[ogbox] (ds) at (11.3,0) {$d_s$};2955 \draw[fw] (mu) -- (es);2956 \draw[fw] (es) -- node[above=2pt,lab,black]{$[M]$} (ec);2957 \draw[fw] (ec) -- node[above=2pt,lab,black]{$A^{n+m}$} (W);2958 \draw[fw] (W) -- node[above=2pt,lab,black]{$B^n$} (dc);2959 \draw[fw] (dc) -- node[above=2pt,lab,black]{$[M]$} (ds);2960 \draw[fw] (ds) -- node[above=2pt,lab,black]{$A_0^n$} (12.9,0);2961\end{tikzpicture}2962\caption{Shannon's first theorem as a composite of two approximate retractions. The middle three boxes are2963within $\varepsilon$ of the identity of $[M]$ by Feinstein's lemma; the outer two are within $\varepsilon$ of the2964identity on $\mu_n$-typical blocks by McMillan's theorem.}\label{fig:shannon}2965\end{figure}2966 2967\begin{theorem}[Shannon's first theorem]\label{thm:shannon1}2968\Scl[\cite{Sha48,Fei54,Khi56}] Let $\nu$ be a channel as in \cref{thm:feinsteinmem}, with ergodic capacity $C$, and let