Databases Reference
In-Depth Information
viewed as an adaptive Golomb code. In the Rice code, a sequence of nonnegative integers
(which might have been obtained from the preprocessing of other data) is divided into blocks
of
J
integers apiece. Each block is then coded using one of several options, most of which are
a form of Golomb codes. Each block is encoded with each of these options, and the option
resulting in the least number of coded bits is selected. The particular option used is indicated
by an identifier attached to the code for each block.
The easiest way to understand the Rice code is to examine one of its implementations. We
will study the implementation of the Rice code in the recommendation for lossless compression
from the Consultative Committee on Space Data Standards (CCSDS).
3.6.1 CCSDS Recommendation for Lossless
Compression
As an application of the Rice algorithm, let's briefly look at the algorithm for lossless data
compression recommended by CCSDS. The algorithm consists of a preprocessor (modeling
step) and a binary coder (coding step). The preprocessor removes correlation from the input
and generates a sequence of nonnegative integers. This sequence has the property that smaller
values aremore probable than larger values. The binary coder generates a bitstream to represent
the integer sequence. The binary coder is our main focus at this point.
The preprocessor functions as follows: given a sequence
{
y
i
}
, for each
y
i
we generate a
prediction
y
i
. A simple way to generate a prediction would be to take the previous value of
the sequence to be a prediction of the current value of the sequence:
ˆ
y
i
−
1
We will look at more sophisticated ways of generating a prediction in Chapter 7. We then
generate a sequence whose elements are the difference between
y
i
and its predicted value
ˆ
y
i
=
ˆ
y
i
:
y
i
The
d
i
value will have a small magnitude when our prediction is good and a large value when
it is not. Assuming an accurate modeling of the data, the former situation is more likely than
the latter. Let
y
max
and
y
min
be the largest and smallest values that the sequence
d
i
=
y
i
−ˆ
{
y
i
}
takes on.
It is reasonable to assume that the value of
y
i
will be confined to the range
ˆ
[
y
min
,
y
max
]
. Define
T
i
=
min
{
y
max
−ˆ
y
i
,
ˆ
y
i
−
y
min
}
(8)
The sequence
{
d
i
}
can be converted into a sequence of nonnegative integers
{
x
i
}
using the
following mapping:
⎧
⎨
2
d
i
0
d
i
T
i
=
2
|
d
i
| −
1
−
T
i
d
i
<
0
(9)
x
i
⎩
T
i
+ |
d
i
|
other
w
ise
The value of
x
i
will be small whenever the magnitude of
d
i
is small. Therefore, the value of
x
i
will be small with higher probability. The sequence
is divided into segments with each
segment being further divided into blocks of size
J
. It is recommended by CCSDS that
J
have
a value of 16. Each block is then coded using one of the following options. The coded block
is transmitted along with an identifier that indicates which particular option was used.
{
x
i
}
