12.1 Information, Probabilities, and Codes
197
Table 12.1 Two different encodings for four symbols, shown in the first column, each appearing
with the probabilities, shown in the second column
Symbol
Probability
Encoding 1
Encoding 2
A
1/2
00
0
B
1/4
01
10
C
1/8
10
110
D
1/8
11
111
with the probabilities 1/2, 1/4, 1/8, and 1/8, respectively. In Table 12.1 we show
the symbols along with their associated probabilities and two ways to encode them.
The first encoding uses binary codes and the second uses a zero to terminate the code
and an increasing number of ones to differentiate the symbols.
Note that we assign the shortest code, a single “0” to the most frequent symbol
“A,” which has the highest probability to appear in a message. It is easy to convince
ourselves that any sequence of zeros and ones can be uniquely converted back to
the original sequence of symbols: count ones up to a maximum of three consecutive
or until a zero is found. For example, “0” without preceeding “1” indicates the
symbol “A”.
Let us now calculate the average number of bits l =
i p i l i , where l i is the
number of bits—the length—of the corresponding code and i identifies the four
symbols. For the first, binary, encoding every symbol is represented by two bits, so
the average length is l 1 = 2. In the second encoding, the average length for the
symbols is l 2 = 7/4, which is smaller than l 1 . The gain is not very big in this
simple example, but illustrates the idea, namely to use shorter codes for the more
frequently appearing symbols.
As a matter of fact, in his source coding theorem, Shannon proved [2] that long
messages with very many, say n, symbols, can be encoded in a sequence of length
L n , given by n H < L n < n H + 1, where the different symbols come from a set of
symbols with probabilities p i and are therefore characterized by the entropy H =
−
i p i log 2 p i . Here n must be sufficiently large in order to exploit the different
probabilities of the symbols. Shannon’s proof, which is outside our scope, only
proves the existence of such an optimal code, but does not describe how to construct
it. Of course, finding efficient codes for a set of symbols with associated probabilities
that minimizes the length of transmitted messages is of considerable interest. The
problem was solved comprehensively in 1952 and led to the construction of Huffman
codes [7].
In his seminal report [2], Shannon centered his analysis around the “entropy” as
defined in (12.2). In the following section we will explore its relation to the concept
of entropy that is well-known in thermodynamics and statistical mechanics.
197
Table 12.1 Two different encodings for four symbols, shown in the first column, each appearing
with the probabilities, shown in the second column
Symbol
Probability
Encoding 1
Encoding 2
A
1/2
00
0
B
1/4
01
10
C
1/8
10
110
D
1/8
11
111
with the probabilities 1/2, 1/4, 1/8, and 1/8, respectively. In Table 12.1 we show
the symbols along with their associated probabilities and two ways to encode them.
The first encoding uses binary codes and the second uses a zero to terminate the code
and an increasing number of ones to differentiate the symbols.
Note that we assign the shortest code, a single “0” to the most frequent symbol
“A,” which has the highest probability to appear in a message. It is easy to convince
ourselves that any sequence of zeros and ones can be uniquely converted back to
the original sequence of symbols: count ones up to a maximum of three consecutive
or until a zero is found. For example, “0” without preceeding “1” indicates the
symbol “A”.
Let us now calculate the average number of bits l =
i p i l i , where l i is the
number of bits—the length—of the corresponding code and i identifies the four
symbols. For the first, binary, encoding every symbol is represented by two bits, so
the average length is l 1 = 2. In the second encoding, the average length for the
symbols is l 2 = 7/4, which is smaller than l 1 . The gain is not very big in this
simple example, but illustrates the idea, namely to use shorter codes for the more
frequently appearing symbols.
As a matter of fact, in his source coding theorem, Shannon proved [2] that long
messages with very many, say n, symbols, can be encoded in a sequence of length
L n , given by n H < L n < n H + 1, where the different symbols come from a set of
symbols with probabilities p i and are therefore characterized by the entropy H =
−
i p i log 2 p i . Here n must be sufficiently large in order to exploit the different
probabilities of the symbols. Shannon’s proof, which is outside our scope, only
proves the existence of such an optimal code, but does not describe how to construct
it. Of course, finding efficient codes for a set of symbols with associated probabilities
that minimizes the length of transmitted messages is of considerable interest. The
problem was solved comprehensively in 1952 and led to the construction of Huffman
codes [7].
In his seminal report [2], Shannon centered his analysis around the “entropy” as
defined in (12.2). In the following section we will explore its relation to the concept
of entropy that is well-known in thermodynamics and statistical mechanics.