7.3. Связь с кодированием для каналов

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

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

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

Рис. 7.6. Совместное кодирование источника и канала

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

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

означает его дополнение. Средняя погрешность, возникающая при совместном использований кода источника 38 и кода канала

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

Из (7.2.1) следует, что

Подставляя эту границу и неравенство

в равенство (7.3.2), находим

Из теории кодирования для каналов (теорема 3.2.1) известно, что существует ксд канала для которого вероятность ошибки при передаче сообщения по каналу удовлетворяет неравенству

где

С другой стороны, из теоремы 7.2.1 следует, что существует код источника такой, у которого

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

Теорема 7.3.1. Для рассмотренной выше объединенной схемы кодирования источника и канала, представленной на рис. 7.6, существуют код источника со скоростью передачи и длиной блока N и код канала со скоростью Я и длиной блока удовлетворяющими равенствам (7.3.1), такие, что средняя погрешность удовлетворяет неравенству

где при удовлетворяющем условию

— пропускная способность канала, измеряемая в натах на символ источника

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

Теорема 7.3.2. Источник, определенный в условиях теоремы

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

Доказательство. Доказательство этой обратной теоремы следует непосредственно из теоремы обработки данных 7.2.1 и обратной теоремы кодирования источников 7.2.3 [см. задачу (7.5)]

Указанная обратная теорема остается справедливой независимо от типа используемых кодеров и декодеров. Для доказательства теоремы 7.3.2 совсем не обязательно, чтобы они были раздельными, как показано на рис. 7.6, или чтобы они образовывали блочную схему кодирования. Так как теорема 7.3.1 верна для представленной на рис. 7.6 блочной схемы кодирования источника и канала, то видно, что в пределе с увеличением длины блока допущение о раздельном кодировании для источника и для канала не нарушает общности постановки задачи. С точки зрения практики такое разделение удобно, так как оно позволяет проектировать кодеры и декодеры для канала независимо от источника и пользователя. Кодер и декодер источника дают практическую возможность согласовать источник и пользователь с любой системой кодирования канала, если только эта система обладает достаточной пропускной способностью. Если кодирование оптимальное, то с увеличением длины блока выходные символы кодера источника становятся равновероятными (согласно свойству асимптотической равновероятности), так что в пределе поведение выхода кодера источника зависит только от скорости кодирования, а не от природы источника.

Из рис. 7.6 видна естественная дуальность блочного кодирования источника и блочного кодирования канала. Действия кодера источника подобны действиям декодера канала, в то время как кодер канала подобен декодеру источника. В кодировании каналов наиболее сложным устройством является, вообще говоря, декодер, тогда как в кодировании источников таковым является кодер. В § 7.4 будет показано, что эта дуальность имеет место и для схем решетчатого кодирования. Заметим, наконец, что хотя кодер

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

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

Такой канал иногда называют «обратным тест-каналом». Рассмотрим далее код источника со скоростью передачи и длиной блока Можно рассматривать как код обратного тест-канала, как показано на рис. 7.7. Предположим, что кодовые слова равновероятны, так что наибольшая вероятность правильного обнаружения, обозначаемая как достигается декодированием по обычному правилу максимума правдоподобия.

Рис. 7.7. Обратный тест-канал

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

Вероятность правильного решения для этого подоптимального декодера ограничена сверху соотношением

где последнее неравенство следует из строгого обращения теоремы кодирования (теорема 3.9.1). Теперь воспользуемся (7.3.13) для того, чтобы объяснить, почему в теореме кодирования источников (теорема 7.2.1, см. также лемму 7.2.1) показатель экспоненты по существу, является показателем экспоненты строгого обращение теоремы кодирования.

Главным образом нас будет интересовать величина

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

что в точности совпадает с утверждением леммы (7.2.1). Тогда, как и в § 7.2, находим, что при средняя погрешность ограничена неравенством

где

Отсюда видно, что теорема кодирования источников может быть выведена непосредственно из строгого обращения теоремы кодирования, указанного Аримото [1973], путем применения его к обратному тест-каналу, соответствующему как показано на рис. 7.7. Так как строгое обращение теоремы кодирования приводит к показателю экспоненты, который дуален показателю экспоненты усредненной по ансамблю вероятности ошибки, то и показатель экспоненты кодирования источников дуален показателю экспоненты средней по ансамблю вероятности ошибки.

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

Для любых двух входных букв канала расстояние Бхаттачария определяется [см. (2.3.15)] как

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

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

Полагая находим, что расстояние Бхаттачария пропорционально расстоянию Хэмминга. Легко показать (§ 7.6), что

и что соответствующий источник есть двоичный симметричный источник (ДСИ).

Напомним, что согласно § 3.4 [см. (3.4.8)] граница с выбрасыванием для ДСК утверждает, что существует блочный код с длиной блока N и скоростью передачи такой, что

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

Используя найденную связь с теорией передачи с погрешностью, можно также доказать границу Гилберта, рассмотренную в § 3.9. Пусть

где

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

где

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

Теорема 7.3.3. Граница Гилберта. Справедливо неравенство где

расстояние Хэмминга.

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

где неравенство следует из (7.3.23). Рассмотрим как блочный код источника. Обратная теорема кодирования источников (теорема 7.2.3) утверждает, что любой код с погрешностью ( имеет скорость

Так как определяется по (7.3.24), то Отсюда, так как строго убывающая функция от в интервале следует, что

Результаты для ДСК обобщаются на произвольные ДКБП, в которых используется расстояние Бхаттачария, если только при значениях параметра определяемых из уравнения матрица положительно определена (см. Джелинек [1968] и Для большинства наиболее важных типов каналов это условие положительной определенности выполняется для всех Это значит, что для произвольного ДКБП расстояние Бхаттачария является естественным обобщением расстояния Хэмминга в двоичных кодах, используемых для ДСК. Обобщенная граница Гилберта может быть получена в виде, аналогичном определяемому теоремой 7.3.3 (см. задачи 7.8 и 7.9).