ПРИЛОЖЕНИЕ Б. КОДИРОВАНИЕ. КОДЫ, ОБНАРУЖИВАЮЩИЕ ОШИБКИ

Б1. Введение

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

В основном тексте книги мы намеренно не касались теоретико-вероятностных приложений комбинаторики, так как они широко освещаются в сочинениях по теории вероятностей Здесь мы отступим от этого правила.

Б2. Передача r-выборки

Передача информации по линии связи осуществляется, как показано на схеме рис. 528 Источник информации уподобляется случайной величине принимающей значения составляющие «алфавит», с вероятностями Сообщение — это последовательность символов

Рис. 528

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

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

Рис. 529.

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

а на выходе принимается -выборка элементов «выходного» алфавита

Линия характеризуется множеством вероятностей перехода, т. е. вероятностей того, что поданная на вход -выборка принимается на выходе как -выборка

Эти вероятности могут зависеть от состояния в котором находится вход в момент «испускания» выборки, т. е. имеют вид

В этом случае говорят о «линии с памятью». В противном случае говорят о «линии без памяти» и тогда

В общем случае линия характеризуется случайной величиной X на входе, принимающей значения

роятностями случайной величиной на выходе, принимаю щей значения с вероятностями и матрицей перехода, составленной из элементов

Имеем

Распределение У целиком определяется распределением X и матрицей перехода. Для данной линии распределение вероятностей на входе однозначно приводит к некоторому распределению вероятностей на выходе, но обратное утверждение неверно. Вероятности определяемые формулой

можно получить из по формулам Байеса. Действительно, полагая

имеем

Важный частный случай представляет собой двоичная симметрическая линия, которая описывается так:

Матрица перехода

Граф перехода можно изобразить на рис. 530, а саму линию представить на рис. 531.

Характеризующая шум на линии вероятность называется «вероятностью ошибки» и обозначается через (см. [26]).

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

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

Рис. 530

Рис. 531.

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

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

Единица измерения информации, конечно, зависит от основания логарифма.

Средняя величина информации для полной системы X попарно взаимноисключающих событий называется энтропией системы и выражается формулой

Таким образом, энтропия определяется как математическое ожидание случайной величины X, принимающей значения с вероятностями

Можно определить некоторые энтропии для линии связи: средняя величина информации, характеризующая вход, она указывает на качество передатчика;

средняя величина информации, характеризующая выход, она указывает на качество приемника;

характеризует линию в целом;

дает оценку возможности восстановления переданного символа по полученному символу;

- дает представление о шуме на линии.

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

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

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

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

а) расположить сообщения в порядке возрастания их вероятности;

б) разбить сообщения на два подмножества так, чтобы вероятности сообщений внутри каждого из подмножеств были возможно более близки друг к другу;

в) приписать каждому из подмножеств двоичный знак, например, первому — нуль, а второму — единицу;

г) произвести операции б) и в) с каждым из подмножеств.

Продолжают так до тех пор, пока все сообщения не окажутся закодированными.

Предположим, например, что из источника 5 передаются сообщения с вероятностями

Закодируем эти сообщения, как показано в таблице:

Среднее число двоичных знаков кодированного сообщения

В идеальном случае среднее число двоичных знаков в сообщении равно

единиц информации на сообщение. Эффективность кодирования можно измерять отношением

Чем это отношение ближе к единице, тем кодирование лучше.

Пример 2. Пусть линия передачи определяется случайной величиной X на входе, принимающей значение с вероятностями Пусть число значений случайной величины на выходе равно 3, и матрица перехода задается следующим образом:

Вычислим вероятности

Для этого используем

откуда имеем

Вероятности и вычисляем по формуле е.

Имеем

откуда

Примечания. 1) Из элементов матрицы получают суммируя элементы в каждой из строк, и суммируя элементы в каждом из столбцов.

2) Если задана матрица то по ней можно найти и