Вернер М. Основы кодирования (2004) (1151882), страница 14
Текст из файла (страница 14)
Теорема кодирования для дискретных каналов без памяти107)С из (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дг,="О"Источник X0,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 дано определение энтропии как меры неопределенностиисточника. При этом предполагалось, что энтропия измеряется посредством случайных экспериментов. В данной главе мы будем применять аналогичный подход к непрерывным источникам.ИсточникX«г\/ \StРис. 8Д. Сигнал непрерывного источника.Вместо источников с конечным алфавитом символов будем рассматривать источники, выходом которых являются непрерывные сигналы. Примером таких сигналов может служить изменяющееся вовремени напряжение в телефонных каналах и т.д. На рисунке 8.1представлен непрерывный источник X, выходом которого являетсяаналоговый сигнал x(t), являющийся некоторой случайной функцией от времени t.
Будем рассматривать значения x(t) в некоторыефиксированные моменты времени как случайные эксперименты, которые несут некоторую информацию об источнике X.8.1. Дифференциальная энтропияНа рисунке 8.2 показаны два непрерывных источника X и У, связанные каналом (аналогично рис. 7.4). Здесь, вместо вероятностей,стоят функции плотностей распределения вероятностей стохастических переменных.Использование стохастических неременных и их функции плотностей распределения вероятностей-позволяет вводить понятие ин-I 10Глава 8. Непрерывные источники и каналыформации, энтропии, условной и взаимной энтропии для двух непрерывных источников по аналогии с дискретными источниками.ИсточникXИсточникYПлотностьраспределенияПлотностьраспределения )Плотностьределен„ярасПjР и с . 8.2.
Два непрерывных источника без памяти, связанных каналом.Преобразуем непрерывный источник X в дискретный. Для этого проквантуем значения аналогового выхода источника с шагом Д(рис. 8.3).ИсточникXР и с . 8.3. Оцифровка непрерывного источника с интервалом квантования Д в моменты наблюдения to, tiи т.д.Кроме этого, как это обычно делается в теории информации, произведем дискретизацию источника по времени. В результате, получим последовательность стохастических переменных Xo,Xi,X2,Следуя таблице 7.2, определим взаимную информацию символов а^и yj, где Xi - значение выходного символа в момент времени tm, a Xj- в момент времени tn= logP{\Xi - А < ХтР(1; - А < ХтIJбит< Xi] П |j - А < Хп << Xi)P(Xj-А<Хп<fxmxn{xi^x2)dxidx28.1. Дифференциальная энтропияВзаимную информацию можно трактовать как «снятую» (утраченную) неопределенность попадания переменной Хп в интервале[XJ — A,Xj[, когда известно, что переменная Хт принадлежит интервалу [xi — Д,Xi[ или наоборот.
Будем считать функцию плотностираспределения вероятности непрерывной функцией. Тогда, устремляя ширину интервала квантования к нулю, получимXiXjJJfxmxn(xi,x2)dxidx2/ fxm{xi)dxxXi-ДAfv(T-\Afv(r)JXj-Д•fv(rAfv(T-Yт.е. результат, аналогичный выражению взаимной информации длядискретных источников. Передаваемую информацию можно определить как математическое ожиданиебит( 8 3 )Замечание. Здесь, для приведения в соответствие обозначенийэтой главы с результатами таблицы 7.2, вместо Хт используетсяX, а вместо Yn - Y.Информация источника определяется исходя из аналогичных рассуждений^= - log2 Р([ХГ -А<Х<]) =Xi(8.4)XiX= -log2 J }x{xi)dx^ХГ-А'-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.битJ оо(8.5)Прежде всего отметим, что такое произвольное определение дифференциальной энтропии подтверждает свою пригодность тем, чтоэнтропийные отношения для дискретных источников оказываютсясправедливыми и для случая непрерывных источников и каналов.
Вчастности, для непрерывных источников имеют место соотношения(7.39) - (7.42).Таким образом, дифференциальная энтропия непрерывного источника зависит только от функции плотности распределения вероятности, которая в общем случае является бесконечной величиной,поэтому, поставим вопрос о том, как велико может быть значениедифференциальной энтропии. Прежде всего отметим, что характеристиками стохастического процесса являются две величины: среднее значение, которое принимает стохастическая неременная (обладающая свойством линейности) ц и стандартное отклонение стохастической переменной а.Среднее значение или математическое ожидание /i не оказываетникакого влияния на дифференциальную энтропию.
С ростом же а,неопределенность источника возрастает, что приводит также к возрастанию дифференциальной энтропии. В связи с этим, сравнениеразличных функций плотностей распределения вероятностей относительно соответствующих им энтропии имеет смысл производитьпри одинаковых <х.Замечание.
В информационной технике за исходный параметрпринимают <т2 - дисперсию, которая определяет среднюю мощность стохастического процесса /10/. Ясно, что с увеличениеммощности передатчика, количество передаваемой информации увеличивается и, наоборот, с увеличением мощности шумов, возрастает неопределенность, т. е. в единицу времени передается меньшеинформации.8.1. Дифференциальнаяэнтропия113,Из теории информации следует, что дифференциальная энтропиядостигает своего максимума при гауссовском распределении вероятности.Теорема 8.1.1.
При заданной дисперсии а2, максимальной дифференциальной энтропией обладает источник с гауссовским распределением, вероятности, причем,HGaus(X) = ~Vb 2' бит.(8.6)Пример: Дифференциальная энтропия гауссовского источника.Из (8.5) следует, что дифференциальная энтропия гауссовскогоисточника равнаЩХ)+ООВыражение в квадратных скобках может быть разложено на два интеграла. Таким образом, окончательно имеем+нат°°/ x2 ехр (2<T2V2^J•V,2J dx =2aЧисленные примеры для трех, наиболее употребительных распределений, приведены в таблице 8.1.Пример: Телефония.Практическая польза приведенных выше результатов может бытьнаглядно показана при помощи оценки достижений скорости передачи информации (в битах) в цифровых телефонных линиях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
