Golomb coding: Difference between revisions

Revision as of 13:53, 19 October 2022

Revision as of 05:48, 7 November 2022

Line 47:

== Simple algorithm ==

Note below that this is the Rice–Golomb encoding, where the remainder code uses simple truncated binary encoding, also named "Rice coding" (other varying-length binary encodings, like arithmetic or Huffman encodings, are possible for the remainder codes, if the statistic distribution of remainder codes is not flat, and notably when not all possible remainders after the division are used). In this algorithm, if the ''M'' parameter is a power of 2, it becomes equivalent to the simpler Rice encoding.:

# Fix the parameter ''M'' to an integer value.

Line 62:

#### If <math>r < 2^{b+1}-M</math> code ''r'' in binary representation using ''b'' bits.

#### If <math>r \ge 2^{b+1}-M</math> code the number <math>r+2^{b+1}-M</math> in binary representation using ''b'' + 1 bits.

Decoding:

# Decode the unary representation of ''q'' (count the number of 1 in the beginning of the code)

# Skip the 0 delimiter

# Let <math>b = \lfloor\log_2(M)\rfloor</math>

## Interpret next ''b'' bits as a binary number ''r'''. If <math>r' < 2^{b+1}-M</math> holds, then the reminder <math> r = r' </math>

## Otherwise interpret ''b + 1'' bits as a binary number ''r''', the reminder is given by <math>r = r' - 2^{b+1} + M</math>

# Compute <math>N = q * m + r</math>

== Example ==