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

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

ОГЛАВЛЕНИЕ

Следующая >>

редатчик - Канал - Приемник (рис. 7.1). Если происходит передача
информации, то символы одного источника должны оказывать влия-
ние на символы другого источника. В качестве примера рассмотрим
двоичные симметричные каналы без памяти.


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

Двоичный симметричный канал (ДСК) является простейшим при-
мером взаимодействия двух дискретных источников без памяти. Он
является дискретной двоичной моделью передачи информации по
каналу с аддитивным белым гауссовским шумом (АБГШ).
Замечание. При проверке эффективности алгоритмов помехоустой-
чивого кодирования, для расчетов и моделирования каналов связи
методом Монте-Карло успешно применяются дискретные модели
каналов.

Двоичный симметричный канал описывается с помощью диаграм-
мы переходов (рис. 7.2). На диаграмме представлены возможные пе-
реходы двоичных символов (0,1) источника X в двоичные символы
источника Y. Каждому переходу приписана переходная вероятность.

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




Р и с . 7.2. Диаграмма передачи данных по двоичному сим-
метричному каналу.


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

Матрица канала с входным алфавитом, состоящим из М симво-
лов Х{ и выходным алфавитом, состоящим из N символов yj, содер-
,86 Глава 7. Дискретные каналы без памяти

жит все переходные вероятности P(yj/xi) и имеет вид

\

(7.1)

рЫ/хм)' Р(У2/ХМ) ••• P{VN/XM)

В случае ДСК имеем

рДСК _ ( 1 - е
[
1 е ) >
?


Из симметрии переходов следует, что равномерное распределение
символов на входе канала влечет за собой равномерное распреде-
ление выходных символов.
Выпишем условные и взаимные информации всех возможных пар
событий, предполагая равномерное распределение входных симво-
лов. Для ДСК имеем

/(2/1 /xi) = - log2p(yi/xi) бит = - Iog2(l - е) бит
= -log 2 p(2/ 2 /zi) бит = -log 2 e6HT . .
1{У2/х\)
бит = -log2e6HT
1{у\/х2) = -\og2p(yi/x2)
= ˜log2p(y2/x2) бит = - I o g 2 ( l - <г) бит.
1{У2/х2)

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

= log2 P { l ) {
бит = log2 = (1 + lo g 2 (l - е))бит
^ ˜^


y2) = log2 % ^ р бит = log2 щ = {1 + log2 e) бит (7.4)
;




\ Vi) = log2 — р у - бит = log2 — = (1 + log2e) бит

{
= log2 ^ ^ бит = log2 ˜f = (1 + Iog2(l - е))бит.

Рассмотрим три особых случая
1. ? = 0 (передача без ошибок)
-f(zi;t/i) = 1{х2\У2) = 1 бит.
Других взаимных информации не существует, так как пары
взаимных символов (cci,j/2) и (x2,yi) никогда не могут появит-
ся. Информация передается от источника X к источнику У без
потерь.
87]
7.2. Двоичный симметричный канал

2. Е = 1/2. Для всех нар символов (x{,yj) имеем

1/2 бит =
/№; Vj) = bg 2 °-
YJ2

Источники X и Y независимы. Передачи информации не про-
исходит.

3. е = 1. В этом случае или какие-то вероятности перепутаны, или
мы где-то полностью заблуждаемся. Обнаружив этот факт и
нроинвертировав принятые символы yi, мы придем к первому
случаю.

В заключении рассмагрим поведение условной I(yi/xi) = 1{у\/х\)
и взаимной I{yi\Xi) = I(y\;xi) информации в ДСК как функций
вероятности ошибки е.

Переданная Неопределенность
информация вносимая каналом



1

0,8

[бит]
\>
!.
0,4
0,2

0
? — » О.5
О 0,1 0,2 0,3


Рис. 7.3. Условная l(yi/xi) и взаимная информация


