Теория вероятности. Вентцель Е.С (4-е издание) (1082431), страница 86
Текст из файла (страница 86)
главу 9). и=1ой " ' + о ~п2 2а~ 2(а~.+ о ) Отсюда )l а22+оо 1 ( М (22) 1 ч-~х "(((~) (ой + !Е2 ~ 24 М (ут) ') 2 (о~ + ет) .3 (18.7.23) Пример 5. Имеется случайная величина Х, распределенная по нормальному закону с параметрами я1 =О, о . Величина Х измеряется с ошибкой 2, тоже распределенной по нормальному закону с параметрами шх = О, е . Ошибка Х не зависит от Х.
В нашем распоряжении — результат измерения, т. е. случайная величина 1'= Х+ У. Определить, сколько информации о величине Х содержит величина 1'. Р е ш е й н е. Воспользуемся для вычисления информации формулой (18.7.21), т. е. найдем ее как математическое ожидание случайной величины у(Х, Г) (7 = 1оа г, (Х) у, ( ) Но та= т„=о, следовательно, 34 [Еэ! = 2) [Е! = аз, 24 [У~! = ьт [У! = ч~ + ч~». Подставляя (18.7.24) в (18.7.23), получим ['",+ .' 7 = 1оя (дв. ед.) ').
Например, при ч, = а, 1 уг х —— 1оа У 2 = — (дв. ел.). Если ч 4; ч = 3, то )г х — — !оя — = 0,74 (лв. ед.). 5 (18.7.24) 18.8. Задачи кодирования сообщений. Код Шеннона — Фэно При передаче сообщений по линиям связи всегда приходится пользоваться тем илн иным кодом, т. е. представлением сообщения в виде рида сигналов. Общеизвестным примером кода может служить принятая в телеграфни для передачи словесных сообщений азбука Морзе. С помощью втой азбуки любое сообщение представляется в виде комбннзции элементарных сигналов: точка, тире, пауза (пробел 'между буквами), длинная пауза (пробел между словами).
Вообще «одировакием называется отображение состояния одной физической системы с помощью состояния некоторой другой. Например. при телефонном разговоре звуковые сигналы кодируются в виде электромагнитных колебаний, з затем снова декодируются, превращаясь в звуковые сигналы на другом конце линии.
Наиболее простым случаем кодирования является случай, когда обе системы Х и (отображаемая и отображающая) имеют конечное число возможных состояний. Так обстоит дело при передаче записанных буквами сообщений, например, при телеграфировании. Мы ограничимся рассмотрением этого простейшего случая кодирования. Пусть имеется некоторая система Л (например, буква русского алфавита), которая может случайным образом принять одно из состоянии кп ха ..., к„. Мы хо:им о;о разкзь е (закодировать) с помощью другой системы У, возможные состояния которой уп уз, ..., у .
Если т(и (число состояний системы У менюпе числа состояния системы Х), то нельзя каждое состояние системы Х закодировать с помощью одного-единственного состояния системы 1'. В таких случаяк одно состояние системы Х приходится отображать с помощью определенной комбинации (последовательности) состояний системы У.
Так, в авбуке Морзе буквы отображаются различными комбииациямн зле- ') Применяя формулу (18.7.20), можно было бы прийти к тому же результату, но более громоздким способом. б02 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИНФОРМАЦИИ 1гл. ~а ~вв! злдлчи кодиповлиия соовщвиии. код швиноил — ээио 503 ментарных символов (точка, тире). Выбор таких комбинаций и установление соответствия между передаваемым сообщением и этими комбинациями и называется «кодированием» з узком смысле слова.
Коды различаются по числу элементарных символов (сигналов), из которых формируются комбинации, иными словами — по числу возмо>кных состояний системы г', В ззбуке Морзе таких элементарных символов четыре (точка, тире, короткая пауза, длинная пауза). Передача сигналов может осуществляться в различной форме: световые вспышки, посылки электрического тока различной длительности, звуковые сигналы и т. и.
Код с двумя элементарными символами (О и 1) называется двоцчлыж. Двоичные коды широко применяются на практике, особенно при вводе информации в электронные цифровые вычислительные машины, работающие по двоичной системе счисления. Одно и то же сообщение можно закодировать различными способами. Возникает вопрос об оптимальных (наивыгоднейших) способах кодирования.
Естественно считать наивыгоднейшим такой код, при котором на передачу сообщений затрачивается минимальное время, Если на передачу каждого элементарного символа (например 0 нли !) тратится одно и то же время, то оптимальным будет такой код, при котором на передачу сообщения ааданной длины будет затрачено минимальное количество элементарных символов.
Предположим, что перед нами поставлена задача: закоднроввть двоичным кодом буквы русской азбуки так, чтобы каждой букве соответствовала определенная комбинация элементарных символов 0 и 1 и ~тобы среднее число этих символов на букву текста было минимальным. Рассмотрим 32 буквы русской азбуки: а, б, в, г, д, е, ж, з, и. й,к,л, м, н,о,п,р,с,т,у,ф,х,ц,ч,шрщ,ъ,ы,ь,э,ю,я плюс промежуток между словами, который мы будем обозначать « — ». Если, как принято в телеграфни, не различать букв ъ и ь (это не приводит к разночтениям), то получится 32 буквы: а, б, в, г, д, е, ж, з, и.й,к, л,м, н,о,п,р,с,т,у,ф,х,шч,ш,щ,(ь,ь) ы,э,ю,я„« — ». Первое, что приходит в голову — это, не меняя порядка букв, з " «ерова~в пч попрал. приписав пц померз ог О до 31, и затем перевести нумерацию В двоичную систему счисления. Двопчпаа система — это такая, в которой единицы разных разрядов представляют собой разные степени двух.
Например, десятичное число 12 изобразится в виде 12 — 1. 2з+1', 2в+О, 21+0. 2в и в двоичной системе запишется как 1100. Десятичное число 25— 26 =-! ° 2'+ ! ° 2з-$- О ° 2з-4- О 2'-1- 1 ° 2в — запишется в двоичной системе как.11001„ 504 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИНФОРМАПИН [Гл уз Каждое из чисел О, 1, 2, ..., 31 может быть изображено пятианачным двоичным числом. Тогда получим следующий код: а — 00000 б — ОООО! в — 00010 г — 00011 я — 11!!О « — » — 11111 В этом коде на изображение каждой буквы трзтится ровно б элементарных символов.
Возникает вопрос, является ли этот простейший код оптимальным и нельзя ли составить другой код, в котором на одну букву будет в среднем приходиться меньше элементарных символову Действительно, в нашем коде на изображение каждой буквы— часто встречающихся «а», «е», «о» или редко встречающихся «ш», «э», «ф» — тратится одно и то же число элементарных символов. Очевидно, разумнее было бы, чтобы часто встречающиеся буквы были закодированы меньшим числом символов, а реже встречающиеся— большим. Чтобы составить такой код, очевидно, нужно знать частоты букв в русском тексте.
Эти частоты приведены в таблице 18.8.1. Буквы в таблице расположены в порядке убывания частот. Таблица !88! Букв~ Буква Частота Буква ~ Частота Частота 0,041,' я 0,039,' ы 0,036 з 0,029 ъ, ь 0,026 , 'б 0,0!9 0,016 0,015 0,015 (1,0!5 0,014 0,013 0,010 0,009, 0,008 0,007 0.006 х ж ю Ш л и О,ооу ш 0,00! з 0,003 ф 0,002 оно ~ г 0,024 у ч 0,021 й 0,05о 0,056 н 0,047 ~ у Пользуясь такой таблицей, можно составить наиболее экономичный код на основе соображений, связанных с количеством информапок Очевидно код будет слмцм эионолсионым «о да как дыв ментарный символ будет передавать максимальную информацию. Рассмоурим элементарный символ 1т. е.
изображающии его сигнал) как физическую систему с двумя возможными состояниями: 0 и 1. ~зз! задачи кодииовлния соовшенип. код шеннона — фэно 505 Информация, которую дает этот символ, равна энтропии системы н максимальна в случае, когда оба состояния равновероятны; в этом случае элементарный символ передает информацию 1 (дв. ед.). Поэтому основой оптимального кодирования будет требование, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто.
Таблица !8.8.2 Изложим здесь способ построения кода, удовлетворяющего поставленному условн|о; этот способ известен под названием «кода Шеннона — Фвно». Идея го вес ои в 1ви, ч.о ко,шр) сны. с ншглы (буквы или комбинации букв) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0 (первый знак двоичного числа, изображающего символ); для второй группы — 1. Далее каждая группа снова делится на две приблизительно раввовероятные подгруппы; для символов первой подгруппы на втором месте ставится нуль; для второй подгруппыв единица я т.
д. Продемонстрируем принцип построения кодз Шеннона — Фэно на материале русского алфавита (табл. 18.8.!). Отсчитаем первые шесть 806 основныя понятия твовин ннеовмлцнн !гл. еа букв (от « — » до «т»); суммируя их вероятности (частоты), получим 0,498! на все остальные буквы (от «н» до «ф») придется приблизительно такая же вероятность 0,802. Первые шесть букв (от « — » до «т») будут иметь на первом месте двоичный знак О. Остальные буквы (от «н» до «ф») будут иметь на первом месте единицу. Далее снова разделим первую группу на лве приблизительно равновероятные подгруппы: от « — » до «о» и от «е» до «т»; для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы— единицу. Процесс будем продолжать до тех пор, пока в каждом подразделении не останется ровно одна буква, которая и будет закодирована определенным двоичным числом.
Механизм построения кода показан на таблице 18.8.2, а сам код приведен в таблице 18,8.3. Т а б л и ц а 18.8.3 д двоичное число двоичное число воичнае ! число Сукне Буква Буква ч й х ж ю ш ц Щ 10ИО г С помощью таблицы 18.8.3 можно закодировать и декодировать любое сообщение. В виде примера запишем двоичным кодом фразу: «теория и- формации» 011101000011010001!0110110000 О!10100011111111100110100 110000!О!111!!10!01!00!1О Заметим, что здесь нет необходимости отделять друг от друга буквы спкциальиыи знаком, так как и без этого декодирование выполняется однозначно. В этом можно убедиться, декодируя с помощью таблицы 18.8.2 следующую фразу: 1001!100!1001!ОО!00111!О!ОООО 1011100111001001101010000!10101 010!10000110110!1О («способ кодирования»).
о е а и т н с Р в Л 000 001 0100 О!01 ОИО ОИ1 1000 1001 10100 10101 к и д и у з ъ, ь б 10И1 ИООО И 0010 ИООИ ИО!00 ИОИО ИОИ1 И 1000 И1001 И! 010 И 10 И ИИ 00 ИИ010 ИИОИ НИ! 00 И И101 И!И1 00 ИИИО! И ИИ10 ИИИИО ИИИИ1 гзл! задачи каднвовлння соовшвнип. код швмнонл — ээно 507 Однако необходимо отметить, что любая ошибка при кодировании (случайное перепутывание знаков 0 и 1) при таком коде губительна, так как декодирование всего следующего за ошибкой текста становится невозможным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
