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. Некоторые коды Голомба при  и .

Предположим, что входной поток данных состоит из целых чисел, причем вероятность числа  равна . Здесь  - некоторый параметр, . Можно показать, что коды Голомба будут оптимальными кодами для этого потока данных, если  выбрать из условия

.

Имея такие данные на входе, легко породить наилучшие коды переменной длины, не прибегая к алгоритму Хаффмана.