Глава 3. КОДИРОВАНИЕ В ДИСКРЕТНЫХ КАНАЛАХ

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

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

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

§ 3.1. Классификация каналов связи

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

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

Рис. 3.1.1. Структурная схема системы связи.

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

Назначение кодера и декодера источника (см. рис. 3.1.1), а также их основные характеристики были подробно рассмотрены в первой главе. Здесь мы будем предполагать, что кодер источника выбран достаточно хорошо, поэтому можно считать, что символы, появляющиеся на его выходе, независимы и равновероятны. Таким образом, пару «источник — кодер источника» можно рассматривать как новый источник дискретных сообщений. Аналогично пару «декодер источника - получатель» мы будем рассматривать как получателя сообщений в системе передачи. Роль остальных блоков системы связи сводится к тому, что обеспечить максимально надежную передачу последовательности независимых равновероятных символов. Основную роль в решении этой задачи играет пара «кодер—декодер» канала.

Роль пары «модулятор—демодулятор» можно пояснить следующим образом. Предположим, что задано множество символов

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

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

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

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

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

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

Определение 3.1.1. Канал называют дискретным по входу (выходу), если множество входных (выходных) сигналов конечно.

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

Определение 3.1.2. Канал называют непрерывным по входу (выходу), если множество входных (выходных) сигналов несчетно.

Определение 3.1.3. Канал называют каналом, дискретным по входу и непрерывным по выходу (полунепрерывным), если множество входных сигналов конечно, а множество выходных сигналов несчетно.

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

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

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

Определение 3.1.5. Канал называют каналом с непрерывным временем, если сигналы на его входе и выходе представляют собой действительные функции времени. Непрерывный по входу и выходу канал с непрерывным временем мы будем называть непрерывным каналом.

В этой главе рассматриваются только дискретные каналы. Непрерывные каналы (с дискретным и непрерывным временем) будут рассмотрены в следующей главе.

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

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

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

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

с элементами из дискретных множеств соответственно заданы условные (или переходные) вероятности получения на выходе канала последовательности если на входе канала была последовательность

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

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

Название «без памяти» подчеркивает тот факт, что если выполняются соотношения (3.1.1), то при очередной передаче канал как бы не помнит результатов предыдущих передач.

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

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

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

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

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

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

и распределение вероятностей на выходных последовательностях канала