Example With n = 10
Another example, encoding an alphabet of size 10 (between 0 and 9) requires k=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.)
Input value |
Offset | Offset value |
Standard Binary |
Truncated Binary |
---|---|---|---|---|
0 | 0 | 0 | 000 | |
1 | 0 | 1 | 001 | |
2 | 0 | 2 | 010 | |
3 | 0 | 3 | 011 | |
4 | 0 | 4 | 100 | |
5 | 0 | 5 | 101 | |
6 | 6 | 12 | 1100 | 1100 |
7 | 6 | 13 | 1101 | 1101 |
8 | 6 | 14 | 1110 | 1110 |
9 | 6 | 15 | 1111 | 1111 |
To decode, read the first k bits. If they encode a value less than u, decoding is complete. Otherwise, add an additional bit and subtract u from the result.
Read more about this topic: Truncated Binary Encoding