English
Menu

What is Average code length?

The average of the codeword lengths of the symbols, weighted by the probability that each symbol occurs. With pᵢ the probability of symbol i and lᵢ the length of its codeword, it is L = Σ pᵢ lᵢ (bits per symbol). Assigning short codewords to frequent symbols makes it small, and for a lossless code it is at least the entropy. The entropy divided by the average code length is called the coding efficiency. For example, coding four symbols of probabilities 0.4, 0.3, 0.2 and 0.1 with a Huffman code gives an average code length of 1.9 bits.

Japanese name: 平均符号長

Average code length appears in 6 practice questions across 1 topic, including Information Theory and Coding Basics.

Field: Information Theory and Coding Basics

Try it: questions about Average code length

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

  1. A2.25 bits
  2. B2.4 bits
  3. C3 bits
Show answer and explanation

Answer: A. 2.25 bits

First 0.1 and 0.15 are merged into 0.25, then 0.2 and 0.25 into 0.45, the remaining 0.25 and 0.3 into 0.55, and finally 0.45 and 0.55. The code lengths are 2 bits for A, B and C and 3 bits for D and E, and the average code length is (0.3 + 0.25 + 0.2) × 2 + (0.15 + 0.1) × 3 = 1.5 + 0.75 = 2.25 bits. For a source whose probabilities are not strongly skewed, a code with nearly equal lengths is shorter than one with stepped lengths such as 1, 2, 3, 4, 4.

Average code length in the explanations

Questions that mention Average code length (6)

  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 a variable-length code compared with a fixed-length code?
  6. Which of the following correctly describes the relationship between lossless compression and the entropy of a source?

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

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

Back to the glossary