English
Menu

Information Theory and Coding Basics

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?

  1. AAbout 65%
  2. B70%
  3. CAbout 93%
Show answer and explanation

Answer: C. About 93%

The Huffman code merges 0.1 and 0.3 into 0.4 and then 0.4 and 0.6, so the code lengths are 1 bit for A and 2 bits for B and C. The average code length is 0.6 × 1 + 0.3 × 2 + 0.1 × 2 = 1.4 bits, and the efficiency is 1.30 ÷ 1.4 ≈ 0.93, that is, about 93%. The remaining 7% or so is waste that arises because code lengths are limited to whole numbers of bits.

  • A. About 65% is 1.30 ÷ 2, the efficiency when the three symbols are represented with a 2-bit fixed-length code.
  • B. 70% is 1.4 ÷ 2, the ratio of the average code length to that of the fixed-length code. It is not the efficiency.
  • C. Correct. 1.30 ÷ 1.4 ≈ 93%.
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 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?
  2. Which of the following correctly describes the relationship between lossless compression and the entropy of a source?
  3. 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?
  4. Which of the following data is most likely to be made smallest by run-length encoding?
  5. Which of the following correctly describes the idea of the LZ77 method used in ZIP, gzip and similar tools?