English
Menu

What is Kraft inequality?

The inequality Σ 2^(−lᵢ) ≤ 1, the necessary and sufficient condition for a binary prefix code with code lengths l₁, l₂, …, lₙ to exist. It is easy to understand by noting that using one codeword of length l rules out every bit string that begins with it, taking up 2^(−l) of the whole. For example, lengths 1, 2, 3, 3 give a sum of exactly 1 and can be realized as 0, 10, 110, 111. Every uniquely decodable code satisfies this inequality (McMillan's theorem), so when choosing code lengths it is enough to look among prefix codes.

Japanese name: クラフトの不等式

Kraft inequality appears in 2 practice questions across 1 topic, including Information Theory and Coding Basics.

Field: Information Theory and Coding Basics

Try it: questions about Kraft inequality

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 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.

Kraft inequality in the explanations

Questions that mention Kraft inequality (2)

  1. 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?
  2. 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?

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Prefix code Average code length Binary symmetric channel Forward error correction (FEC) Hamming code Hamming distance Huffman coding Information entropy Lossless compression Lossy compression

Back to the glossary