Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.9. Длины серий

Вероятность серий из нулей равна (поскольку после каждой такой серии появляется единица). Суммируя по всем возможным длинам имеем

как и следовало ожидать.

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

указанное число нулей и затем одну 1. Если иослано число 0, то приемник просто генерирует одну 1. Если послано число приемник генерирует нулей, за которыми не следует 1. Если после этого послано число 0, то, конечно, генерируется 1; для любого другого числа генерируется указанное число нулей и затем единица. Таким образом, передав достаточное число -значных двоичных чисел, можно указать любую длину серии, состоящей из нулей.

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

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

Поэтому средняя длина равна (через m обозначено число а через вероятность появления серии нулей длины

Поскольку получаем

Суммируя члены в скобках, приводим это выражение к виду

Эта сумма, в свою, очередь, равна

Нужна небольшая таблица (табл. 5.9.1) функции которая позволяет для данного выбрать наилучшее (табл. 5.9.2).

Средняя длина серий равна

Из обеих таблиц видно, что эффективность кодирования серий зависит от выбора и для оптимального кодирования выбор

Зависит от Ясно, что для данного легко выбрать соответствующее .

Таблица 5.9.1 (см. скан) Значение

Таблица 5.9.2 (см. скан) Эффективность кодирования

Задача

5.9.1. Рассмотрите кодирование серий нулей кодом Хаффмена.

<< Предыдущий параграф Следующий параграф >>
Оглавление