ДВУСТОРОННИЕ КАНАЛЫ СВЯЗИ

1. Введение

Двусторонний канал связи схематически изображен на рис. 1. Здесь являются соответственно входными и выходными буквами на первом конце; входные и выходные буквы на втором конце канала.

Рис. 1.

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

Рис. 2.

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

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

Рис. 3.

Рис. 4.

На рис. 4 входные и выходные сигналы снова могут принимать лишь по два значения и канал характеризуется соотношением Здесь также можно вести передачу со скоростью один бит в секунду по обоим направлениям одновременно, но ее нужно вести несколько более утонченным методом. Хотя в качестве могут быть переданы произвольные двоичные числа, но при декодировании наблюденные значения у должны быть прокорректированы, чтобы исключить влияние переданного значения х. Так, чтобы определить переданное значение надо к наблюденному значению прибавить точное значение переданного Конечно, и здесь можно получить пары скоростей, меньшие чем (1,1), и снова аппроксимировать любую точку квадрата рис. 3.

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

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

Таблица I (см. скан)

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

Передача по двум направлениям в этом канале может быть названа несовместимой. Передача в прямом направлении (1—2 возможна, если только положить

Рис. 5.

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

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

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

2. Краткое изложение содержания

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

Рис. 6.

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

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

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

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

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

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

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

3. Основные определения

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

Пара блоковых кодов длины такого канала для передачи сообщений в прямом направлении и в обратном состоит из двух множеств по функций в каждом:

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

Система декодирования для пары блоковых кодов длины состоит из пары функций которые принимают значения от 1 до и от 1 до соответственно.

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

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

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

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

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

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

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