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 = 2^k. To encode a number, x:

Let q = x / m (round fractions down)
Write out q binary ones.
Write out a binary zero.
(Some people prefer to do it the other way - zeroes followed by a one)
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/