11. Примеры кодирования простыми блоковыми арифметическими кодами

Пример. Пусть алфавит языка состоит из пяти букв: а, в, л, о, с . Их кодирование в цифровую последовательность возможно по правилу: а ,в ,л ,о ,с . В этом случае длина кода. Получатель, которому по телефону диктуют цифровые последовательности

или

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

или же искажаться

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

Переходим к кодированию букв в двоичной системе: а ,в ,о ,с , забывая пока о пятой букве. Таким образом длина кода. Предположим, что на каждое передаваемое кодовое слово канал связи дает не более одной ошибки: в каждом блоке длины 2 может менятьнаилина— но не сразу оба бита (и не «затирает» бит полностью). Что может произойти при передаче закодированного сообщения

по такому каналу? Получатель может увидеть следующие варианты:

или или

но не получит следующие:

или

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

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

Этот пример служит примером кода, исправляющего ошибки — в данном случае одну ошибку. Что произойдет если зашумленность канала оказывается более высокой, чем предполагалось? Возможны ситуации, когда полученный в результате передачи блок будет содержаться в таблице. Например, если на вход подается блок , а канал портит два бита, то получатель может увидеть блок, который хоть и содержится в таблице, но декодируется совсем не в ту букву, которая передавалась. А может случиться и так, что на выходе из канала получится блок, который совсем не содержится в таблице. Эта ситуация иногда более выгодна, чем предыдущая: декодер можно заставить извещать пользователя об обнаружении ошибки в случае когда полученный блок не содержится в таблице. Можно заложить в декодере одновременно обе возможности — сигнализации об ошибке и ее исправления. На примере полученного блокапосмотрим, что можно предпринять. Обратим внимание, что этот блок отличается от отправленногоа в двух битах, от блокав — также в двух битах, а от каждого из блоково илис — в трех битах. Поэтому, ввиду гипотезы о не более чем двух зашумленных битах, можно при декодировании отбросить два последних варианта, как невозможные.