Кловский Д.Д. Теория электрической связи. Сборник задач и упражнений (1990) (1151854), страница 14
Текст из файла (страница 14)
Количество информации 1(В, В)=0, если символы на входе и выходе независимы (очень сильные помехи или обрыв канала связи), и 1(В, В) =1(В), если помехи отсутствуют. Из (48) следует, что определяет информацию (энтропию) выходных символов канала. Часть этой информации является полезной (информация о входных символах Ь,).
Остапа. ная часть информации является .тожной (созданной помехами в канале). Веля. чина Н(В/В) =1(В)В) определяет информацию, содержащуюся в последовательности выходных символов В при известной последовательности входных символов В. Поскольку выходная последовательность отличается от входной исключительно из-за помех в канале, то Н(В~В) характеризует информацвю имен. но о помехах в канале или энтропию шума: Н (В)В) =- — 2', 2; Р(Ь;, Ьу) )ойР (Ь1(Ь;). (4. 11) 1=1 1=3 Если на вход дискретного канала поступает в среднем о, символов в единицу времени, то можно определить среднюю скорость передачи информации по каналу с шумами; 1'(В, В) =о„1(В, В) =Н'(и) — Н'(В!В) =Н'(8) — Н'(В)В).
Здесь Н'(В) — производительность источника на входе канала; Н'(В~В) — ненадежность канала в единицу времени; Н'(В) — производительность источника, образованного выходом канала; Н'(В!В) — количество ложной информации, создаваемой шумом в единицу времени. Пропускной способностью канала назынается предельная скорость передачи информации при заданныт своиствах канала (заданной помеле) Для дн. скретного канала пропзскиая способность причем шах ищется по всем возможным источникам входа при заданном и, и объеме алфавита символов входа ш*. С понятием пропускной способности канала связана одна из важнейших теорем теории информации — основная теорема К.
Шеннона об оптимальном кодировании. Применительно к дискретному источнику эта теорема гласит: если производительность источника сообщений меньше пропускной способности канала то сущестпует способ оптимального кодирования и декодирования (преобразования сообщения в сигнал на передаче н обратного его преобразования в сообщение на приеме), прн котором вероятность ошибки может быть сделана как угодно малой.
Если Н'(А) З»С, такого способа не существует, Средняя вероятность ошибки при оптимальном кодировании определяется соотношением 2 — тьс — ыцли (4. 15) где Т вЂ” длительность сигнала, соответствующего последовательности символов источника достаточно большой длины л; С вЂ” Н'(А) — запас пропускной способности канала, Для дискретного канала без шумов теорема оптимального кодирования формулируется следующим образом; если производительность источника меньше пропускной способности канала, то существуют способы кодирования, прп которых передача сообщений может осуществляться со скоростью где и — скорость передачи двоичных кодовых символов; а — как угодно махач положительная величина, Из этой теоремы следует, что при оптимальном (по Шеннону) кодировз. нни можно на один символ источника затратить 4.2.1.
Найти, ненадежность О(В(В),и энтропию шума двоично- го симметричного канала со стиранием (рис. 4.1) с вероятностями переходов Р(0)0) = Р(1!1) = 1 — рэ — рс', Р(г(0) = Р(9)1) = рс', Р(110) =Р(0)1) =рэ и ап~риорными вероятностями символов Р(0) и Р(!) =1 — Р(0). 4.2.2. Показать, что в симметричном и-ичном канале без па- мяти и стираний энтропия шума определяется выражением Н(В) В) = — р)ой.(р/(и — !) 1 — (1 — р)!оп (1 — р), где р — суммарная вероятность ошибки. ' Строго говоря, С следует определить как наименьшую верхнюю границу от !(В, В), так как одно единственное максимальное значение скорости по всевозможным источникам входа может и не существовать 69 Рнс. 4.1.
Граф двоичного симметричного канала со стиранием Вариант !о Н(В) 1О-', бнт/сим- вол Н(В) 10-', бнт)снам вол Н(В(8) 10-', бнт/ символ 10 8 7 9 10 200 800 4 9 9 15 400 900 !2 200 1000 290 200 800 4.2.8. На вход дискретного канала поступает Н(В) бит/символ, а по каналу в среднем .передается 1(В, В) бит/символ полезной информации. Энтропия шума в канале Н(В'(В) бит/символ. Найти ненадежность канала ~и энтропию выходных си~мволов. Определить производительность источника,на входе канала, ненадежность канала в единицу времени, среднюю скорость передачи информации по каналу и скорость создания ложной информации в канале, если на вход .канала поступает в срвднвм оа символ/с (значения Н(В), 1(В, В), Н(В~)В), пн даны в табл.
4.7). Таблица 4.7 8 9 ~110 Вариант Н(В) 7(В, В) Н(В(В] 20 10 40 50 40 30 60 40 чо 70 120 90 40 20 60 70 80 40 120 60 70 60 100 юо 50 20 80 100 80 30 90 75 200 !Оо 300 100 60 50 90 80 4.2,8. Показать, что для тиичного симметричного канала без памяти и стирания с ввроятиостями переходов ('1 — р при 1=!', Р (67(Ь!) = ( р ! — при /ФЕ (и — 1 70 г-ла-ри „4.2.8. Найти энтропию шума в двоич- Ю ном канале без памяти по заданной энтропии источника на входе канала о Н(В), энтропии источника, образованРа р* ного выходом канала Н(Й) и ненадежности канала Н(В!В) (значвния Н(В), Н(В), Н(В(В) даны в табл. 4.5). г ра ла 4.2,4. Показать, что при вероятности ошибки, стремящейся к нулю, скорость передачи информации по двоичному симметричному каналу со стиранием (задача 4.2.1) определяется соотношением Р(В, Я)=о„(1 — р,)Н(В), где о„— число символов, поступающих на вход канала в единицу времени. Таблица 4.6 пропускная способность определяется соотношением С = пи ~ 1оа гп + (1 — р) 1оа (! — р) + р 1ой У!простить эту формулу для двоичного канала.
Построить график зависимости пропускной способности двоичного канала от вероятности ошибки. 4.2.7. Найти пропускную способность гп-ичного симметричного канала без памяти и стирания по числовым значениям, приведенны~м,в та|бл. 4.8. 'Таблица 48 1О Вариант 700 8 0,02 1000 3 0,01 500 10 0,01 300 4 0,015 500 8 О,!5 200 800 3 7 0,2 0,02 700 4 0,1 700 6 0,01 .ам Оа гн Р 6 0,003 4.2.8.
Показать, что избыточность оптимального по Шениону кода определяется соотношением м,,„„,=1 — С/(Он!сд т)+в (е — сколь угодно малая положительная величина). Найти минимально возможную, избыточность оптимального кода для двоичного канала при,вероятности ошибки р=О и 0,5.
4.2.9. Показать, что способы кодирования и декодирования, обеспечивающие сколь угодно малую вероятность ошибки, существуют лишь ~в случае, когда срвднее число си~мволов кода,на один символ источника удовлетворяет условию — вн Н (А) и= — ) снах! (В, В) 4.2.10. Какой запас пропускной способности С вЂ” Н'(А) должен иметь канал, чтобы при использовании оптимального кода с длительностью кодовой комбинации 7=100 мс ввроятность ошибки не превысила величину 10 аР Во сколько раз изменится длительность кодовой комбипаци~и оптимального кода, вол~и при неизменной вероятности ошибки запас пропускной способности канала уменьшается и 2 раза? 4.2.11.
Показать, что ввроятность оши~бки в канале с шумами не ~может быть сколь угодно малой, если пропускная способность канала С меньше производительности Н'(А). 4.2.12. Некоторый дискретный источник выдает символы из ансамбля (а;), 1=1, 9 с вероятностями, приведенными в табл. 4.9. Закодировать символы данного ансамбля кодом Хаффмена. Построить граф кода и определить среднюю длину кодовой комби- 71 Таблица 4.9 Свмввл а, аа ла ав 0,1 0,1 0,05 0,06 0,15 0,15 0,12 0,04 (4.20) 0,2 Р(а,) (4.22) (4.
25) (4. 26) й<Х)--: . )" и',(х)1ояш,<х]г<х <4 !6) (4.27) Задачи йч„,(Х) =)оя У'2лепз, (4.19) 73 72 нации. Сравнить полученный ~результат с минимальной длиной кодовой комбинации при кодировании равномерным двоичным кодом. Показать, что код Хаффмена близок к оптимальному по Шеннону коду. 4.2.13. Закодировать кодом Хаффмена символы источника, появляютциеся с вероятностямл Р(а|) =Р(аз) =1/4, Р(аз) =Р(ав) = =1/8, Р(аз) =Р(а,) =Р(ат) =Р(а,) =1/16. Какую экономию в числе кодовых разрядов на один символ источи~яка дает этот код по сравнению со случаем ра|вномерного двоичного кода? 4.2,14. Построить код Хаффмена для шести сообщений А, В, С, Р, Е, Р, появляющихся с вероятностями 0,4; 0,25; О,!5; 0,1; 0,05; 0,05.
Построить кодовое дерево, вычислить среднюю дл~ину кодовой комбинации и сравнить ее с энтропией сообщения. 4.2.15. Закодировать двоичным кодом Шеннона — Фаио ансамбль сообщений (а!), 1=1,8, если вероятности символов имеют следующие значен~ия: Р(а!) =Р(а,) =1/4; Р(а,) =Р(ав) =1/8; Р(аз) =Р(а,) =Р(а,) =Р(аз) =1/16.
Найти среднее число разрядов в кодовой комбинации. Показать, что та~кой код близок к оптимальному. 4.2.16. Построить код Шеннона — Фано для сообщений, заданных в задаче 4.2.14. Вычислить среднюю длину кодовой комбинации и сравнить ее с энтропией сообщения. 4.2.!7. Построить код Шеннона — Фаио для сообщений А, В, С, Р, если оии имеют вероятности а) 0,5; 0,25; 0,125; 0,125; б) 0,6; 0,2; 0,15; 0,05. Для обоих случаев сра~вн~ить среднюю длину ко~девой комбинации с энтропией сообщения.
4.8. ЭНТРОПИЯ И ПРОИЗВОДИТЕЛЬНОСТЬ НЕПРЕРЫВНОГО ИСТОЧНИКА СООБЩЕНИЙ .зля описания ннформзцнонных свойств непрерывного источника широко используется понятие дифференциальной энтропии й<Х): Это тв часть энтропвн непрерывного источника, которая ззвнсги от функции п.шгвостн вероятности сигнала Х «), выдаваемого источником г!зибольшее значение дифференциальной энтропии при неззввснмых отсчетах и заданной дисперсии о' имеет случвйвый процесс Х(<) с гауссовским распределением мшшвенных значений В этом случае По аналогии с формулами для дискретного источника количество информации, содержащееся в одном непрерывном отсчете процесса У(<) относительно отсчета процесса Х(0, определяется формулой ! (Х, У) = ( ~ ш (х, у) 1ой ахс<у. шх (х) ш, (у) Здесь шз(х, у) — совместная плотность вероятности процессов Х(0 и У(1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
