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

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 for2989which the equivocation of the source block given the received block is less than $n\varepsilon'$.2990\end{theorem}2991 2992\begin{proof}2993Take the code of \cref{thm:shannon1}. The received block determines the decoded block, which differs from2994the source block with probability at most $\varepsilon$. By Fano's inequality (\cref{lem:feinstein3})2995the equivocation is at most $1+\varepsilon\,n\log|A_0|$.2996\end{proof}2997 2998In the language of \cref{ch:inequalities}: a morphism within $\varepsilon$ of having a left inverse has2999equivocation at most $\hb(\varepsilon)+\varepsilon\log(\text{size})$. The second theorem is the first theorem passed3000through Fano's inequality, and Khinchin proves it that way.3001 3002\section{The converse, and the two kinds of statement}3003 3004\begin{theorem}[Converse]\label{thm:converse}3005\Scl[\cite{Fan61}] Let $W$ be a memoryless channel with capacity $C$ and $\mu$ a stationary source with entropy3006$H_0>C$. For every $n$ and every pair of maps $A_0^n\to A^n$, $B^n\to A_0^n$ the probability $P_e$ that a block is3007not recovered satisfies3008\[ P_e\ \ge\ \frac{H_0-C-1/n}{\log|A_0|}. \]