Truncated binary encoding

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.

When "n" is exactly 2"k", truncated binary encoding simply assigns each symbol one of the "n" codewords of length "k". When "n" is equal instead to 2"k"+"b", truncated binary encoding assigns the first 2"k"−"b" symbols the first 2"k"−"b" codewords of length "k" and then assigns the remaining 2"b" symbols the last 2"b" 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. For example, for the alphabet {0, 1, 2, 3, 4}, "n" = 5 = 2²+1. Truncated binary encoding assigns the first three symbols (2²−1) the codewords 00, 01, and 10, all of length 2, then assigns the last two symbols the codewords 110 and 111, the last two codewords of length 3, each of which is the unused two-bit codeword 11 with an extra digit appended.

For example, if "n" is 5, plain binary encoding and truncated binary encoding allocates these codewords: (struck digits/bits are not transmitted in truncated binary.)

This last example demonstrates that a leading zero bit does not always indicate a short code; if "u" < 2"k"−1, some long codes will begin with a zero bit.

If "n" is a power of two, then the encoding may be done with either of two different values of "k". Both produce equivalent outputs; one just has "u" = 2"k" and encodes all values as "short" "k"-bit codes, while the other has "u" = 0 and encodes everything with "long" "k"+1-bit codes.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Golomb coding — is a data compression scheme invented by Solomon W. Golomb in the 1960s. The scheme is based on entropy encoding and is optimal (in the sense of Shannon s source coding theorem) for alphabets following a geometric distribution, making it highly… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Golomb-Code — Der Golomb Code ist eine Darstellungsform für alle nichtnegativen ganzen Zahlen, im Gegensatz zu anderen Codes, die nur einen endlichen Bereich (z. B. 0 255) darstellen können. Er wurde 1966 von Solomon W. Golomb vorgestellt. Der Code… …   Deutsch Wikipedia

  • Hash function — A hash function is any well defined procedure or mathematical function for turning some kind of data into a relatively small integer, that may serve as an index into an array. The values returned by a hash function are called hash values, hash… …   Wikipedia

  • Serialization — This article is about data structure encoding. For other uses, see Serialization (disambiguation). In computer science, in the context of data storage and transmission, serialization is the process of converting a data structure or object state… …   Wikipedia

  • Floating point — In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent …   Wikipedia

  • Comparison of analog and digital recording — This article compares the two ways in which sound is recorded and stored. Actual sound waves consist of continuous variations in air pressure. Representations of these signals can be recorded using either digital or analog techniques. An analog… …   Wikipedia

  • GS1 DataBar — GS1 US has filed a DMCA Infringement notice with Wikipedia’s designated agent on November 2, 2011 GS1 DataBar barcode symbol encoding a GTIN 12 number. GS1 DataBar Stacked Omni Directional barcode symbol encoding 001234567890 …   Wikipedia

  • Pi — This article is about the number. For the Greek letter, see Pi (letter). For other uses, see Pi (disambiguation). The circumference of a ci …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”