Truncated binary encoding

Contents
On efficiency
See also
References

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 2 < n < 2and let u = 2 − 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.

stringBinary(intx,intlen) { strings=""; while(x!=0){ if(even(x)) s='0'+s; elses='1'+s; x>>=1; } while(s.Length<len) s='0'+s; returns; }

On efficiency

edit

If n is not a power of two, and k-bit symbols are observed with probability p, then (k + 1)-bit symbols are observed with probability 1 − p. We can calculate the expected number of bits per symbol bu=k+1 bits. Then relative space saving s (see Data compression ratio) of the encoding can be defined as

bu decreases.

References

edit

View original on Wikipedia | Back | FazBrowse Home

On efficiency

See also

References