§ 3.2. Постановка задачи кодирования в дискретном канале

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

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

Заданием величины Действительно, если х, у— последовательности длины из нулей и единиц на входе и выходе канала, то

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

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

Рассмотрим другой метод кодирования (передачу с помощью повторений): если надо передать то по каналу передается последовательность из нулей, если же надо передать то по каналу передается последовательность из единиц. Приемник работает по следующему правилу: если в принятой последовательности количество нулей больше количества единиц, считается, что передавалось в противном случае считается, что передавалось

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

Так как математическое ожидание числа ошибок в последовательности длины равно то в силу закона больших чисел Я стремится к нулю при возрастании

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

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

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

Определение 3.2.1. Кодом с длиной и объемом для канала называется множество из пар где последовательности длины образованные входными сигналами канала и называемые кодовыми словами при — решающие области, образованные выходными

последовательностями канала, причем при множества и не пересекаются.

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

Определение 3.2.2. Скоростью кода (или скоростью передачи) называется величина

где объем и длина кода.

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

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

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

Очевидно, что код длины имеющий скорость имеет объем Такой код в дальнейшем будем обозначать символом

Пример 3.2.2. Предположим, что двоичный источник без памяти имеет энтропию Как было показано в гл. 1, при кодировании сообщений такого источника можно достичь скорости, близкой к Это означает, что при появлении на входе кодера источника двоичных символов, где достаточно велико, на выходе кодера появляется примерно двоичных символов, что меньше, чем Если теперь рассматривать последовательности длины как входные сообщения для кодера двоичного канала, осуществляющего кодирование со скоростью то длина кодовых слов будет равна

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

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

где дополнение к множеству

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

Вторая — средняя вероятность ошибки

где вероятность передачи кодового слова.

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

Выражение (3.2.6) совпадает с (3.2.5) в случае оптимального кодирования источника, когда

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

С — это верхняя грань скоростей кодов, для которых выполняется (3.2.7), поэтому передача с произвольно малой

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

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

1) при любом и любом положительном 6 существует код длины скорость которого равна и максимальная вероятность ошибки удовлетворяет неравенству (прямая теорема кодирования);

2) для всякого найдется положительное число такое, что для любого и любого кода (обратная теорема кодирования).

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

Лемма 3.2.1. Пусть существует код объема с вероятностью ошибки , определенной соотношением (3.2.6), тогда существует код объема максимальная вероятность ошибки которого удовлетворяет неравенству

Доказательство. Предположим, что в коде объема кодовые слова им упорядочены по невозрастанию вероятности ошибки, т. е. при Имеет место следующая цепочка неравенств:

В силу упорядоченности вероятностей ошибок из (3.2.8) вытекает, что

для всех Тогда код объема образованный словами Или имеет максимальную вероятность ошибки, не превышающую . Лемма доказана.

Из леммы 3.2.1 следует, что, если при любом суще-, ствует код такой, что

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

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