5.4. МЕТОДЫ ЭФФЕКТИВНОГО КОДИРОВАНИЯ ПРИ НЕИЗВЕСТНОЙ СТАТИСТИКЕ СООБЩЕНИЙ

Коды, экономичные одновременно для некоторого класса источников, называют универсальными кодами. Сформулируем постановку задачи универсального кодирования источников Предположим, что алфавит состоит из двух букв появляющихся независимо с вероятностями Однако величина заранее неизвестна. Требуется построить код, для которого среднее число символов «0» и «1» на одну букву алфавита приближалось бы к при любом Этот код строится так Множество всех блоков длины в алфавите А разбиваем на группы, которые имеют одинаковые вероятности при любом . Таких групп будет ровно . В нулевой группе отсутствует буква она состоит из единственного блока вероятность появления которого Первая группа состоит из всех блоков длины , содержащих одну букву Эта группа состоит из блоков, вероятность каждого из которых равна Группа с номером k состоит из всех блоков длины , содержащих k букв Эта группа содержит блоков, вероятность каждого из которых

Универсальный код для группы состоит из двух частей: префикса и суффикса. Префикс содержит двоичных знаков. Префикс указывает, к какой группе сообщений принадлежит кодируемый блок, суффикс содержит двоичных символов и указывает номер блока в группе.

Таблица 5.6

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

Код 1 в табл. 5.6 построен описанным выше способом. Здесь выделены штриховой линией префиксы Этот метод кодирования называется комбинаторным.

Префикс каждой из групп при комбинаторном кодировании содержит ровно символов «0» и «1». Еще большего эффекта можно достичь, если префикс кодировать неравномерным кодом (5.1). Код 2 в табл. 5.6 построен именно этим методом. Универсальные методы кодирования хороши не только тем, что они экономичны для любого распределения вероятностей, но и достаточно просто реализуются. Для универсального кодирования на передающем и приемном концах не обязательно знать таблицу, которая определяет кодирование. Код каждого блока вычисляется по мере поступления на кодирующее устройство букв На приемном конце также можно декодировать, не прибегая к таблицам. При этом число операций на кодирование и декодирование блока длины не превосходит

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

Опишем алгоритм нахождения суффикса. Пусть в блоке А длины буква встречается на местах тогда суффиксом для А назовем число вычисляемое по правилу:

Очевидно, что блоки с разными наборами получают разные номера. При этом максимальное значение номера равно

Таким образом, двоичная запись номера (суффикса) должна иметь длину Для нахождения воспользуемся таблицей биноминальных коэффициентов (треугольником Паскаля):

Элементы этой таблицы вычисляются по мере надобности либо размещаются в памяти кодирующего устройства. Приведем фрагмент этой таблицы, в которой на пересечении строки и столбца стоит

Пример 5.3. Пусть тогда Тогда номер блока Слагаемые к N(А) находим, используя таблицу дополнительных коэффициентов выделены жирным шрифтом Таким образом, или в двоичном записи

Декодирование производится с помощью этой же таблицы.

Пример 5.4. Пусть нам известно, что длина передаваемого блока равна 8, и что в блоке пять букв (количество букв в блоке находим по префиксу). Находим максимальное число в столбце, не превосходящее 32, это следовательно, находим разность Находим далее максимальное число столбца, не превосходящее 11. Это Аналогично находим Следовательно, декодированное сообщение имеет вид

Рассмотренные кодирование и декодирование достаточно просто осуществляются с помощью специализированных вычислительных средств.