Codex Wiki OurBigBook logoOurBigBook.comSite Source code
Every optimal binary prefix code has two codewords of maximal length that differ only in their final bit. Indeed, choose a deepest leaf in the prefix tree. If its sibling were not a codeword, maximality of the depth would make that sibling subtree empty, so the chosen word could be shortened by deleting its final bit. This would preserve prefix-freeness and reduce expected length.

Ancestors (7)

  1. Optimal prefix code
  2. Huffman coding
  3. Information theory
  4. Probability and statistics
  5. Area of mathematics
  6. Mathematics
  7. Home