Численные расчеты для некоторых простых каналов

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

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

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

каналу двоичных знаков. Другими простыми кодами, которые кодируют 2-, 3-, 4- и 5-ти буквенные сообщения в однобуквенный сигнал, в канале являются следующие: для отношения числа букв сообщения к числу букв сигнала, равного 3 или 5, последовательности сообщений из 3 или 5 знаков кодируются как 0 или 1 соответственно, в зависимости от того, содержит ли последовательность больше нулей или единиц.

Рис. 5.

Рис. 6.

Для отношения 2 или 4 делается то же самое, исключая последовательности с равным числом нулей и единиц, кодируемых 0. На приемном конце 0 декодируется в последовательность нулей соответствующей длины, в последовательность единиц. Эти в какой то степени вырожденные коды отмечены на рис. 5 крестиками. Несмотря на их простоту (длина блокового кода в канале равна всего только единице), они все же в известной мере аппроксимируют нижнюю границу.

На том же рисунке нанесены черные кружки, соответствующие хорошо известным кодам, корректирующим одиночную ошибку с

длинами блоков 3,7,15 и 31. Эти коды используются здесь в обратном порядке — любое сообщение в -мерном кубе, например, передается по каналу как сообщение из одиннадцати знаков, образующих ближайшую кодовую точку. На приемном конце соответствующее пятнадцатизначное сообщение восстанавливается. Оно может отличаться от исходного сообщения самое большее в одной позиции.

Рис. 7.

Следовательно, в этом случае отношение числа букв сигнала к числу букв сообщения равно 11/15, и легко найти, что вероятность ошибки будет 1/16. Эта серия точек дает близкую аппроксимацию нижней границы.

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

Эта интерполяция определяет выпуклую кривую между любыми двумя кодовыми точками. Будучи применена к отмеченным на рис. 5 ряду простых кодов и кодов, корректирующих одиночную ошибку, она дает интерполяционные линии, изображенные пунктиром.

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

Рис. 8. (см. скан)

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

На рис. 7 показана кривая для другого простого случая: источник является двоичным с независимыми буквами, а воспроизводимый алфавит состоит из 3-х букв Мера искажения равна 0 для правильного знака, 1 для неправильного знака и 0,25 для символа «?». На том же рисунке для сравнения показана кривая для случая, когда символ на выходе невозможен.

На рис. 8 приведены кривые для источников независимых букв с различным числом равновероятных букв в алфавите (2, 3, 4, 5, 10, 100). Здесь снова в качестве меры искажения принята вероятность ошибки (на знак). Если число букв в алфавите равно функция выражается формулой