Вернер М. Основы кодирования (2004), страница 11

ВведениеВ главе 4 были рассмотрены два связанных источника информации.Были введены такие ключевые понятия как совместные, взаимныеи условные информации пар событий (символов) для связанных источников. На их основе мы пришли к фундаментальным понятияминформации - совместной, взаимной и условной энтропии. (См.

табл.4.3). Там же было отмечено, что совместная и условная энтропииимеют аналоги в теории вероятностей и определяются как математические ожидания совместных и условных информации всех парсобытий двух источников.ПередатчикПриемникИсточникИсточникXКРис. 7.1. Модель передачи.Мы продолжим эти рассуждения, уделив основное внимание взаимной энтропии. Для описания каналов передачи информации используем концепцию двух связанных источников.

Оказывается, чтос помощью понятий, введенных в главе 4, удается полностью описатьпроцесс передачи информации по каналам без памяти. В результате, мы оценим возможность передачи информации по каналу, т.е.пропускную способность канала.В Шенноновской модели канала связи информация одного источника (передатчика) передается по каналу приемнику и выдаетсяпотребителю. Для потребителя имеет значение только выход приемника, т.е. приемник сам является источником информации, поэтому,7.2. Двоичный симметричный каналмодель связанных источников полностью применима к цепочке Передатчик - Канал - Приемник (рис. 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)1{У2/х\)1{у\/х2)1{У2/х2)= - log2p(yi/xi)= -log 2 p(2/ 2 /zi)= -\og2p(yi/x2)= ~log2p(y2/x2)бит = - Iog2(l - е) битбит = -log 2 e6HTбит = -log2e6HTбит = - I o g 2 ( l - <г) бит...О т с ю д а следует= log2 P;{^l)бит = log2{~^y2) = log2 % ^ р бит = log2 щ= (1 + lo g 2 (l - е))бит= {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 к источнику У безпотерь.7.2. Двоичный симметричный канал2. Е = 1/2. Для всех нар символов (x{,yj) имеем/№; Vj) = bg 21/2YJ2бит =°-Источники X и Y независимы. Передачи информации не происходит.3. е = 1. В этом случае или какие-то вероятности перепутаны, илимы где-то полностью заблуждаемся. Обнаружив этот факт инроинвертировав принятые символы yi, мы придем к первомуслучаю.В заключении рассмагрим поведение условной I(yi/xi) = 1{у\/х\)и взаимной I{yi\Xi) = I(y\;xi) информации в ДСК как функцийвероятности ошибки е.ПереданнаяинформацияНеопределенностьвносимая каналом[у10,8[бит]0,4\>!.0,20О0,10,2Рис.

7.3. Условная l(yi/xi)0,3£ — » О.5и взаимная информацияУсловную информацию 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) информации не зависит от е и всегдаравна одному биту.87]Глава 7. Дискретные каналы без памяти7.3. Передача информацииПосле рассмотрения отдельных нар событий в предыдущем разделе,вернемся опять к модели передачи информации.

На рис. 7.4 показанаисходная ситуация.Описание канала с помощью переходных вероятностей сводится,в конечном счете, к совместным вероятностям нар событий. С этойточки зрения, оба источника в модели передачи информации равнозначны, поэтому подразделять источники на передатчик и приемник,имея в виду направление передачи информации, здесь и в дальнейшем не всегда имеет смысл.Источник¥ИсточникXАлфавитX = {xt, х2,..., х„]Условные вероятностиptyjlx,) и pOc,lyi)Вероятность р(хдСовместная вероятностьАлфавит¥={У1.У2.-Ун)Вероятность р(удР и с . 7.4.

Два дискретных источника без памяти, связанныеканалом.В главе 4 (см. таб. 4.3) совместная энтропия двух источниковопределена как математическое ожидание информации всех возможных пар событийH(X,Y)бит(7.5)XYТочно так же определяется условная энтропияXYЛIV/V\fj(би(7.6)тИз этого следуетH{X,Y) = H{Y) + ЩХ/Y) = Н{Х) + H{Y/X)(7-7)иH(X,Y)<H(Y)(7.8)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,1(Х;У)>0.(7.12)Доказательство.При доказательстве будем исходить из определения I(X; Y) и используем три приема.

Во-первых, воспользуемся оценкой функциинатурального логарифма (2.19). Во-вторых, без ограничения общности будем рассматривать только такие пары символов, вероятностькоторых отлична от нуля. В третьих, в аргументе логарифмическойфункции из (2.19) поменяем местами числитель и знаменатель, чтоэквивалентно умножению логарифмической функции на минус 1, поэтому, нам достаточно доказать справедливость неравенстванатТак как, в силу сделанного, нами ограничения, суммы берутся толькопо парам (х, у), для которых р(х, у) ф 0, аргумент логарифмическойфункции v ? s всегда имеет отличное от нуля конечное положительное значение, поэтому, используем оценку (2.19)натху0ФЫX(7Л4)^ VР(Ф)1 < о.YЕсли бы (7.12) не выполнялось, передача информации не снижалабы энтропии (т.е.

определенность источника не повышалась бы).То, что переданная информация всегда неотрицательна и всегда справедливы равенства (7.11) и (7.7), лишний раз подтверждаетсправедливость следующих утверждений:Любое ограничение не может повышать неопределенность источникаН(Х) > H(X/Y).(7.15)917.3. Передача информацииСовместная энтропия достигает своего максимума, когда источники независимыЩХ, Y) < Н(Х) + H(Y).(7.16)Найденные зависимости можно наглядно пояснить при помощидиаграммы потоков информации (рис.7.5). Диаграмма помогает уяснить смысл условных энтропии H{X/Y) и H(Y/X).Утечка информацииH(X/Y)Энтропия навходеканала Н(Х)Переданная информацияH(X)-H(X/Y)= I(X; Y)=H(Y)-H(Y/X)Энтропия навыходеканала Н(¥)Н(¥/Х)Посторонняя информацияР и с .