English
Menu

Information Theory and Coding Basics

A source emits the symbols A, B, C and D independently with probabilities 0.4, 0.3, 0.2 and 0.1, and it is encoded with a Huffman code. Which of the following is the average code length per symbol?

  1. AAbout 1.85 bits
  2. B1.9 bits
  3. C2 bits
Show answer and explanation

Answer: B. 1.9 bits

A Huffman code repeatedly merges the two smallest probabilities. 0.1 and 0.2 are merged into 0.3, then 0.3 and 0.3 into 0.6, and finally 0.6 and 0.4, so the code lengths are 1 bit for A, 2 bits for B and 3 bits for C and D. The average code length is 0.4 × 1 + 0.3 × 2 + 0.2 × 3 + 0.1 × 3 = 1.9 bits.

  • A. About 1.85 bits is the entropy of this source, the lower bound of the average code length. The probabilities are not reciprocals of powers of 2 such as 1/2 or 1/4, so even a Huffman code cannot get that short.
  • B. Correct. 0.4 + 0.6 + 0.6 + 0.3 = 1.9 bits.
  • C. 2 bits is the code length of a fixed-length code that represents the four symbols with equal lengths.
Practice this topic Back to topic

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

More Information Theory and Coding Basics questions

  1. A source emits the symbols A to E independently with probabilities 0.3, 0.25, 0.2, 0.15 and 0.1, and it is encoded with a Huffman code. The codewords may change depending on which of two equal probabilities is chosen first, but the average code length does not. Which of the following is the average code length per symbol?
  2. A source emits the symbols A, B and C independently with probabilities 0.6, 0.3 and 0.1, and its entropy is about 1.30 bits. Which of the following is closest to the efficiency (entropy ÷ average code length) when this source is encoded with a Huffman code?
  3. A binary source emits 0 with probability 0.8 and 1 with probability 0.2, independently. Symbols are taken two at a time, each of the four pairs 00, 01, 10 and 11 is treated as one symbol, and they are encoded with a Huffman code. Which of the following is the average code length per original symbol?
  4. Which of the following correctly describes the relationship between lossless compression and the entropy of a source?
  5. The 40-character string AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12 As, 4 Bs, 20 Cs and 4 Ds) is compressed with run-length encoding, which represents each run of the same character as a pair of "character (1 byte) and count (1 byte)". The original string uses 1 byte per character. Defining the compression ratio as "size after compression ÷ size before compression", which of the following is the compression ratio?