5.3. ОПТИМАЛЬНОЕ ЭФФЕКТИВНОЕ КОДИРОВАНИЕ

Оптимальное эффективное кодирование позволяет согласовать источник с каналом и обеспечить наилучшее использование пропускной способности канала. Сущность эффективного (Кодирования заключается в том, что неравномерное распределение вероятностей появления коррелированных символов сообщений с помощью определенным образом выбранного кода переводят в равномерное распределение вероятностей появления независимых кодовых символов.

Рассмотрим оптимальное эффективное кодирование сообщений источников без памяти и с памятью.

5.3.1. Кодирование сообщений источников без памяти. Символы сообщений «источников без памяти являются независимыми. Покажем, чем определяется и как достигается минимальная длина кодовой комбинации при кодировании символов сообщений источников без памяти. Обеспечение минимальной средней длины кодовой комбинации и равновероятного появления в ней независимых кодовых символов равносильно увеличению средней скорости передачи информации до максимальной потому, что за одно и то же время коротких кодовых -комбинаций можно передать больше а. это при прочих равных условиях соответствует передаче большего (Количества информации.

Минимальная средняя длина Пот кодовой комбинации определяется совместным выполнением условий (5.29), (5.32):

Если ошибки в канале отсутствуют, то минимальная средняя длина комбинации определяется только условием (5.29) при . Поэтому для идеальных каналов

Например, при двоичном кодировании сообщений для идеального канала

Следовательно, если энтропия двоичного кодера максимальна, среднее число кодовых символов в комбинациях минимально и равно энтропии источника. Оценка (5.44) средней длины кодовой комбинации является предельной; средняя длина кодовой комбинации не может быть меньше под. Эта оценка показывает, к чему необходимо стремиться при выборе способа эффективного кодирования. Теорема Шеннона для идеального канала утверждает, что такие способы кодирования существуют.

Если двоичный канал является реальным, то из-за ошибок растет средняя длина кодовых комбинаций и избыточность кода. Это вызвано необходимостью вводить в комбинации дополнительные кодовые символы, позволяющие обнаруживать и исправлять ошибки. В этом случае оценка средней минимальной длины кодовой комбинации подчиняется условию (5.40).

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

Этого недостатка лишен код Шеннона — Фано. Он построен по следующему алгоритму. Все символы алфавита сообщений записывают в порядке убывания вероятностей их появления. Полученную ранжированную (упорядоченную) последовательность символов разбивают на две группы так, чтобы суммы вероятностей трупп были примерно одинаковыми. Для символов верхней группы в качестве первого символа кодовой комбинации присваивают кодовый символ 0, для символов нижней группы — кодовый символ 1. Полученные группы символов сообщений опять разбивают на две подгруппы по указанному принципу и опять кодируют. Такое разделение продолжают до тех пор, пока в последних подгруппах не останется по одному символу сообщений. Верхнему последнему символу в качестве последнего символа кодовой комбинации присваивается символ 0, нижнему — символ 1. При кодировании по этому алгоритму средняя длина кодовой комбинации близка к минимальной, энтропия кодера максимальна (вероятности появления кодовых символов примерно одинаковы),

избыточность кода минимальна, скорость передачи информации, близка к максимальной приближается к пропускной способности канала.

Рассмотрим на конкретном примере особенности оптимального эффективного кодирования по алгоритму Шеннона-Фано. Предположим, что объем алфавита источника основание кода вероятности появления символов: канал идеальный. Оценим скорость передачи информации, пропускную способность и коэффициент использования идеального канала для равномерного кодирования и оптимального эффективного кодирования.

Вначале определим информационные характеристики источника сообщений. Энтропия источника

максимальное значение энтропии бит/симв., избыточность источника

Найдем характеристики равномерного двоичного кода. Длину кодовых комбинаций определим из условия

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

Энтропия кодера

скорость передачи информации пропускная способность канала

Коэффициент использования канала при равномерном кодировании

Найдем характеристики неравномерного двоичного кода Шеннона-Фано для этого случая. Особенности процедуры кодирования показаны в табл. 2 и с помощью графа кодирования на рис. 5.2. Граф кодирования показывает, как «расщепляется» ранжированная последовательность символов на группы и отдельные

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

Энтропия эффективного кодера

скорость передачи информации коэффициент использования канала

Таблица 2 (см. скан)

Рис. 5.2. Граф кодирования

Анализ и сравнение результатов равномерного и оптимального эффективного (неравномерного) кодирования для идеального канала в рассмотренном примере показывают следующее. Энтропия эффективного кодера и скорость передачи информации при неравномерном кодировании примерно на 33% выше, чем при равномерном, избыточность кода — на 33% ниже, коэффициент использования канала выше на 33% и близок к единице. Средняя длина кодовых комбинаций (5.44) при неравномерном кодировании близка (к минимальной: Так как максимальное количество информации, которое может переносить двоичный кодовый сигнал, равно 1 бит, то важно отметить, что энтропия эффективного кодера близка к максимальной — каждый кодовый сигнал несет 0,97 бит информации. Следовательно, в результате кодирования символы 0 и 1 появляются почти с одинаковой вероятностью. Таким образом, эффективный кодер преобразовал неравновероятные независимые символы источника сообщений в равновероятные независимые кодовые сигналы.

Важным свойством кода Шеннона — Фано является отсутствие характерных для других кодов трудностей в определении границ кодовых комбинаций. Коды, которые обладают такими свойствами, называют неприводимыми, они позволяют однозначно декодировать кодовые комбинации. Код Шеннона — Фано является неприводимым потому, что короткие комбинации никогда не

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

Соотношение (5.48) может навести на мысль, что для двоичного канала пропускная способность равна скорости передачи сигналов во всех случаях. Это справедливо для тех случаев, когда все кодовые сигналы являются переносчиками информации. Когда есть сигналы, не несущие информации, скорость передачи сигналов и пропускная способность имеют различные значения. Например, стартстопный телеграфный аппарат передает один символ сообщения семью посылками: одной пусковой длительностью пятью кодовыми длительностью каждая и одной стоповой длительностью Скорость передачи телеграфных сигналов

а пропускная способность определяется количествам только кодовых посылок в 1 с (пусковая и стоповая посылки, которые используют для синхронизации, информации не несут), поэтому

Для сравнения минимальной длины кодовых комбинаций в идеальном и реальном каналах покажем, как изменится для рассмотренного примера значение если в канале есть ошибки и вероятность появления ошибки при «передаче одного кодового сигнала . В соответствии с (5.42) получим

Избыточность неравномерного кода для реального канала

Энтропия кодера

Скорость передачи информации пропускная способность канала

коэффициент (использования канала

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

5.3.2. Кодирование сообщений источников с памятью. Если источник имеет память на символов, то для устранения межсимвольной корреляции применяют укрупнение первичного алфавита. В роли «символов» вторичного алфавита выступают последовательности (блоки) из символов первичного алфавита. В результате укрупнения обеспечивается переход от коррелированных символов первичного алфавита к независимым блокам вторичного алфавита. После такой перекодировки независимые неравновероятные блоки кодируют способами, применяемыми для источников без памяти.

Следовательно, кодирование сообщений источников с памятью выполняют в два этапа: на первом этапе осуществляют разбивку сообщений на блоки длиной в результате чего блоки нового алфавита становятся независимыми, а на втором этапе используют оптимальные коды, подобные коду Шеннона — Фано.

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

где -время передачи одного символа первичного алфавита; Т — задержка блоков в канале. Производительность источника блоков

где среднее количество информации в одном блоке.

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

где объем укрупненного алфавита; объем первичного алфавита. Из формулы (5.54) следует, что избыточность сообщений, составленных из символов первичного и вторичного алфавита, одна и та же.

Оптимальное эффективное кодирование сообщений почти полностью устраняет их избыточность. Из-за этого процесс передачи информации становится чувствительным к воздействию помех. Особенно сильно проявляется эта особенность при кодировании

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

Контрольные вопросы

(см. скан)