I don't understand the Golomb-Rice algorithm. I found a few resources on it such as

http://en.wikipedia.org/wiki/Golomb_coding

and while I understand that "M" or the divisor is a tunable parameter I don't understand why it is chosen to be what it is. Also I don't understand why for example with a divisor of 4 and the numbers 8 to 15 the number of digits needed for coding is more than the number of binary digits needed to encode 15 i.e. 2^4 - 1 = 15 so we could do it in 4 bits where as the value 8 uses 5 bits in the Golomb-Rice encoding. So how is this an overall reduction in the amount of information needed to represent a given number?

Value, Quotient, Remainder, Code

0 0 0 100

1 0 1 101

2 0 2 110

3 0 3 111

4 1 0 0100

5 1 1 0101

6 1 2 0110

7 1 3 0111

8 2 0 0000

9 2 1 00101

10 2 2 00110

11 2 3 00111

12 3 0 000100

13 3 1 000101

14 3 2 000110

15 3 3 000111

Furthermore, in the Wikipedia article above there is the sentence:

Formally, the two parts are given by the following expression, where x is the number being encoded: q = floor((x-1)/M) and r = x − qM − 1 The final result looks like: (q+1)*r where q is the quotient, r is the remainder, x is the number to be encoded, and M is the tunable Golomb-Rice parameter. I do not understand how (q+1)*r is the final result... What does this mean???

I understand the idea of probability encoding but don't really see how this fits in to the above scenario of numbers especially since 3 quarters of the numbers being encoded come out to be as long or longer than the number of bits needed to represent 15, (which is 4) and the average number of bits used for the 16 numbers above is 4.5, ((3*4 + 4*4 + 5*4 + 6*4)/16), which is higher than the 4 needed to encode 0-15.

Can anyone break this down for me?

Thank you,

Brian