Truncated Binary Encoding - Example With n = 5

Example With n = 5

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 the following codewords. Digits shown struck are not transmitted in truncated binary.

The nearest power of 2 after n = 5 is 2³ = 8, so there are u = 8−5 = 3 unused codes in the straightforward 3-bit binary encoding.

In numerical terms, to send a value 0 ≤ x < n, which is one of 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.