EE274: Data Compression, course notes

Welcome! This e-book serves as lecture notes for the Stanford EE course, EE274: Data Compression. This set of lecture notes is WIP, so please file an issue at https://github.com/stanfordDataCompressionClass/notes/issues if you find any typo/mistake.

Lossless data compression

The first part of the lecture notes pertain with lossless data compression

1. Introduction
2. Prefix Free Codes
3. Kraft Inequality
4. Entropy and Neg-log likelihood thumb rule
5. Huffman coding
6. Asymptotic Equipartition Property
7. Arithmetic coding
8. Asymmetric Numeral Systems

Introduction to lossless coding

Data compression, is one area of EECS which we are aware of and unknowingly make use of thousands of times a day. But, not many engineers are aware of how things work under the hood. Each text, image and video is compressed before it gets transmitted and shared across devices using compression schemes/formats such as GZIP, JPEG, PNG, H264 ... and so on. A lot of these compression schemes are somewhat domain specific, for example typically use GZIP for text files, while we have JPEG for images. While there is significant domain expertise involved in designing these schemes, there are lots of commonalities and fundamental similarities.

Our focus in the first half of the course is going to be to understand these common techniques part of all of these compression techniques, irrespective of the domain. The goal is to also build an intuition for these fundamental ideas, so that we can appropriately tweak them when eventually designing real-life and domain-specific compression techniques. With that in mind, we are going to start with very simple hypothetical but relevant scenarios, and try to tackle these. As we will see, understanding these simpler cases will help us understand the fundamental details of compression.

Let's start with a simple example:

Let's say we are given a large random text file consisting of 4 letters $A,B,C,D$. To be more precise, each letter of the text file is generated randomly by picking a letter from the set $\mathcal{S}=\{A,B,C,D\}$ independently and with uniform probability. i.e.

$$P(A)=P(B)=P(C)=P(D)=1/4$$

An example of such a file is given below. Let's say we have such a file containing $1,000,000$ letters.

ACABDADCBDDCABCDADCBDCADCBDACDACDBAAAAACDACDA...

Now if one examines this file, then the size of the file is going to be 1,000,000 bytes, as can be seen below.

➜ ls -l sample_ABCD_uniform.txt 
-rw-rw-r-- 1 kedar kedar 1000000 Jun 23 19:27 sample_ABCD_uniform.txt

This is quite obvious as we are using 1 byte (or 8 bits/symbol) to represent each alphabet. In fact, if we look at the bits in the file, we see that each symbol has a unique codeword, given by the ASCII table:

Every time we write text to a file, the programming language encodes the text file using ASCII encoding table -- to map the characters and other punctuations to binary data. Also, when we read the file back, the binary data is read 8 bits at a time and then decoded back to the character.

Now, the question we want to answer is "Can we reduce the size of the file?"

To be more precise, we will restrict ourselves to Symbol codes, which are encoding schemes where we have a unique binary string (called a codeword) for every symbol.

Fixed Bitwidth encoding

If we look at the ASCII code table, we see that all the codes start 1000, which is kind of redundant. It is useful if we have other letters in the file, but in this case we only have 4 letters. Thus, we don't need all the 8-bits! In fact, we can just use 2 bits/symbol to represent them all as follows:

Note that this is lossless compression, as during decoding as well we can just read 2 bits at a time and map them to A,B,C,D. Thus, this simple idea has given us a compression of 4x!

In general, if we have $k=|\mathcal{S}|$ different symbols in our text file, then using this simple idea we can represent/encode the data using $\lceil {\log }_{2}k\rceil$ bits.

Going beyond Fixed Bitwidth encoding

Now, this 2 bits/symbol compression is all well and good, but works only if some letters are fully absent from our text file. For example, if now our file the letters $C,D$ were absent and only the letters $\{A,B\}$ were present, then we could go from 2 bits/symbol to 1 bit/symbol, by assigning codes a follows:

But, what if $C,D$ were present, but in a smaller proportion? Is it possible to achieve better compression? Here is a more precise question:

Clearly, if we stick with fixed bitwidth encoding, then irrespective of the distribution of letters in our file, we are always going to get compression of 2 bits/symbol for all the 4 symbols, and so of course we can't achieve compression better than 2 bits/symbol. But, intuitively we know that most of the time we are only going to encounter symbol $A$ or $B$, and hence we should be able to compress our file closer to 1 bit/symbol. To improve compression, the idea here is to go for variable length codes, where the code length of each symbol can be different.

But, designing variable length codes which are also lossless is a bit tricky. In the fixed bitwidth scenario, the decoding was simple: we always looked at 2 bits at a time, and just performed a reverse mapping using the code table we had. In case of variable length codes, we don't have that luxury as we don't really know how many bits does the next codeword consists of.

Thus, the variable length codes need to have some special properties which makes it both lossless and also convenient to decode.

Instead of just mentioning the property, we are going to try to discover and reverse engineer this property! With that in mind, I am going to present the solution to the Quiz-2, but what you have to do is figure out the decoding procedure! So here is one possible code:

Some questions for you to answer:

Even before we try to answer these questions, lets try to first eyeball the designed code and see if we can understand something! We see that the code for $A$ is now just 1 bit instead of 2. At the same time, the code lengths for $C,D$ are 3 instead of 2. So, in a way, we are reducing the code length for symbols which are more frequent, while increasing the code length for symbols which occur less frequently, which intuitively makes sense if we want to reduce the average code length of our file!

Compression ratio: Lets try to answer the first question: "Are we doing better than 2 bits/symbol in terms of the average compression?" To do this, we are going to compute $\mathbb{E}(L)$, the average code length of the code:

$$\begin{array}{rl}\mathbb{E}(L)& =p(A)\ast 1+p(B)\ast 2+p(C)\ast 3+p(4)\ast 3\\ & =0.49\ast 1+0.49\ast 2+0.01\ast 3+0.01\ast 3\\ & =1.53\end{array}$$

So, although in the worst case this increases the symbol code length from 2 to 3, we have been able to reduce the average code length from 2 to 1.53, which although is not as good as 1 bit/symbol we see when $C,D$ were completely absent, it is still an improvement from 2 bits/symbol. Great!

Lossless Decoding: Now that we have answered the first question, lets move to the second one: "Is the code really lossless?"

Okay, lets get back to the code we have:

Let's take an example string and see how the encoding/decoding proceeds:

input_string = ABCADBBA

The encoding proceeds in the same way as earlier: for every symbol, we look at the lookup table and write the corresponding bits to the file. So, the encoding for our sample string looks like:

input_string = ABCADBBA
encoding = concat(0, 10, 110, 0, 111, 10, 10, 0)
= 010110011110100

Now, lets think about how we can decode this bit sequence: 010110011110100. The issue with using a variable length code, unlike before where we used 2 bits for each symbol is that we don't know where each code ends beforehand. For example, we don't know how to decode symbol no. 7 directly. but let's see how we can decode the input sequentially, one symbol at a time.

1. The first bit of 010110011110100 is 0. We see that only one codeword (corresponding to $A$) starts with 0, so we can be confident that the first letter was an $A$! At this time we have consumed 1 bit, and so to decode the second symbol we have to start reading from the second bit.

2. Let's now focus our attention on the remaining bits: 10110011110100. Now, the first bit is a 1. Unfortunately $B,C,D$ have codewords which start with a 1, so lets read another bit: 10. Okay! we have a match with the symbol $B$. We can also be confident that the second symbol is indeed $B$, as no other codeword begins with 10. Thus, our decoded string until now is A,B

3. We can continue in the same way and decode the remaining symbols one at a time, by following the following procedure, to recover the input string: ABCADBBA.

Below is a pseudocode to decode a single symbol using the matching scheme described above.

codewords_table = {A: 0, B: 10, C: 110, D: 111}


def decode_symbol(encoded_bitstring, codewords_table):
    temp_bits = ""

    # read until we find a match with a codeword in the codewords_table
    while not find_match(temp_bits, codewords_table):
        temp_bits += encoded_bitstring.read_next_bit()

    decoded_symbol = find_match(temp_bits, codewords_table)
    return decoded_symbol

Note, that one reason why our decoding procedure works is because no codeword is an initial segment of another codeword, i.e. no two codewords are prefixes of each other. Thus, if codeword for $B$ is 10, then no other codeword can begin with 10. This kind of Symbol codes are known as prefix-free codes (or simply Prefix Codes). As we just saw, we can confidently say that if a code is * prefix-free*, then it indeed leads to lossless compression, and a convenient decoding procedure.

Note that prefix-free codes aren't the only way of designing symbol codes which are lossless. For example, consider the following code

