Notices
Results 1 to 1 of 1

Thread: The Golomb-Rice algorithm

  1. #1 The Golomb-Rice algorithm 
    Suspended
    Join Date
    Jan 2009
    Posts
    2
    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


    Reply With Quote  
     

  2.  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •