Введение в прикладную комбинаторику, Кофман А. (984071), страница 54
Текст из файла (страница 54)
При несоблюдении этого условия увеличивается риск получить искаженное сообщение (это иллюстрируется на рис. 529). На рис. 529 ~ ~з ---------- — — - — — - — е — возможный скачок зна- % чения хз. Такой скачок приф~ ~Ф вЂ вЂ вЂ вЂ вЂ вЂ вЂ вЂ вЂ -~ †-1 4 водит к смешению сигналов, г — — — - — — — -т — 1 ', ~в соответствующих буквам х„ Колебание сигнала вокруг его среднего значения вызывается «шумом», который можно характеризовать Рис. 529. вероятностью смешения двух разных букв алфавита.
Определение линии передачи. Пусть на вход линии подается г-выборка (Б2.1) А=(а„а„..., ао ..., а„), а на выходе принимается г-выборка элементов «выходного» алфавита (Б2.2) В=(5, рл °, 5Р . ° . р,). Линия характеризуется множеством вероятностей перехода, т. е, вероятностей того, что поданная на вход г-выборка (агр ас,..., а~,) принимается на выходе как г-выборка (йй, йсн ..., 5~,): рг(б,н 5;Р ..., ~, )ай, асл ..., аг ). (Б2.3) Эти вероятности могут зависеть от состояния з, в котором находится вход в момент «испускания» выборки, т. е.
имеют внд рг(5~,, 5~,, ..., 5~ ~аги а~и ..., а~, з). (Б2А) В этом случае говорят о «линии с памятью». В противном случае говорят о «линии без памяти» и тогда рг(РВ Рг, ° ° °, Рс (ай, аин ° ., а~ )=ргф~,)ай)... ргфс )аг !). (Б2.5) В общем случае линия характеризуется случайной величиной Х на входе, принимающей значения хь 1= 1, 2... п, с ве- 440 роятностями ро случайной величиной У на выходе, принимающей значения уя ! = 1, 2, ..., т, с вероятностями пя н матрицей перехода, составленной из элементов р = рг (У = у ~ Х = х,), ! = 1, 2, ..., и; 1 = 1, 2, ..., т. (Б2.6) Имеем (Б2.7) Распределение У целиком определяется распределением Х н матрицей перехода.
Для данной линии распределение вероятностей на входе однозначно приводит к некоторому распределению вероятностей на выходе, но обратное утверждение неверно. Вероятности я!, определяемые формулой я,'=рг(Х=х, ~ У=у ), (Б2.8) ри=рг(Х=х~ и У=у), имеем 1=1, 2...„пл 1=1, 2, ..., т, (Б2.9) Р~Р~ Р~Рг (Б2.10) и/ Ф ~ Ре»! ю=ю Важный частный случай представляет собой двоичная симметрическая линия, которая описывается так: Х еи )х, = О, х, = 1), (Б2.11) Уев(у,=О, у,=1), (Б2.12) (В2.13) (Б 2. 14) р,' = рг (У = 0 ~ Х = 1) = р~ = рг (У = 1 ! Х = 0) = р, р~ ~= рг (У = 0 1 Х = О) = р, '= рг (У = 1 ! Х = 1) = 1 — р=д. Матрица перехода (Б2.15) Граф перехода можно изобразить на рис.
530, а саму линию представить на рис. 531. Характеризующая шум на линии вероятность р называется «вероятностью ошибки» и обозначается через р(е) (см. [26]). Основной проблемой прн передаче информации является ограничение действия шума на линии. Очевидно, что влияние шума тем меньше, чем больше вероятности и( (которые вычисляются по формуле (Б2.10)). Практически задача сводится к 441 можно получить из р, и р' по формулам Байеса. Действительно, полагая тому, чтобы определить правило принятия решения, по которому, наблюдая г-выборку на выходе, можно было бы принять ее или отвергнуть в зависимости от того, подверглось ли сообщение изменению в ходе передачи. Другими словами, надо К у ! К Ряс.
531. Рис. 53Ц 1(Е;) = 1оаь —. ! Рс (Б2.16) Единица измерения информации, конечно, зависит от основания логарифма. Средняя величина информации для полной системы Х попарно взаимноисключающих событий называется энтропией системы и выражается формулой Н(Х)=р!1оць — +р,(оць — + ... +р,1оць — = 1 1 1 Р~ Рь Рп = —,~~1 Р! 1оКь Ро (Б2.17) Таким образом, энтропия определяется как математическое ожидание случайной величины Х, принимающей значения с ! 3 !од» вЂ” с вероятностями рь, 1=1, 2, ..., и, ~! р! =1.
Р! ь=! Можно определить некоторые энтропии для линии связи: Н (Х) †средн величина информации, характеризующая вход, она указывает на качество передатчика; Н(У) — средняя величина информации, характеризующая выход, она указывает на качество приемника; Н (ХУ) — характеризует линию в целом; 442 найти правило, которое позволило бы обнаруживать ошибки: более того, могло бы указать наиболее вероятную г-выборку на входе и тем самым дало бы возможность эти ошибки исправлять. Мера информации и энтропия.
Информацию мы будем рассматривать как некоторую физическую реальность, которую можем попытаться измерить. Величиной информации, полученной при наблюдении события Еь происходящего с вероятностью Рь будем считать Н (Х(У) — дает оценку возможности восстановления переданного символа по полученному символу; Н(У ~Х) — дает представление о шуме на линии. Взаимная информация н пропускная способность линии.
Выражение (Б2.18) 1(Х 1У) = Н (Х) — Н (Х ~ У) определяет «взаимную информацию» ((п1огша11оп пш(не11е), Оно имеет большое значение, так как позволяет измерить «прирост» информации при наблюдении выхода линии, и с его помощью определяется весьма существенная характеристика линии, называемая пропускной способностью. Под этим понимается максимальное значение взаимной информации, где максимум берется по всевозможным распределениям на входе: (Б2.19) С = шах1(Х ~У). рм! Исходя из этих определений, Шеннон показал, что если взять закон распределения, дающий максимум, то это приведет к устранению влияния шума на линии.
Чем ближе подходить к этому пределу, тем незначнтельнее действие шума и тем меньше вероятность ошибки р(е). Если энтропия Н (5) источника информации не превосходит пропускной способности линии С, то появляется возможность кодировать информацию источника с помощью входного алфавита. При этом, учитывая закон распределения источника, кодовые слова следует составить так, чтобы закон распределения на входе был по возможности близок к закону, дающему максимум взаимной информации.
Множество кодовых слов называется кодом. П р и м е р 1, Рассмотрим код Фано для двоичной симметрической линии. Для такой линии вероятностным законом, приво! дящим к максимальному значению 1(Х~ У) будет р д= —; в этом случае передача каждого двоичного знака несет в среднем одну единицу информации (при логарифмах по основанию 2). Фано предложил следующий метод кодирования информации: а) расположить сообщения в порядке возрастания их вероятности; б) разбить сообщения на два подмножества так, чтобы вероятности сообщений внутри каждого из подмножеств были возможно более близки друг к другу; в) приписать каждому из подмножеств двоичный знак, например, первому — нуль, а второму — единицу; г) произвести операции б) н в) с каждым нз подмножеств.
Продолжают так до тех пор, пока все сообщения не окажутся закодированными. 443 Предположим, например, что из источника В передаются сообщения А, В, С, Р, Е, Е с вероятностями р(А)=0,5, р(В)=0,25, р(С)=0,1, р(Р)=0,08, р(Е)=0,05, р(Р)=0,02. (Б2.20) Закодируем зти сообщения, как показано в таблице: Соолыевие источнинв Веравтнастн последове- тельныь попмноыеств Кодовые ело. вв длины л! вероятно- сти р! лтдр! 0,50 0,50 0,25 0,25 О,!О 0,15 0,08 0,07 Среднее число двоичных знаков кодированного сообщения й = ~п,р,=1,97. В идеальном случае среднее число двоичных знаков в сообщении равно Н= — У' рт!одт — = 1,952 (Б2.21) ! А единиц информации на сообщение. Эффективность кодирования можно измерять отношением — =0 98. Н 1,952 ! 97 (Б2.22) Чем зто отношение ближе к единице, тем кодирование лучше.
П ример 2. Пусть линия передачи определяется случайной величиной Х на входе, принимающей значение х!, хм хм х„с вероятностями р(х!) = 0,1, р(хт) = 0,2, р(хд) = 0,3, р(хе) = 0,4. Пусть число значений случайной величины на выходе У равно 3, и матрица перехода задается следующим образом: (Б2.23) Вычислим вероятности я! —— рг (У = у!), 1'= 1, 2, 3; (Б2. 24) гр! = рг(Х=х,11'=у!), 1=1, 2, 3, 4; /=1, 2, 3; (Б2 25) РН=Рг(Х=х!, У Уг), 1=1, 2, 3, 4; /=1, 2, 3.
(Б2.25) 444 А в с Гр Е Р 0,50 0,25 0,10 0,08 0,05 0,02 0 1О 110 1 1!О !1 !!О 11 !!1 0,50 0 0,50 0,20 0,40 0,40 0,5 0,25 0,25 0 0,50 0,50 !Х0,50=0,50 2Х0,25 0,50 ЗХО,! 0=0,30 4Х0,08=0,32 5Х0,05=0,25 5Х0,02=0,10 (Б2.27) нс=рг(У=у)=0,24, нс=рг(у=у)=0355, из — — рг (Г = уз) = 0,405. (Б2.29) Вероятности и! и р„вычисляем по формуле (Б2.10), т. е.
с ис = РсРс Ри (Б2.30) с 4 я ,с~~~ рср/ с 1 Имеем 5/24 4/24 15/24 0 !!ПС!! = 0 8/355 75/355 20/355 5/40Л 8/40,5 7,5/40,5 20/40,5 (Б2.31) откуда Рс (Б2.32) ис.' 0,24 0,355 0,405. Примечания. 1) Из элементов матрицы !срсс!! получают рс, суммируя элементы в каждой из строк, и пь суммируя элементы в каждом из столбцов. 2) Если задана матрица ~~рсД, то по ней можно найти сссс и р'! (Б2.33) (Б2.34) БЗ. Коды, обнаруживающие и исправляющие ошибки Расстояние Хэмминга. Пусть мы получили код, в котором каждая г-выборка закодирована словом, состоящим из и символов (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