Notice that codeword for $C$ starts with 01 which is in fact the codeword for $B$ (similarly for $B$ and $A$). Thus, this code is not prefix-free and our decoding procedure described above will fail. For example if we encode a $C$ -> 011..., our decoding procedure will always output a $B$, as it would find a match at 01 itself. Note that although our simple decoding scheme above fails, lossless decoding is still possible. Although, the decoding scheme might be more complicated as, we have to read "future bits" to determine if a $B$ or a $C$ was encoded here.

As a fun exercise, can you try to figure out how the decoding works for this code?

To summarize: the key idea to learn from the design of our code is that

Another name for prefix-free codes is instantaneous codes as the decoding procedure is in a sense "instantaneous", i.e. we don't have to read bits written by future symbols to decode the current symbols.

Next Lecture

In this lecture, we discussed the design of a simple prefix-free code which improves upon the compression of a non-uniform source from 2 bits/symbol to 1.53 bits/symbol by using variable length codewords. We also briefly discussed how the decoding might proceed.

In the next lecture we will take this discussion further and try to answer the following questions:

1. Implementing the decoding: We will see how to transform our simple decoding procedure into an efficient algorithm, which we can implement in practice

2. Designing prefix-free codes: We will discuss how to design prefix-free codes to obtain better compression.

Prefix(-Free) Codes

As a recap, in the previous lecture, we discussed a simple example of a prefix-free code. We also discussed a simple procedure for decoding data encoded using the prefix-free code. In this lecture we will be thinking about how to actually go about implementing the decoding, and also how to design prefix-free code itself.

Lets start by thinking about the decoding. As a recap, here is our prefix-free code and the decoding procedure

### Prefix-free decoding procedure
codewords_table = {A: 0, B: 10, C: 110, D: 111}

def decode_symbol(encoded_bitstring, codewords_table):
    temp_bits = ""

    # read until we find a match with a codeword in the codewords_table
    while not find_match(temp_bits, codewords_table):
        temp_bits += encoded_bitstring.read_next_bit()

    decoded_symbol = find_match(temp_bits, codewords_table)
    return decoded_symbol

The procedure is as follows:

• We start from the encoded bitstream, and try to find a match with either of the codewords. We stop when we get our first match
• Note that the decoding procedure above is "correct" because we have a prefix-free code, and so we can stop searching when find_match obtains its first match.

Let's think about how we can implement the find_match function.

Idea-1: Hash-tables: One simple way to implement the find_match function in the decoding is via a hash table. We can just create a hash table using the codewords_table. We can then just query the hash table with the temp_bits, until we get a match.

Can we think of a simple data-structure which will make this procedure faster?

Prefix-free Tree

Another approach towards prefix-free code decoding is to construct a prefix-free tree and use this tree for decoding. Lets get back to our prefix-free code example to see what I mean by that:

Given the codewords table, we can represent it as a binary tree follows:

graph TD
  *(Root) -->|0| A:::endnode
  *(Root) -->|1| n1(.)
  n1 -->|10| B:::endnode
  n1 -->|11| n2(.)
  n2 -->|110| C:::endnode
  n2 -->|111| D:::endnode

1. The idea behind the prefix-free tree construction is simple. For each codeword, we add a node at depth len(codeword) from root node, taking the right path or the left path from previous node in the tree depending on whether the corresponding bit in the codeword is 1 or 0. E.g. in our codewords table B -> 10. In this case we add a node to the binary tree at depth 2 = len(10), corresponding to the path 10 -> right, left from the root node. Similarly, for C -> 110, we add a node at depth 3 corresponding to the path 110 -> right, right, left.
2. Notice that for prefix-free codes, the codewords correspond to the leaf nodes. This can be shown using contradiction. If there was another node n2 corresponding to codeword c2 sprouting out of node n1 (with codeword c1), then based on the construction of prefix-free tree defined in the previous step, c1 is a prefix of c2. This is a contradiction because we're violating the prefix-free property of our code. In fact, the property that prefix-free codes correspond to the leaf nodes of prefix-free tree is another way to define prefix-free codes!

Okay, now that we have understood how to create the prefix-free tree data structure for any prefix-free code, can we use this tree structure to improve the decoding algorithm? Take a look!

## Prefix-free code decoding using a prefix-free tree

prefix_tree = ...  # construct the tree here using codewords

def decode_symbol(encoded_bitarray, prefix_tree):
    # start from the root node and read bits until you read a leaf node
    node = prefix_tree.root
    while not node.is_leaf_node:
        bit = encoded_bitarray.read_next_bit()
        node = node.right if bit else node.left
    # return the symbol corresponding to the node, once we reached a leaf node
    return node.symbol

Some observations:

1. This decoding scheme is similar in logic to the previous one, but quite a bit more efficient, as we are not querying the hash table multiple times.
2. The key idea is that for prefix-free codes the codewords correspond to leaf nodes. Hence, we just parse the tree with the bits from the output until we reach one of the leaf nodes.
3. Note that we need to create the prefix-free tree during the pre-processing step of our decoding as a one-time cost, which typically gets amortized if the data we are encoding is quite big.

As we will see later the prefix-free tree is not just useful for efficient decoding, but is a great way to think and visualize prefix-free codes. We will in fact use the structure when we learn about how to design a good prefix-free code.

How to design good prefix-free codes?

Okay, now that we have convinced that prefix-free codes are indeed lossless and that they have an efficient decoding scheme, lets revisit our code and think again about why the scheme leads to better compression

To recap: we wanted to design a code for the skewed non-uniform distribution: $$P(A)=0.49,P(B)=0.49,P(C)=P(D)=0.01$$

we started with the following Fixed Bitwidth code.

Then we were able to construct a variable-length code, which is indeed lossless and improves the compression from 2 bits/symbol to 1.53 bits/symbol on an average.

How did this improvement come about?

1. The Fixed Bitwidth code is assigning equal importance to all the symbols $A,B,C,D$, as the code-lengths are the same ( 2 bits/symbol). This seems all good, in case they are equiprobable. i.e. if the probabilities are: $$p(A)=p(B)=p(C)=p(D)=0.25$$

2. But in case of the skewed probability distribution, clearly $A,B$ are more important as they occur much more frequently. So, we should try to assign a shorter codeword to $A,B$ and could afford to assign longer codewords to $C,D$ as they occur much less frequently.

Thus we have a simple and somewhat obvious thumb rule for a code:

Even though we want to assign shorter codes to symbols with higher probability, it is not clear what the proportionality should be.

For example, the prefix-free code we have works well for distribution $$\begin{array}{r}p(A)=p(B)=0.49\\ p(C)=p(D)=0.01\end{array}$$ and gives us the average codelength of 1.53 bits/symbol. But, the same code doesn't work well for a less skewed distribution like:

$$\begin{array}{r}p(A)=p(B)=0.3\\ p(C)=p(D)=0.2\end{array}$$ as in this case the average codelength is 2.1 bits/symbol (which is even higher than Fixed Bitwidth code!).

This problem, (and much more) was definitively analyzed in the brilliant work by Claude Shannon in his 1948 paper A Mathematical theory of Communication. Shannon's work laid the theoretical foundations of not just the field of data compression, but more so of the area of error-free data communication. (The paper remains surprisingly accessible and short for its legendary nature. Do take a look!)

We will definitely come back in the future lectures to understand the work in more detail, but here is another thumb rule from Shannon's work for the optimal code-lengths:

$$l_{optimal}(symbol)\approx {\log }_2\frac{1}{p(symbol)}$$

Note that this is still a thumb rule, until we prove it and show convincingly in which scenarios it holds true. But, lets try to verify this rule in a couple of simple cases:

1. Uniform Distribution: Let's consider the case of $$P(A)=P(B)=P(C)=P(D)=1/4$$ We know that as we have 4 equiprobable symbols, we can encode data using 2 bits/symbol. This matches the thumb rule above: $$\begin{array}{rl}{l}_{optimal}(symbol)& \approx {\log }_2\frac{1}{p(symbol)}\\ & ={\log }_{2}4\\ & =2\end{array}$$ In general, we see that if the probability is $1/k$ for all the $k$ symbols of a distribution, then the optimal codelength is going to be $lo{g}_{2}k$, according to the thumb rule. Now, in cases where $k$ is not a power of $2$, and if we have a single unique codeword per symbol, then the best we can achieve is $$\lceil lo{g}_{2}k\rceil \ge lo{g}_{2}k$$

