Editing Truncated binary encoding (section)

{{More references|date=December 2009}}

'''Truncated binary encoding''' is an [[entropy encoding]] typically used for uniform [[probability distribution]]s 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 numeral system|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 log<sub>2</sub>(''n''). Otherwise let ''k'' = floor(log<sub>2</sub>(''n'')), such that 2<sup>''k''</sup> < ''n'' < 2<sup>''k''+1</sup>and let ''u'' = 2<sup>''k''+1</sup> − ''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]].