6. Блочное кодирование и теорема Шеннона.

Используя свойства энтропии можно в каком-то смысле уточнить теорему Шеннона. Пусть мы будем кодировать не буквы алфавита A, а блоки из k букв алфавита A. Вероятность каждого блока – это произведение вероятностей входящих в него букв. Тогда блок может быть представлен как произведение независимых событий. Энтропию такого блока H(AA…A) обозначим H^k(A). Минимальную стоимость кодирования для блока обозначим через C^k(A). Очевидно, что минимальная стоимость кодирования C(A) для одной буквы блока удовлетворяет соотношению C(A) ≤ C^k(A)/k.

Из свойства энтропии (5) следует, что H(A)= H^k(A)/k. Из этих соотношений и теоремы Шеннона для блоков получаем

C^k(A) – 1 ≤ H^k(A)/logq ≤C^k(A)

Отсюда следуетследует

C^k(A)/k – 1/k ≤ H(A)/logq ≤C^k(A)/k.

Отсюда при k →∞ получаем, что H(A)/logq → C^k(A).

За такую точность приходится платить трудоемкостью алгоритмов кодирования (декодирования).

Таким образом, была доказана теорема.

Теорема. Для любого ε > 0 существует N_ε такое, что при блочном кодировании с числом блоков N > N_ε справедливо неравенство |C_ε(A) – H(A)| < ε.

Здесь C_ε(A) - среднее число символов на одну букву в данном алгоритме кодирования. (Например, блочный алгоритм Хаффмена.)

Данное утверждение известно как теорема Шеннона для канала без шума. Приведем это утверждение в более распространенной формулировке.

Пусть скорость источника А - V_c букв в секунду.

Тогда можно считать, что на одну букву приходится H(А) битов. Тогда битовая скорость источника v_c = V_c H(X).

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

Канал

Получатель

Бинарный

поток

Бинарный

поток

Проблема: синхронизация скорости источника и пропускной способности канала.

Очевидно, что если по каналу можно передавать информацию со скоростью v_k < V_c log n, то могут произойти потери информации, так как max H(А) = log n. Если же технические возможности канала таковы, что он обеспечивает скорость v_k ≥ V_c log n, то информация может быть передана без потерь.

Теорема. (Теорема Шеннона для канала без шума). Для источника A с энтропией H(A) скорость v передачи по каналу без шума удовлетворяет условиям:

1. v > Vc H(X).

2. Существует такая кодировка букв источника битовыми словами, что для любого ε > 0 v< Vc H(X) + ε.

На самом деле задача сложнее, если учесть Замечание (Раздел 8.3.1). Приходится синхронизировать не только скорость передачи и пропускную способность канала, но еще и скорость кодирования символов.

Переходим теперь к следующему (последнему) разделу нашего курса.

Раздел 3. Передача информации. Защита от искажений.

5. Передача информации по каналу с шумом.

Рассмотрим теперь следующую более общую схему.

Код

Источник

F

Получатель

F^-1

Декодер

II

Декодер

I

Канал

Потери информации

Избыточность

Часть рисунка вне овала соответствует изучаемой раньше схеме, т.е. кодер (Кодер I ) и декодер (Декодер I) – это, например, устройства реализующие алгоритм Хаффмена или что-то подобное. Но в отличие от предыдущего случая (канала без шума) добавился еще один кодер (Кодер II ) и декодер (Декодер II). Их задача – обеспечить защиту передаваемой информации от шума в канале. Под шумом можно понимать самые разные искажения сигнала при передаче по каналу.

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

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

Пусть Bⁿ - булев куб размерности n.

Опр. Кодом C называется произвольное подмножество .

Пусть M – мощность множества C. Элементы этого подмножества будем называть кодовыми словами.

Опр. Пропускная способность канала

C(p) = 1 – H(p)

- энтропия канала.

Как раз для случая p=1/2 энтропия равна единице, что соответствует полной неопределенности (абсолютному беспорядку), а пропускная способность канала нулевая.

Опр. Скорость передачи кода .