Пропускная способность для суммы и произведения каналов

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

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

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

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

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

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

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

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

Теорема 5. При любом коде длины и скорости вероятность ошибки удовлетворяет неравенству где — минимальная не равная нулю вероятность

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

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