ПРОПУСКНАЯ СПОСОБНОСТЬ КАНАЛА С ШУМОМ ПРИ НУЛЕВОЙ ОШИБКЕ

Краткое содержание

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

Введение

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

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

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

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

Последовательность входных букв будет называться входным словом, последовательность выходных букв — выходным словом. Отображением сообщений (которые можно перенумеровать цифрами 1, 2, М) в некоторое подмножество входных слов длины будет называться блоковым кодом длины Входной скоростью этого кода будет называться . Если не будет специальных оговорок, то слово «код» будет означать такой блоковый код. В работе будут употребляться натуральные логарифмы и натуральные (а не двоичные) единицы информации, так как это упрощает проводимые ниже аналитические выкладки.

Рис. 1.

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

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

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

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

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