Golomb Coding - Simple Algorithm

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.

1. Fix the parameter M to an integer value.
2. For N, the number to be encoded, find
   1. quotient = q = int
   2. remainder = r = N modulo M
3. Generate Codeword
   1. The Code format : , where
   2. Quotient Code (in unary coding)
      1. Write a q-length string of 1 bits
      2. Write a 0 bit
   3. Remainder Code (in truncated binary encoding)
      1. If M is power of 2, code remainder as binary format. So bits are needed. (Rice code)
      2. If M is not a power of 2, set
         1. If code r as plain binary using b-1 bits.
         2. If code the number in plain binary representation using b bits.