Кловский Д.Д. Теория электрической связи. Сборник задач и упражнений (1990) (1151854), страница 38
Текст из файла (страница 38)
Следо- вательно, в т-ичном симметричном канале вероятности переходов удовлетворяют условиям р(Ь )1 ) 1 Р при /=!о р/(т — 1) прн /~ь1. Подставляя эти вероятности в выражение (4.11), находим эн- тропию шума о! о~ Н(В)В) — ~ ~', Р(Ь) Р(Ь~)Ь!) )ойр(Ь )Ь!). )=ое-! )89 Выделяя нз этой суммы слагаемые с номером т=!', получаем Н (В[В) = — ~', Р(Ь!) (1 — р) !од(1 — р)— ! ! — ~'„2, 'Р(5!) Р [ок )-! !м! = — (1 — р) [оя (1 — р) — р [оц 4.2.4.
Согласно формуле (4.12) находим скорость передачи нн- формации 1'(В, В) =гн!(В, В) =п„(Н(В) — И(В~В)1. Как показано в решении задачи 4.2.1, ненадежность двоичного симметричного канала со стиранием прн ро-!-0 Н(В~ В) =р,Н(В). Следовательно, скорость передачи информации в таком канале 1'(В, В) =сн(Н(В) — р,Н(В)! =пнН(В) (1 — р,).
Чем больше вероятность стирания р„тем надежнее отождест- вляются символы 1 н 0 в месте приема, однако одновременно па- дает скорость передачи ннформацнн по каналу. Следовательно, имеет место обмен между верностью (качеством) н колнчест- вом переданной информации. 4.2.8. Согласно (4.13) пропускная способность канала С= п„!пах (Н (В) — Н (В ) В) ), Как показано в решении задачи 4.2.2, энтропия шума т-нчно- го симметричного канала без памяти н без стирания равна Н (В [ В) = — (1 — р) [оя (1 — р) — р [оя С учетом этого имеем С = ои [шах Н (В) + (1 — р) [од (1 — р) + р [оц Очевидно, что гпахН(В) =[ори. Следовательно, С = пн [[ой и+ (1: р) [оя (1 — р) + р [оя Для двоичного симметричного канала без памяти н стирания (т=т'=2) С=о,(1+р[од р+ (1 — р) [оп(1 — р) ].
График величины С!и, в зависимости от р показан на рнс. Р.4.3. Пропускная способность канала равна нулю, когда вероятности перехода Р(0~11) =Р(110) =05. (В этом случае символы на входе н выходе оказываются независимыми.) 4.2.8. Избыточность кода (вторнчного алфавита) можно опре- делить по (4.4): м„=[ — Н(В)!И „,(В), 190 где Н(В) — энтропня ансамбля кодовых сФ„ символов. Очевидно, что прн объеме ансамбля кодовых символов т Н„,„.(В)= =!оп т. Следовательно, ! хси Н (В) В' (В) [оя пт ин (оя пх где Н'(В) =п„Н(В); п„— число кодовых снмволов, поступающих на вход канала в йб 'л единицУ вРемени.
ПосколькУ пРн коднРо- ри р4 Рис. Р.4.3. Зависимость ваннн должны отсутствовать потери ннфор- нормированной пропускмацнн, то Н'(В) =Н'(А) =п„Н(В), где ной способности двоичо„— число снмволов, создаваемых нсточнн- ноно симметричного паком сообщения в единицу времеви; Н(А) — энтропия нсточннка.С учетом этого приеме символа ои В ('1) мн он )оя Iп Согласно теореме Шеннона лишь прн инН(А) (С существует оптимальный способ кодирования.
Следовательно, избыточность кода не может быть меньше величины С мн.мии +е, о„)оя пх где е — сколь угодно малая положительная величина. Для двоичного симметричного канала без памяти н стирания согласно решению задачи 426. С=о„(1+р[од р+ (1 — р) [оя (1 — р)). Подставляя эту величину в выражение н,, „н учитывая, что т= =2, получаем он [1+ р )акр+ (! — р) )ой(1 — р)1 Мн,мии +а о„)оях 2 = — р [оа р — (1 — р) [од (1 — р) + е. Если р=О (в канале нет ошибок), то х,,„.„=е- О. Если р= =0,01, то ин ни-0,067, т. е, прн не очень сильных помехах в канале избыточность оптимального кода невелнка.
4.2.9. Способы кодирования н декодирования, обеспечивающие сколь угодно малую вероятность ошибки, согласно теореме Шеннона, существуют лишь прн Н'(А) (С. Если источник информации выдает в единицу времени о. символов, а его энтропия Н(А), то Н'(А) =пнИ(А). Пропускная способность канала по определению равна С=нишах!(В, В).
Следовательно, можно записать, что оптимальное кодирование по Шеннону возможно лишь прн пиИ(А) - пншах1(В, В) нлн й= — ") . Здесь й— юах! (В, В) среднее число символов кода на одни символ источника. 4.2.10. Из (4.!5) получаем запас пропускной способности С вЂ” Н' (А) я" ро я' 90,96 бнт!с. т зю,(о — з 191 Подчеркнем, что чем больше запас пропускной способности, тем легче реализуется система связи, но одновременно падает ее 1аяа Рош эффективность.
Очевидно, что Т =— С вЂ” Н' (А) Поэтому при сохранении вероятности ошибки (качества связи) неизменной уменьшение запаса пропускной способности в 2 раза (рост эффективности системы) влечет за собой увеличение дли- тельности кодовой комбинации в 2 раза, что приводит к усложне- нию системы (в частности, из-за усложнения устройств памяти на передаче и приеме). 4.2.11. Предположим, что можно закодировать некоторый ис- точник с производительностью Н'(А)=С+2э, а.аО так, что не- надежность канала Н'(А*!А) (е. Тогда оказывается, что скорость передачи информации в системе связи 1(А,А) =Н'(А) — Н'(А ~А) ) )С+э, т. е. будет больше пропускной способности канала, что противоречит ее определению. Противоречия не будет, если до- пустить, что при Н'(А) ~С сообщение передается с отличной от нуля ненадежностью Н'(А !А) )е.
4.2 12. При кодировании по методу Хаффмена все символы ис- точника располагают в порядке убывания вероятностей. Если не- сколько букв имеют одинаковые вероятности, их располагают ря- дом в произвольном порядке. Затем выбирают две буквы с наи- меньшими вероятностями, и одной из них в качестве первого сим- вола двоичного кода приписывают символ О, а дру~ой — символ 1, Выбранные буквы объединяют в «промежуточную» букву, имею- щую вероятность, равную сумме вероятностей выбранных букв.
Затем в ансамбле оставшихся букв (вместе с промежуточной) вновь находят две с наименьшими вероятностями и поступают так же, как и на первом шаге. Эту процедуру осуществляют до тех пор, пока не будет исчерпан весь алфавит. Процесс кодирования показан в табл. Р.4.2. Средняя длина коз довой комбинации данного кода й= Х инва=3,08. Минимальная ! ! длина кодовой комбинации примитивного кода, которым можно закодировать данный алфавит, 5,„„= 1оя К1!од т= 4. При оптимальном двоичном кодировании в канале без шумов 9 йа,„=Н(А)1!одт=Н(А)= — Х р, (одр;=3,04. 1=1 Средняя длина кодовой комбинации кода Хаффмена отличает- ся от средней длины оптимального кода на . 100% = 1,32%, 3,04 что позволяет считать код Хаффмена близким к оптимальному, 4.2.15.
Кодирование по методу Шеннона — Фана осуществля- ется следующим образом. Все буквы записываются в порядке 192 Таблаца Р,42 убывания их вероятностей. Затем вся совокупность букв разбивается на две примерно равновероятные группы. Всем буквам верхней группы приписывается первый кодовый символ 1, а буквам нижней группы — символ О. Затем каждая группа аналогичным образом разбивается на подгруппы по возможности с одинаковыми вероятностями, причем верхним подгруппам в обеих группах приписывается символ 1 (второй кодовый символ), а нижним — символ О. Эта процедура осуществляется до тех пор, пока в каждой подгруппе не останется по одной букве.
Процесс кодирования по Шеинону — Фано иллюстрируется табл. Р.4.3. Средняя длина кодовой комбинации в и ~',и1р;=2,75. !=! Прн оптимальном двоичном кодировании в и, = Н(А) = — ~„'р, !оп р, =2,75, 1=1 Та блица Р.4.3 7 — бз 193 Следовательно, в данном случае код Шеннона — Фано является оптимальным. РЕШЕНИЯ И УКАЗАНИЯ К РЕШЕНИЮ ЗАДАЧ й 4.3. 43..(. Рассмотрим сечение случайного процесса Х(»), предположив, что процесс в этом сечении имеет плотность вероятности п»»(х).
Разделим область изменений Х на дискретные уровни х» с малым интервалом Лх между ними. Вероятность того, что значение Х лежит в интервале (х», х»+Лх), приближенно равна р»= =гр»(х») Лх. Будем считать, что отдельные отсчеты случайного сигнала Х(») независимы, а их распределение не зависит от времени (стационарный источник без памяти). Тогда согласно (4.3) можно записать выражение для энтропии на один отсчет квантованного сигнала: Нд„(Х) = — 2',ц»»(х») Лх!ок [в»,(х,) Л х] = = — 2', и»» (х») Лх 1оя [»р» (х»)] — 2', и», (х») Лх [оц Лх. » Чтобы непрерывный отсчет воспроизвести абсолютно точно, необходимо, чтобы Лх-~0.
Заменив тогда суммы соответствующими интегралами, найдем энтропию одного отсчета непрерывного сигнала »О Н(Х) = — ['п»,(х)!од»р»»(х)»(х — Вт!ойЛх ['ш,(х)»(х= д.»-»0 — ]'»р, (х) 1ой и»» (х)»(х — 1!ш 1од Лх. дк 0 Так как !пп 1оаЛХ= — ор, Н(Х) =со. Полученный результат оздх- о начает, что один непрерывный отсчет сигнала мог бы перенести бесконечно много информации, если была бы возможность воспроизвести его абсолютно точно. К сожалению, в реальных каналах этой возможности нет.
4.3.2. Подставим в (4.16) выражение плотности вероятности гауссовского случайного процесса: Х ~-[ой)72ла' — ",*) !оае~»(х. Вводя новую переменную (х — т„)/о и интегрируя, получаем Ь(Х) =!од У 2пео». Следовательно, величина Ь(Х) не зависит от т„. 194 4.3.3. Условная дифференциальная энтропия может быть определена по формуле Ь (Х]Х»»р) 1 ( ы»» (х» хпр) 1ой»Р» (х!х»»р)»(х»(хрр Согласно [3] и», (х]х,р) = ехр à —, (х — х,р Й)'~, ')»'2я»»» (! — й')» 2»»» (1 — )2») 1 Г 1 Подставляя эти выражения в соотношение для условной диф- ференциальной энтропии, получаем х ] — 1оаУ2па' (1 — )»Р) — (х — х, М)Р 1од е!»(Х»(х 2»7» (1 — )7») После простых преобразований имеем Ь(Х]Х,р) = 1оа]/2п ео'(1 — Я'), Обратим внимание на то, что с ростом нормированной корре- ляционной функции условная дифференциальная энтропия умень- шается.
4.3.6. Указание к решению. Принять во внимание, что выход- ной сигнал У(!) =Х(!)+М(!) при гауссовских и независимых про- цессах Х(!) и М(() будет иметь гауссовское распределение и дис- персию о'р — — о'„+а' . При вычислении условной дифференциаль- ной энтропии учесть, что » ]'»и, (х) и»» (у] х)»(х = и», (у). 4.3.7. По определению Н,(Х) =т!п1(Х, Х) =Ь(Х) — тахЬ(Х]Х). Поскольку Х(()» Х(() — М(!), то условная дифференциальная энтропия Ь(Х]Х) при заданном сигнале Х(() полностью определяется шумом воспроизведения (каиала) М(() .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