Условную информацию 1(уг/х,) можно рассматривать как неопре-
деленность, вносимую каналом, а взаимную информацию I(yi\Xi)
как информацию, передаваемую по каналу. При передаче одного
двоичного символа е = 0, информация передается без потерь, поэто-
му I{Vi/xi) = 0, a I(yi;Xi) = 1 бит. С ростом вероятности ошибки
;, неопределенность, вносимая каналом, возрастает, а передаваемая
информация, наоборот, убывает. При е = 0,5, передача информации
отсутствует, поэтому I(yi/xi) = 1, a I(yi\Xi) = 0. Сумма же условной
4yi/%i) и взаимной I{yi\Xi) информации не зависит от е и всегда
равна одному биту.
Глава 7. Дискретные каналы без памяти


7.3. Передача информации
После рассмотрения отдельных нар событий в предыдущем разделе,
вернемся опять к модели передачи информации. На рис. 7.4 показана
исходная ситуация.
Описание канала с помощью переходных вероятностей сводится,
в конечном счете, к совместным вероятностям нар событий. С этой
точки зрения, оба источника в модели передачи информации равно-
значны, поэтому подразделять источники на передатчик и приемник,
имея в виду направление передачи информации, здесь и в дальней-
шем не всегда имеет смысл.


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

Алфавит Условные вероятности Алфавит
ptyjlx,) и pOc,lyi)
X = {xt, х2,..., х„] ?={У1.У2.-Ун)
Вероятность р(хд Вероятность р(уд
Совместная вероятность




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

В главе 4 (см. таб. 4.3) совместная энтропия двух источников
определена как математическое ожидание информации всех возмож-
ных пар событий
H(X,Y)
(7.5)
бит
X Y

Точно так же определяется условная энтропия


X Y
(7.6)
fj( V/V\

б и т

Л I


Из этого следует

H{X,Y) = H{Y) + ЩХ/Y) = Н{Х) + H{Y/X) (7-7)

и
(7.8)
H(X,Y)<H(Y)
7.3. Передача информации

причем, знак равенства имеет место только для независимых источ-
ников.
В случае двух источников, связанных каналом, совместная неопре-
деленность снижается, так как событие одного источника позволяет
заранее предполагать событие другого источника. С точки зрения
теории информации, снижение неопределенности означает обмен ин-
формацией между источниками. Рассуждая аналогично, приходим к
выводу, что среднее значение информации, передаваемой по каналу,
определяется как математическое ожидание взаимных информации
всех пар событий.

Среднее значение информации, которым обмениваются два дис-
кретных источника без памяти X и У, равно




Замечание. Обратите внимание на знак «минус» в левой части
равенства и знак «плюс.» перед правой частью.

Из определения передаваемой информации следует



X У

-H(X/Y) бит
(7Л0)




н(Х) бит

и, поэтому,

ЦХ; Y) = Н{Х) - H(X/Y) = H(Y) - H{Y/X). (7.11)

В этом месте опять возникает вопрос о сущности аксиоматического
определения энтропии. В качестве «пробного камня» докажем спра-
ведливость следующего утверждения.
Глава 7. Дискретные, каналы без памяти

Теорема 7.3.1. Передаваемая информация I(X;Y) всегда неотри-
цательна, причем, она равна нулю только для независимых источ-
ников X и Y ,
(7.12)
1(Х;У)>0.

Доказательство.
При доказательстве будем исходить из определения I(X; Y) и ис-
пользуем три приема. Во-первых, воспользуемся оценкой функции
натурального логарифма (2.19). Во-вторых, без ограничения общно-
сти будем рассматривать только такие пары символов, вероятность
которых отлична от нуля. В третьих, в аргументе логарифмической
функции из (2.19) поменяем местами числитель и знаменатель, что
эквивалентно умножению логарифмической функции на минус 1, по-
этому, нам достаточно доказать справедливость неравенства

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

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

ОГЛАВЛЕНИЕ

Следующая >>