Assume that one knows that a sequence of bits is going to consist of bit pairs w
ID: 1845664 • Letter: A
Question
Assume that one knows that a sequence of bits is going to consist of bit pairs with the following frequency:
Bit Pair Frequency
00 50%
01 30%
10 10%
11 10%
Can you come up with an "alphabet" that allows you to transmit fewer bits on average than simply transmitting the bits as they appear? Keep in mind that the alphabet you come up with would have to allow for unique decoding. Try your scheme with the following sequence and count the number of bits transmitted using your scheme vs. the original number of bits: 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1
Explanation / Answer
Using the HUFFMAN TREE coding scheme, I got the following codes:
00 => 0
01 => 11
10 => 100
11 => 101
The alphabets can be decoded uniquely because they fulfill the condition that no alphabet is the prefix of remaining alphabets.
for more understanding and reference, you can have a look at: http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/
For evaluating the scheme, the original message was:
0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 (Number of bits = 42)
Using the coding scheme, same message was transmitted as:
0 0 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 1 (Number of bits = 36)
Saving in bit rate = (42 - 36)/42 * 100 % = 100/7 % = 14.28 % (~ 15%)