SHANNON’S NOISELESS CODING THEOREM

Abstract. We will discuss entropy from the perspective of infor-mation theory. 1. Some coding terminology For what follows it may be helpful to imagine that you are trying to encode a page of text written in English into a binary sequence for digital transmission or storage. Also make the unrealistic assumption that letters of the alphabet occur independent with some probability distribution. For a set A, let A ∗ denote the set of all finite sequences of A. Some-times it will be convenient to think of elements of A ∗ as words. A pre-fix of a word a = (a1,..., an) ∈ A ∗ is a word of the form (a1,..., ak) for some 1 ≤ k ≤ n. Let S be a finite set, and p be a probability measure on S. We think of S as a source alphabet. A map c: S → {0, 1} ∗ is called a (source) code. The extension of c is the mapping c ∗ : S ∗ → {0, 1}∗ given by the concatenation c∗(s) = c(s1)c(s2)... c(sn). We call the image c(S∗) the code words. We say that c is non-singular if it is an injective mapping. We will only consider non-singular codes. We say that a non-singular code is uniquely decod-able if its extension is non-singular. We say that c is a prefix-(free) code or instananeous code if no code word is a prefix of another code word. Note that a prefix code is uniquely decodable. For each s ∈ S, let `(s) be the length of the binary sequence c(s). We say the expected length of c is L(c):= s∈S p(s)`(s). We want to find a code c that is uniquely decodable and has small expected length. Exercise 1. Define a uniquely decodable code that is not a prefix code