Contents

1 Basics

• When the probabilities of the symbols follow an exponential distribution, the Golomg encoder [1] has the same efficiency than the Huffman coding, but it is faster. In this case, the probabilities of the symbols shoud be

  $$p\left(s\right)=2^{-\left(\right.m⌊\frac{s+m}{m}⌋\left)\right.}$$

  (Eq:Golomb)

  where $s=0,1,\cdots$ is the symbol and $m=0,1,\cdots$ is the “Golomb slope” of the distribution.

• If $m=2^k$, it is possible to find a very efficient implementation and the encoder is also named Rice encoder [2]. In this case

  $$p\left(s\right)=2^{-\left(\right.2^k⌊\frac{s+2^k}{2^k}⌋\left)\right.}$$

  (Eq:Rice)

• Notice that for $m=1$, we take the unary encoding.
• The following distribution is for $m=2$:

2 Golomb Encoder

1. $k\leftarrow \lceil {log}_2\left(m\right)\rceil$.
2. $r\leftarrow s\mathrm{mod}m$.
3. $t\leftarrow 2^k-m$.
4. Output $\lfloor s∕m\rfloor$ using an unary code. /* Most significant bits */
5. If $r<t$:
   1. Output the integer encoded in the $k-1$ least significant bits of $r$ using a binary code. /* Least significant bits */
6. Else:
   1. $r\leftarrow r+t$.
   2. Output the integer encoded in the $k$ least significant bits of $r$ using a binary code.

2.1 Example ($m=7$ and $s=8$)

1. [1] $k\leftarrow \lceil {log}_2\left(8\right)\rceil =3$.
2. [2] $r\leftarrow 8\text{mod}7=1$.
3. [3] $t\leftarrow 2^3-7=8-7=1$.
4. [4] Output $\leftarrow \lfloor 8∕7\rfloor =1$ as an unary code (2 bits). Therefore, output $\leftarrow 10$.
5. [5] $r=1\le t=1$.
6. [6.A] $r\leftarrow 1+1=2$.
7. [6.B] Output $r=2$ using a binary code of $k=3$ bits. Therefore, $c\left(8\right)=10010$.

3 Golomb Decoder

1. $k\leftarrow \lceil {log}_2\left(m\right)\rceil$.
2. $t\leftarrow 2^k-m$.
3. Let $s\leftarrow$ the number of consecutive ones in the input (we stop when we read a $0$).
4. Let $x\leftarrow$ the next $k-1$ bits in the input.
5. If $x<t$:
   1. $s\leftarrow s\times m+x$.
6. Else:
   1. $x\leftarrow x\times 2+$ next input bit.
   2. $s\leftarrow s\times m+x-t$.

3.1 Example (decode 10010 for $m=7$)

1. [1] $k\leftarrow 3$.
2. [2] $t\leftarrow 2^k-m=2^3-7=1$).
3. [3] $s\leftarrow 1$ because we found only one $1$ in the input.
4. [4] $x\leftarrow {\text{input}}_{k-1}={\text{input}}_2=01$.
5. [5] $x=1\nless t=1$.
6. [6.A] $x\leftarrow x\times x\times 2+\text{next input bit}=x\times 1\times 2+0=2$.
7. [6.B] $s\leftarrow s\times m+x-t=1\times 7+2-1=8$.

3.2 Lab

TO-DO

4 Rice Encoder

1. $m\leftarrow 2^k$.
2. Output $\leftarrow \lfloor s∕m\rfloor$ using an unary code ($\lfloor s∕m\rfloor +1$ bits).
3. Output $\leftarrow$ the $k$ least significant bits of $s$.

4.1 Example ($k=1$ and $s=7$)

1. [1] $m\leftarrow 2^k=2^1=2$.
2. [2] Output $\leftarrow \lfloor s∕m\rfloor =\lfloor 7∕2\rfloor =3$ using an unary code of 4 bits. Therefore, output $\leftarrow 1110$.
3. Output $\leftarrow$ the $k=1$ least significant bits of $s=7$. So, output $\leftarrow 1$. Total output $c\left(7\right)=11101$.

5 Rice Decoder

1. Let $s$ the number of consecutive ones in the input (we stop when we read a 0).
2. Let $x$ the next $k$ input bits.
3. $s\leftarrow s\times 2^k+x$.

5.0.1 Example (decode 11101 for $k=1$)

1. [1] $s\leftarrow 3$ because we found $3$ consecutive ones in the input.
2. [2] $x\leftarrow$ next input $k=1$ input bits. Therefore $x\leftarrow 1$.
3. [3] $s\leftarrow s\times 2^k+x=3\times 2^1+1=6+1=7$.

5.1 Lab

TO-DO

References