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. 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. History Used since at least 1984, phase-in codes, also known as economy codes, are also known as truncated binary encoding. Example with n = 5 For example, for the alphabet {0, 1, 2, 3, 4}, n = 5 and 22 ≤ n < 23, hence