Golomb code

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

The Rice Code is a variant of the Golomb Code in which the control parameter is a power of two . This restriction is advantageous since the multiplication or division of 2 can be implemented very efficiently, particularly in digital processing. 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 coded (approximately) form a geometric distribution . Typical areas of application are image compression and audio data compression as a sub-method alongside other algorithms .

Working method

The code works with the idea of replacing the number to be displayed with a quotient and the remainder in the case of division with a parameter . ${\ displaystyle n}$ ${\ displaystyle q}$ ${\ displaystyle r}$ ${\ displaystyle b}$

The number with is through ${\ displaystyle n}$ ${\ displaystyle n \ geq 0}$

{\ displaystyle q = \ left \ lfloor {\ frac {n} {b}} \ right \ rfloor}

and

{\ displaystyle r = n-qb \,}

described. The number is added for a better description

{\ displaystyle c = \ left \ lceil \ log _ {2} b \ right \ rceil}

needed. First q + 1 is output unary , i.e. H. will be "1" bits followed by a "0" stored. ${\ displaystyle q}$

The rest is then stored in an encoding called “truncated binary encoding ”. This representation stores some of the values, if possible, with bits and the other part with bits. The number of values that can be stored with bits is . ${\ displaystyle c-1}$ ${\ displaystyle c}$ ${\ displaystyle c-1}$ ${\ displaystyle 2 ^ {c} -b}$

Examples

The representation of the number 10 with a parameter 4:

{\ displaystyle q = \ left \ lfloor {\ frac {10} {4}} \ right \ rfloor = 2}

{\ displaystyle r = 10-2 \ cdot 4 = 2}

{\ displaystyle c = \ left \ lceil \ log _ {2} 4 \ right \ rceil = 2}

The coding is completed depending on : ${\ displaystyle c}$

if < is written as a binary code with the length . ${\ displaystyle r}$ ${\ displaystyle 2 ^ {c} -b}$ ${\ displaystyle r}$ ${\ displaystyle c-1}$
if ≥ is written as a binary code with the length . ${\ displaystyle r}$ ${\ displaystyle 2 ^ {c} -b}$ ${\ displaystyle r + 2 ^ {c} -b}$ ${\ displaystyle c}$

The bit sequence results from this 110 10. The space shows the transition from the quotient to the remainder.

A few more examples:

n	0	1	2	3	4th	5	6th	7th	8th	9	10
b = 3	0 0	0 10	0 11	10 0	10 10	10 11	110 0	110 10	110 11	1110 0	1110 10
b = 4	0 00	0 01	0 10	0 11	10 00	10 01	10 10	10 11	110 00	110 01	110 10
b = 5	0 00	0 01	0 10	0 110	0 111	10 00	10 01	10 10	10 110	10 111	110 00
b = 7	0 00	0 010	0 011	0 100	0 101	0 110	0 111	10 00	10 010	10 011	10 100

application

The two graphs show the redundancy of the Golomb code per symbol. The probability of occurrence of the more frequent symbol can be read on the abscissa.

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

If the probabilities of the numbers have a certain distribution ( geometric distribution ), then the Golomb code can be as efficient as the Huffman code , but is more economical with memory, easier to implement and faster to run.

Rice code

The Rice Code is a variant of the Golomb Code where the parameter is a power of 2. These codes can be implemented very easily with bit shifting and logical bit operations. ${\ displaystyle b}$

Suppose it holds . Then ${\ displaystyle b = 2 ^ {p}}$

{\ displaystyle q = n \ gg p}

and

{\ displaystyle r = n \ land (b-1)}

The symbol stands for bit-wise shifting to the right and for bit-wise AND operation. is always represented with exactly bits and normal binary. ${\ displaystyle \ gg}$ ${\ displaystyle \ land}$ ${\ displaystyle r}$ ${\ displaystyle p}$

Individual evidence

↑ Solomon W. Golomb: Run-Length Encodings. In: IEEE Transactions on Information Theory IT-12 (3). 1966, pp. 399-401 , accessed April 19, 2013 .
^ Robert F. Rice, J. Plaunt: Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data . Ed .: IEEE Transactions on Communication Technology. tape 19 , no. 6 . California Institute of Technology, Pasadena 1971, p. 889-897 , doi : 10.1109 / TCOM.1971.1090789 .

[golomb1-1] Solomon W. Golomb: Run-Length Encodings. In: IEEE Transactions on Information Theory IT-12 (3). 1966, pp. 399-401 , accessed April 19, 2013 .

[rice1-2] Robert F. Rice, J. Plaunt: Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data . Ed .: IEEE Transactions on Communication Technology. tape 19 , no. 6 . California Institute of Technology, Pasadena 1971, p. 889-897 , doi : 10.1109 / TCOM.1971.1090789 .