English
Menu

Information Theory and Coding Basics

A binary prefix code is to be built by assigning codewords of the following lengths (numbers of bits) to the four symbols A to D. Which of the following sets of code lengths makes this possible?

  1. AA: 1, B: 2, C: 3, D: 3
  2. BA: 1, B: 2, C: 2, D: 3
  3. CA: 1, B: 1, C: 2, D: 3
Show answer and explanation

Answer: A. A: 1, B: 2, C: 3, D: 3

A prefix code with code lengths l₁, l₂, … can be built exactly when the Kraft inequality Σ 2^(−lᵢ) ≤ 1 holds. For 1, 2, 3, 3 the sum is 1/2 + 1/4 + 1/8 + 1/8 = 1, so it can be built, for example as 0, 10, 110, 111. For 1, 2, 2, 3 the sum is 1/2 + 1/4 + 1/4 + 1/8 = 9/8, and for 1, 1, 2, 3 it is 1/2 + 1/2 + 1/4 + 1/8 = 11/8; both exceed 1, so neither can be built.

  • A. Correct. The sum of 2^(−l) is exactly 1, and the code can be built as 0, 10, 110, 111.
  • B. The sum is 9/8, which exceeds 1. The length-1 word 0 and the length-2 words 10 and 11 use up every way a bit string can begin, leaving no room for a length-3 codeword.
  • C. The sum is 11/8, which exceeds 1. If both 0 and 1 are used as length-1 codewords, every other codeword must begin with one of them.
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 prefix code is being built, and the length-2 codewords 00 and 01 are already in use. Which of the following is the maximum number of length-3 codewords that can be added while keeping the prefix condition?
  2. 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?
  3. 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?
  4. 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?
  5. 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?