§ 6.3. Кодирование в каналах с множественным доступом

6.3.1. Постановка задачи.

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

Рис. 6.3.1. Канал с множественным доступом.

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

Системы передачи, в которых имеется несколько передающих станций, один канал связи, доступный всем станциям, и один приемник, который должен определить, что передавала каждая станция, называются системами передачи по каналу с множественным доступом (КМД). На рис, 6.3.1 показана схема передачи по такому каналу в случае двух станций. Источники сообщений порождают сообщения соответственно. Эти сообщения отображаются кодерами в кодовые слова х, у, которые и подаются на

вход канала. На выходе канала появляется последовательность которая поступает в декодер. На выходах декодера появляются оценки передававшихся сообщений.

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

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

Передача по КМД в каждый момент времени задается набором переходных вероятностей Процесс передачи в моментов времени будем задавать посредством вероятностей появления на выходе канала последовательности если на первом входе была последовательность х, а на втором — последовательность у, причем будем полагать, что

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

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

Определение 6.3.1. Кодом длины со скоростями для КМД называется совокупность причем множества не пересекаются при Последовательности называются кодовыми словами первого и второго пользователей соответственно, а множества А называются решающими областями.

Легко видеть, что код для КМД является одновременно и кодом для обычного дискретного канала с переходными вероятностями Заметим, что каждое слово произвольного кода

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

Для каждого кода определяется обычным образом средняя вероятность X ошибки декодирования

Определение 6.3.2. Пара скоростей называется допустимой для КМД, если для любых найдется такое, что для всех существует код , с вероятностью ошибки декодирования Множество 5, состоящее из всех пар допустимых скоростей, называется областью пропускной способности

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

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

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

6.3.2. Двоичный суммирующий КМД.

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

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

Если на первый вход канала поступает сигнал а на второй — сигнал то на выходе канала возникает сигнал принимающий значения О, 1 или 2 в зависимости от значений х и у. Таким образом, в рассматриваемом КМД шума нет, а имеется только взаимное влияние сигналов пользователей. Такой канал с множественным доступом называется двоичным суммирующим (ДСКМД). Он имеет следующие переходные вероятности:

ДСКМД можно рассматривать как обычный канал без памяти с четверичным входом троичным выходом (см. рис. 6.3.3) и переходными вероятностями (6.3.2). Пропускную способность такого канала легко вычислить. Она равна

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

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

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

Рис. 6.3.3. ДСКМД как обычный канал с четверичным входом и троичным выходом.

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

Нетрудно видеть, что максимум в (6.3.4) достигается при При этом для любой допустимой пары

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

могут быть записаны в виде

Мы установили, что любая допустимая пара скоростей в ДСКМД должна удовлетворять трем неравенствам

при Множество пар скоростей удовлетворяющих неравенствам (6.3.5), представляет собой часть плоскости, ограниченную прямыми (см. рис. 6.3.2, 6),

Покажем теперь, что любая пара скоростей удовлетворяющая условиям (6.3.5), действительно допустима при передаче по ДСКМД. Заметим вначале, что в силу возможности использования разделения времени достаточно доказать допустимость только пар

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

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

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

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

Рис. 6.3.4. Замыкание области допустимых пар скоростей.

Теперь мы перейдем к рассмотрению произвольных КМД без памяти.

6.3.3. Обратная теорема кодирования.

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

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

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

В следующей лемме дается простая интерпретация множества . Лемма 6.3.1. Пусть множество состоит из двух элементов распределение вероятностей на Пусть распределение вероятностей на ансамбле задается следующим образом:

Обозначим через множество ансамблей с распределениями вероятностей (6.3.8), получающимся при различных выборах распределений Пусть

Тогда

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

Тогда для построенного ансамбля пара скоростей и удовлетворяет неравенствам

Следовательно,

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

Совместимость условий (6.3.11) вытекает из условий (6.3.9). Из (6.3.11) следует, что Таким образом, Лемма доказана.

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

Теорема 6.3.1 (обратная теорема кодирования). Пусть задан дискретный КМД без памяти, причем входные алфавиты, выходной алфавит и переходные вероятности. Пусть множество пар скоростей, определенное соотношениями (6.3.9). Если в рассматриваемом КМД пара скоростей допустима, то она принадлежит т. е.

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

Это распределение вероятностей определяет ансамбль Декодирование для кода определяет, кроме того, ансамбль Таким образом, распределение (6.3.12), КМД и код в совокупности определяют ансамбль Для этого ансамбля

Пусть К — средняя вероятность ошибки для рассматриваемого кода Тогда, используя неравенство Фано, из (6.3.13) получим

где использованы неравенства следует, что

Справедливы также следующие соотношения для ансамбля

где использована независимость а также что Обозначим через вероятность ошибки декодирования сообщения первого кодера при условии, что второй кодер передает слово и через — среднюю вероятность ошибки декодирования сообщений первого кодера: Тогда

из неравенства Фано вытекают неравенства

Усредняя обе части последнего неравенства по ансамблю и используя выпуклость функции получим

откуда следует, что Аналогичным образом выводится неравенство

где — средняя вероятность ошибки декодирования сообщений второго кодера.

Оценим теперь информации Учитывая, что рассматриваемый КМД не имеет памяти, получим

и аналогично

Заметим, что слагаемое в каждой из сумм (6.3.18) — (6.3.20) вычисляется по распределению вероятностей распределению, определяемому из распределения

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

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

6.3.4. Прямая теорема кодирования.

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

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

Пусть распределения вероятностей фиксированы. Положим

для всех последовательностей

Вероятность кода в ансамбле положим равной

Такое задание распределения вероятностей на ансамбле кодов соответствует независимому выбору кодовых слов для первого и второго кодеров.

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

Эта вероятность не равна произведению вероятностей

Аналогичная ситуация имеет место и при Вместе с тем, если то пары кодовых слов независимы. Наличие зависимости между некоторыми парами кодовых слов вносит дополнительные, правда легко преодолимые, трудности.

Пусть фиксирован код Обозначим через условную вероятность ошибки при передаче кодовых слов Тогда

где

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

Оценим теперь функцию подобно тому, как это делалось в параграфе 3.12. Имеет место следующее неравенство

где Действительно, если то по крайней мере в одном слагаемом числитель не меньше, чем знаменатель, и поэтому правая часть этого неравенства не меньше чем 1. Подставляя оценку функции в (6.3.25), получим, что

где

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

Теорема 6.3.2 {прямая теорема кодирования). Пусть фиксированы дискретный КМД без памяти и распределение вероятностей Любая пара скоростей допустима.

Доказательство. Обозначим через средние значения величин по ансамблю кодов

При усреднении будем учитывать что:

а) пары кодовых слов и при статистически независимы в ансамбле

б) при фиксированном слове кодовые слова статистически независимы в ансамбле

в) при фиксированном слове кодовые слова статистически независимы в ансамбле

г) для всех имеет место неравенство где произвольная случайная величина и черта означает усреднение;

д) средние по ансамблю кодов значения вероятностей не зависят от индексов

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

которые производились в пунктах 3.12.2 и 3.12.3. получим

где

Для того чтобы оценить обозначим через условное математическое ожидание величины при фиксированном кодовом слове Произведя операцию усреднения, получим

Усредняя затем и выполняя стандартные преобразования, получим

где

Аналогичным образом можно получить, что

где

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

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

Следовательно, средняя по ансамблю вероятность ошибки

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