We shall consider now the encoding of signals on [-T,T][-T,T] where T>0T>0 is fixed.
Ultimately we shall be interested in encoding classes of bandlimited signals like the class B A B A
However, we begin the story by considering the more general setting of encoding
the elements of any given compact subset KK of a normed linear space XX. One can determine
the best encoding of KK by what is known as the Kolmogorov entropy of KK in XX.
To begin, let us consider an encoder-decoder pair (E,D)(E,D)
EE maps KK to a finite stream of bits.
DD maps a stream of bits to a signal in XX.
This is illustrated in Figure 1.
Note that many functions can be mapped onto the same bitstream.
Define the distortion dd for this encoder-decoder by
d(K,E,D,X):=sup f∈K ∥f-D(Ef)∥ X ̲ ¯ .d(K,E,D,X):=sup f∈K ∥f-D(Ef)∥ X ̲ ¯ .(1)
Let
n(K,E)=sup f∈K #Efn(K,E)=sup f∈K #Ef where
#Ef#Ef is the number of bits
in the bitstream
EfEf.
Thus
nn is the maximum
length of the bitstreams for the various
f∈Kf∈K. There are two ways we can
define optimal encoding:
- Prescribe ϵϵ, the maximum distortion that
we are willing to tolerate. For this ϵϵ, find the smallest
n ϵ (K,X):=inf (E,D) {n(K,E):d(K,E,D,X)≤ϵ}n ϵ (K,X):=inf (E,D) {n(K,E):d(K,E,D,X)≤ϵ}. This is the smallest bit budget under which we could encode all elements of KK to distortion ϵϵ.
- Prescribe NN : find the smallest distortion d(K,E,D,X)d(K,E,D,X)
over all E,DE,D with n(K,E)≤Nn(K,E)≤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.
