196
12 Cryptocurrencies
omitting the much more likely vowels y cn stll ndrstnd ths sntnc.
1 Therefore, we need
to work out how to characterize information if the symbols are not equally probable.
Let us consider a source of characters that sequentially ejects one character of
written English per unit time and find out how much information we can expect to
receive. Following Shannon [2], we assume that the probabilities p i , with which the
characters appear, are known. Here i labels the characters, such that i = 1 corresponds to “A” and so forth. To find the average entropy H per ejected character we
calculate the expectation value of the entropy log 2 (1/ p i ), carried by each character,
which occurs with probability p i
H =
i
p i log 2 (1/ p i ) = −
i
p i log 2 ( p i ) ,
(12.2)
where the sum extends over all possible characters that are ejected by the source.
Note that in the special case, where all probabilities p i are equal to p i = 1/n for
i = 1, . . . , n, (12.2) reverts to (12.1). When calculating expressions such as T (x) =
x log 2 x, we follow the convention that T (0) = 0, which is justified by continuity
in the limit x → 0. Moreover, this assumption guarantees that configurations with
probability p = 0, which never occur, do not contribute to the entropy H .
To gain a better understanding of (12.2) and its implications we download the file
pg10.txt with the ASCII text of the King James bible [4] from Project Gutenberg [5]. Using the simple script from Appendix B.9 we prepare the following file
containing the number of occurrences of each character
751152
275735 A
48880 B
:
The space occurs 751152 times and the letter “A” occurs 272735 times in the cleanedup file which contains the text of the King James bible. From the character frequencies
n i , shown in the first column, it is straightforward to calculate the probabilities p i =
n i /
i n i and the average information per character H from (12.2). For the King
James bible we find H K J B ≈ 4.04. Repeating the same exercise for Shakespeare’s
Hamlet [6], we find a similar value of H Hamlet ≈ 3.94. We conclude that, instead of
using one byte with eight bits, we could use only four bits per character, or half of
a byte, also called nibble, to encode English texts.
But how does one send Hamlet using only four bits per character if there are more
than 16 different characters in use? This is, in fact, accomplished by using fewer
bits to encode the more frequently appearing characters and use longer “codes” for
the rarer characters. This task, which is called source encoding, is easily illustrated
with a simple example, where only four characters, say A, B, C, and D, or, more
generally, four symbols, are transmitted. Let us assume that these symbols appear
1 ..you can still understand this sentence.
12 Cryptocurrencies
omitting the much more likely vowels y cn stll ndrstnd ths sntnc.
1 Therefore, we need
to work out how to characterize information if the symbols are not equally probable.
Let us consider a source of characters that sequentially ejects one character of
written English per unit time and find out how much information we can expect to
receive. Following Shannon [2], we assume that the probabilities p i , with which the
characters appear, are known. Here i labels the characters, such that i = 1 corresponds to “A” and so forth. To find the average entropy H per ejected character we
calculate the expectation value of the entropy log 2 (1/ p i ), carried by each character,
which occurs with probability p i
H =
i
p i log 2 (1/ p i ) = −
i
p i log 2 ( p i ) ,
(12.2)
where the sum extends over all possible characters that are ejected by the source.
Note that in the special case, where all probabilities p i are equal to p i = 1/n for
i = 1, . . . , n, (12.2) reverts to (12.1). When calculating expressions such as T (x) =
x log 2 x, we follow the convention that T (0) = 0, which is justified by continuity
in the limit x → 0. Moreover, this assumption guarantees that configurations with
probability p = 0, which never occur, do not contribute to the entropy H .
To gain a better understanding of (12.2) and its implications we download the file
pg10.txt with the ASCII text of the King James bible [4] from Project Gutenberg [5]. Using the simple script from Appendix B.9 we prepare the following file
containing the number of occurrences of each character
751152
275735 A
48880 B
:
The space occurs 751152 times and the letter “A” occurs 272735 times in the cleanedup file which contains the text of the King James bible. From the character frequencies
n i , shown in the first column, it is straightforward to calculate the probabilities p i =
n i /
i n i and the average information per character H from (12.2). For the King
James bible we find H K J B ≈ 4.04. Repeating the same exercise for Shakespeare’s
Hamlet [6], we find a similar value of H Hamlet ≈ 3.94. We conclude that, instead of
using one byte with eight bits, we could use only four bits per character, or half of
a byte, also called nibble, to encode English texts.
But how does one send Hamlet using only four bits per character if there are more
than 16 different characters in use? This is, in fact, accomplished by using fewer
bits to encode the more frequently appearing characters and use longer “codes” for
the rarer characters. This task, which is called source encoding, is easily illustrated
with a simple example, where only four characters, say A, B, C, and D, or, more
generally, four symbols, are transmitted. Let us assume that these symbols appear
1 ..you can still understand this sentence.