<< Предыдущая

стр. 19
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

бит

Так как в симметричном канале с равномерным распределени-
ем входных символов I(X;Y) совпадает с пропускной способностью
107)
7.6. Теорема кодирования для дискретных каналов без памяти


С из (7.58), совместную энтропию и две условные энтропии мож-
но подсчитать, используя таблицу 7.3. Диаграмма информационных
потоков изображена на рис. 7.15.

Н(ХЛГ) = 0,7142 бит



Энтропия ^ . Энтропия
//(*)= I бит / /№)0 = 0,2858бит \ W ( y ) = 1 5813бит



) = 1,2967 бит



Рис. 7.15. Диаграмма информационных потоков двоичного
симметричного канала со стираниями.

5. Пересчет матрицы переходных вероятностей канала Ру/х в
матрицу Px/Y предоставляем сделать читателю в качестве самосто-
ятельного упражнения. Диаграмма канала с входным источником У
и выходным X приведена на рис. 7.16 для контроля.
0,8571

дг,="О"
Источник X


0,1429.

Уз="1" С^"0,8571


Рис. 7.16. Двоичный симметричный канал со стираниями.




7.6. Теорема кодирования для дискретных каналов
без памяти
Рассмотрим дискретный канал без памяти с пропускной способно-
стью С[бит/символ], в котором каждый символ передается в течении
7's сек. Для этого канала С[бит/сек]= С[бит/сек]/Г«.
Пусть энтропия некоторого источника X, измеренная в течении
Тя сек, составляет Н(Х) бит. Тогда имеет место следующая теорема.
Глава 7. Дискретные каналы без памяти

Теорема 7.6.1. Теорема кодирования для канала (теорема Шенно-
на).
Для источника X со скоростью R — H(X)/TS [бит/сек] и R < С
существует некоторый код, с помощью которого информация источ-
ника X может быть передана.но каналу связи с пропускной способ-
ностью С[бит/сек] со сколь угодно малой вероятностью ошибки.1
Доказательство теоремы кодирования для канала (см..например,
[10]) довольно сложно и выходит за рамки этой книги, поэтому огра-
ничимся здесь следующими замечаниями.

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

• Теорема кодирования определяет также верхнюю границу для
скорости передачи R. 2

• При доказательстве теоремы вводится показатель экспоненци-
альной оценки До, который может быть использован для оцен-
ки технически достижимой скорости передачи данных [4|.




1
Теорема кодирования справедлива не только для дискретных каналов, она так-
же верна и при передаче дискретных сообщений по непрерывным каналам. -
Прим. перев.
2
Здесь необходимо сделать разъяснение. Существует обратная теорема кодиро-
вания, которая говорит о том, что при R > С не существует никакого метода
кодирования, позволяющего передавать информацию с как угодно малой веро-
ятностью ошибки.- Прим. перев.
ГЛАВА 8
НЕПРЕРЫВНЫЕ
ИСТОЧНИКИ
И КАНАЛЫ

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


Источник



«г\/ \St
X




Рис. 8Д. Сигнал непрерывного источника.

Вместо источников с конечным алфавитом символов будем рас-
сматривать источники, выходом которых являются непрерывные сиг-
налы. Примером таких сигналов может служить изменяющееся во
времени напряжение в телефонных каналах и т.д. На рисунке 8.1
представлен непрерывный источник X, выходом которого является
аналоговый сигнал x(t), являющийся некоторой случайной функци-
ей от времени t. Будем рассматривать значения x(t) в некоторые
фиксированные моменты времени как случайные эксперименты, ко-
торые несут некоторую информацию об источнике X.


8.1. Дифференциальная энтропия
На рисунке 8.2 показаны два непрерывных источника X и У, свя-
занные каналом (аналогично рис. 7.4). Здесь, вместо вероятностей,
стоят функции плотностей распределения вероятностей стохастиче-
ских переменных.
Использование стохастических неременных и их функции плот-
ностей распределения вероятностей-позволяет вводить понятие ин-
I 10 Глава 8. Непрерывные источники и каналы


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


Источник Источник
Y
X

Плотность Плотность
Плотность
распределения ределен„я
распределения ) расП j




Р и с . 8.2. Два непрерывных источника без памяти, связан-
ных каналом.

Преобразуем непрерывный источник X в дискретный. Для это-
го проквантуем значения аналогового выхода источника с шагом Д
(рис. 8.3).


Источник
X




Р и с . 8.3. Оцифровка непрерывного источника с интерва-
лом квантования Д в моменты наблюдения to, ti
и т.д.

Кроме этого, как это обычно делается в теории информации, про-
изведем дискретизацию источника по времени. В результате, полу-
чим последовательность стохастических переменных Xo,Xi,X2,
Следуя таблице 7.2, определим взаимную информацию символов а^
и yj, где Xi - значение выходного символа в момент времени tm, a Xj
- в момент времени tn


бит
j - А < Хп <
P{\Xi - А < Хт < Xi] П |
= log
Р(1; - А < Хт < Xi)P(Xj -А<Хп<

fxmxn{xi^x2)dxidx2
I J
8.1. Дифференциальная энтропия

Взаимную информацию можно трактовать как «снятую» (утра-
ченную) неопределенность попадания переменной Хп в интервале
[XJ — A,Xj[, когда известно, что переменная Хт принадлежит интер-
валу [xi — Д,Xi[ или наоборот. Будем считать функцию плотности
распределения вероятности непрерывной функцией. Тогда, устрем-
ляя ширину интервала квантования к нулю, получим
Xi Xj
J J fxmxn(xi,x2)dxidx2

/ fxm{xi)dxx J
Xi-Д Xj-Д



fv
Afv (T-\Afv (r) • (rAfv (T-Y
т.е. результат, аналогичный выражению взаимной информации для
дискретных источников. Передаваемую информацию можно опреде-
лить как математическое ожидание



бит (83)




Замечание. Здесь, для приведения в соответствие обозначений
этой главы с результатами таблицы 7.2, вместо Хт используется
X, а вместо Yn - Y.

Информация источника определяется исходя из аналогичных рас-
суждений

^ = - log2 Р([ХГ -А<Х< (8.4)
]) =
Xi

Xi

= -log2 J }x{xi)dx^X -lo g2 (A/ x fe)) =
' . -
ХГ-А
= -log2A-log2/x(a:i).

В отличие от выражения (8.3) для взаимной информации, в (8.4)
появляется слагаемое, зависящее от интервала квантования Д.
При Д — оо, величина log 2 (A) также стремится к бесконечно-
>
сти. В результате, выражение для I{xi) также стремится к оо. Это
не удивительно, так как с уменьшением шага квантования, число
отдельных событий (символов алфавита источника) возрастает и,
следовательно, неопределенность источника также растет.
Глава 8. Непрерывные источники и каналы

Величина log 2 (A) не зависит от источника и совершенно не умест-
на для его описания,«поэтому, кажется вполне естественно использо-
вать только функцию плотности распределения вероятности непре-
рывного источника. Таким образом, мы переходим к следующему
определению.

Средняя информация непрерывного источника, так называемая
дифференциальная энтропия, определяется как

/•оо
Н(Х)
= - / f(x)log2f(x)dx. (8.5)
бит J оо

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

<< Предыдущая

стр. 19
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>