Independent scholarship · Open accessThe monthly digest

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 2889–2988 of 4249. Source text is displayed literally.

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 let2969$[A_0,\mu]$ be an ergodic source with entropy $H_0<C$. For every $\varepsilon>0$ and all large $n$ there are maps2970$A_0^n\to A^{n+m}$ and $B^n\to A_0^n$ such that a block of $n$ letters from the source, encoded, transmitted and2971decoded, is recovered with probability at least $1-\varepsilon$.2972\end{theorem}2973 2974\begin{proof}2975Choose $\delta>0$ with $H_0+\delta<C-\delta$ and put $M=2^{\lceil n(H_0+\delta)\rceil}$. By \cref{prop:corank} the block2976law $\mu_n$ has an $(M,\varepsilon/2)$-compression for large $n$. By \cref{thm:feinsteinmem} the block channel $W_n$2977has a $(2^{\lceil n(C-\delta)\rceil},\varepsilon/2)$-code for large $n$, and $2^{\lceil n(C-\delta)\rceil}\ge M$. Apply2978\cref{lem:compose}.2979\end{proof}2980 2981\section{The second theorem}2982 2983Khinchin's second theorem says that the code can be chosen so that the rate of transmission between the2984source and the received signal is as close as desired to the entropy $H_0$ of the source, or equivalently2985so that the equivocation per letter is small.2986 2987\begin{theorem}[Shannon's second theorem]\label{thm:shannon2}2988\Scl[\cite{Khi56}, \S16] Under the hypotheses of \cref{thm:shannon1}, for every $\varepsilon'>0$ there is a code for