Databases Reference
In-Depth Information
T A B L E 3 . 22
Golomb code for
m
=5.
nqr
Codeword
nqr
Codeword
0
0
0
0000
08
1
3
101100
1
0
1
0010
09
1
4
101110
2
0
2
0100
10
2
0
110000
3
0
3
0110
11
2
1
110010
4
0
4
0111
12
2
2
110100
5
1
0
1000
13
2
3
110110
6
1
1
1001
14
2
4
110111
7
1
2
1010
15
3
0
111000
is the integer part of
x
. In other words,
q
is the quotient and
r
is the remainder when
n
is
divided by
m
. The quotient
q
can take on values 0
x
,
1
,
2
,...
and is represented by the unary
code of
q
. The remainder
r
can take on the values 0
If
m
is a power of two,
we use the log
2
m
-bit binary representation of
r
.If
m
is not a power of two, we could still
use
,
1
,
2
,...,
m
−
1
.
is the smallest integer greater than or equal to
x
. We can reduce
the number of bits required if we use the
log
2
m
bits, where
x
log
2
m
-bit binary representation of
r
for the first
2
log
2
m
−
2
log
2
m
−
+
m
values, and the
log
2
m
-bit binary representation of
r
m
for the
rest of the values.
Examp l e 3 . 5 . 1 : Golomb Code
Let's design a Golomb code for
m
=
5. As
log
2
5
=
3 and
log
2
5
=
2
the first 8
0, 1, 2) will be represented by the 2-bit binary
representation of
r
, and the next two values (that is,
r
−
5
=
3 values of
r
(that is,
r
=
=
3, 4) will be represented by the 3-bit
representation of
r
3. The quotient
q
is always represented by the unary code for
q
. Thus,
the codeword for 3 is 0110, and the codeword for 21 is 1111001. The codewords for
n
+
=
0,
…, 15 are shown in Table
3.22
.
It can be shown that the Golomb code is optimal for the probability model
p
n
−
1
q
P
(
n
)
=
,
q
=
1
−
p
when
1
log
2
p
m
=
−
.
3.6 Rice Codes
The Rice code was originally developed by Robert F. Rice (he called it the Rice machine)
[
28
,
29
] and later extended by Pen-Shu Yeh and Warner Miller [
30
]. The Rice code can be
