Теория радиосвязи

102

составляет R = 1 – 2,423/2,45 = 0,011.

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

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

Другой весьма хороший код – это код Шеннона-Фано. Здесь также буквы алфавита предварительно располагаются в порядке убывания вероятностей. Кодирование двоичным кодом проводится в несколько этапов:

1)весь алфавит делится на две группы (верхнюю и нижнюю) так, чтобы суммарные вероятности в каждой из групп были по возможности равны друг другу (к сожалению, если вероятности всех букв не могут быть представлены в виде (4.18), при выполнении этой операции возможен субъективный подход); затем для каждой буквы записывается первый символ кодового слова: 1– для букв, попавших в верхнюю группу, и 0 – для букв из нижней группы;

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

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

Если m > 2, на каждом шаге проводится деление группы букв на m равновероятных подгрупп и для их нумерации используются символы 0,1,...,(m–

1).

Обратите внимание, что при кодировании и кодом Хафмана, и кодом Шеннона-Фано в самой структуре кодовой таблицы уже заложена возможность разделения при приеме последовательно передаваемых кодовых комбинаций. Например, при кодировании кодом рис. 4.2 принятая двоичная последовательность 0011000100111однозначно декодируется как последова-

тельность букв x2x4x5x2x6 . Это обусловлено тем, что в кодовой таблице никакая комбинация не является началом другой, более длинной комбинации.

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

105

взаимной информации между xj и yk.

2) В канале без помех возможны лишь пары xj, yj, поэтому для остальных пар находить взаимную информацию просто нет смысла. Для таких пар имеем

т.к. в таком канале всегда p(xj/yj)= p(yj/xj)=1. В канале без помех, как уже отмечалось, вся информация, создаваемая источником, достигает получателя.

3) Взаимная информация есть разность двух собственных информа-

но, I(xj/yj)<I(xj), тогда I(xj;yj)>0. Но иногда все-таки случается k ≠ j, и в этой ситуации вполне возможно, что I(xj/yk)>I(xj) и, следовательно, количество получаемой информации отрицательно I(xj;yk)<0.

4) Если X и Y независимы (помеха полностью подавляет полезный сигнал), всегда I(xj;yk)=0, т.к. P(xj/yk)=P(xj).

Математическое ожидание случайной величины “взаимная информация” равно

I(xj;yk) можно подставить любое из трех соотношений (4.20).

Средняя взаимная информация также обладает свойствами: симметрии

Напомним, что Н(Х) ≥ 0 и Н(Х/Y) ≥ 0.

Воспользовавшись неравенством Иенсена для логарифмической функции при Z>0

Отсюда, кстати, следует, что всегда H(X/Y)≤H(X).

В свете сказанного величины, входящие в формулу (4.24), приобретают вполне определенный смысл. Информация H(X), созданная источником, делится на две части:

I(X;Y) – то, что доходит до получателя;

H(X/Y) – то, что потеряно в канале из-за воздействия помех на сигнал. Соотношение между этими двумя частями в первую очередь зависит от

отношения сигнал/помеха.

106

Приведенные выше соотношения, конечно, по своей сути справедливы и в более общем случае, когда переданное сообщение X=X[1],…, X[n] и принятый сигнал Y=Y[1],…, Y[n] – это последовательности длины n, состоящие из m- ичных символов.

Взаимная информация между конкретными реализациями этих последовательностей равна

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

Средняя взаимная информация между последовательностями X и Y

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

Для нее также справедливо соотношение (4.24)

где Hn H (X [1] ,..., X [n] ) ,

Hn усл H ( X [1] ,..., X [n] / Y [1] ,...,Y [n] ) – энтропия и условная энтропия передаваемого сообщения X соответственно. Поскольку все члены в (4.29) возрастают при увеличении длины последовательностей n, удобнее провести нормировку и представить это соотношение в виде

где H=Hn/n – скорость создания информации;

I=In/n – скорость передачи информации (логичнее было бы назвать эту величину скоростью приема информации, но первый термин уже прочно вошел в употребление);

Hусл=Hn усл/n – скорость потерь информации.

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

4.4 Пропускная способность канала и теоремы о кодировании в цифровом канале с помехами

