1.1 Optimal encoding

We shall consider now the encoding of signals on $[-T,T]$ where $T>0$ is fixed. Ultimately we shall be interested in encoding classes of bandlimited signals like the class $B_A$ However, we begin the story by considering the more general setting of encoding the elements of any given compact subset $K$ of a normed linear space $X$ . One can determine the best encoding of $K$ by what is known as the Kolmogorov entropy of $K$ in $X$ .

To begin, let us consider an encoder-decoder pair $(E,D)$ $E$ maps $K$ to a finite stream of bits. $D$ maps a stream of bits to a signal in $X$ . This is illustrated in . Note that many functions can be mapped onto the same bitstream.

Define the distortion $d$ for this encoder-decoder by

• Prescribe $ϵ$ , the maximum distortion that we are willing to tolerate. For this $ϵ$ , find the smallest $n_{ϵ}(K,X):=\text{inf}{}_{(E,D)}\left\{n\right(K,E):d(K,E,D,X)\le ϵ\}$ . This is the smallest bit budget under which we could encode all elements of $K$ to distortion $ϵ$ .
• Prescribe $N$ : find the smallest distortion $d(K,E,D,X)$ over all $E,D$ with $n(K,E)\le N$ . This is the best encoding performance possible with a prescribed bit budget.

There is a simple mathematical solution to these two encoding problems based on the notion of Kolmogorov Entropy.