Материал: 5856

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