Truncated binary encodingTruncated binary encoding
is an entropy encoding
typically used for uniform probability distributions
with a finite alphabet. It is parameterized by a maximum number n
. It is slightly more general than binary encoding
which is only optimal where n
is a power of two.
For example, if n is 4, binary encoding allocates these codewords:
Instead, truncated binary allocates:
You can think of this as allocating an UNUSED to the first few symbols (until you run out of UNUSEDs), to make the first few symbols' codewords shorter.