Golomb coding

The Golomb code is a entropy for all non-negative integers, which can represent only a finite range (eg, the value range 0-255) in contrast to other codes in the source code. It was developed in 1966 by Solomon W. Golomb. The code uses a few bits for small and many bits for larger numbers. In this case, it can be controlled by a positive integer parameters. The larger the parameter, the slower growing, the number of bits required for the representation, but the greater is the number of minimum bits required for the small numbers.

Rice code is a variant of the Golomb codes, in which the control parameter is a power of two. This limitation is advantageous since in particular in the digital processing, the Mulitiplikation or division by 2 can be implemented very efficiently. The Rice code was introduced in 1971 by Robert F. Rice and J. Plaunt.

The code can be used in the field of lossless data compression if the probabilities of the source data to be encoded ( approximate ) form a geometric distribution. Typical applications are, as a part of process in addition to other algorithms, the image compression and audio data compression.

Operation

The code works with the idea of ​​replacing the number to be represented by a quotient and the remainder in a division with a parameter.

The number associated with is

And

Described. For a better description, it is the number

Needed. First, q 1 is output unary, ie it will be "1" bits followed by "0" is stored.

The remainder is then in a " truncated binary representation " ( Truncated Binary Encoding) filed said encoding. This representation specifies a part of the values ​​, if possible, bits and the other part with bits from. The number of values ​​that can be stored with bits.

Examples

The representation of the number 10 with a parameter 4:

Depending on the encoding is completed:

• If < is, is written as a binary code of length.

• If ≥ is, is written as a binary code of length.

This results in the bit sequence " 110 10". The space shows the transition from rest to the quotient

A few more examples:

Application

The Golomb code can be used when numbers of unknown size to be stored, but the actual field of application is in data compression.

If the probability of numbers having a predetermined distribution ( geometric distribution ), then the Golomb code can similarly efficient as the Huffman code may be, but is more economical to store, easier to implement and quickly to perform.

Rice Code

Rice code is a variant of the Golomb codes, in which the parameter is a power of 2. These codes are very easy to implement with Bitshiften and logical bit operations.

Assuming it applies. Then

And

The symbol stands for bitwise right shift and bitwise AND operation. is always with just bits and displayed normal binary.