книги из ГПНТБ / Бовбель, Е. И. Элементы теории информации
.pdfЕ. Я. Бовбелъ
И. К. Данейко
В. В. Изох
ТЕОРИИ
ИНФОРМАЦИИ
Е. И. БОВБЕЛЬ, И. К. ДА НЕЙКО, В. В. ИЗ ОХ
ЭЛЕМЕНТЫ
ТЕОРИИ
ИНФОРМАЦИИ
Под редакцией В. В. И 3 О X А
ИЗДАТЕЛЬСТВО БГУ им. В. И. ЛЕНИНА
МИНСК 1974
У Д К 621.391.3
Элементы теории информации. Б о в б е л ь Е. И., Д а н е й ко И. К.,
Из о X В. В. Млгиск, Изд-во БГУ, 1974.
Вкниге рассматриваются основные положения теории информа ции, описываются источники дискретных сообщений, дискретные и непрерывные каналы с шумами, прощаемы кодирования. Основные положения теории информации проиллюстрированы большим коли чеством примеров и задач, которые помогут глубже понять изложен ный материал.
Книга |
предназначена для студентов физических факультетов. |
Она может |
быть полезна студентам электротехнических институтов |
связи и раднотехнігческих институтов. Данная книга рекомендуется также для самостоятельного знакомства с основами излагаемой тео рии.
Бовбель Е. И. и др.
Б 73 Элементы теории информации. Под. ред. В. В. Изоха. Мн., Изд-во БГУ, 1974.
112 стр. с илл.
Перед загл. авт.: Е. И. Бовбель, И. К- Данейко, В. В. Мзох.
Пособие содержит основные положения теории информации, про иллюстрированные' множеством задач и примеров. Предназначено для студентов физических факультетов вузов. Может быть использовано для самостоятельного изучения основ излагаемой теории.
|
|
6Ф0.1 |
Б |
0231—027 fl_ 74 |
Издательство БГУ нм. В. И. Ленина. 1974 г. |
|
М317—74 |
П Р Е Д И С Л О В И Е
За последние 20 лет слово «информация» стало очень популярно в современном лексиконе, широкого круга спе циалистов и общественности. Под информацией (от ла тинского informatio — разъяснение, изложение) первона чально подразумевались сведения, передаваемые устно, письменно и каким-либо другим способом, а также сам процесс передачи ііли получения этих сведений. Инфор мация всегда играла в жизни человека важную роль. Особенно велико ее значение в наши дни. В середине XX века произошли изменения в трактовке понятия «инфор- * мация»,что связано с бурным развитием науки и техники. Данное понятие было расширено путем включения в него не только обмена сведениями между человеком и челове ком, но также между человеком и автоматом, автоматом
•и автоматом, обмена сигналами в животном и раститель ном мире. Была предложена количественная мера инфор мации, которая привела к созданию теории информации.
Теоріия информации в ее современном виде — это на-' учная дисциплина, изучающая способы передачи и хра-ѵ нения информации наиболее надежным и экономным методом. Истоки ее можно найти в древнерусском языке: часто слова записывались несколькими буквами. Нагляд но это можно проследить по книге белорусского мысли теля XVI века Г. Скорины «Псалтыри». Этот принцип на блюдается и в теории информации, т. е. чем чаще встре чается сообщение, тем меньше нужно о нем сообщать. Если проанализировать все виды связи, существовав
шие в Древней Руси («лесной телеграф», костры и т. п.), можно сделать вывод, что очень давно был понят один из основных принципов теории информации, заключающий ся в том, что сообщение можно передавать двоичным ко дом.
В 1832 г. Морзе ввел код «точки-тире». Морзе, вероят- • но, первым осознал статистический аепект данной проб лемы. Он понимал, что частота появления отдельных
3'
букв/ангЛПйского алфавита различна. Посещая типогра фию и подсчитывая используемые литеры, Морзе оценил частоту появления отдельных букв и свой код построил так, что наиболее встречающимся буквам были присво ены наиболее короткие комбинации точек и тире. Благо даря этому удалось в кодированных сообщениях в сред нем использовать меньшее количество символов.
Первым количественную меру информации ввел Харт ли в .1928 г. Точная мера количества информации на ста тистической основе появилась только после того, как Ко тельников, Колмогоров, Винер выяснили статистический характер передачи информации. Эта мера была введена и детально разработана’ Шенноном в его классических работах.
Теория информации была вызвана к жизни практиче скими потребностями техники связи. В теории информа ции, созданной К. Шенноном, были слиты два аспекта теории информации: фундаментальный и. прикладной. Фундаментальный аспект привел к развитию теории ин формации как математической дисциплины. Второй ас пект вызвал распространение идей теории информации на различные области знаний, выходящие за пределы теории связи, в частности: в радиолокации, измеритель ной технике, телевидении, искусстве, психологии и т. д.
Данный аспект привел к образованию прикладной теории информации как специального научного направ ления. В прикладной теории информации теоретико-ин формационные представления становятся средством для решения других специфических задач.
Существенный вклад в развитие теории информации внесли советские ученые А. Н. Колмогоров, А. Â. Харкевич, А. Я. Хинчин, Р. Л. Добрушии, Л. М. Финкг Р. Л. Отратонович, И. М. Коган, Ф. Е. Темников. ,
. Данная книга возникла из основных разделов курса лекций, читаемых в течение ряда лет на физическом фа культете БГУ имени В. И. Ленина. Авторы надеются, что это учебное пособие введет читателей в круг задач, реша емых теорией информации. Изложение основано на клас сических работах Шеннона, Харкевичд, Хинчина. •
Авторы, ориентируясь на математическую подготовку студентов^-физиков, старались на физическом уровне строгости и на большом количестве задач продемонстри ровать основные .положения теории информации.
Г Л А В А 1
ЭНТРОПИЯ. КОЛИЧЕСТВО ИНФОРМАЦИИ
§ 1. Установление количественной меры информации лри отсутствии, неопределенности после опыта -
* |
к |
В теории |
информации понятие информации не опре |
деляется. ' Необходимым и достаточным для построения теории является (понятие к о л и ч е с т в а ‘и н ф о р м а- ц и и.
.В соответствии с определением предмета теории ин формации в ее современном состоянии вводимая мера информации должна быть полезной для анализа и синте за систем передачи ті хранения информации. Поэтому ис комая мера, очевидно, должна быть «нечувствительной» к смыслу, ценности, степени правдивости информации. Например, задачей системы связи является точная и свое временная передача сообщений независимо от того, со держат ли последние для получателя ценность, смысл и правдивость или же нет.
Количество информации должно определяться через нечто общее, объективно присущее всему многообразию различной информации, оставаясь при этом созвучным нашим интуитивным представлениям, связанным с фак том получения информации. Этим общим, характеризу ющим факт получения пронзіволы-юй информации, явля ется, во-первых, наличие опыта. Всякая информация добывается нами в результате опыта и только опыта. Опы том может служить прослушивание радиопередачи, ви зуальное наблюдение события, измерение некоторого параметра процесса тем или иным прибором и т. п. Во-вто рых, до опыта должна существовать некоторая неопреде ленность, в том или ином исходе опыта. В самом деле, если бы получателю до опыта было известно, какое сооб щение он получит, то, получив его, он не приобрел бы ни какого количества информации.
Таким образом, до опыта всегда имеется большая или меньшая неопределенность в интересующей нас ситуа
5
)
ции. Пасле опыта (после получения информации) ситу ация становится более определенной и на поставленный вопрос мы можем ответить либо однозначно, либо число возможных ответов уменьшится и, следовательно, умень шится существовавшая ранее неопределенность. Количе ство уменьшенной неопределенности после опыта, оче видно, можно отождествить с количеством полученной информации в результате такого опыта.
Теперь ясно, что для установления формулы для вы числения количества информации необходимо уметь вы числять неопределенность некоторой ситуации до и пос ле опыта. Разность между этими количествами неопреде ленности и даст нам искомое количество информации, полученное от такого опыта.
Для этого предположим сначала, что после опыта не определенности нет. К примеру, при бросаниях монеты возможны два исхода опыта: выпадет орел или выпадет решка. После опыта .неопределенности исхода нет — вы пал, к примеру, орел. В данном случае, как ясно из ска занноговыше, неопределенность до опыта будет числен но равна количеству полученной информации.
В этой ситуации к количеству информации (или, что то же самое, к количеству неопределенности до опыта) можно предъявить три интуитивных требования.
1. Количество получаемой информации больше в том опыте, у которого большее число возможных исходов.
Обозначая количество информации буквой 1, а число возможных исходов /?, первый постулат запишем в виде
I (п2) , если п\ |
іі2. |
2. Опыт с единственным исходом |
необходимо несет |
количество информации, равное нулю. Символически это выглядит так: І(п = 1) = 0 .
3. Количество информации от двух независимых опы тов должно равняться сумме количеств информации от каждого из них.
Например, количество информации, содержащееся в двух различных по содержанию (независимых) книгах, равно сумме количеств информации, содержащихся в отдельных книгах. Однако если одна книга содержит часть другой, то количество информации от двух таких книг не будет равно сумме количеств информации от книг в отдельности, а будет несколько меньше.
6
Ваналитической записи условие 3 примет вид
—I(п\) - ( - /(н-г),
так как опыт, объединяющий два опыта с исходами соот ветственно П[ и п2) имеет пг п2 исходов.
Очевидно, единственной функцией аргумента п, удов летворяющей трем поставленным условиям, является ло гарифмическая. Итак, количество информации от опыта с п исходами при условии, что после опыта неопределен ность отсутствует,
I = c\ogan, |
(1.1) |
где с и а — произвольные постоянные. |
|
Заметим, что при установлении формулы (1.1) |
мы не |
различали исходы опыта по степени их возможности на ступить, т. е. исход опыта маловероятный мы не отлича
ли |
от исхода |
опыта, имеющего |
большую вероятность, |
А |
кольэтотак, |
то исходы опыта |
в (1.1) следует считать |
равновероятными, т. е. вероятность любого исхода равна
*/п = Р. Учтя это, перепишем формулу |
(1.1) в виде |
||
|
I = |
— c\ogaP. . |
|
Выбор постоянной с и основания |
логарифмов здесь |
||
несуществен, так |
как |
в силу известного тождества |
|
\ogbn = log^alogö/i |
переход от одной системы логариф |
||
мов к другой сводится к умножению на постоянный мно житель, Тѵ е. равносилен простому изменению масштаба
/. Поэтому, простоты ради, положим с — 1, а = |
2. Тогда |
I = — log2^ = ІОg2n. |
(1.2) |
В этом случае единицу количества информации назы вают би т(ом ). Как видно из (1.2), бит есть количество информации,- получаемое в результате опыта с двумя равновероятными исходами.
Кик изменится формула (1.2), если исходы опыта не
обладают равной вероятностью? |
Предположим, что у |
||
опыта X имеется п исходов, |
хі с |
соответственными ве- |
|
|
|
|
п |
роятностями наступления Pt |
(/= 1 |
, |
2, ..., п) и 2 Рі = 1 - |
Тогда количество информации, несомое сообщением, что наступил исход хи равное по (1.2) — ІоgP(Xi) = ^Объ является случайной величиной. Чтобы не иметь дело ca
7
случайной 'мерой информации, усредним частные коли чества информации:
:< і (хі) > = 2 |
I(xt) Р(х0 = - £ P(xt)log P(x,). (1.2a) |
/=І |
/=1 |
Данная формула определяет среднее количество ин формации (или среднюю неопределенность до опыта), несомое произвольным исходом х і , при условии, что, как и прежде, после опыта неопределенность исхода отсутст вует.
Задача 1. Пусть в некотором городе 25% населения составляют студенты. Среди студентов' 50% юношей. Все го же юношей в городе 35%. Сколько дополнительной ин формации содержится в сообщении, что встреченный юноша — студент?
Р е ш е н и е . 1- й с п о с о б . Обозначим событие «встречен юноша» через хь а событие «встречен студент» через хо. По теореме умножения вероятность совместно го наступления событий Х\ и х2 равна
P'(xl)P(x2/x{) = P ( x 2)P(xlfx2). |
(1.3) |
|||
По условию |
задачи |
Я (*і)=0,35, |
Р ( х 2) =0,25 |
и |
Р(х\/х2) = 0 ,5 . |
Подставив |
эти значения |
вероятностей |
в |
(1.3), найдем вероятность, что встреченный юноша—г сту дент.
|
Р(х2іх г) |
0,25-0,5 |
0,357. |
|
0,35 |
||
|
|
|
|
Искомое |
количество информации |
|
|
/ = |
— l og Р(х2/х\) = |
— log 0,357 = 1,486 (бит). |
|
2 -й с п о с о б . Количество информации, несомое со общением, что встреченный юноша — студент:
І(хи х>) = — log Р(хь х2) = — log [Р(х2) |
р (Хі/х2)] = |
=• -lo g (0 ,2 5 -0 ,5 ), |
.(1.4) |
а что встречен юноша: |
|
. І(хі) = — log Р(х\) = — log 0,35. |
(1.5) |
Но нам по условию задачи известно, что встречен юноша, т. е. -мы уже получили количество информации (,І.5), и при этом от нас требуют узнать, сколько допол нительной информации содержится в сообщении, что он
Г |
* |
8
студент. Для этого нам, очевидно, нужно вычесть из (1.4) количество известной информации (1.5):
/ = I(XV xt) = - log -P-f f f L = 1,486 (бит).
Задача 2. Колода состоит из 32 карт от семерки и вы ше. - Игрок №. 1 вытаскивает любую карту. Игрок № 2 должен угадать, какая карта вытащена, задавая вопро сы, на которые игрок № 1 дает ответ «да» или «нет». Оп ределить минимальное число вопросов, которое гаранти рует отгадывание вытащенной карты.
Р е ш е н и е . Предположим, что игрок № 1 вытащил • бубновый туз. В результате этого опыта он получил ко-
.л ичество иифор мации
/ , = — log-T- = log32 = 5 (бит). ■
Чтобы достоверно узнать вытащенную карту, игрок № 2, очевидно, должен приобрести путем определенной системы вопросов то же количество информации у-игро ка № 1. Игрок № 2 может с равной вероятностью услы шать ответ «да» или «нет» на свой вопрос. Поэтому ко личество информации, несомое ответом,
h = — lo g -T = log 2 = 1 (бит). |
(1.6) |
Таким образом, игрок № 2, отнимая в результате' каждого вопроса 1 бит у игрока № 1, должен задать ми нимум 5 вопросов.
Задача решена. Однако остается невыясненным,, ка кому правилу должен следовать игрок № 2, задавая во просы, которые помогли бы ему реализовать найденный минимум. Это правило заложено в результате (1.6): чтобы ответ игрока № 1 нес нам количество информации, рав ное одному биту, необходимо, чтобы всякий вопрос игрока № 2 относился к одной из подгрупп последователь ного разбиения колоды карт йа две равновероятные под- , группы. В противном случае количество информации, по лучаемое игроком № 2, будет в среднем меньше одного бита, в результате чего в среднем возрастет число необ ходимых вопросов.. •
Задача 3. Скупой обладает 12 монетами одного досто инства; 11 из них имеют одинаковый вес, а одна, фаль шивая, легче остальных. Кредитор только что пришел к нему с требованием немедленно выплатить долг. Разуме-
9