2. Dyadic distribution: Based on the thumb rule, we need ${\log }_2\frac{1}{p(symbol)}$ to be an integer, which is only possible if $p(symbol)$ is a negative power of $2$ for all symbols. Such distributions are known as dyadic distributions

   Dyadic distribution A distribution $P$ is called dyadic if $$\exists l_i\in \mathbb{N},P(s_i)=\frac{1}{2^{l_i}},\forall s_i\in \mathcal{S}$$

   Based on the thumb rule, it is unambiguously clear that for dyadic distribution, the symbol $s_i$ should have codeword of length $l_i$. For example: for the following dyadic distribution $$P(A)=1/2,p(B)=1/4,P(C)=P(D)=1/8$$ the code-lengths are going to be:

   Symbol	Prob	Optimal codelength
   A	1/2	1
   B	1/4	2
   C	1/8	3
   D	1/8	3

3. General Distributions: For generic distributions, $l_{optimal}(symbol)={\log }_2\frac{1}{p(symbol)}$, might not be achievable in general. But, a good goal to aim for is: $$l(symbol)=\lceil {\log }_2\frac{1}{p(symbol)}\rceil$$ Is this possible? Lets look at this problem in the next section

Designing prefix-free codes

Okay! So, now that we know that the code-lengths to shoot for are: $$l(symbol)=\lceil {\log }_2\frac{1}{p(symbol)}\rceil$$ let's try to think how.

Let's take a simple example (see below) and see if we can try to come up with a prefix-free code with the prescribed lengths.

We know that all prefix-free codes have a corresponding prefix-free tree. So, essentially we want to come up with a binary tree with the leaf nodes at a distance equal to the code-lengths from the root node. For example, in the above example, we want to construct a binary tree with leaf nodes at distance 1, 2, 4, 4 from the root node. Note that there can be some additional leaf nodes to the binary tree which are not assigned to any codeword.

1. Let's start with nodes at distance 1. We know a binary tree has 2^1 = 2 nodes at distance 1 from the root node. These correspond to codewords 0 (left node) and 1 (right node). Let's make the left node a leaf node corresponding to symbol $A$ (with codelength = 1 as needed)

graph TD
     *(Root) -->|0| A:::endnode
     *(Root) -->|1| n1(.)

2. Now we have the right node (corresponding to codeword 1), which we can split further into two nodes corresponding to 10 and 11. As we are needed to assign a codeword with length 2, lets assign node corresponding to 10 to symbol $B$, and make it a leaf node.

graph TD
     *(Root) -->|0| A:::endnode
     *(Root) -->|1| n1(.)
     n1 -->|10| B:::endnode
     n1 -->|11| n2(.)

3. We are now again left with the right node 11, which we can split further into two nodes 110, 111 at distance = 3 from the root node. Now, looking at the table of code-lengths, we do not have any code to be assigned to length 3, so lets split node 110 further into nodes corresponding to 1100 and 1101. We can now assign these two nodes to symbols $C,D$ respectively.

graph TD
     *(Root) -->|0| A:::endnode
     *(Root) -->|1| n1(.)
     n1 -->|10| B:::endnode
     n1 -->|11| n2(.)
     n2 --> |110| n3(.)
     n2 --> |111| n4(.)
     n3 --> |1100| C:::endnode
     n3 --> |1101| D:::endnode

Thus, our final codewords are:

Notice that the leaf node corresponding to 111 was not linked to any symbol. That is absolutely ok! It just implies that we could have squeezed in another symbol here with length 3, and points to the slight inefficiency in using the approximation $l(symbol)=\lceil {\log }_2\frac{1}{p(symbol)}\rceil$.

The procedure we followed seems general enough that we can follow it for any distribution:

1. Sort the distribution in descending order and compute codelengths as $l(symbol)=\lceil {\log }_2\frac{1}{p(symbol)}\rceil$
2. Assign the first lexicographically available codeword to the next symbol which is not a prefix of the previous ones and is of the stipulated length.

We still need to argue the correctness of the procedure and that it will work in all cases! For example, how can we be sure that we will not run out of nodes?

We will look at all these problems in the next lecture.

Summary & Next Lecture

To summarize: here are the key takeaway's for this lecture:

1. Prefix-free codes: Among the symbol codes, prefix-free codes allow for efficient and convenient encoding/decoding. In fact as we will see, given any uniquely-decodable code (or lossless code), we can construct a prefix-free code with exact same code-lengths and thus the same compression performance. Thus, we restrict ourselves to the analysis of prefix-free codes among the symbol codes.

2. Prefix-free tree: Any prefix-free code has a prefix-free binary tree associated with it, which has the leaf nodes corresponding to the codewords.

3. Compression thumb rule: One, somewhat obvious thumb rule we learnt for symbol codes was that if $$P(s_1)\ge P(s_2)⟹l(s_1)\le l(s_2)$$ else we could swap the codewords for symbols $s_1,s_2$ and achieve lower average codelength.

4. Neg Log-likelihood: Another thumb-rule we learnt was that the optimal code-lengths for a prefix-free code are $$l_{optimal}(symbol)\approx {\log }_2\frac{1}{p(symbol)}$$ We will understand why this rule is true in the next lecture.

5. Prefix-free code construction: We looked at a procedure for constructing prefix-free codes for any distribution. In the next lecture, we will justify the correctness of the procedure and also discuss a couple of more ideas of constructing prefix-free codes

Designing prefix-free codes

As a recap, in the previous lecture we discussed how to design a prefix free code given the code lengths. We discussed a simple procedure which constructs a prefix-free tree given the code-lengths.

We also saw a simple thumb rule $l_{optimal}(symbol)\approx {\log }_2\frac{1}{p(symbol)}$ which tells us what the code-lengths of the prefix-free code should be. In this lecture we are going to discuss two things:

1. Justify that correctness of our prefix-free tree construction with lengths $l(symbol)=\lceil {\log }_2\frac{1}{p(symbol)}\rceil$
2. Look at a few more prefix-free code constructions

Kraft Inequality & converse

With the goal of proving the correctness of the prefx-free tree construction, we will first look at a simple but fundamental property of binary trees, called the Kraft-Mcmillan Inequality (or simply the Kraft Inequality)

The inequality is quite elegant, and so is its proof. Any thoughts on how the proof might proceed? Here is a hint:

Hint: Let $l_{max}={\max }_{i=1}^k{l}_i$. Then, the Kraft inequality can be written as: $$\sum _{i=1}^k{2}^{l_{max}-l_i}\le 2^{l_{max}}$$ All we have done here is multiply both sides by $2^{l_{max}}$, but this simple transformation will help make the inequality more interpretable! Can you see the proof now? Here is a proof sketch:

• Let's try to interpret the RHS, $2^{l_{max}}$ are the number of nodes of the binary tree at depth $l_{max}$.
• The LHS also has a natural interpretation: Given a leaf node at depth $l_i$, one can imagine that it corresponds to $2^{l_{max}-l_i}$ nodes at depth $l_{max}$.

graph TD
  *(Root) -->|0| A:::endnode
  A -.-> n6(.):::fake
  A -.-> n7(.):::fake
  n6-.-> n8(.):::fake
  n6-.-> n9(.):::fake
  n7-.-> m1(.):::fake
  n7-.-> m2(.):::fake
  *(Root) -->|1| n1(.)
  n1 -->|10| B:::endnode
  B -.-> m3(.):::fake
  B -.-> m4(.):::fake
  n1 -->|11| n2(.)
  n2 --> |110| C:::endnode
  n2 --> |111| D:::endnode
  classDef fake fill:#ddd;

For example in the tree example above, node $A$ has 4 nodes corresponding to it at depth = 3, while node $B$ has 2 nodes.

• It is clear that the nodes at depth $l_{max}$ are distinct for each of the leaf nodes $n_i$ (Think why?). As the "total number of nodes at depth $l_{max}$", is larger than "the sum of nodes at depth $l_{max}$ corresponding to leaf nodes $n_i$, we get the inequality

$$\sum _{i=1}^k{2}^{l_{max}-l_i}\le 2^{l_{max}}$$

• This completes the proof sketch for the Kraft Inequality:

$$\sum _{i=1}^k{2}^{-l_i}\le 1$$

Well, that was a short and simple proof! It is also clear that the equality is true, if and only if there is no leaf node left unaccounted for.

We can use the Kraft inequality to now show the correctness of the prefix-free tree construction with code-lengths $l_i$, as we discussed in last lecture.

Prefix-tree construction correctness

To recap, our prefix-free tree construction proceeds as follows:

1. We are given probability distribution $p_1,p_2,\dots ,p_k$ for symbols $s_1,s_2,\dots ,s_k$. WLOG assume that: $$p_1\ge p_2\ge ...\ge p_k$$ Now, compute code-lengths $l_1,l_2,\dots ,l_k$ such that: $$l_i=\lceil {\log }_2\frac{1}{p_i}\rceil$$ Thus, the lengths, $l_1,l_2,\dots ,l_k$ satisfy $$l_1\le l_2\le ...\le l_k$$

