Пропускная способность канала при нулевой ошибке

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

равны нулю. На рис. 1 буквы а и с являются смежными, тогда как не являются смежными.

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

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

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

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

наилучший код длины свободный от ошибок. В общем случае это утверждение не верно, хотя оно и справедливо во многих случаях, особенно при малом числе входных букв. Первое отступление от этого правила происходит в случае пяти входных букв в канале, изображенном на рис. 2. В этом канале возможно выбрать по крайней мере две несмежные буквы, например 0 и 2. Используя составленные из них последовательности 00, 02, 20 и 22, получаем четыре слова в коде длины два. Возможно, однако, сконструировать код длины два из пяти попарно несмежных элементов 00, 12, 24, 31. 43.

Рис. 2.

Рис. 3.

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

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

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

образом матрицу смежности

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

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

Теорема 1. Пропускная способность дискретного канала без памяти при нулевой ошибке ограничена неравенствами

Здесь С — пропускная способность любого канала, имеющего переходные вероятности и матрицу смежности

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

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

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

Докажем теперь справедливость оценки снизу. Воспользуемся методом построения случайных кодов, основанных на вероятностях для букв. Последние будут выбраны так, чтобы минимизировать квадратичную форму Построим ансамбль кодов, каждый из которых состоит из М слов, содержащих по букв. Слова в коде выбираются следующим стохастическим методом. Любая буква в любом слове выбирается независимо от всех остальных букв и с вероятностью Вычислим теперь в этом ансамбле вероятность того, что какое-либо выбранное слово не является смежным ни с каким другим словом кода. Вероятность того, что первая буква первого слова не смежна с первой буквой второго слова, равна так как здесь случаи смежности суммируются с коэффициентом 1, а случаи несмежности с коэффициентом 0. Вероятность того, что два слова смежны по всем буквам и, следовательно, смежны как слова, равна . Это значит, что вероятность несмежности равна Вероятность того, что все других слов в коде не смежны данному слову в силу их независимого выбора, равна

Согласно хорошо известному неравенству, эта вероятность больше, чем что в свою очередь больше, чем

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

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

Теорема 2. Для дискретного канала без памяти с переходными вероятностями и вероятностями входных букв следующие три утверждения являются эквивалентными.

1) Скорость передачи

стационарна при вариации всем не равным нулю связанным условием и при вариации по таким для которых

2) Взаимная информация между парой вход — выход является постоянной для всех пар с неравными нулю вероятностями (т. е. для пар, у которых

3) Функция является функцией для всех для которых а сумма есть постоянная, не

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

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

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

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

при всех и для которых не равны нулю. Это условие требует, чтобы

Пусть — вероятность выходной буквы У, тогда последнее равенство эквивалентно равенству

Иначе говоря, не зависит от и является функцией тогда, когда Эту функцию от обозначим через Таким образом,

если равенство не имеет места.

Взяв теперь частную производную по получим

Для того чтобы функция была стационарной при условии требуется, чтобы Таким образом,

Так как для имеем то последнее равенство переходит в

Таким образом, не зависит от и может быть записано как а. Следовательно,

всегда, когда

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

то с помощью простой подстановки в формулу для получим Следовательно, стационарно при вариации подчиняющихся условию Далее, , следовательно, вариация обращается в нуль при

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

Чтобы доказать, что из утверждения 3) вытекает утверждение предположим, что

когда Тогда

Суммируя теперь равенства и используя предположение из утверждения 3), состоящее в том, что получим

так что равно и не зависит от Следовательно,

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

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

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

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

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

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

(кликните для просмотра скана)

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

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

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