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.
If n is a power of two then the coded value for 0 ≤ x < n is the simple binary code for x of length log2(n). Otherwise let k = floor( log2(n) ) such that 2k < n < 2k+1 and let u = 2k+1 - n.
Truncated binary encoding assigns the first u symbols codewords of length k and then assigns the remaining n - u symbols the last n - u 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 and 22 ≤ n < 23, hence k = 2 and u = 23 - 5 = 3. Truncated binary encoding assigns the first u symbols the codewords 00, 01, and 10, all of length 2, then assigns the last n - u symbols the codewords 110 and 111, the last two codewords of length 3.
For example, if n is 5, plain binary encoding and truncated binary encoding allocates the following codewords. Digits shown struck are not transmitted in truncated binary.
It takes 3 bits to encode n using straightforward binary encoding, hence 23 - n = 8 - 5 = 3 are unused.
In numerical terms, to send a value x where 0 ≤ x < n, and where there are 2k ≤ n < 2k+1 symbols, there are u = 2k + 1 − n unused entries when the alphabet size is rounded up to the nearest power of two. The process to encode the number x in truncated binary is: If x is less than u, encode it in k binary bits. If x is greater than or equal to u, encode the value x + u in k + 1 binary bits.
Another example, encoding an alphabet of size 10 (between 0 and 9) requires 4 bits, but there are 24 − 10 = 6 unused codes, so input values less than 6 have the first bit discarded, while input values greater than or equal to 6 are offset by 6 to the end of the binary space. (Unused patterns are not shown in this table.)