2. The prefix-free tree construction follows by starting with an empty binary tree, and then recursively adding a leaf node at depth $l_i$ to the binary tree.

We want to argue the correctness of the tree construction at each step, i.e. we want to show that when we are adding node $n_k$, there will always be a node available for us to do so.

Let's proceed towards showing this inductively.

• In the beginning, we just have the root node, so we can safely add the node $n_1$ with length $l_1$. To do so, we need to create a binary tree with $2^{l_1}$ leaf nodes, and just assign one of the leaf nodes to node $n_1$
• Now, let's assume that we already have a binary tree ${\mathcal{T}}_{r-1}$ with nodes $n_1,n_2,\dots ,n_{r-1}$ and that we want to add node $n_r$. We want to argue that there will always be a leaf node available with depth $l_r$ in the binary tree ${\mathcal{T}}_{r-1}$. Let's see how can we show that:
• If we look at the code-lengths, i.e. the depths of the nodes $l_i$, we see that they follow the Kraft inequality $$\begin{array}{rl}\sum _{i=1}^k{2}^{-l_i}& =\sum _{i=1}^k{2}^{-\lceil {\log }_2\frac{1}{p_i}\rceil }\\ & =\sum _{i=1}^k{2}^{\lfloor {\log }_2{p}_i\rfloor }\\ & \le \sum _{i=1}^k{2}^{{\log }_2{p}_i}\\ & \le \sum _{i=1}^k{p}_i\\ & =1\end{array}$$ Now as ${\sum }_{i=1}^k{2}^{-l_i}\le 1$ it implies that the node depths of the tree ${\mathcal{T}}_{r-1}$ satisfies ${\sum }_{i=1}^{r-1}{2}^{-l_i}<1$ (for $r<=k$)
• We know from the Kraft inequality that if the inequality is not tight, then there will be a leaf node available at ${\max }_{i=1}^{r-1}{l}_i=l_{r-1}$ depth. Now, as $l_r\ge l_{r-1}$, we can safely say that the node $n_k$ can be added to the binary tree ${\mathcal{T}}_{r-1}$.
• This completes the correctness proof.

In fact if you look at the proof, all we have used is the fact that ${\sum }_{i=1}^k{2}^{-l_i}\le 1$. Thus, the same proof also gives us the following converse theorem of the Kraft inequality:

Kraft inequality and the thumb rule

