Cryptography: Theory and Practice:Shannon s Theory | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

2.2.1 Huffman Encodings and Entropy

In this section, we discuss briefly the connection between entropy and Huffman encodings. As the results in this section are not relevant to the cryptographic applications of entropy, it may be skipped without loss of continuity. However, this discussion may serve to further motivate the concept of entropy.

We introduced entropy in the context of encodings of random events which occur according to a specified probability distribution. We first make these ideas more precise. As before, X is a random variable which takes on a finite set of values, and p(X) is the associated probability distribution.

An encoding of X is any mapping

where {0, 1}* denotes the set of all finite strings of 0’s and 1’s. Given a finite list (or string) of events x₁ ... x_n, we can extend the encoding f in an obvious way by defining

where || denotes concatenation. In this way, we can think of f as a mapping

Now, suppose a string x₁ ... x_n is produced by a memoryless source such that each x_i occurs according to the probability distribution on X. This means that the probability of any string x₁ ... x_n is computed to be p(x₁) × . . . × p(x_n). (Notice that this string need not consist of distinct values, since the source is memoryless. As a simple example, consider a sequence of n tosses of a fair coin.)

Now, given that we are going to encode strings using the mapping f, it is important that we are able to decode in an unambiguous fashion. Thus it should be the case that the encoding f is injective.

Example 2.2

Suppose X = {a, b, c, d}, and consider the following three encodings:

It can be seen that f and g are injective encodings, but h is not. Any encoding using f can be decoded by starting at the end and working backwards: every time a 1 is encountered, it signals the end of the current element.

An encoding using g can be decoded by starting at the beginning and proceeding sequentially. At any point where we have a substring that is an encoding of a, b, c, or d, we decode it and chop off the substring. For example, given the string 10101110, we decode 10 to b, then 10 to b, then 111 to d, and finally 0 to a. So the decoded string is bbda.

To see that h is not injective, it suffices to give an example:

From the point of view of ease of decoding, we would prefer the encoding g to f. This is because decoding can be done sequentially from beginning to end if g is used, so no memory is required. The property that allows the simple sequential decoding of g is called the prefix-free property. (An encoding g is prefix-free if there do not exist two elements x, y ∈ X, and a string z ∈ {0, 1}* such that g(x) = g(y) || z.)

The discussion this point has not involved entropy. Not surprisingly, entropy is related to the efficiency of an encoding. We will measure the efficiency of an encoding f as we did before: it is the weighted average length (denoted by ) of an encoding of an element of X. So we have the following definition:

where |y| denotes the length of a string y.

Now, our fundamental problem is to find an injective encoding, f, that minimizes . There is a well-known algorithm, known as Huffman’s algorithm, that accomplishes this goal. Moreover, the encoding f produced by Huffman’s algorithm is prefix-free, and

Thus, the value of the entropy provides a close estimate to the average length of the optimal injective encoding.

We will not prove the results stated above, but we will give a short, informal description of Huffman’s algorithm. Huffman’s algorithm begins with the probability distribution on the set X, and the code of each element is initially empty. In each iteration, the two elements having lowest probability are combined into one element having as its probability the sum of the two smaller probabilities. The smaller of the two elements is assigned the value “0” and the larger of the two elements is assigned the value “1.” When only one element remains, the coding for each x ∈ X can be constructed by following the sequence of elements “backwards” from the final element to the initial element x.

This is easily illustrated with an example.

Example 2.3

Suppose X = {a, b, c, d, e} has the following probability distribution: p(a) = .05, p(b) = .10, p(c) = .12, p(d) = .13 and p(e) = .60. Huffman’s algorithm would proceed as indicated in the following table:

This leads to the following encodings:

x	f(x)

a	000
b	001
c	010
d	011
e	1

Thus, the average length encoding is

Compare this to the entropy:

Table of Contents