English
Menu

Information Theory and Coding Basics

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?

  1. A4
  2. B6
  3. C8
Show answer and explanation

Answer: A. 4

There are 2³ = 8 bit strings of length 3, but the four that begin with 00 or 01 (000, 001, 010 and 011) cannot be used. The remaining four, 100, 101, 110 and 111, are not in a prefix relation with either 00 or 01, so all of them can be added. The Kraft inequality gives the same result: 2/4 + n/8 ≤ 1, so n ≤ 4.

  • A. Correct. The four length-3 bit strings that begin with 1 can be used.
  • B. 6 is the 8 length-3 bit strings minus the number of codewords used, 2. But 00 and 01 are each the beginning of two length-3 bit strings, so four cannot be used.
  • C. 8 is every length-3 bit string, including those that begin with 00 or 01.
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, 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?
  2. 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?
  3. 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?
  4. 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?
  5. Which of the following correctly describes the relationship between lossless compression and the entropy of a source?