Rice coding

Rice coding is a variant of Golomb coding where the parameter is a power of two. This makes it easier to encode the remainder of the euclidean division.

Implement Rice coding in your programming language and verify that you can consistently encode and decode a list of examples (for instance numbers from 0 to 10 or something).

Rice coding is initially meant to encode natural numbers, but since relative numbers are countable, it is fairly easy to modify Rice coding to encode them too. You can do that for extra credit.

Julia

""" Golomb-Rice encoding of a positive number to bit vector using M of 2^k"""
function rice_encode(n::Integer, k = 2)
    @assert n >= 0
    m = 2^k
    q, r = divrem(n, m)
    return [fill(true, q); false; Bool.(reverse(digits(r, base=2, pad=k+1)))]
end
""" see wikipedia.org/wiki/Golomb_coding#Use_with_signed_integers """
extended_rice_encode(n, k = 2) = rice_encode(n < 0 ? -2n - 1 : 2n, k)

""" Golomb-Rice decoding of a vector of bits with M of 2^k """
function rice_decode(a::Vector{Bool}, k = 2)
    m = 2^k
    zpos = something(findfirst(==(0), a), 1)
    r = evalpoly(2, reverse(a[zpos:end]))
    q = zpos - 1
    return q * m + r
end
extended_rice_decode(a, k = 2) = (i = rice_decode(a, k); isodd(i) ? -((i + 1) ÷ 2) : i ÷ 2)

println("Base Rice Coding:")
for n in 0:10
    println(n, " -> ", join(map(d -> d ? "1" : "0", rice_encode(n))), 
       " -> ", rice_decode(rice_encode(n)))
end
println("Extended Rice Coding:")
for n in -10:10
    println(n, " -> ", join(map(d -> d ? "1" : "0", extended_rice_encode(n))), 
       " -> ", extended_rice_decode(extended_rice_encode(n)))
end

Output:

Base Rice Coding:
0 -> 0000 -> 0
1 -> 0001 -> 1
2 -> 0010 -> 2
3 -> 0011 -> 3
4 -> 10000 -> 4
5 -> 10001 -> 5
6 -> 10010 -> 6
7 -> 10011 -> 7
8 -> 110000 -> 8
9 -> 110001 -> 9
10 -> 110010 -> 10
Extended Rice Coding:
-10 -> 11110011 -> -10
-9 -> 11110001 -> -9
-8 -> 1110011 -> -8
-7 -> 1110001 -> -7
-6 -> 110011 -> -6
-5 -> 110001 -> -5
-4 -> 10011 -> -4
-3 -> 10001 -> -3
-2 -> 0011 -> -2
-1 -> 0001 -> -1
0 -> 0000 -> 0
1 -> 0010 -> 1
2 -> 10000 -> 2
3 -> 10010 -> 3
4 -> 110000 -> 4
5 -> 110010 -> 5
6 -> 1110000 -> 6
7 -> 1110010 -> 7
8 -> 11110000 -> 8
9 -> 11110010 -> 9
10 -> 111110000 -> 10

raku

unit module Rice;

our sub encode(Int $n, UInt :$k = 2) {
  my $d = 2**$k;
  my $q = $n div $d;
  my $b = sign(1 + sign($q));
  my $m = abs($q) + $b;
  flat
    $b xx $m, 1 - $b,
    ($n mod $d).polymod(2 xx $k - 1).reverse
}

our sub decode(@bits is copy, UInt :$k = 2) {
  my $d = 2**$k;
  my $b = @bits.shift;
  my $m = 1;
  $m++ while @bits and @bits.shift == $b;
  my $q = $b ?? $m - 1 !! -$m;
  $q*$d + @bits.reduce(2 * * + *);
}

CHECK {
  use Test;
  constant N = 100;
  plan 2*N + 1;
  is $_, decode encode $_ for -N..N;
}