Rice Coding

Named after Robert Rice, Rice coding is a specialised form of Golomb coding. It's used to encode strings of numbers with a variable bit length for each number. If most of the numbers are small, fairly good compression can be achieved. Rice coding is generally used to encode entropy in an audio/video codec.

Rice coding depends on a parameter k and works the same as Golomb coding with a parameter m where m = 2k. To encode a number, x:

  1. Let q = x / m (round fractions down)
    Write out q binary ones.
  2. Write out a binary zero.
    (Some people prefer to do it the other way - zeroes followed by a one)
  3. Write out the last k bits of x

Decoding works the same way, just backwards. You can see my implementation here:

encode.c
decode.c

The encoder calculates the output length of a Rice coding using all values of k between 0 and 7, then encodes the input data using the k value that will create the shortest compressed file.

In general, a lower value of k will make smaller numbers cheaper and bigger numbers more expensive to store, while a bigger value of k will make big numbers relatively cheap to store, while increasing the storage overhead on all smaller values and making them more expensive to store. For example:

x k = 1 k = 4
0 0 00000
1 10 00001
2 110 00010
3 1110 00011
4 11110 00100
5 111110 00101
6 1111110 00110
7 11111110 00111
8 111111110 01000
9 1111111110 01001
10 11111111110 01010
11 111111111110 01011
12 1111111111110 01100
13 11111111111110 01101
14 111111111111110 01110
15 1111111111111110 01111
16 11111111111111110 100000
17 111111111111111110 100001

References

http://www.firstpr.com.au/audiocomp/lossless/


Valid XHTML 1.1
copyright © 2004 Emil Mikulic
$Date: 2006/04/22 07:06:40 $