Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Truncated binary encoding
open-in-new
<p>Truncated binary encoding is an <a href="/facts/Entropy_encoding/44I0n8F8">entropy encoding</a> typically used for uniform <a href="/facts/Probability_distribution/EpsKKVRu">probability distributions</a> with a finite alphabet. It is parameterized by an alphabet with total size of number <i>n</i>. It is a slightly more general form of <a href="/facts/Binary_numeral_system/a6JDSRPs">binary encoding</a> when <i>n</i> is not a <a href="/facts/Power_of_two/MA6WEpTt">power of two</a>. </p><p>If <i>n</i> is a power of two, then the coded value for 0 ≤ <i>x</i> < <i>n</i> is the simple binary code for <i>x</i> of length log2(<i>n</i>). Otherwise let <i>k</i> = floor(log2(<i>n</i>)), such that 2<i>k</i> < <i>n</i> < 2<i>k</i>+1and let <i>u</i> = 2<i>k</i>+1 − <i>n</i>. </p><p>Truncated binary encoding assigns the first <i>u</i> symbols codewords of length <i>k</i> and then assigns the remaining <i>n</i> − <i>u</i> symbols the last <i>n</i> − <i>u</i> codewords of length <i>k</i> + 1. Because all the codewords of length <i>k</i> + 1 consist of an unassigned codeword of length <i>k</i> with a "0" or "1" appended, the resulting code is a <a href="/facts/Prefix_code/461neBYx">prefix code</a>. </p>