ИНФОРМАЦИЯ И НЕОПРЕДЕЛЁННОСТЬ
Информация - это сведения или данные, не содержащая неопределённость для адресата. Если всё же информация содержит некоторую неопределённость, то её можно воспринять только с некоторой вероятностью. Поэтому, при наличии неопределённости, получатель информации каким-либо образом добивается свести к минимуму саму неопределённость. Если при этом удаётся получателю информации исключить неопределённость полностью, то он владеет информацией вполне. Вопросы о том, как это можно делать на практике, являются содержанием данной главы.
КОЛИЧЕСТВЕННАЯ МЕРА НЕОПРЕДЕЛЁННОСТИ
Для сравнения неопределённостей, рассмотрим следующие примеры или опыты a, b и g, содержащие неопределённости H(a), H(b) и H(g) соответственно:
1. Определить очередного чемпиона мира по шахматам (опыт a).
2. Определить номер лотерейного билета, на который выпадет наибольший выигрыш в предстоящем тираже лотереи (опыт b).
3. Определить следующего президента РФ (опыт g).
Очевидно, степень неопределённости каждого опыта отличается от двух других, причём скорее всего имеют место неравенства
H(b) > H(a) > H(g),
где H(a), H(b) и H(g) - количественные меры неопределённостей (или энтропии) опытов a, b и g соответственно. В частном случае, если для некоторого опыта d имеет место равенство H(d) = 0, то говорят, что опыт d достоверный, т.е. он не содержит неопределённости. Другими словами неоределённость опыта есть не что иное как недостача информации или отрицательная информация.
|
|
|
I. Формула Хартли. Пусть a - произвольный опыт с k равновероятными исходами Аk
События А 1 А 2 . . . А k
Вероятности 1/ k 1/ k . . . 1/ k .
При k = 1 H(a) = 0, а при возрастании k H(a) также возрастает, т.е.
H(a) = f (k) ,
где f - некоторая функция от k. С другой стороны, если b независимый от a другой опыт с l равновероятными исходами Вl, то для сложного опыта ab, состоящего в одновременном выполнении опытов a и b, естественно считать что степень неопределённости опыта ab равна сумме неопределённостей, характеризующих опыты a и b, т.е.
H(ab) = H(a) + H(b).
Таким образом, в качестве функции f можно выбрать логарифмическую функцию и считать, что
H(a) = log2k .
Это есть формула Хартли и она представляет собой меру неопределённости относительно опыта a, содержащимся в опыте a и имеющим два равновероятных исхода (например,"да" или "нет"). Другими словами, H(a) это то количество информации (за единицей измерения количества информации считается бит), с помощью которого неопределённость опыта a превращается в достоверность.
|
|
|
Так, например, для угадывания задуманного числа в диапазоне от 1 до 8 необходимо максимум 3 бит информации, т.е. необходимо задать три вопроса.
II. Формула Шеннона. Пусть a - произвольный опыт с к неравновероятными исходами Ак:
События А 1 А 2 . . . А k
Вероятности Р(А1) Р(А2) . . . Р(Аk) .
Тогда k
H(a) = - å P(A i)log2P(A i)
i = 1
- есть мера неопределённости опыта a по Шеннону. В частности, при Р(А i) = 1/ k , из формулы Шеннона следует формула Хартли.
3.1.1. Доказать, что H(ab) = H(a) + H(b).
3.1.2. Сколько вопросов необходимо задать студентам академической группы преподавателю, чтобы определить старосту этой группы (ответы на вопросы преподавателя могут быть либо "да" либо "нет").
3.1.3. Рассмотреть задачу 3.1.2. в случае одного вопроса.
3.1.4. Пусть х- элемент множества М мощности m. Какое количество
информации необходимо для определения элемента х ?
3.1.5. Пусть х 1 и х 2 - два произвольных элемента множеств М 1 и М 2 мощностей m 1 и m 2 соответственно. Какое количество информации необходимо для одновременного определения элементов х 1 и х 2 ?
|
|
|
3.1.6. Пусть имеется 27 золотых монет, из которых одна фальшивая (легче настоящих), и весы с чашками. Сколько взвешиваний необходимо произвести, чтобы определить фальшивую монету ?
3.1.7. Доказать, что любого опыта a H(a) ³ 0, причём H(a) = 0 тогда и только тогда, когда одна из вероятностей равна 1, а остальные равны 0.
3.1.8. Доказать, что H(a) ≤ log2k , где k - число исходов опыта a , причём равенство достигается лишь в случае, когда исходы равновероятны.
3.1.9. Какими свойствами обладает H(a) , если a имеет два исхода ?
УСЛОВНАЯ НЕОПРЕДЕЛЁННОСТЬ.
КОЛИЧЕСТВО ИНФОРМАЦИИ
Пусть a и b - два произвольных опыта с k и l исходами А k , В l соответственно. Тогда если a и b независимы, то
H(ab) = H(a) + H(b) ,
а если же a и b зависимы, то
H(ab) = H(a) + H a(b) ,
где Ha (b) - условная неопределённость опыта b при условии выполнения опыта a и определяется равенством k
Ha(b) = å P(A i)H A i (b) .
i = 1
|
|
|
Здесь H A i (b) - условная неопределённость опыта b при условии исхода A i и определяется формулой: l
H A i (b) = - å PA i( B j ) log 2 PA i( B j ) , i = 1 , k .
j = 1
Очевидно, если a и b независимы , то Ha(b) = H(b) , и Ha(b) ≤ H(b) , если a и b зависимы.
Имеет место также равенство
H(ab) = H(ba) .
Рассмотрим разность
I (a , b) = H(b) - Ha (b) ,
которая указывает, насколько исход опыта a уменьшает неопределённость опыта b. Число I (a , b) называется количеством информации относительно опыта b, содержащимся в опыте a.
В частности, при a =b имеем I (a , a ) = 0, что можно трактовать как количество информации об опыте a, содержащимся в самом себе . Если же a и b независимы, то
I (a , b) = 0 ,
т.е. в целом
I (a , b) ≥ 0 ,
что можно трактовать примерно так: от всего, чему учат в университете, вреда не будет, а в худшем случае просто не будет пользы.
Так как
I (a , b) = I (b, a ) ,
то I (a , b) можно назвать также взаимной информацией двух опытов a и b
друг относительно друга. Далее, так как
H(ab) = H(a) + H a(b) ,
то
I (a , b) = H(a) + H(b) - H(ab) ,
следовательно, k l
I (a , b) = Σ Σ P(A iB j) log 2 P(A iB j) /( P(A i ) P(B j)) .
i = 1 j = 1
Таким образом, мы получили окончательную формулу относительно количества информации I (a , b).
3.2.1. Доказать, что если a и b произвольные опыты, то;
а) H(ab) = H(a) + Ha(b) ;
б) H(ab) ≤ H(a) + H(b) ;
в) 0 ≤ Ha(b) ≤ H(b) ;
г) I (a , b) = I (b, a ) ;
д) I (a , b) ≤ H(a) ;
3.2.2. Вывести формулу относительно I (a , b) .
3.2.3. Пусть опыт b состоит в извлечении одного шара из урны, содержащий m чёрных и n белых шаров, опыт a k - в предварительном извлечении из той же урны (без возвращения обратно) k шаров. Чему равна неопределённость опыта b и информация об опыте, содержащаяся в опытах a6,
a13 и a14 ?
3.2.4. Пусть из партий в n деталей, изготовленных на конвейере, для выборочного контроля изъяты m деталей. Обозначим через a процент брака всей партии, а через b - процент брака в выборке. Определить I (a , b).
3.2.5. (О городах лжецов и честных людей). Пусть известно, что жители некоторого города А всегда говорят правду, а жители соседнего города Б всегда обманывают. Наблюдатель Н знает, что он находится в одном из этих двух городов, но не знает, в каком именно. Путём опроса встречного ему требуется определить, в каком городе он находится, или в каком городе живёт его собеседник (жители А могут заходить в Б и обратно), или то и другое вместе. Спрашивается, каково наименьшее число вопросов, которые должен задать Н (на все вопросы Н встречный отвечает лишь "да" или "нет").
ПЕРЕДАЧА ИНФОРМАЦИИ
Ещё раз вернёмся к общей схеме передачи информации, рассматривая реальные сообщения как некоторые опыты с соответствующими таблицами распределения вероятностей в них отдельных букв или сочетания букв.
В частности, если х и х' - переданное и искажённое сообщения соответственно, то определим количество информации I(x' , x) - выхода канала относительно его входа как:
I(x' , x) = Н(х) - Нх ' (х) ,
где Н(х), Н(х') энтропии сообщений х и х' соответственно.
Значение
C = max I(x' , x)
х
называется пропускной способностью канала, т.е. она характеризует максимальное количество информации, которое может быть передано через канал за один такт времени. А в самом деле, пропускная способность канала является верхней границей скорости R надёжной передачи информации, причём к этой границе можно подойти сколь угодно близко.
Теорема 1.(о кодировании). Для любого числа R, меньшего пропускной способности С канала, и любого e>0 существует способ блоковой передачи со скоростью, не меньшей R, и вероятностью ошибки Р(е), не превосходящей e.
В то же время всякий способ передачи информации со скоростью, большей пропускной способности, приводит к тому, что вероятность ошибки будет больше некоторой фиксированной величины.
Теорема 2.(обращение теоремы кодирования). Если величина R превосходит пропускную способность канала С, то найдётся константа e0 (зависящая от R и C) такая, что при любом способе блоковой передачи информации со скоростью, не меньшей R, выполнено неравенство
Р(е)³ e0.
Обозначим через I(a i) количество информации, содержащееся в символе a i и определим его как:
I( a i ) = - log2 P(a i) ,
где P(a i) - вероятность появления символа a i в самом тексте сообщения.
Если же текст сообщений записан на некотором естественном языке
( а его можно рассматривать как естественный код, обнаруживающий и исправляющий ошибки ), то каждая буква этого языка имеет свою частоту встречаемости в тексте ( так, например, в русском языке буквы о , е , ё гораздо чаще встречаются ( Ро = 0.09 , Ре,ё = 0.07) , чем буквы э и ф ( Рэ= 0.003, Рф = 0.002 )) и поэтому неопределённость HL естественного языка определяется как m
HL= - å P( a i ) log2 P( a i ) ,
i = 1
а избыточность СL соответственно как
СL= 1 - HL/ log2 m ,
где m - количество букв естественного языка.
Очевидно, что 0 ≤ СL ≤ 1, следовательно, при оптимальном кодировании часть текста можно без ущерба для понимания опустить.
Так, например, СL= 0.5 для литературного английского языка, а избыточность других языков несколько меньше.
Отметим, что избыточность языка не является недостатком, а скорее преимуществом, так как, например, если СL= 50% , то это означает что по половине искажённого текста можно восстановить весь текст.
3.3.1. Определить пропускную способность ДСК.
3.3.2. Найти I(x' , x) для ДСК.
3.3.3. Определить избыточность и неопределённость русского языка.
3.3.4. Определить количество информации букв английского языка.
3.3.5. Доказать теоремы Шеннона для блочных кодов.
3.3.6. Восстановить текст:
а) С??зд ц?ли??м ? п?лн???ью од??ри? м??опр??т?я ц? пар??? ?о ??рьб? ? ?а?о?ом;
б) ?об?ка ?ае? ка?ав?н ???ает.
ОГЛАВЛЕНИЕ
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
1. Алфавит дискретных устройств . Конечные поля . . . . . . . . . . 4
1.1. Простое поле Галуа GF(P) . . . . . . . . . . . . . . . . . . . . . 4
1.2. Составное поле Галуа GF(Pn) . . . . . . . . . . . . . . . . . . . 6
2. Кодирование информации . . . . . . . . . . . . . . . . . . . . . . .9
2.1. Основные понятия . Примеры кодов . . . . . . . . . . . . . . . 9
2.2. Линейные коды . Способы их задания . . . . . . . . . . . . 15
2.3. Свойства линейного кода . Коды Хэмминга . . . . . . . . . . 22
2.4. Циклические коды . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5. Коды БЧХ , исправляющие две ошибки . . . . . . . . . . . . .32
2.6. Нелинейные коды . Коды Адамара . . . . . . . . . . . . . . . .36
2.7. Границы мощности кодов . . . . . . . . . . . . . . . . . . . . 40
3. Информация и неопределённость . . . . . . . . . . . . . . . . . . 44
3.1. Количественная мера неопределённости . . . . . . . . . . . .45
3.2. Условная неопределённость . Количество информации . . . . .47
3.3. Передача информации . . . . . . . . . . . . . . . . . . . . . .50
Осипян Валерий Осипович
ЭЛЕМЕНТЫ ТЕОРИИ ПЕРЕДАЧИ ИНФОРМАЦИИ
Редактор Т.В.Шилова
Технический редактор И.А. Зиновская
Корректор М.Е. Шулепова
ЛР № 200378 от 22.01.97
Подписано в печать 29.01.97.
Формат 60´841/16. Бумага тип. № 3.
Печать трафаретная. Усл. печ. л. 2,75.
Уч.-изд. л. 2,7. Тираж 300 экз. Заказ №
Кубанский государственный университет
350040 г. Краснодар, ул. Ставропольская, 149.
Тип. КубГУ, ул. Октябрьская, 25.
Дата добавления: 2019-02-13; просмотров: 1727; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!