3.8. JPEG-LS
Метод сжатия JPEG-LS использует коды Голомба, поэтому мы дадим краткое описание этих мало известных кодов.
3.8.1. Коды Голомба
Код Голомба неотрицательного целого числа
[Golomb 66] может быть эффективным кодом Хаффмана. Этот код зависит от выбора некоторого параметра
. Прежде всего необходимо вычислить две величины
,
(где выражение
обозначает округление
), а затем построить код из двух частей; первая часть - это число
, закодированное с помощью унарного кода (см. стр. 195), а вторая - двоичное выражение для
, состоящее из
бит (для малых остатков) или из
бит (для больших). Если взять
, то три возможных остатка 0, 1 и 2 будут кодироваться как 0, 10 и 11. Выбрав
, получаем 5 остатков от 0 до 4, которые кодируются как 00, 01, 100, 101 и 110. В табл. 3.60 приведены некоторые коды Голомба при
и
.

|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|

|
0|0
|
0|10
|
0|11
|
10|0
|
10|10
|
10|11
|
110|0
|
110|10
|
110|11
|
1110|0
|

|
0|00
|
0|01
|
0|100
|
0|101
|
10|110
|
10|00
|
10|01
|
10|100
|
10|101
|
110|110
|
Табл. 3.60. Некоторые коды Голомба при
и
.
Предположим, что входной поток данных состоит из целых чисел, причем вероятность числа
равна
. Здесь
- некоторый параметр,
. Можно показать, что коды Голомба будут оптимальными кодами для этого потока данных, если
выбрать из условия
.
Имея такие данные на входе, легко породить наилучшие коды переменной длины, не прибегая к алгоритму Хаффмана.