Глава 6. КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ В КАНАЛЕ

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

Первая теорема, утверждающая возможность передачи сообщений по каналу со случайными помехами при сколько угодно малой вероятности ошибки, была опубликована Шенноном в 1948 г. С тех пор эта основная теорема уточнялась и обобщалась как самим Шенноном, так и другими авторами. В этой главе изложен простой пример методов кодирования и декодирования, при которых обеспечивается произвольно малая вероятность ошибки. В гл. 7 и 9 будут выведены различные границы вероятности ошибки для дискретных постоянных каналов.

6.1. Блоковое кодирование и декодирование

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

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

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

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

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

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

Рис. 6.1. Схематическое представление блокового кодирования и декодирования.

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

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

Это отображение точек пространства сообщений в точки пространства входных последовательностей схематически изображено в левой части рис. 6.1. Выходное пространство V в

правой части рис. 6.1, состоит из всевозможных последовательностей из символов, принадлежащих выходному алфавиту У.

Получающийся канал с входным пространством и выходным пространством V мы будем рассматривать как степень дискретного постоянного канала с входным алфавитом X и выходным алфавитом У. Так как первоначальный канал — постоянный, то условные распределения вероятностей для степени канала определяются по формуле (5.3) как

где — некоторый символ х алфавита некоторый символ у выходного алфавита условное распределение вероятностей, определяющее канал.

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

а условные вероятности сообщений при заданной выходной последовательности равны:

Целью декодирования является отождествление переданных сообщений на основании сведений, доставляемых выходной последовательностью. В этом процессе отождествления могут использоваться различные критерии. Если при декодировании известно распределение вероятностей сообщений, то декодер может вычислить по формуле (6.4) условные вероятности каждого сообщения для частной последовательности на выходе канала. За переданное сообщение принимается то, для которого эта апостериорная вероятность — наибольшая. Тогда вероятность ошибки при отождествлении сообщений равна

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

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

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

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

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

можно получить из выражения (6.2) при любых заданных кодере и декодере.

Теорема. Средняя взаимная информация между не может превзойти средней взаимной информации между т. е.

Доказательство. Так как однозначно определяется по то

С другой стороны,

откуда

Это неравенство устанавливает, что ненадежность ансамбля (условная энтропия больше, когда задано чем когда задано V, и, поскольку много точек множества V отображаются в одну точку из это соответствует нашим интуитивным представлениям. Доказываемое неравенство (6.8) немедленно следует из неравенства (6.11). Ч. Т. Д.

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