Truncated binary encoding

Truncated binary encoding is an entropy encoding typically used for uniform probability distributions with a finite alphabet. It is parameterized by an alphabet with total size of number "n". It is a slightly more general form of binary encoding when "n" is not a power of two.

When "n" is exactly 2^"k", truncated binary encoding simply assigns each symbol one of the "n" codewords of length "k". When "n" is equal instead to 2^"k"+"b", truncated binary encoding assigns the first 2^"k"−"b" symbols the first 2^"k"−"b" codewords of length "k" and then assigns the remaining 2"b" symbols the last 2"b" codewords of length "k"+1. Because all the codewords of length "k"+1 consist of an unassigned codeword of length "k" with a "0" or "1" appended, the resulting code is a prefix code. For example, for the alphabet {0, 1, 2, 3, 4}, "n" = 5 = 2²+1. Truncated binary encoding assigns the first three symbols (2²−1) the codewords 00, 01, and 10, all of length 2, then assigns the last two symbols the codewords 110 and 111, the last two codewords of length 3, each of which is the unused two-bit codeword 11 with an extra digit appended.

For example, if "n" is 5, plain binary encoding and truncated binary encoding allocates these codewords: (struck digits/bits are not transmitted in truncated binary.)

This last example demonstrates that a leading zero bit does not always indicate a short code; if "u" < 2^"k"−1, some long codes will begin with a zero bit.

If "n" is a power of two, then the encoding may be done with either of two different values of "k". Both produce equivalent outputs; one just has "u" = 2^"k" and encodes all values as "short" "k"-bit codes, while the other has "u" = 0 and encodes everything with "long" "k"+1-bit codes.