Групповые эффективные коды. Кодирование Хаффмана для факсимильной передачи

Эффективность сжатия данных может быть существенно повышена, если осуществить кодирование не отдельных символов последовательности, а группы этих символов. В частности, особенно удачным групповое кодирование является для двоичных кодов, получаемых от специфических источников. Наиболее важным коммерческим применением является факсимильное кодирование, используемое для передачи документов по электронной почте.

Факсимильная передача – это процесс передачи неподвижного изображения или двумерного образа как последовательности последовательных строчных разверток. В действительности, наиболее распространенными образами являются документы, содержащие цифры и текст. Положение строчное развертки и положение вдоль развертки квантуется в пространственное расположение, которое определит двумерную координатную сетку элементов картинки, называемых пикселями. Ширина стандартного формата МСЭТ определяется равной 20,7 см.(8,27 дюймов), а длина 29, 2 см.(11,7 дюймов). Пространственное квантование для нормального расширения составляет 1 728 пикселей/строку и 1 188 строк на документ. Стандарт также определяет квантование с высоким разрешением с теми же 1 728 пикселей на строку, но с 2 376 строками на документ.

Общее число отдельных пикселей для факсимильной передачи с нормальным разрешением составляет 2052864 и оно удваивается для более высокого разрешения. Для сравнения, число пикселей частного американского телевидения 307200. Т.о., факсимильное изображение имеет разрешение в 6. 7 или в 13, 4 раза больше разрешения стандартного телевизионного образа.

Относительная яркость или затененность разверточного образа в каждом положении на строке развертки квантуется на 2 уровня: Ч – черный, Б – белый. Т.о., сигнал, наблюдаемый на протяжении линии развертки, - это двухуровневая модель, представляющая элементы черный и белый. Горизонтальной развертка страницы будет представлять последовательность, состоящей из длинных групп уровней черного и белого. Легко видеть, что горизонтальная развертка данной страницы будет представлять последовательность, состоящую из длинных групп уровней Ч и Б. Стандарт МСЭТ схемы группового кодирования для сжатия отрезков черного и белого уровней базируется на коде Хаффмана переменной длины, который приведен в таблице. (В приведённой здесь таблице заполнены только те строки, которые используются в рассматриваемом ниже примере). Определяется два типа шаблона: белый и черный. Таблица состоит из двух таблиц. В верхней таблице приведены коды для групп черных и белых символов, длины которых кратны 64. Во второй таблице представлены оконечные кодовые слова, т. е. приведены коды для групп от 0 до 63 символов. Каждой серии из знаков Ч или Б длиной от 0 до 63 соответствует единственной кодовое слово Хаффмана, как и каждой группе длины .

Так же кодом определен уникальный символ конца строки (End Of Line - EOL), который устанавливает, что дальше не идет четный или белый символ. Следовательно, должна начаться новая строка.

Таблица 1 – Модифицированный код Хаффмана для стандартных кодов связи МСЭТ

Таблица 2 – Оконечные кодовые слова

Рассмотрим пример использования кода группового кодирования. Используем модифицированный код Хаффмана для сжатия строки

200 Б 10 Ч 10 Б 84 Ч 1424 Б,

состоящей из 1728 пиксельных элементов.

Используя таблицы, определяем, каким должно быть кодирование этой модели:

192Б – 010111; 8Б – 10011; и т.д.

010111 10011 0000100 00111 0000001111 00001101000 000000000001

192 Б 8 Б 10 Ч 10 Б 64 Ч 20 Ч EOL

Итак, требуется всего 56 бит, чтобы послать эту строку, содержащую 1728 бит.