In the last chapter we introduced the thumb rule $l_{optimal}(symbol)\approx {\log }_2\frac{1}{p(symbol)}$ without any justification. Since then we have seen a code construction that gets close to this thumb rule. Here we briefly sketch how Kraft inequality can be shown to justify the thumb rule. Details can be found in section 5.3 of extremely popular book by Cover and Thomas "Elements of Information Theory". The idea is to consider the optimization problem $$\begin{gathered} \min \sum _{i=1}^k{p}_i{l}_i \\ \mathrm{subject}\mathrm{to}\sum _{i=1}^k{2}^{-l_i}\le 1 \end{gathered}$$ This is simply the optimization problem to minimize the expected code lengths for a prefix code (Kraft's inequality gives a mathematical way to express the constraint). While this is a integer optimization problem (due to the code lengths being integral) and hence is hard to solve, we can relax the integer constraint and try to solve this for any positive $l_i$. Then the method of Lagrange multipliers from convex optimization can be used to sovle this problem and obtain the optimal code lengths $l_i=-\log p_i$. In the next chapter, we will look again into this and derive the thumb rule in a different way (though the Kraft inequality still plays a crucial role).

Entropy & Neg-log likelihood thumb rule

In this lecture, our goal is to understand where the thumb rule $l_{optimal}(symbol)\approx {\log }_2\frac{1}{p(symbol)}$ for prefix-free code-lengths came from. To understand this, we are going to take a brief detour and get a sneak-peek into the area of Information Theory.

Information theory is the science of information, and is an area which tries to understand the fundamental nature of what is information, how do we store it, how do we communicate it etc. The whole field (along with some of the most fundamental results in the field) was laid down in a single seminal paper A Mathematical theory of Communication by Claude Shannon in 1948.

Rather than talking about information in philosophical terms, we are going to understand information theory mathematically. We are going to first define some quantities and properties central to information theory. As we will see, understanding the mathematical properties of these quantities is what will lead us to the intuition and understanding of information theory.

Entropy

So, lets get started: the first property, or information-theoretic measure we are going to define is the Entropy. The entropy, although a term overloaded with a lot of meaning in the (math/science) pop culture, has a precise definition in information theory.

Some comments:

• As you can see, $H(X)$ is a simple function of the distribution $P$. So, some works also denote $H(X)$ as a $H(P)$. We will use both of these notations interchangeably; but note that that the $H(X)$ notation is more precise and will be more helpful when we deal with more complex distributions (like Markov distributions).
• Another way to look at $H(X)$ is as expectation over the negative-log likelihood function $NLL(X)={\log }_2\frac{1}{P(X)}$ $$\begin{array}{rl}H(X)& ={\mathbb{E}}_P\left[NLL(X)\right]\\ H(X)& ={\mathbb{E}}_P\left[{\log }_2\frac{1}{P(X)}\right]\\ & =\sum _{i=1}^k{p}_i{\log }_2\frac{1}{p_i}\end{array}$$ Although, this feels a bit weird, the neg-log likelihood function is a completely legitimate function of the random variable $X$. All the different viewpoints are useful in different scenarios

Properties of Entropy

Now that we have defined Entropy, lets take a look at some properties of $H(X)$. To prove most of these properties, we are going to need a simple but a very profound property of convex functions: the Jensen's inequality.

Jensen's inequality

• If one looks at the LHS: $\mathbb{E}[f(X)]=p_{1}f(x_1)+p_{2}f(x_2)$, then it can be understood as simply a weighted average with weights $p_1,p_2$ over the points $f(x_1),f(x_2)$. This weighted average corresponds to a point somewhere on the segment joining points $f(x_1)$ and $f(x_2)$
• If one looks at the RHS: $f(\mathbb{E}[X])=f(p_1{x}_1+p_2{x}_2)$. Thus, the RHS corresponds to the value of the convex function $f$ at the weighted averaged point $p_1{x}_1+p_2{x}_2$. It is clear from the figure that because of the "bowl-shaped* nature of $f$, $\mathbb{E}[f(X)]\ge f(\mathbb{E}[X])$.
• It is also clear from the figure why the equality condition holds true iff $x_1=x_2$

We won't prove the Jensen's inequality here, but it is useful to understand and visualize the inequality. For a rigorous proof look at the wiki article on Jensen's Inequality. In the simple discrete case, it can be proved using induction.

Okay, we are all set to look at some properties of Entropy. As you can guess, in our case, we will be specifically using Jensen's inequality on the concave function ${\log }_2(.)$.

1. Non-negativity of Entropy: $H(X)\ge 0$:

It is easy to see that $H(X)\ge 0$. The reason is that: ${\log }_2\frac{1}{p_i}\ge 0$, as $0\le p_i\le 1$ $$\begin{array}{rl}H(X)& =\sum _{i=1}^k{p}_i{\log }_2\frac{1}{p_i}\\ & \ge \sum _{i=1}^k{p}_i\times 0\\ & =0\end{array}$$

2. Upper bound on Entropy: $H(X)\le lo{g}_{2}k$:

We know that $H(X)\ge 0$. We can also compute an upper bound on $H(X)$: $$\begin{array}{rl}H(X)& ={\mathbb{E}}_P{\log }_2\frac{1}{p(X)}\\ & \le {\log }_2{\mathbb{E}}_P\frac{1}{p(X)}\\ & ={\log }_2\sum _{i=1}^k{p}_i\ast \frac{1}{p_i}\\ & ={\log }_{2}k\end{array}$$ The first step of the proof follows from Jensen's inequality for the Concave function ${\log }_2(.)$. Also, note that the equality $H(X)={\log }_{2}k$ is possible only if: $${\log }_2\frac{1}{p_1}={\log }_2\frac{1}{p_2}=\dots ={\log }_2\frac{1}{p_k}$$ which implies that $$p_1=p_2=\dots =p_k⟺H(X)={\log }_{2}k$$

3. Joint entropy of independent random variables:

If we have random variables $X_1,X_2$, we can define their entropy simply as the entropy of the pair $(X_1,X_2)$. The joint entropy is denoted as $H(X_1,X_2)$ and can be expanded as $$H(X_1,X_2)=\sum _{x_1,x_2}P(X_1=x_1,X_2=x_2){\log }_2\frac{1}{P(X_1=x_1,X_2=x_2)}$$

Now if $X_1$ and $X_2$ are independent random variables, then we have $$\begin{array}{rl}H(X_1,X_2)& =\sum _{x_1,x_2}P(X_1=x_1,X_2=x_2){\log }_2\frac{1}{P(X_1=x_1,X_2=x_2)}\\ & =\sum _{x_1,x_2}P(X_1=x_1)P(X_2=x_2){\log }_2\frac{1}{P(X_1=x_1)P(X_2=x_2)}\\ & =\sum _{x_1,x_2}P(X_1=x_1)P(X_2=x_2){\log }_2\frac{1}{P(X_1=x_1)}+\sum _{x_1,x_2}P(X_1=x_1)P(X_2=x_2){\log }_2\frac{1}{P(X_2=x_2)}\\ & =\sum _{x_1}P(X_1=x_1){\log }_2\frac{1}{P(X_1=x_1)}\sum _{x_2}P(X_2=x_2)+\sum _{x_2}P(X_2=x_2){\log }_2\frac{1}{P(X_2=x_2)}\sum _{x_1}P(X_1=x_1)\\ & =\sum _{x_1}P(X_1=x_1){\log }_2\frac{1}{P(X_1=x_1)}+\sum _{x_2}P(X_2=x_2){\log }_2\frac{1}{P(X_2=x_2)}\\ & =H(X_1)+H(X_2)\end{array}$$

Thus, the joint entropy of independent random variables is simply the sum of their individual entropies. This generalizes to $n$ independent random variables using induction. In particular, if the $n$-tuple $X^n=(X_1,\dots ,X_n)$ consists of i.i.d. random variables distributed like $X$, then $H(X^n)=nH(X)$. The general case of dependent random variables and their joint entropy is studied in a later chapter.

4. Entropy as a lower bound: $H(X)\le {\mathbb{E}}_P{\log }_2\frac{1}{q(X)}$ for any distribution $q(X)$:

Let us spell out this property in a bit more detail. Given any probability distribution $q(X)$, the following is true: $$H(X)\le {\mathbb{E}}_P{\log }_2\frac{1}{q(X)}$$ the equality holds iff $q(X)=p(X)$, i.e. we want to show that $$\begin{array}{rl}0& \le {\mathbb{E}}_P{\log }_2\frac{1}{q(X)}-H(X)\\ & ={\mathbb{E}}_P{\log }_2\frac{1}{q(X)}-{\mathbb{E}}_P{\log }_2\frac{1}{p(X)}\\ & ={\mathbb{E}}_P{\log }_2\frac{p(X)}{q(X)}\end{array}$$ Okay, so proving the lower bound property is equivalent to showing that ${\mathbb{E}}_P{\log }_2\frac{p(X)}{q(X)}\ge 0$. Any idea how can we do this?

The idea is again to use Jensen's inequality:

$$\begin{array}{rl}{\mathbb{E}}_P{\log }_2\frac{p(X)}{q(X)}& =-{\mathbb{E}}_P{\log }_2\frac{q(X)}{p(X)}\\ & \ge -{\log }_2{\mathbb{E}}_P\frac{q(X)}{p(X)}\\ & \ge -{\log }_2\sum _{i=1}^k{p}_i\ast \frac{q_i}{p_i}\\ & \ge -{\log }_2\sum _{i=1}^k{q}_i\\ & \ge -{\log }_{2}1\\ & =0\end{array}$$

Note that we used Jensen's inequality in step (2), but the sign of the inequality is reversed because of the negation. We also know that equality holds iff $$\frac{q_1}{p_1}=\frac{q_2}{p_2}=\dots =\frac{q_k}{p_k}$$ i.e. if $q(X)=p(X)$!

Alright! This proves our property as $${\mathbb{E}}_P{\log }_2\frac{q(X)}{p(X)}\ge 0\to H(X)\le {\mathbb{E}}_P{\log }_2\frac{1}{q(X)}$$

Let's pause a bit and think about what this property is telling:

• Essentially we are telling that $H(X)$ is the solution to the minimization problem: $$H(X)=\underset{q(X)}{\min }{\mathbb{E}}_P{\log }_2\frac{1}{q(X)}$$ We will see that this characterization is often quite useful.
• Another corollary we proved is that $${\mathbb{E}}_P{\log }_2\frac{q(X)}{p(X)}=\sum _{i=1}^k{p}_i{\log }_2\frac{p_i}{q_i}\ge 0$$ for any two distributions $p,q$. The quantity on the right is also known as the KL-Divergence $D_{KL}(p||q)$ between the two distributions.

The KL-Divergence is a very important information theoretic quantity, which we will revisit!

Okay, now that we have defined and got a bit familiar with some of the information theoretic measures, we are all set to understand where the thumb rule $l_{optimal}(symbol)\approx {\log }_2\frac{1}{p(symbol)}$ comes from!

To do so, let's try to answer the question:

Optimal prefix-free codes

The question seems quite daunting! How can we even go about approaching this one? The space of all prefix-free codes is quite large, and not very structured.

Luckily, based on the converse of Kraft's inequality, we know that the space of all prefix-free codes can be characterized by the inequality:

$$\sum _{i=1}^k{2}^{-l_i}\le 1$$ where $l_i$ represent the code-lengths (i.e the depths of the nodes in the prefix-free tree)

Thus, the problem of finding the optimal prefix-free code given a probability distribution $p_1,p_2,\dots ,p_k$ can be formulated as a concise optimization problem.

Quite elegant! We have disassociated the problem of finding optimal prefix-free codes from unclear search spaces over trees and so on. Instead, we now just have this concrete optimization problem. Unfortunately we have integers $l_i$ to optimize over; and integer optimization problems might not be a feasible problem in general. In this case however, we can indeed solve this problem! We will look at a solution in the next lecture.

For this lecture, our goal is to see what best average compression performance we can achieve, i.e what is the solution (or a lower bound) to the minimization objective ${\sum }_{i=1}^k{p}_i{l}_i={\mathbb{E}}_P[L]$

Lower bounding the average codelength

Okay, lets try to see how we can obtain a lower bound for ${\sum }_{i=1}^k{p}_i{l}_i$, given the constraint that ${\sum }_{i=1}^k{2}^{-l_i}\le 1$.

Let's start by adding a dummy length $l_{k+1}$, so that: $$\sum _{i=1}^{k+1}{2}^{-l_i}=1$$ The benefit of this formulation is that we can now imagine $2^{-l_i}=q_i$ as probability values, and use the plethora of properties we proved earlier! Note that $l_{k+1}$ might not be an integer, but that is okay.

Let's also define $p_{k+1}=0$, so that the new objective is equal to the average codelength.

$${\mathbb{E}}_P[L]=\sum _{i=1}^k{p}_i{l}_i=\sum _{i=1}^{k+1}{p}_i{l}_i$$

Okay, now that we have the setup ready, let us try to analyze the average codelength:

$$\begin{array}{rl}\sum _{i=1}^{k+1}{p}_i{l}_i& =\sum _{i=1}^{k+1}{p}_i{\log }_2{2}^{l_i}\\ & =\sum _{i=1}^{k+1}{p}_i{\log }_2\frac{1}{2^{-l_i}}\\ & =\sum _{i=1}^{k+1}{p}_i{\log }_2\frac{1}{q_i}\end{array}$$

All we have done until now is some basic math yoga, but the outcome is that we have transformed the objective ${\sum }_{i=1}^{k+1}{p}_i{l}_i$ into a form more amenable for our purpose. Do you now see the lower bound?

Using the property 3 of entropy for distribution $P$ and $Q$ proved above, we can now show that:

$$\begin{array}{rl}\sum _{i=1}^{k+1}{p}_i{l}_i& =\sum _{i=1}^{k+1}{p}_i{\log }_2\frac{1}{2^{-l_i}}\\ & =\sum _{i=1}^{k+1}{p}_i{\log }_2\frac{1}{q_i}\\ & \ge \sum _{i=1}^{k+1}{p}_i{\log }_2\frac{1}{p_i}\\ & =\sum _{i=1}^k{p}_i{\log }_2\frac{1}{p_i}\\ & =H(X)\end{array}$$

Thus, the lower bound on average codelength of any prefix-free code is the Entropy $H(X)$! It is also easy to see that the equality holds if and only if: $p_i=q_i=2^{-l_i}$ for all $i\in \{1,2,\dots ,k\}$.

To summarize the important theorem:

Some observations/comments:

1. Thumb-rule justification

Notice that the equality condition tells us that optimal compression can be achieved by the prefix-free code iff:

$$l_i={\log }_2\frac{1}{p_i}$$

and, this is the justification for the thumb rule $l_{optimal}(symbol)\approx {\log }_2\frac{1}{p(symbol)}$, we discussed in the previous lecture and used for construction of Shannon code.

2. Shannon code performance

Another point to note is that, we can never achieve avg codelength equal to entropy $H(X)$, unless $p_i=2^{-l_i}$, i.e. all the probabilities $p_i$ are powers of $2$. This can be quite unlikely in real life, which is a bit of a bummer.

The positive news is that we can in fact get quite close to $H(X)$.

Let's analyze the performance of Shannon code. We know that Shannon code has code-lengths $l_i=\lceil {\log }_2\frac{1}{p_i}\rceil$, thus the average codelength is:

$$\begin{array}{rl}\sum _{i=1}^k{p}_i{l}_i& \le \sum _{i=1}^k{p}_i\lceil {\log }_2\frac{1}{p_i}\rceil \\ & \le \sum _{i=1}^k{p}_i({\log }_2\frac{1}{p_i}+1)\\ & =\sum _{i=1}^k{p}_i{\log }_2\frac{1}{p_i}+1\\ & =H(X)+1\end{array}$$

Thus, Shannon code guarantees that we can always achieve average code-lengths within $1$ bit of the optimal. This is quite promising!

Essentially, unless the entropy $H(X)$ is very low, we are not missing much by using Shannon codes.

3. Coding in blocks

As discussed above Shannon codes only guarantee performance up to 1 bit of entropy, and this gap is too much in some scenarios, especially with highly compressible data. In such cases, one common strategy is to code in blocks. This simply means we can treat an input $n$-tuple $X^n=(X_1,\dots ,X_n)$ as a symbol in a bigger alphabet, and apply Shannon code to this alphabet. So we split the input stream into blocks of size $n$ symbols, encode each block and concatenate the results. Here again, Shannon codes get us to within 1 bit of entropy and hence we have (denoting the expected code length by $\bar{l}$): $$\bar{l}(X^n)\le H(X^n)+1$$

Using the properties of joint entropy for i.i.d. random variables, and dividing by $n$ we get $$\frac{1}{n}\bar{l}(X^n)\le H(X)+\frac{1}{n}$$ which means coding in blocks of $n$ brings us within $\frac{1}{n}$ bits of entropy. This means we can get arbitrary close to entropy using block coding and hence entropy is not only the lower bound, but it is also achievable. In the next chapter, we will look at some examples of this phenomenon where we'll see how the average code length improves as we code with bigger and bigger blocks. But there is no free lunch with block coding! Note that a naive implementation would lead to a complexity exponential in $n$ as if the alphabet size is $k$ per-symbol, with block-coding the number of symbols in the alphabet an encoder needs to handle expands to a size of $k^n$. Moreover, we now have a decoding delay of $n$ since we cannot just go and decode a single symbol until we get the entire block. In later chapters, we will look at clever implementations that successfully get the benefits of block coding while reducing this penalty.

4. Entropy as a lower bound for uniquely decodable codes

We showed that $H(X)$ lower bounds the average code-lengths for prefix-free codes. But, what about general symbol codes which are uniquely decodable (or lossless)?

We saw that even for general uniquely decodable symbol codes, the Kraft inequality holds true. i.e: $$\sum _{i=1}^k{2}^{-l_i}\le 1$$ Notice that this is precisely the only property we use for proving the lower bound on $H(X)$, and so, entropy is in fact a lower bound on average code-lengths for general uniquely decodable codes.

5. Mismatched coding and KL-divergence

We saw above that the code optimized of a source $P$ will have code lengths $l_i\approx {\log }_2\frac{1}{p_i}$. This achieves expected code length close to entropy: $$\bar{l}=\sum p_i{l}_i\approx \sum p_i{\log }_2\frac{1}{p_i}=H(P)$$

Now, consider a scenario where we optimize a code for source distribution $Q$ but then use it for a source with distribution $P$. In this case, the code lengths will be $l_i\approx {\log }_2\frac{1}{q_i}$ and the average code length will be $$\begin{array}{rl}\bar{l}& =\sum p_i{l}_i\\ & \approx \sum p_i{\log }_2\frac{1}{q_i}\\ & =\sum p_i{\log }_2\frac{1}{p_i}+\sum p_i{\log }_2\frac{p_i}{q_i}\\ & =H(P)+D(P||Q)\end{array}$$ In this scenario, the optimal code length was $H(P)$ but the actual average code length exceeds it by $D(P||Q)$. Thus the KL-divergence is the penalty for mismatched coding for using the incorrect distribution for designing the code. Later in the class we will study universal codes which imply existence of distributions that can closely approximate any distribution from a large class, meaning that a single code (over a block) is able to perform well irrespective of the actual source distribution.

Entropy beyond data compression

Given a random variable $X$ over $\{1,2,\dots ,k\}$ with distribution $P=\{p_1,p_2,\dots ,p_k\}$, we know that the fundamental limit on compression of the random variable $X$ using symbol codes is $H(X)$.

$H(X)$ is sometimes also referred to as the self-information of the random variable $X$, as in a way, we are saying that the amount of information (on an average) in each instantiation of the random variable $X$ is $H(X)$ bits. This is quite natural, as we should not be able to compress an input better than the amount of information it is worth.

The discussion, although a bit hand-wavy is quite fundamental. Due to this, we see $H(X)$ popping up at lots of other places as a fundamental limit of a problem, and not just in case of compression.

For example, here are a few scenarios, for which the answer is related to $H(X)$. Try to solve them for fun!

1. Simulating non-uniform random variables: Lets say you want to simulate a random variable $X$ over $\{1,2,\dots k\}$ with distribution $P=\{p_1,p_2,\dots ,p_k\}$. To simulate the random variable, you are only allowed to use fair coin tosses. In that case, what is fundamental limit on the average number of coins you would have to toss to simulate $X$?

2. Simulating a fair coin using a biased coin: Lets now say you have a biased coin with probability of H/T to be $p,1-p$ respectively. The goal is to use this coin to simulate a fair coin. One simple way to do this is to toss the coin twice, and associate (H,T) as heads, and (T,H) as tails. If we get (H,H), (T,T), then we discard the result and toss again. Is this the optimal strategy though? Can you do better? What is the fundamental limit on the average number of biased coins you would have to toss do to obtain a fair coin?

3. Biased binary search: We are familiar that given a sorted array of size $k$, we can locate a query $q$ in one of the $n$ bins using $\lceil {\log }_{2}k\rceil$ comparisons. However, a lot of times, we already have a good idea which bins the query might lie in. Can we accelerate the binary-search in this case? To be more precise, lets say you have a bias that the query will lie in each of the bins with probability $p_1,p_2,\dots ,p_k$. (usually this bias is uniform, i.e $p_i=1/n$). In such a scenario what is the fundamental limit on the average number of comparisons you have to do to locate the query $q$?

Although all these scenarios seem very different, they are essentially related to Entropy $H(X)$, and use the property that the self information, the amount of bits corresponding to random variable $X$ is $H(X)$. This key intuition led to a very diverse and vibrant area of mathematics called Information Theory. What we saw in today's lecture is just a small glimpse into information theory, but if you are interested please take a look at the course EE 276, and the resources listed there.

Summary and next lecture

To summarize this lecture:

1. Entropy: We took a detour into information theory and understood some properties of entropy $H(X)$.
2. Entropy as a limit of compression: We derived the properties of $H(X)$ and used them to show that $H(X)$ is the fundamental limit on the compression, i.e. the average codelength of any prefix-free code designed for compressing a given source $X$ is always lower bounded by $H(X)$.

Although we were able to show that $H(X)$ is the fundamental limit on average codelength, and that we can always come within 1 bit of the fundamental limit using Shannon codes, it is a bit unsatisfactory as we don't know if Shannon Code is the optimal prefix code.

In the next lecture, we are doing to discuss Huffman Code, which is the answer to the question:

Given a random variable with instances sampled i.i.d with probability distribution $P=\{p_1,p_2,\dots ,p_k\}$, what is the best prefix free code for this source?

Huffman Code

Introduction

As a recap, in the last lecture we formulated the problem of finding the optimal prefix-free code given a probability distribution $p_1,p_2,\dots ,p_k$ as a concrete optimization problem as follows:

We also showed that the optimal average codelength $L(p)$ is lower bounded by $H(p)$, the entropy corresponding to source $p$. (i.e. $L(p)\ge H(p)$). In this lecture we are going to discuss the famous Huffman codes, which is in fact (one of) the solutions to the optimization problem above!

The problem of finding optimal prefix-free codes eluded researchers for quite some time; until David Huffman, then a mere graduate student in the EE dept at MIT solved it as his course project! Here is an anecdote about the discovery of Huffman codes, borrowed from the maa webpage.

"The story of the invention of Huffman codes is a great story that demonstrates that students can do better than professors. David Huffman (1925-1999) was a student in an electrical engineering course in 1951. His professor, Robert Fano, offered students a choice of taking a final exam or writing a term paper. Huffman did not want to take the final so he started working on the term paper. The topic of the paper was to find the most efficient (optimal) code. What Professor Fano did not tell his students was the fact that it was an open problem and that he was working on the problem himself. Huffman spent a lot of time on the problem and was ready to give up when the solution suddenly came to him. The code he discovered was optimal, that is, it had the lowest possible average message length. The method that Fano had developed for this problem did not always produce an optimal code. Therefore, Huffman did better than his professor. Later Huffman said that likely he would not have even attempted the problem if he had known that his professor was struggling with it."

Huffman code construction

Even before we get started, it is important to note that Huffman codes are one of the optimal prefix-free codes for a given distribution, and that there are multiple of those. It is easy to see why: for example, given codewords 0, 10, 110, ... from Huffman code, we can just switch 0 with 1 and that is another legit optimal prefix-free code (1, 01, 001, ...). So, we are going to discuss one of the many possible optimal prefix free constructions.

Let's first discuss the construction of the Huffman codes, and then we will discuss the optimality. Let's start with an example probability distribution:

probs_dict = {"A": 0.35, "B": 0.25, "C": 0.2, "D": 0.12, "E": 0.08}

STEP 0: The initial step is to first build singleton nodes from these probabilities.

graph TD
  N1["A<br/>(p=0.35)"]:::endnode
  N2("B<br/>(p=0.25)"):::endnode
  N3("C<br/>(p=0.2)"):::endnode
  N4("D<br/>(p=0.12)"):::endnode
  N5("E<br/>(p=0.08)"):::endnode

Note that each Node has the following structure.

class Node:
    str symbol_name
    float prob
    Node left = None
    Node right = None

Each node has a symbol_name and a prob fields. The node also has left and right fields, which are pointers to its children.

node_list = [Node(A, 0.35), Node(B, 0.25), Node(C, 0.2), Node(D, 0.12), Node(E, 0.08)]

Essentially we now have 5 nodes (or binary trees with a single node). The Huffman tree construction works by joining these nodes in a recursive fashion using the next 2 steps, to construct a single tree.

Step 1: We pop out the two nodes with the smallest probability from the node_list. In our example, these are Node(D, 0.12) and Node(E, 0.08)

Thus, the node_list now looks like:

node_1, node_2 = Node(D, 0.12), Node(E, 0.08)
node_list = [Node(A, 0.35), Node(B, 0.25), Node(C, 0.2)]

Step 2: In the next step, we join the two popped nodes and create a new node as a parent of these two nodes. The probability of the new node is equal to the sum of the two children nodes. In our example, the new node is node N1 and has prob = 0.12 + 0.08 = 0.2.

This new node is re-added to the node_list.
So, now our node list is:

## Iter 1
node_list = [Node(A, 0.35), Node(B, 0.25), Node(C, 0.2), Node(N1, 0.2)]

graph TD
  N1["A<br/>(p=0.35)"]:::endnode
  N2("B<br/>(p=0.25)"):::endnode
  N3("C<br/>(p=0.2)"):::endnode
  N4("D<br/>(p=0.12)"):::endnode
  N5("E<br/>(p=0.08)"):::endnode
  N6("N1<br/>(p=0.2)") --> N4
  N6 --> N5

  style N6 fill:#dddddd

Let's pause and see what the two steps above did: Step 1,2 reduced the length of node_list by 1 (as we removed 2 nodes and added 1). We can thus apply Step 1, Step 2 recursively, to obtain a single node/tree. The resulting final tree is our Huffman tree!

## Iter 2
node_list = [Node(A, 0.35), Node(B, 0.25), Node(N2, 0.4)]

graph TD
  N1["A<br/>(p=0.35)"]:::endnode
  N2("B<br/>(p=0.25)"):::endnode
  N3("C<br/>(p=0.2)"):::endnode
  N4("D<br/>(p=0.12)"):::endnode
  N5("E<br/>(p=0.08)"):::endnode
  N6("N1<br/>(p=0.2)") --> N4
  N6 --> N5
  N7("N2<br/>(p=0.4)") --> N6
  N7 --> N3

  style N6 fill:#dddddd
  style N7 fill:#dddddd

## Iter 3
node_list = [Node(N2, 0.4), Node(N3, 0.6)]

graph TD
  N1["A<br/>(p=0.35)"]:::endnode
  N2("B<br/>(p=0.25)"):::endnode
  N3("C<br/>(p=0.2)"):::endnode
  N4("D<br/>(p=0.12)"):::endnode
  N5("E<br/>(p=0.08)"):::endnode
  N6("N1<br/>(p=0.2)") --> N4
  N6 --> N5
  N7("N2<br/>(p=0.4)") --> N6
  N7 --> N3
  N8("N3<br/>(p=0.6)") --> N1
  N8 --> N2

  style N6 fill:#dddddd
  style N7 fill:#dddddd
  style N8 fill:#dddddd

## Iter 4
node_list = [Node("*", 1.0)]

graph TD
  N1["A<br/>(p=0.35)"]:::endnode
  N2("B<br/>(p=0.25)"):::endnode
  N3("C<br/>(p=0.2)"):::endnode
  N4("D<br/>(p=0.12)"):::endnode
  N5("E<br/>(p=0.08)"):::endnode
  N6("N1<br/>(p=0.2)") --> N4
  N6 --> N5
  N7("N2<br/>(p=0.4)") --> N6
  N7 --> N3
  N8("N3<br/>(p=0.6)") --> N1
  N8 --> N2
  N9("*<br/>(p=1.0)") --> N8
  N9 --> N7

  style N6 fill:#dddddd
  style N7 fill:#dddddd
  style N8 fill:#dddddd
  style N9 fill:#dddddd

Thus, our procedure for constructing the Huffman tree can be described in pseudo-code as follows:

# Input -> given prob distribution
probs_dict = {A1: p_1, A2: p_2, ..., Ak: p_k} # p_1, .. are some floating point values

class Node:
    str symbol_name
    float prob
    Node left = None
    Node right = None

    
def build_huffman_tree(probs_array):
    ## STEP 0: initialize the node_list with singleton nodes
    node_list = [Node(s,prob) for s,prob in probs_array.items()]

    # NOTE: at each iter, we are reducing length of node_list by 1
    while len(node_list) > 1:
        ## STEP 1: sort node list based on probability,
        # and pop the two smallest nodes 
        node_list = sort(node_list) # based on node.prob
        node_0, node_1 = node_list.pop(0, 1) # remove the smallest and second smallest elements

        ## STEP 2: Merge the two nodes into a single node
        new_node_prob = node_0.prob + node_1.prob
        new_node = Node(symbol_name="", prob=new_node_prob, left=node_0, right=node_1)
        node_list.append(new_merged_node)
    
    # finally we will have a single node/tree.. return the node as it points to the 
    # root node of our Huffman tree
    return node_list[0] 

Quite cool! We are essentially constructing the tree in by stitching one node at a time, until we have a single tree. Nodes with smaller probabilities join into a sub-tree earlier and thus, they will likely have higher depth in the final tree (and thus longer codelength). As we will see this greedy approach is in fact optimal!

Once the Huffman tree is constructed, we can use this tree as a prefix-free code for encoding/decoding data. For example, in our case the table we get is:

Here is another example below of the Huffman code constructed on a typical text of english language. Notice that vowels, punctuations have much shorter length as they occur quite frequently.

Optimizing the tree construction

There are certain optimizations which can be performed in the Huffman tree construction:

For example, STEP 1 in the pseudocode can be replaced with a priority queue, as we mainly need top two elements and nothing more. Here is the full code implementation in the Stanford Compression Library: https://github.com/kedartatwawadi/stanford_compression_library/blob/main/compressors/huffman_coder.py.

Optimality of Huffman codes

To get some intuition into the Huffman code optimality, let's think about what are the necessary conditions for a prefix-free code to be optimal? Let me list a couple of conditions, and we will see why they are true:

Condition 1 proof

Condition 1 is quite obvious but fundamental: it just says that if the probability of a symbol is higher than it necessarily has to have a shorter codelength. We have seen condition Condition 1 before, as a thumb-rule. But, lets show that it is explicitly true in this case. Let's assume that our code $\mathcal{C}$ is optimal but for $p_i>p_j$ has $l_i>l_j$. Let the average codelength of code $\mathcal{C}$ be $L_1$. Now, lets consider a prefix-free code $\hat{\mathcal{C}}$ where we exchange the codewords corresponding to i and j. Thus, the new code-lengths ${\hat{l}}_i$ are: $$\begin{array}{rl}{\hat{l}}_r& =l_r,\text{ if }r\ne i\text{ and }r\ne j\\ {\hat{l}}_i& =l_j\\ {\hat{l}}_j& =l_i\end{array}$$

The new average codelength $L_2$ is: $$\begin{array}{rl}{L}_2& =\sum _{i=1}^k{p}_r{\hat{l}}_r\\ & =L_1+p_i({\hat{l}}_i-l_i)+p_j({\hat{l}}_j-l_j)\\ & =L_1+p_i(l_j-l_i)+p_j(l_i-l_j)\\ & =L_1-(l_i-l_j)(p_i-p_j)\end{array}$$

As $(l_i-l_j)(p_i-p_j)>0$, it implies that $L_2<L_1$, which is in contradiction to our assumption that code $\mathcal{C}$ is optimal. This proves the Condition 1.

Condition 2 proof

The Condition 2 is also equally simple to prove. Let's show it by contradiction again. For example, let $c_k=0110101$ be the unique longest codeword. Then, as there is no other codeword of length $7$, we can be sure that we can drop one bit from $c_k$, and the resulting code will still be a valid prefix-free code. Thus, we can assign ${\hat{c}}_k=011010$, and we get a shorter average codelength!

As we can see, these two properties are satisfied by the construction procedure of Huffman coding.

1. The symbols with higher probability are chosen later, so their code-lengths are lower.
2. We always choose the two symbols with the smallest probability and combine them, so the Condition 2 is also satisfied.

Note that these are just observations about Huffman construction and don't prove its optimality. The optimality proof is a bit more technical, and we refer you to the Cover, Thomas text, section 5.8.

The main property is that after the merge step of merging two smallest probability nodes of probability distribution $(p_1,p_2,\dots ,p_k)$, the remaining tree is still optimal for the distribution $(p_1,p_2,\dots ,p_{k-1}+p_k)$.

Practical prefix-free coding

Huffman codes are actually used in practice due to their optimality and relatively convenient construction! Here are some examples:

• http/2 header compression: https://www.rfc-editor.org/rfc/rfc7541#appendix-B

• ZLIB, DEFLATE, GZIP, PNG compression: https://www.ietf.org/rfc/rfc1951.txt

• JPEG huffman coding tables: https://www.w3.org/Graphics/JPEG/itu-t81.pdf

A lot of times in practice, the data is split into streams and after multiple transformations needs to be losslessly compressed. This is the place where Huffman codes are used typically.

Fast Prefix-free decoding

In practice, Huffman coders lie at the end of any compression pipeline and need to be extremely fast. Let's look at the typical encoding/decoding and see how we can speed it up.

For simplicity and clarity we will work with a small exmaple. Let's say this is our given code:

encoding_table = {"A": 0, "B": 10, "C": 110, "D": 111}

1. The encoding itself is quite simple and involves looking at a lookup table.

## Prefix-free code encoding
encoding_table = {"A": 0, "B": 10, "C": 110, "D": 111}
def encode_symbol(s):
    bitarray = encoding_table[s]
    return bitarray, len(bitarray)

The typical prefix-free code decoding works by parsing through the prefix-free tree, until we reach a leaf node, e.g. see the code in SCL: https://github.com/kedartatwawadi/stanford_compression_library/blob/main/compressors/prefix_free_compressors.py. Here is a pseudo-code for the decoding algorithm:

## Prefix-free code decoding: 
prefix_free_tree = ... # construct a tree from the encoding_table
def decode_symbol_tree(encoded_bitarray):
    # initialize num_bits_consumed
    num_bits_consumed = 0

    # continue decoding until we reach leaf node
    curr_node = prefix_free_tree.root_node
    while not curr_node.is_leaf_node:
        bit = encoded_bitarray[num_bits_consumed]
        if bit == 0:
            curr_node = curr_node.left_child
        else:
            curr_node = curr_node.right_child
        num_bits_consumed += 1

    # as we reach the leaf node, the decoded symbol is the id of the node
    decoded_symbol = curr_node.id
    return decoded_symbol, num_bits_consumed

Although this is quite simple, there are a lot of branching instructions (e.g. if, else conditions). These instructions are not the fastest instructions on modern architectures. So, here is an alternative decoding procedure for this example:

## faster decoding
state_size = 3
decode_state = {
    000: "A",
    001: "A",
    010: "A",
    011: "A",
    100: "B",
    101: "B",
    110: "C",
    111: "D",
}
codelen_table = {
    "A": 1,
    "B": 2,
    "C": 3,
    "D": 3,
}
def decode_symbol_tree(encoded_bitarray):
    state = encoded_bitarray[:state_size] 
    decoded_symbol = decode_state[state]
    num_bits_consumed = codelen_table[decoded_symbol]
    return decoded_symbol, num_bits_consumed

Looking at the new decoding pseudo-code, we see following observations:

1. The state_size=3 corresponds to the maximum depth of the prefix-free tree.
2. The state is the first 3 bits of the encoded_bitarray. We use the state as an index to query thr decode_state lookup table to obtain the decoded_symbol.
3. As the state is sometimes reading in more bits that what we wrote, we need to output the num_bits_consumed correctly to be codelen_table[decoded_symbol].

One natural question is why should the decoded_symbol = decode_state[state] operation output the correct state? The reason is because of the prefix-free nature of the codes. So, if we look at the entries in decode_state table corresponding to B, we see that these are 100, 101 both of which start with 10 which is the codeword corresponding to B.

Based on first look, the decoding is indeed simpler with this new decoding procedure, but we do have to pay some cost. The cost is in terms of memory consumption. For example, we now need to maintain a table decode_state which has size $2^{|maxdepth|}$. This is clearly more memory than a typical prefix-free tree. In a way we are doing some caching. But for caching to work properly, the table sizes need to be small. The bigger the lookup table, the slower the table lookup is. So, practically the maximum leaf depth needs to be kept in check.

Thus, practically we want to get a Huffman tree with a maximum leaf depth constraint. Typically, the depth is also set to be 16 or 24 so that it is a byte multiple. For more details on efficient Huffman Coding, we encourage the reader to have a look at this blog entry by Fabian Giesen on Huffman coding: https://fgiesen.wordpress.com/2021/08/30/entropy-coding-in-oodle-data-huffman-coding/?hmsr=joyk.com&utm_source=joyk.com&utm_medium=referral.

Asymptotic Equipartition Property

We have been looking at the problem of data compression, algorithms for the same as well as fundamental limits on the compression rate. In this chapter we will approach the problem of data compression in a very different way. The basic idea of asymptotic equipartition property is to consider the space of all possible sequences produced by a stochastic (random) source, and focusing attention on the "typical" ones. The theory is asymptotic in the sense that many of the results focus on the regime of large source sequences. This technique allows us to recover many of the results for compression but in a non-constructive manner. Beyond compression, the same concept has allowed researchers to obtain powerful achievability and impossibility results even before a practical algorithm was developed. Our presentation here will focus on the main concepts, and present the mathematical intuition behind the results. We refer the reader to Chapter 3 in Cover and Thomas and to Information Theory lecture notes (available here) for some details and proofs.

Before we get started, we define the notation used throughout this chapter:

1. Alphabet: $\mathcal{U}=\{1,2,\dots ,r\}$ specifies the possible values that the random variable of interest can take.
2. iid source: An independent and identically distributed (iid) source produces a sequence of random variables that are independent of each other and have the same distribution, e.g. a sequence of tosses of a coin. We use $U_1,U_2,\dots \mathrm{iid}\sim U$ notation for iid random variables from distribution $U$.
3. Source sequence: $U^n=(U_1,\dots ,U_n)$ denotes the $n$-tuple representing $n$ source symbols, and ${\mathcal{U}}^n$ represents the set of all possible $U^n$. Note that we use lowercase $u^n$ for a particular realization of $U^n$.
4. Probability: Under the iid source model, we simply have $P(U^n)={\Pi }_{i=1}^{n}P(U_i)$ where we slightly abuse the notation by using $P$ to represent both the probability function of the $n$-tuple $U^n$ and that for a given symbol $U_i$.