108

также не зависит от вероятностных характеристик переданного сигнала X и является энтропией случайного вектора ошибок E. Следовательно, чтобы максимизировать величину (4.33), нужно формировать передаваемый сигнал

X таким образом, чтобы H(Y)=H(Y)max=nlogm=n при m=2. Это возможно лишь в том случае, когда все символы в последовательности Y независимы, а

каждый символ с одинаковой вероятностью принимает значение 0 или 1 (сигнал Y не содержит избыточности). Это, в свою очередь, при р ≠ 0,5 возможно лишь тогда, когда передаваемый сигнал Х также не содержит избыточности. В итоге получим формулу для пропускной способности

Эта зависимость представлена на рис. 4.5 (анализируя график, учтите, что при р=1 после инвертирования выходного сигнала мы фактически полу-

чаем канал без ошибок).

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

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

ним, возможно ли это при I<C.

“Удлиним” канал, т.е. включим в его состав кодер и декодер, и обозначим А и В – цифровые сигналы на его входе и выходе соответственно. Напомним, что способ кодирования определен, если из общего количества N возможных последовательностей X выбраны NA<N последовательностей, признанных в качестве разрешенных к передаче (включенных в кодовую таблицу), при этом каждому из NA возможных сообщений a соответствует своя последовательность x=f(a). В свою очередь, функция b=g(y) определяет способ декодирования. Тогда имеем

109

Принципиальный вопрос теории помехоустойчивого кодирования в упрощенной постановке можно сформулировать следующим образом: существуют ли такие преобразования f и g, которые позволяют канал с ошибками после “удлинения” превратить в канал без ошибок, т.е. обеспечить H(A/B)=0.

Ответ на этот вопрос дают теоремы Шеннона о кодировании в дискретном канале с шумом (1948 год).

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

При доказательстве теоремы предполагалось, что код случаен, т.е. отбор NA разрешенных кодовых комбинаций X из общего их количества N произведен случайным образом. Далее записывалось соотношение для вероятности правильного декодирования Pпр, т.е. вероятности того, что принятая комбинация y окажется ближе к передаваемой комбинации x, нежели к любой другой разрешенной комбинации. Поскольку для случайного кода Pпр – тоже случайная величина, находилось ее математическое ожидание M[Pпр] (среднее значение). Затем осуществлялся предельный переход при n→∞ и оказалось, что M[Pпр]→1, следовательно, вероятность ошибки при декодировании M[Pош]→0, M[H(A/B)] →0, M[I(A;B)] →H(A). И, наконец, очевидно, что в этом ансамбле случайных кодов существует хотя бы один код, для которого характеристики помехоустойчивости не хуже средних, т.е. Pош≤M[Pош].

В частности, если все последовательности А, Х, У, В – двоичные, и все NA значений сообщения А равновероятны, условие Н<C означает

где k – длина последовательности А, т.е. количество информационных символов при использовании линейного блочного кода (n,k).

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

Обратная теорема. Если Н>C, никакой код не позволит получить сколь угодно малую вероятность ошибки Рош и обеспечить скорость потерь информации Нусл меньшую, чем Н–С.

Из (4.30) имеем Нусл=H–I. По определению (4.31) I≤C, следовательно, Нусл≥Н–С>0. Но Рош→0 возможно лишь при Нусл→0, откуда и следует утвер-

110

ждение теоремы.

Кстати, если Н>С, увеличение длины кодовых комбинаций n, наоборот, ведет к увеличению вероятности ошибки Рош.

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

4.5 Пропускная способность непрерывного канала с шумом

Большая часть из того, что было сказано об информационных характеристиках цифровых сигналов, по сути, применимо и к непрерывным сигналам. В частности, если X и Y – непрерывные случайные величины, то величина взаимной информации между их значениями x и y, подобно (4.19), равна

а величина средней взаимной информации

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

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

Как видно, под знаком логарифма здесь стоит размерная величина (напомним, что размерность W(x) есть размерность величины x-1). Поэтому величина H(X) зависит от выбора единиц, в которых измеряется значение x. Величины (4.38) и (4.39) определены корректно и такой зависимости не имеют.

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