База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

ВВЕДЕНИЕ

Новые направления, возникшие в математике в ХХ ве­ке, обычно оперируют со сложными понятиями и представлениями, которые с трудом поддаются попу­ляризации. На этом фоне весьма значительна заслуга выдающегося американского математика и инженера Клода Шеннона, который в 1947—1948 годах, исходя из элементарных соображений, открыл новую область ма­тематики - теорию информации. Толчком к созда­нию новой науки были чисто технические проблемы передачи информации по телеграфным и телефонным проводам, однако к настоящему времени благодаря об­щему характеру теория информации находит применение в исследованиях, относящихся к передаче и сохране­нию любой информации в природе и технике.

В конце сороковых годов, на заре развития теории информации, идеи разработки новых эффективных способов кодирования информации носились в возду­хе. Исследователи занимались вопросами энтропии, содержимого информации и избыточности. Интерес­но, что эти первоначальные работы в области сжатия информации велись до появления современного циф­рового компьютера. Сегодня теория информации раз­вивается параллельно с программированием, но в то время идея разработки алгоритмов, использующих двоичную арифметику для кодирования символов, была значительным шагом вперед.

Одними из первых алгоритмов эффективного кодиро­вания информации были алгоритмы Шеннона – Фано и Хафмана.

В данной работе рассмотрены базовые понятия эн­тропии и информации, а также описаны принципы кодирования сообщений по Шеннону – Фано и Хафману, показана их важ­ная роль при передаче информации по линиям связи.

Но линии связи, для которых были разработаны эти методы кодирования информации, уже в прошлом. К счастью, для принципов Шеннона - Фано и Хафмана нашли применение и в современном мире: для сжатия информации.  Архиваторы PKZIP, ARJ, а также часть всем нам хорошо известного стандарта JPEG (сжатие графической информации с потерями) работают именно на этих принципах.

Коды Шеннона – Фано и Хафмана преподаются во всех технических ВУЗах мира и, кроме того, входят в программу для углубленного изучения информатики в школе.

Поэтому изучение методов кодирования Шеннона – Фано и Хафмана является актуальным.

Цель данной работы - изучить принципы кодирования информации Шеннона - Фано и Хафмана и применение их при решении задач.

Задача состоит в том, чтобы изучить энтропии и избыточность конкретных типов сообщений для последующего применения к ним принципов Шеннона - Фано и Хафмана.

1. Информация и кодирование. Коды Шеннона - Фано и Хафмана.

1.1 Информация и кодирование.

Слово «информация» известно в наше время каждому. Происходит оно от латинского «informatio», что означает – разъяснение, сообщение, осведомленность. Однако в постоянное употребление оно вошло не так давно, в середине двадцатого века, с подачи Клода Шеннона. Он ввел этот термин в узком техническом смысле применительно к теории связи или передачи кодов, которая получила название «Теория информации». Здесь важны не любые сведения, а лишь те, которые снимают полностью или уменьшают существующую неопределенность. Философское, и поэтому более широкое определение этого термина дает один из основателей информатики, известный американский ученый Норберт Винер: «Информация – это обозначение содержания, черпаемого нами из внешнего мира в процессе нашего приспособления к нему и приведение в соответствие с ним нашего мышления». Разумеется, это далеко не единственные в своем роде определения информации.

В настоящее время этот термин имеет более глубокий и многогранный смысл. Во многом  оставаясь интуитивным, он получает разные смысловые наполнения в разных отраслях человеческой деятельности:

v    

v    

v    

v    

Такое разнообразие подходов не случайно, а следствие того, что выявилась необходимость осознанной организации процессов движения и обработки того, что имеет общее название – информация.

Для дальнейшего рассмотрения нам необходимо то понятие информации, которое подразумевает передачу информационных сообщений по линиям связи. Рассмотрим общую схему передачи сообщений; для определенности будем говорить, например, о телеграфии. На одном конце линии отправитель подает некоторое сообщение, записанное при помощи любого из известных нам алфавитов или цифр, или  и букв и цифр вместе взятых. Для передачи такого рода сообщений используются последовательности сигналов постоянного тока, некоторые характеристики которого телеграфист может менять по своему усмотрению, воспринимаемых вторым телеграфистом на приемном конце линии. Простейшими различимыми сигналами, широко используемыми на практике, является посылка тока (т.е. включение его на некоторое вполне определенное время) и отсутствие посылки – пауза (выключение тока на то же время); при помощи одних только этих двух сигналов уже можно передать любое сообщение, если условиться заменять каждую букву или цифру определенной комбинацией посылок тока и пауз.

В технике связи правило, сопоставляющее каждому передаваемому сообщению некоторую комбинацию сигналов, обычно называется кодом (в случае телеграфии – телеграфным кодом), а сама операция перевода сообщения в последовательность различных сигналов – кодированием сообщения. Под «кодом» будет пониматься такая совокупность п кодовых обозна­чений, сопоставляемых п буквам алфавита, для которой выполняется условие: никакое кодовое обозначение одной буквы не совпадает с началом какого-либо другого более длинного кодового обозначения, т.е. коды должны быть однозначно декодируемыми. При этом коды, использующие только два различных элементарных сигнала (например, посылку тока и паузу), называются двоичными кодами. В некоторых телеграфных аппаратах кроме простого включения и выключения тока можно также изменять его направление на обратное. При этом появляется возможность вместо посылок тока и пауз использовать в качестве основных сигналов посылку тока в двух различных направлениях или же использовать сразу три различных элементарных сигнала одной и той же длительности – посылку тока в одном направлении, посылку тока в другом направлении и паузу (такой способ кодирования называется троичным кодом). Возможны также еще более сложные телеграфные аппараты, в которых посылки тока различаются не только оп направлению, но и по силе тока; тем самым мы получаем возможность сделать число различных элементарных сигналов еще большим. Увеличение числа разных элементарных сигналов позволяет сделать код более сжатым. Однако вместе с тем оно усложняет и удорожает систему передачи, так что в технике все же предпочтительно используются коды с малым числом элементарных сигналов.

Пусть имеется сообщение, записанное при помощи некоторого «алфавита», содержащего п «букв». Требуется «закодировать» это сообщение, т.е. указать правило, сопоставляющее каждому такому сообщению определенную последовательность из т различных «элементарных сигналов», составляющих «алфавит» передачи. Мы будем считать кодирование тем более выгодным, чем меньше элементарных сигналов приходится затратить на передачу сообщения. Если считать, что каждый из элементарных сигналов продолжается одно и то же время, то наиболее выгодный код позволит затратить на передачу сообщения меньше всего времени.

Главным свойством случайных событий является отсутствие полной уверенности в их наступлении, создаю­щее известную неопределенность при выполнении связан­ных с этими событиями опытов. Однако совершенно ясно, что степень этой неопределенности в различных случаях будет совершенно разной. Для практики важно уметь численно оценивать сте­пень неопределенности самых разнообраз­ных опытов, чтобы иметь возможность сравнить их с этой стороны. Рассмотрим два независимых опыта  и а также сложный опыт  и имеет k равновероятных исходов, а опыт  имеет l равновероят­ных исходов. Очевидно, что неопределенность опыта  больше неопределенности опыта здесь добавляется еще неопределенность исхода опыта  и

Условиям   при  удовлетворяет только одна функция -

Рассмотрим опыт А, состоящий из опытов  и имеющих вероятности А будет равна

Это последнее число будем называть энтропией опыта  и обозначать через

Если число букв в «алфавите» равно п, а число используемых элементарных сигналов равно т, то при любом методе кодирования среднее число элементарных сигналов, приходящихся на одну букву алфавита, не может быть меньше чем ; однако он всегда может быть сделано сколь угодно близким к этому отношению, если только отдельные кодовые обозначения сопоставлять сразу достаточно длинными «блоками», состоящими из большого числа букв.

Мы рассмотрим здесь лишь простейший случай сообщений, записанных при помощи некоторых п «букв», частоты проявления которых на любом месте сообщения полностью характеризуется вероятностями р₁, р₂, … …, р_п, где, разумеется, р₁ + р₂ + … + р_п = 1, при котором вероятность p_i проявления i-й буквы  на любом месте сообщения предполагается одной и той же, вне зависимости от того, какие буквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимы друг от друга. На самом деле в реальных сообщениях это чаще бывает не так; в частности, в русском языке вероятность появления той или иной буквы существенно зависит от предыдущей буквы. Однако строгий учет взаимной зависимости букв сделал бы все дельнейшие рассмотрения очень сложными, но никак не изменит будущие результаты.

Мы будем пока рассматривать двоичные коды; обобщение полученных при этом результатов на коды, использующие произвольное число т элементарных сигналов, является, как всегда, крайне простым. Начнем с простейшего случая кодов, сопоставляющих отдельное кодовое обозначение – последовательность цифр 0 и 1 – каждой «букве» сообщения. Каждому двоичному коду для п-буквенного алфавита может быть сопоставлен некоторый метод отгадывания некоторого загаданного числа х, не превосходящего п, при помощи вопросов, на которые отвечается  лишь «да» (1) или «нет» (0) , что и приводит нас к двоичному коду. При заданных вероятностях р₁, р₂, … …, р_п отдельных букв передача многобуквенного сообщения наиболее экономный код будет тот, для которого при этих именно вероятностях п значений х среднее значение числа задаваемых вопросов (двоичных знаков: 0 и 1 или элементарных сигналов) оказывается наименьшим.

Прежде всего среднее число двоичных элементарных сигналов, приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше Н, где Н = - p₁ log p₁ – p₂ log p₂ - … - p_n log p_n – энтропия опыта, состоящего в распознавании одной буквы текста (или, короче, просто энтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М букв требуется не меньше чем МН двоичных знаков, и никак не может превосходить одного бита.

Если вероятности р₁, р₂, … …, р_п  не все равны между собой, то Н < log n; поэтому естественно думать, что учет статистических закономерностей сообщения может позволить построить код более экономичный, чем наилучший равномерный код, требующий не менее М log n двоичных знаков для записи текста из М букв.

1.2 Коды Шеннона – Фано.

Для удобства расположим все имеющиеся п букв в один столбик в порядке убывания вероятностей. Затем все эти буквы следует разбить на две группы – верхнюю и нижнюю – так, чтобы суммарная вероятность первой группы была наиболее близка к суммарной вероятности второй группы. Для букв первой группы в качестве первой цифры кодового обозначения используется цифра 1, а для букв второй группы – цифра 0. Далее, каждую из двух групп подобным образом снова надо разделить на две части и в качестве второй цифры кодового обозначения мы будем использовать цифру 1 или 0 в зависимости от того, принадлежит ли наша группа к первой или ко второй из этих подгрупп. Затем, каждая из содержащих более одной буквы групп снова делится на две части возможно более близкой суммарной вероятности и т.д.; процесс повторяется до тех пор, пока мы не придем к группам, каждая из которых содержит по одной единственной букве.

Такой метод кодирования сообщений был впервые предложен в 1948 – 1949 гг. независимо друг от друга Р. Фано и К. Шенноном; поэтому соответствующий код обычно называется кодом Шеннона – Фано. Так, например, если наш алфавит содержит всего шесть букв, вероятность которых (в порядке убывания) равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05, то на первом этапе деления букв на группы мы отщепим лишь одну первую букву (1-я группа), оставив во второй группе все остальные. Далее, вторая буква составит 1-ю подгруппу 2-й группы; 2-я же подгруппа той же группы, состоящая из оставшихся четырех букв, будет и далее последовательно делиться на части так, что каждый раз 1-я часть будет состоять лишь из одной буквы.

№ буквы	вероят-ность	разбиение на подгруппы (римские цифры обозначают номера групп и подгрупп)					кодовое обозначение
1	0,4	} I					1
2	0,2	} II	} I				01
3	0,2		} II	} I			001
4	0,1			} II	} I		0001
5	0,05				} II	} I	00001
6	0,05					} II	00000

                                                                                                              Табл.1

Аналогично предыдущему примеру разобран случай «алфавита», включающего 18 букв, имеющих следующие вероятности: 0,3; 0,2; 0,1 (2 буквы); 0,05; 0,03 (5 букв); 0,02(2 буквы); 0,01 (6 букв). (Табл. 2)

№ буквы	вероят-ность	разбиение на подгруппы							кодовое обозначение
1	0,3	} I	} I						11
2	0,2		} II						10
3	0,1	} II	} I	} I					011
4	0,1			} II	} I				0101
5	0,05				} II				0100
6	0,03		} II	} I	} I	} I			00111
7	0,03					} II			00110
8	0,03				} II	} I			00101
9	0,03					} II			00100
10	0,03			} II	} I	} I			00011
11	0,02					} II	} I		000101
12	0,02						} II		000100
13	0,01				} II	} I	} I		000011
14	0,01						} II	} I	0000101
15	0,01							} II	0000100
16	0,01					} II	} I		000001
17	0,01						} II	} I	0000001
18	0,01							} II	0000000

                                                                                                              Табл.2

Основной принцип, положенный в основу кодирования по методу Шеннона – Фано, заключается в том, что при выборе каждой цифры кодового обозначения мы стараемся, чтобы содержащееся в ней количество информации было наибольшим, т. е. чтобы независимо от значений всех предыдущих цифр эта цифра принимала оба возможных для нее значения 0 и 1 по возможности с одинаковой вероятностью. Разумеется, количество цифр в различных обозначениях при этом оказывается различным (в частности, во втором из разобранных примеров он меняется от двух до семи), т. е. код Шеннона – Фано является неравномерным. Нетрудно понять, однако, что никакое кодовое обозначение здесь не может оказаться началом другого, более длинного обозначения; поэтому закодированное сообщение всегда может быть однозначно декодировано. В результате,  среднее значение  длины такого обозначения все же оказывается лишь немногим большим минимального значения Н, допускаемого соображениями сохранения количества информации при кодировании. Так, для рассмотренного выше примера 6-буквенного алфавита наилучший равномерный код состоит из трехзначных кодовых обозначений (ибо 2² < 6 < 2³), и поэтому в нем на каждую букву исходного сообщения приходится ровно 3 элементарных сигнала; при использовании же кода Шеннона – Фано среднее число элементарных сигналов, приходящихся на одну букву сообщения, равно

 Это значение заметно меньше, чем 3, и не очень далеко от энтропии

Аналогично этому для рассмотрения примера 18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовых обозначений (так как 2⁴ < 18 < 2⁵); в случае же кода Шеннона – Фано имеются буквы, кодируемые даже семью двоичными сигналами, но зато среднее число элементарных сигналов, приходящихся на одну букву, здесь равно  

Последнее значение заметно меньше, чем 5, - и уже не намного отличается от величины

    Особенно выгодно бывает кодировать по методу Шеннона – Фано не отдельные буквы, а сразу целые блоки из нескольких букв. Правда, при этом все равно невозможно превзойти предельное значение Н двоичных знаков на одну букву сообщения. Рассмотрим, например, случай, когда имеются лишь две различные буквы А и Б, имеющие вероятности р(А) = 0,7 и р(Б) = 0,3; тогда

H = - 0,7 log0,7 – 0,3 log0,3 = 0,881…

Применение метода Шеннона – Фано к исходному двухбуквенному алфавиту здесь оказывается бесцельным: оно приводит нас лишь к простейшему равномерному коду

буква	вероятность	кодовое обозначение
А	0,7	1
Б	0,3	0

требующему для передачи каждой буквы одного двоичного знака – на 12% больше минимального достижимого значения 0,881 дв.зн./букву. Применяя же метод Шеннона – Фано к кодированию всевозможных двухбуквенных комбинаций (вероятность которых определяется правилом умножения вероятностей для независимых событий), мы придем к следующему коду:

комбина- ция букв	вероятность	кодовое обозначение
АА	0,49	1
АБ	0,21	01
БА	0,21	001
ББ	0,09	000

Среднее значение длины кодового обозначения здесь равно

так что на одну букву алфавита здесь приходится в среднем  двоичных знаков – лишь на 3% больше значения 0,881 дв.зн./букву. Еще лучше результаты мы получим, применив метод Шеннона – Фано к кодированию трехбуквенной комбинации; при этом мы придем к следующему коду:

комбина- ция букв	вероятность	кодовое обозначение
ААА	0,343	11
ААБ	0,147	10
АБА	0,147	011
БАА	0,147	010
АББ	0,063	0010
БАБ	0,063	0011
ББА	0,063	0001
БББ	0,027	0000

Среднее значение длины кодового обозначения здесь равно 2,686, т.е. на одну букву текста приходится в среднем 0,895 двоичных знаков, что всего на 1,5% больше значения  дв.зн./букву.

    В случае еще большей разницы в вероятностях букв А и Б приближение к минимально возможному значению Н дв.зн./букву может несколько менее быстрым, но оно проявляется не менее наглядно. Так, при р(А) = 0,89 и р(Б) = 0,11 это значение равно  – 0,89 log0,89 – 0,11 log0,11 ≈ 0,5 дв.зн./букву, а равномерный код  (равносильный применению кода Шеннона – Фано к совокупности двух имеющихся букв) требует затраты одного двоичного знака на каждую букву – в два раза больше. Нетрудно проверить, что применение кода Шеннона – Фано к всевозможным двухбуквенным комбинациям здесь приводит к коду, в котором на каждую букву приходится в среднем 0,66 двоичных знаков, применение к трехбуквенным комбинациям - 0,55, а к четырехбуквенным блокам - в среднем 0,52 двоичных знаков – всего на 4% больше минимального значения 0,50 дв.зн./букву.

    1.3 Коды Хафмана.

    Близок к коду Шеннона – Фано, но еще выгоднее, чем последний, так называемый код Хафмана. Построение этого кода опирается на простое преобразование используемого алфавита, называемое сжатием алфавита. Пусть мы имеем алфавит А, содержащий буквы

Условимся теперь не различать между собой две наименее вероятные буквы нашего алфавита, т.е. будем считать, что а_п-1 и а_п – это одна и та же буква b нового алфавита А₁, содержащего теперь уже буквы  и b (т.е. а_п-1 или а_п), вероятности появления которых в сообщении соответственно равны  и р_п-1 + р_п. Алфавит А₁ и называется полученным из алфавита А с помощью сжатия (или однократного сжатия).

    Расположим буквы нового алфавита А₁ в порядке убывания их вероятностей и подвергнем сжатию алфавит А₁; при этом мы придем к алфавиту А₂, который получается из первоначального алфавита А с помощью двукратного сжатия (а из алфавита А₁ – с помощью простого или однократного сжатия). Ясно, что алфавит А₂ будет содержать уже всего п – 2 буквы. Продолжая эту процедуру, мы будем приходить ко все более коротким

алфавитам; после (п – 2)-кратного сжатия мы придем к алфавиту А_п-2, содержащему уже всего две буквы.

    Вот, например, как преобразуется с помощью последовательных сжатий рассмотренный выше алфавит, содержащий 6 букв, вероятности которых равны 0,4, 0,2, 0,2, 0,1, 0,05 и 0,05:

№ буквы	Вероятности
	исходный алфавит А	сжатые алфавиты
		А1	А2	А3	А4
1		0,4	0,4	0,4	0,6
2	0,2	0,2	0,2	0,4	0,4
3	0,2	0,2	0,2	0,2
4	0,1	0,1	0,2
5	0,05	0,1
6	0,05

                                                                                       Табл.3

Условимся теперь приписывать двум буквам последнего алфавита А_п-2 кодовые обозначения 1 и 0. Далее, если кодовые обозначения уже приписаны всем буквам алфавита A_j, то буквам «предыдущего» алфавита A_j-1 (где, разумеется, А_1-1 = А₀ – это исходный алфавит А), сохранившимся и в алфавите A_j, мы пишем те же кодовые обозначения, которые они имели в алфавите A_j-1; двум же буквам a’ и a’’ алфавита A_j, «слившимся» в одну букву b алфавита A_j-1, мы припишем обозначения, получившиеся из кодового обозначения буквы b добавлением цифр 1 и 0 в конце. (Табл.4)

№ буквы	Вероятности
	исходный алфавит А	сжатые алфавиты
		А1	А2	А3	А4
1	0	0,4      0	0,4     0	0,4      0	0,6      1
2	0,2      10	0,2      10	0,2     10	0,4      11	0,4      0
3	0,2      111	0,2      111	0,2     111	0,2      10
4	0,1      1101	0,1      1101	0,2     110
5	0,05    11001	0,1      1100
6	0,05    11000

                                                                                                                          Табл. 4

Легко видеть, что из самого построения получаемого таким образом кода Хафмана вытекает, что он удовлетворяет общему условию: никакое кодовое обозначение не является здесь началом другого, более длинного кодового обозначения. Заметим еще, что кодирование некоторого алфавита по методу Хафмана (так же, впрочем, как и по методу Шеннона – Фано) не является однозначной процедурой.

Так, например, на любом этапе построения кода можно, разумеется, заменить цифру 1 на цифру 0 и наоборот; при этом мы получим два разных кода (отличающихся весьма несущественно друг от друга). Но помимо того в некоторых случаях можно построить и несколько существенно различающихся кодов Хафмана; так, например, в разобранном выше примере можно строить код и в соответствии со следующей таблицей:

№ буквы	Вероятности
	исходный алфавит А	сжатые алфавиты
		А1	А2	А3	А4
1	11	0,4       11	0,4     11	0,4      0	0,6      1
2	0,2       01	0,2       01	0,2     10	0,4      11	0,4      0
3	0,2       00	0,2       00	0,2     01	0,2      10
4	0,1       100	0,1       101	0,2     00
5	0,05     1011	0,1       100
6	0,05     1010

                                                                                                                          Табл.5

Получаемый при этом новый код также является кодом Хафмана, но длины имеющихся кодовых обозначений теперь уже оказываются совсем другими. Отметим, что среднее число элементарных сигналов, приходящихся на одну букву, для обоих построенных кодов Хафмана оказывается точно одинаковым: в первом случае оно равно

а во втором – равно

    Можно показать, что код Хафмана всегда является самым экономичным из всех возможных в том смысле, что ни для какого другого метода кодирования букв некоторого алфавита среднее число элементарных сигналов, приходящихся на одну букву, не может быть меньше того, какое получается при кодировании по методу Хафмана (отсюда, разумеется, сразу вытекает и то, что для любых двух кодов Хафмана средняя длина кодового обозначения должна быть точно одинаковой – ведь оба они являются наиболее экономными).

Рассуждения, приведенные в пунктах 1.2 и 1.3 полностью реализуются при решении  задач (пример такой задачи приведен в приложении А).

2. Энтропия конкретных типов сообщений.    

2.1 Основная теорема о кодировании.      

Достигнутая в рассмотренных  выше примерах степень близости среднего числа двоичных знаков, приходящихся на одну букву сообщения, к значению Н может быть еще сколь угодно увеличена при помощи перехода к кодированию все более и более длинных блоков. Это вытекает из следующего общего утверждения, которое мы будем в дальнейшем называть основной теоремой о кодировании, точнее, основной теоремой о кодировании при отсутствии помех: при кодировании сообщения, разбитого на N-буквенные блоки, можно, выбрав N достаточно большим, добиться того, чтобы среднее число двоичных элементарных сигналов, приходящихся на одну букву исходного сообщения, было сколь угодно близко к Н. Кодирование сразу длинных блоков имеет значительные преимущества при наличии помех, препятствующих работе линии связи.

    Ввиду большой важности сформулированной здесь основной теоремы о кодировании мы приведем ниже ее доказательство, основанное на использовании метода кодирования Шеннона - Фано. Предположим сначала, что при составляющем основу метода Шеннона – Фано последовательном делении совокупности кодируемых букв (под которыми могут пониматься также целые «блоки») на все меньшие и меньшие группы нам каждый раз удается добиться того, чтобы вероятности двух получаемых групп были точно равны между собой. В таком случае после первого деления мы придем к группам, имеющим суммарную вероятность ½, после второго – к группам суммарной вероятности ¼, …, после l-го деления – к группам суммарной вероятности 1/2^l. При этом l-значное кодовое обозначении будут иметь те буквы, которые оказываются выделенными в группу из одного элемента ровно после l делений; иначе говоря, при выполнении этого условия длина l_i кодового обозначения будет связана с вероятностью р_i соответствующей буквы формулой

В общем случае величина – log p_i, где p_i – вероятность i-й буквы алфавита, целым числом не будет, поэтому длина l_i кодового обозначения i-й буквы не сможет быть равна log p_i. Поскольку при кодировании по методу Шеннона – Фано мы последовательно делим наш алфавит на группы, по возможности близкой суммарной вероятности, то длина кодового обозначения i-й буквы при таком кодировании будет близка к – log p_i. Обозначим, в этой связи, через l_i первое целое число, не меньше чем – log p_i:

                                                 (А)

Последнее неравенство можно переписать еще так:

или

                                                           (Б)

    Здесь отметим, что в случае любых п чисел

                                                       (1)

существует двоичный код, для которого эти числа являются длинами кодовых обозначений, сопоставляемых п буквам некоторого алфавита.

Среднее число l двоичных сигналов, приходящихся на одну букву исходного сообщения (или, средняя длина кодового обозначения) дается суммой

Умножим теперь задающее величину l_i неравенство (А) на p_i, сложим все полученные таким образом неравенства, отвечающие значениям i = 1, 2, …, п, и учтем, что

где   - энтропия опыта p₁ + p₂ + … +p_n = 1. В результате получаем, что

    Применим это неравенство к случаю, когда описанный выше метод используется для кодирования всевозможных N-буквенных блоков (которые можно считать буквами нового алфавита). В силу предположения о независимости последовательных букв сообщения энтропия опыта

Следовательно, средняя длина l_N кодового обозначения N-буквенного блока удовлетворяет неравенствам

Но при кодировании сразу N-буквенных блоков среднее число l двоичных элементарных сигналов, приходящихся на одну букву сообщения, будет равно средней длине l_N кодового обозначения одного блока, деленной на число N букв в блоке:

Поэтому при таком кодировании

то есть здесь среднее число элементарных сигналов, приходящихся на одну букву, отличается от минимального значения Н не больше, чем на

    Приведенное доказательство может быть применено также и к более общему случаю, когда последовательные буквы текста являются взаимно зависимыми. При этом придется только неравенство для величины l_N писать в виде

где

- энтропия N-буквенного блока, которая в случае зависимости букв сообщения друг от друга всегда будет меньше чем NH (ибо  и

значит, в этом более общем случае при  (при безграничном увеличении длины блоков) среднее число элементарных сигналов, затрачиваемых на передачу одной буквы, неограниченно приближается к величине

есть «удельная энтропия», приходящаяся на одну букву многобуквенного текста. Существование предела  следует из неравенств  является монотонно не возрастающей последовательностью положительных (больших 0) чисел.

    Все предыдущее утверждения легко переносятся также и на случай т-ичных кодов, использующих т элементарных сигналов. Так, для построения т-ичных кодов Шеннона – Фано надо лишь разбивать группы символов не на две, а на т частей по возможности близкой вероятности, а для построения т-ичного кода Хаффмана надо использовать операцию сжатия алфавита, при которой каждый раз сливаются не две, а т букв исходного алфавита, имеющих наименьшие вероятности. Ввиду важности кодов Хаффмана, остановимся на последнем вопросе чуть подробнее. Сжатие алфавита, при котором т букв заменяются на одну, приводит к уменьшению числа букв на т – 1; так как для построения т-ичного кода, очевидно, требуется, чтобы последовательность «сжатий» в конце концов привела нас к алфавиту из т букв (сопоставляемых т сигналам кода), то необходимо, чтобы число п букв первоначального алфавита было представимо в виде n = m + k(m - 1), где k – целое число. Этого, однако, всегда можно добиться, добавив, если нужно, к первоначальному алфавиту еще несколько «фиктивных букв», вероятности которых считаются равными нулю. После этого построение т-ичного кода Хаффмана и доказательство его оптимальности (среди всех т-ичных кодов) проводятся уже точно так же, как и случае двоичного кода. Так, например, в случае уже рассматривавшегося выше алфавита из 6 букв, имеющих вероятности 0,4, 0,2, 0,2, 0,1, 0,05, и 0,05 для построения троичного кода Хаффмана, надо присоединить к нашему алфавиту еще одну букву нулевой вероятности и далее поступать так, как указано ниже:

№ буквы	вероятности и кодовые обозначения
	исходный алфавит	сжатые алфавиты
1	0,4             0	0,4               0	0,4                0
2	0,2             2	0,2               2	0,4                1
3	0,2            10	0,2              10	0,2                2
4	0,1            11	0,1              11
5	0,05          120	0,1              12
6	0,05          121
7	0                -

                                                        Табл.6

Столь же просто переносятся на случай т-ичных кодов и на приведенное выше доказательство основной теоремы о кодировании. В частности, соответствующее видоизменение основывается на том факте, что  любые п чисел l₁, l₂, …, l_n , удовлетворяющих неравенству

являются длинами кодовых обозначений некоторого т-ичного кода для п-буквенного алфавита. Повторяя рассуждения для случая т = 2, легко получить следующий результат (называемый основной теоремой о кодировании для  т-ичных кодов):  при любом методе кодирования, использующем т-ичный код, среднее число элементарных сигналов, приходящихся на одну букву сообщения, никогда не может быть меньше отношения   (где Н – энтропия одной буквы сообщения); однако оно всегда может быть сделано сколь угодно близким к этой величине, если кодировать сразу достаточно длинные «блоки» из N букв. Отсюда ясно, что если по линии связи за единицу времени можно передать L элементарных сигналов (принимающих т различных значений), то скорость передачи сообщений по такой линии не может быть большей, чем

 букв/ед. времени;

однако передача со скоростью, сколь угодно близкой к v (но меньшей v!), уже является возможной. Величина v, зависит лишь от самой линии связи (в то время как знаменатель Н характеризует передаваемое сообщение). Эта величина указывает на наибольшее количество единиц информации, которое можно передать по нашей линии за единицу времени (ибо один элементарный сигнал, как мы знаем, может содержать самое большее log m единиц информации); она называется пропускной способностью линии связи. Понятие пропускной способности играет важную роль в теории связи.        

 2.2 Энтропия и информация конкретных типов сообщений.

2.2.1 Письменная речь

Для передачи М-буквенного сообщения допускающей m различных элементарных сигналов, требуется затратить не меньше чем  сигналов, где n — число букв «алфавита. Так как русский «телеграфный» алфавит содержит 32 буквы (не различаются букв е и ё, ь и ъ, но причисляются к числу букв и «нулевая буква» — пустой промежуток между словами), то на передачу М-буквенного сообщения надо затратить  элементарных сигналов. Здесь

Н₀ = log 32 = 5 бит

- энтропия опыта, заключающегося в приеме одной буквы русского текста, при условии, что все буквы считаются одинаково вероятными.

Для получения текста, в котором каждая буква содержит 5 бит информации требуется выписать 32 буквы на отдельных билетиках, сложить все эти билетики в урну и затем вытаскивать их по одному, каждый раз записывая вытянутую букву, а билетик возвращая обратно в урну и снова перемешивая ее содержимое. Произведя такой опыт, мы придем к «фразе» вроде следующей:

СУХЕРРОБЬДЩ ЯЫХВЩИЮАЙЖТЛФВНЗАГФОЕН-ВШТЦР ПХГБКУЧТЖЮРЯПЧЬКЙХРЫС

Разумеется, этот текст имеет очень мало общего с русским языком!

Для более точного вычисления информации, содержащейся в одной букве русского текста, надо знать вероятности появления различных букв. Ориентировочные значения частот отдельных букв русского языка собраны в следующей таблице:

буква относ. частота	– 0,175	о 0,090	е, ё 0,072	а 0,062	и 0,062	т 0,053	н 0,053	с 0,045
буква относ. частота	р 0,040	в 0,038	л 0,035	к 0,028	м 0,026	д 0,025	п 0,023	у 0,021
буква относ. частота	я 0,018	ы 0,016	з 0,016	ь, ъ 0,014	б 0,014	г 0,013	ч 0,012	й 0,010
буква относ. частота	х 0,009	ж 0,007	ю 0,006	ш 0,006	ц 0,004	щ 0,003	э 0,003	ф 0,002

                                                                                                                             Табл.7

Приравняв эти частоты вероятностям появления соответствующих букв, получим для энтропии одной буквы русского текста  приближенное  значение ):

Из сравнения этого значения с величиной Н₀ = log 32 = 5 бит видно, что неравномерность появления различных букв алфавита приводит к уменьшению информации, содержащейся в одной букве русского текста, примерно на 0,65 бит.

Сокращение числа требующихся элементарных сигналов можно показать кодированием отдельных букв русского алфавита по методу Шеннона — Фано:

буква	код. обозн.	буква	код. обозн.	буква	код. обозн.
	111	к	01000	х	0000100
а	1010	л	01001	ц	00000010
б	000101	м	00111	ч	000011
в	01010	н	0111	ш	00000011
г	000100	о	110	щ	00000001
д	001101	п	001100	ы	001000
е, ё	1011	р	01011	ь,ъ	000110
ж	0000011	с	0110	э	000000001
в	000111	т	1000	ю	00000010
и	1001	у	00101	я	001001
й	0000101	ф	000000000

                                                                                            Табл.8

Среднее количество элементарных сигналов при таком методе кодирования,  будет равно

то есть будет весьма близко к значению

При определении энтропии  опыта  состоящего в определении одной буквы русского текста, мы считали все буквы независимыми. Это значит, что для составления «текста», в котором каждая буква содержит  бит информации, мы должны прибегнуть к помощи урны, в которой лежат тщательно перемешанные 1000 бумажек, на 175 из которых не написано ничего, на 90 — написана буква о, на 72 — буква е, ..., наконец, на 2 бумажках — буква ф (см. табл.7). Извлекая из такой урны бумажки по одной, мы придем к «фразе» вроде следующей:

ЕЫНТ ЦИЯЬА ОЕРВ ОДНГ ЬУЕМЛОЛЙК ЗБЯ ЕНВТША.

Эта «фраза» несколько более похожа на осмысленную русскую речь, чем предыдущая, но и она, разумеется, еще очень далека от разумного текста.

Несходство нашей фразы с осмысленным текстом естественно объясняется тем, что на самом деле последовательные буквы русского текста вовсе не независимы друг от друга. Так, например, если мы знаем, что очередной буквой явилась гласная, то значительно возрастает вероятность появления на следующем месте согласной буквы; буква «ь» никак не может следовать ни за пробелом, ни за гласной буквой; за буквой «ч» никак не могут появиться буквы «ы», «я» или «ю», а скорее всего будет стоять одна из гласных «и» и «е» или согласная «т» и т. д.

Наличие в русском языке дополнительных закономерностей, не учтенных в нашей «фразе», приводит к дальнейшему уменьшению степени неопределенности одной буквы русского текста. Для этого надо лишь подсчитать условную энтропию  опыта предшествующей буквы того же текста. Условная энтропия  определяется следующей формулой:

р(-), р(а), р(б), ..., р(я) обозначены вероятности (частоты) отдельных букв русского языка. Разумеется  заранее можно сказать, что вероятности р(- -), р(яь)  и многие другие (например, р(ьь), р(- ь), р(чя) и т.д.) будут равны нулю. Мы можем быть уверены, что условная энтропия  окажется меньше безусловной энтропии

Величину  можно конкретизировать как «среднюю информацию», содержащуюся в определении исхода следующего опыта. Имеется 32 урны, обозначенные 32 буквами русского алфавита; в каждой из урн лежат бумажки, на которых выписаны двухбуквенные сочетания, начинающиеся с обозначенной на урне буквы, причем количества бумажек с разными парами букв пропорциональны частотам (вероятностям) соответствующих двухбуквенных сочетаний. Опыт состоит в многократном извлечении бумажек из урн и выписывании с них последней буквы. При этом каждый раз (начиная со второго) бумажка извлекается из той урны, которая содержит сочетания, начинающиеся с последней выписанной буквы; после того как буква выписана, бумажка возвращается в урну, содержимое которой снова тщательно перемешивается. Опыт такого рода приводит к «фразе» вроде следующей:

УМАРОНО КАЧ ВСВАННЫЙ РОСЯ НЫХ КОВКРОВ

НЕДАРЕ.

По звучанию эта «фраза» заметно ближе к русскому языку.

Знание двух предшествующих букв еще более уменьшает неопределенность опыта, состоящего в определении следующей буквы, что находит отражение в положительности разности  -  «условная энтропия второго порядка»:

            Наглядным подтверждением сказанного является опыт, состоящий в вытаскивании бумажек с трехбуквенными сочетаниями из 32² урн, в каждой из которых лежат бумажки, начинающиеся на одни и те же две буквы (или опыт с русской книгой, в которой много раз наудачу отыскивается первое повторение последнего уже выписанного двухбуквенного сочетания и выписывается следующая за ним буква), приводит к «фразе» вроде следующей:

ПОКАК ПОТ ДУРНОСКАКА НАКОНЕПНО ЗНЕ

СТВОЛОВИЛ СЕ ТВОЙ ОБНИЛЬ,

еще более близкой к русской речи, чем предыдущая.

Аналогично этому можно определить и энтропию

отвечающую опыту по определению буквы русского текста при условии знания трех предшествующих букв. Он состоит в извлечении бумажек из 32³ урн с четырехбуквенными сочетаниями (или — аналогичный описанному выше эксперимент с русской книгой), приводит к «фразе» вроде следующей:

ВЕСЕЛ ВРАТЬСЯ НЕ СУХОМ И НЕПО И КОРКО,

Еще лучшее приближение к энтропии буквы осмысленного русского текста дают величины

при N = 5,6, .... Нетрудно видеть, что с ростом N энтропия Н_N может только убывать.

 Если еще учесть, что все величины Н_N положительны, то отсюда можно будет вывести, что величина  при  стремится к определенному пределу

Нам уже известно, что среднее число элементарных сигналов, необходимое для передачи одной буквы русского текста, не может быть меньшим

Разность  к величине

Избыточность R является весьма важной статистической характеристикой языка, но ее численное значение пока ни для одного языка не определено с удовлетворительной точностью. В отношении русского языка, в частности, имеются лишь данные о значениях величин Н₂ и Н₃.

Н0	Н1	Н2	Н3
log 32 = 5	4,35	3,52	3,01

(для полноты мы здесь привели также и значения энтропии Н₀ и Н₁). Отсюда можно только вывести, что для русского языка R значительно больше этого числа.

Ясно, что для всех языков, использующих латинский алфавит, максимальная информация Н₀, которая могла бы приходиться па одну букву текста, имеет одно и то же значение:

(26 различных букв алфавита и 27-я «буква» — пустой промежуток между словами). Использовав   таблицы  относительных частот различных букв в английском, немецком, французском и испанском языках, можно показать, что энтропия Н₁ для этих языков равна (в битах):

язык	англ.	немецк.	франц.	испанск.
Н1	4,03	4,10	3,96	3,98

Мы видим, что во всех случаях величина Н₁ заметно меньше, чем Н₀ = log 27  4,76 бит, причем ее значения для различных языков не очень сильно разнятся между собой.

Величины Н₂ и Н₃ для английского языка были подсчитаны Шенноном, при этом он использовал имеющиеся таблицы частот в английском языке различных двухбуквенных и трехбуквенных сочетаний. Учтя также и статистические данные о частотах появления различных слов в английском языке, Шеннон сумел приближенно оценить и значения величин Н₅ и H₈.

В результате он получил:

Н0	Н1	Н2	Н3	Н5	Н8
4,76	4,03	3,32	3,10	≈2,1	≈1,9

Отсюда можно заключить, что для английского языка избыточность R во всяком случае не меньше, чем

Подсчет величин Н₉, Н₁₀ и т. д. по известной нам формуле невозможенен, так как уже для вычисления Н₉ требуется знание вероятностей всех 9-буквенных комбинаций, число которых выражается 13-значным числом (триллионы!). Поэтому для оценки величин H_N при больших значениях N приходится ограничиваться косвенными методами. Остановимся на одном из такого рода методе, предложенном Шенноном.

«Условная энтропия» Н_N представляет собой меру степени неопределенности опыта N-й буквы текста, при условии, что предшествующие N — 1 букв нам известны. Эксперимент по отгадыванию N-й буквы легко может быть поставлен: для этого достаточно выбрать (N — 1)-буквенный отрывок осмысленного текста и предложить кому-либо отгадать следующую букву. Подобный опыт может быть повторен многократно, при этом трудность отгадывания N-й буквы может быть оценена с помощью среднего значения Q_N числа попыток, требующихся для нахождения правильного ответа. Ясно, что величины Q_N, определенные для разных значений N, являются определенными характеристиками статистической структуры языка, в частности, его избыточности. Шеннон произвел ряд подобных экспериментов, в которых N принимало значения 1, 2, 3, ..., 14, 15 и 100. При этом он обнаружил, что отгадывание 100-й буквы по 99 предшествующим является заметно более простой задачей, чем отгадывание 15-й буквы по 14 предыдущим. Отсюда можно сделать вывод, что Н₁₅ ощутимо больше, чем Н₁₀₀, т. е. что Н₁₅ никак еще нельзя отождествить с предельным значением N = 1, 2, 4, 8, 16, 32, 64, 128 и N ≈ 10 000. Из полученных данных можно заключить, что величина Н₃₂ (так же как и H₆₄ и Н₁₂₈) практически не отличается от Н₁₀₀₀₀, в то время как «условная энтропия» Н₁₆ еще заметно больше этой величины. Таким образом, можно предположить, что при возрастании N величина H_N убывает вплоть до значений N  = 30, но при дальнейшем росте N она уже практически не меняется; поэтому вместо «предельной энтропии»  можно говорить, например, об условной энтропии H₃₀ или H₄₀.

Эксперименты по отгадыванию букв не только позволяют судить о сравнительной величине условных энтропии H_N при разных N, но дают также возможность оцепить и сами значения Н_N. По данным таких экспериментов можно определить не только среднее число Q_N попыток, требующихся для отгадывания N-й буквы текста по N — 1 предшествующим, но и вероятности (частоты)  того, что буква будет правильно угадана с 1-й, 2-й, 3-й, ..., n-й попытки (где п = 27 - число букв алфавита; Q_N = равны вероятностям  букв  алфавита, расположенных в порядке убывания частот. В самом деле, если ни одна из букв, предшествующих отгадываемой букве х, нам не известна, то естественно прежде всего предположить, что х совпадает с самой распространенной буквой a₁ (причем вероятность правильно угадать здесь будет равна р(а₁)); затем следует предположить, что х совпадает с а₂ (вероятность правильного ответа здесь будет равна р(а₂)) и т. д. Отсюда следует, что энтропия Н₁ равна сумме

.

Если же N > 1, то можно  показать, что сумма

(*)

не будет превосходить условную энтропию H_N (это связано с тем, что величины  представляют собой определенным образом усредненные вероятности исходов опыта

     (**)

при всяком N будет не больше условной энтропии Н_N. Таким образом, выражения (*) и (**) (составленные из вероятностей H_N.

Надо только еще иметь в виду, что обе оценки (*) и (**) получаются в предположении, что  - это те вероятности угадывания буквы по N — 1 преды­дущим буквам с первой, второй, третьей и т. д. попыток, которые получаются в предположении, что отгадывающий всегда называет очередную букву наиболее целе­сообразно — с полным учетом всех статистических закономерностей данного языка. В случае же реальных опытов любые ошибки в стратегии отгадывающего (т. е. отличия называемых им букв от тех, которые следовало бы назвать, исходя из точной ста­тистики языка) будут неизбежно приводить к завышению обеих сумм (*) и (**); именно поэтому целесообразно учи­тывать лишь данные «наиболее успешного отгадывающего», так как для него это завышение будет наименьшим. Поскольку каждый отгадывающий иногда оши­бается, то оценку (**) на практике нельзя считать вполне надежной оценкой снизу истинной энтропии (в отличие от оценки сверху (*), которая из-за ошибок отгадывающего может только стать еще больше).

Кроме того, значения сумм (*) и (**), к сожалению, не сближаются неограниченно при увеличении N (на­чиная с N ≈ 30 эти суммы вообще перестают зависеть от N); поэтому полученные на этом пути оценки избыточности языка не будут особенно точными. В частности, опыты Шеннона показали лишь, что величина H₁₀₀ по-видимому, заключается между 0,6 и 1,3 бит. Отсюда можно заключить, что избыточность

для английского языка по порядку величины должна быть близка к 80%.

2.2.2  Устная речь.

Перейдем теперь к вопросу об энтропии и информации устной речи. Ес­тественно думать, что все статистические характеристики такой речи будут еще более зависеть от выбора разговари­вающих лиц и от характера их разговора. Пониженное значение энтропии устной речи может быть связано с тем, что в разговоре мы зачастую употреб­ляем больше повторений одних и тех же слов и нередко добавляем довольно много «лишних» слов — это делается как для облегчения восприятия речи, так и просто затем, чтобы говорящий имел время обдумать, что он хочет сказать дальше.

Определив среднее число букв, произносимых за еди­ницу времени, можно приближенно оценить количество информации, сообщаемое при разговоре за 1 сек; обычно оно имеет порядок 5 - 6 бит. Из разговора мы мо­жем судить о настроении говорящего и об его отношении к сказанному; мы можем узнать говорящего, если даже никакие другие источники информации не указывают нам его; мы мо­жем во многих случаях определить место рождения не­знакомого нам человека по его произношению; мы можем оценить громкость устной речи, которая в случае передачи голоса по линии связи во многом определяется чисто тех­ническими характеристиками линии передачи, и т. д. Количественная оценка всей этой информации представ­ляет собой очень сложную задачу, требующую значительно больших знаний об языке.

Исключением в этом отношении является сравнительно узкий вопрос о логических ударениях, подчеркивающих в фразе отдельные слова. Ударение чаще всего падает на наиболее редко употреб­ляемые слова (что, впрочем, довольно естественно - ясно, что вряд ли кто будет выделять логическим ударением наиболее распространенные слона - например, предлоги или союзы). Если вероятность того, что данное слово W_r находится под ударением, мы обозначим через q_r, то сред­няя информация, заключающаяся в сведениях о наличии или отсутствии ударения на этом слове, будет равна

Пусть теперь  - вероятности (частоты) всех слов W₁, W₂, . . ., W_K (здесь К - общее число всех упо­требляемых слов. В таком случае для средней информа­ции Н, заключенной в логическом ударении, можно написать следующую формулу:

Cредняя информация, которую мы получаем, выяснив, на какие слова падает логическое ударение, по порядку величины близка к 0,65 бит/слово.

Во время разговора отдельные буквы никогда не про­износятся, а произносятся звуки, существенно отличаю­щиеся от букв. Поэтому основным элементом устной речи надо считать отдельный звук - фонему. Осмысленная устная речь составляется из фонем точно так же, как осмысленная письменная речь составляется из букв. Поэтому во всех случаях, когда нас интересует лишь передача «смысловой информации» устной речи наибольший интерес представляет не энтропия и информация одной «произнесенной буквы», а энтропия и информация одной реально произ­несенной фонемы.

Список фонем данного языка, разумеется, не совпадает со списком букв алфавита,  так как одна и та же буква в раз­ных случаях может звучать по-разному. В русском языке 42 различные фонемы и подсчитали частоты отдельных фонем (а также различных комбинаций двух и трех следующих друг за другом фонем). Н₀ = log 42 одной фонемы, энтропии первого порядка  (где  - относительные частоты различных фонем) и «условных энтропии» Н₂ и Н₃:

Н0	Н1	Н2	Н3
log 42 ≈ 5,38	4,77	3,62	0,70

Если сравнить эти значения со значениями величин Н₀, Н₁, Н₂, H₃ для пись­менной русской речи, то убывание ряда условных энтропии для фонем происходит заметно быстрее, чем в случае букв  письменного текста.

Для определения избыточности R^(слова), можно ус­тановить связь между избыточностями устной и письмен­ной речи. Из того, что устная речь может быть записана, а письменная - прочитана, следует, что «полная инфор­мация», содержащаяся в определенном тексте, не зави­сит от того, в какой форме - устной или письменной - этот текст представлен, т. е. что

Отсюда вытекает, что

где  есть среднее число букв, приходящихся на одну фонему («средняя длина фонемы»). Эта величина явля­ется важной статистической характеристикой языка, связывающей устную и письменную речь. Из последней формулы следует также, что

или

где k - общее число фонем, а п - число букв; за  здесь естественнее принимать

2.2.3 Музыка.

Исследования того же рода могут быть проведены и в отношении музыкальных сообщений. Естест­венно думать, что связи между последовательными зву­ками некоторой мелодии, выражающимися отдельными нотными знаками, достаточно сильны: так как одни соче­тания звуков будут более благозвучны, чем другие, то первые будут встречаться в музыкальных произве­дениях чаще вторых. Если мы выпишем ряд нот на­удачу, то информация, содержащаяся в каждой ноте этой записи, будет наибольшей; однако с музыкальной точки зрения такая хаотическая последовательность нот не будет представлять никакой ценности. Для того чтобы получить приятное на слух звучание, необходимо внести в наш ряд определенную избыточность; при этом можно опасаться, что в случае слишком большой избыточности, при которой последующие ноты уже почти  однозначно определяются предшествующими, мы получим лишь край­не монотонную и малоинтересную музыку. Какова же та избыточность, при которой может получиться «хорошая» музыка?

Избыточность простых мело­дий никак не меньше, чем избыточность осмысленной речи. Необходимо было бы специально изучить вопрос об избыточности различных форм музыкальных произведений или произведений различных композиторов. К примеру, проанализировать с точ­ки зрения теории информации популярный альбом детских песенок. Для простоты в этой работе предполагалось, что все звуки находятся в пределах одной октавы; так как в рассматриваемых мелодиях не встречались так называемые хроматизмы, то все эти мелодии могли быть приведены к семи основным звукам; До, ре, ми, фа, соль, ля и си, каждый длительностью в одну восьмую. Учет звуков, длительностью более одной восьмой, осуществлял­ся с помощью добавления к семи нотам восьмого «основ­ного элемента» О, обозначающего продление предшествую­щего звука еще на промежуток времени в одну восьмую (или же паузу в одну восьмую). Таким образом, «макси­мальная возможная энтропия» Н₀ одной ноты здесь равна

Н₀ = log 8 = 3 бита.

Подсчитав частоты (вероятности) отдельных нот во всех 39 анализируемых песенках, находим, что

С помощью найденных вероятно­стей сочетаний из двух нот, можно подсчитать также условную энтропию Н₂, она оказывается близкой к 2,42 . По одним только зна­чениям Н₁ и Н₂ еще очень мало что можно сказать о сте­пени избыточности рассматриваемых, по-видимому, она заметно выше, чем

2.2.4 Передача телевизионных изображений.

Наш глаз способен различить лишь конечное число степеней яркости изо­бражения и лишь не слишком близкие его участки, по­этому любое изображение можно передавать «по точкам», каждая из которых является сигналом, принимающим лишь конечное число значений. Не­обходимо учитывать значительное число (несколько десятков) градаций степени почернения («яркости») каждого элемента, кроме того, на телеэкране ежесекундно сменяется 25 кадров, создавая впечатление «движения». Однако, по линии связи фактически пере­дается не исход опыта  может иметь уже лишь конечное число исходов, и мы можем измерить его энтропию Н.

Общее число элементов («точек») для черно-белого телевидения, на которые следует разлагать изображение, определяется в первую очередь так называемой «разрешающей способностью» глаза, т. е. его способностью различать близкие участки изображения. В современном телевидении это число обычно имеет поря­док нескольких сотен тысяч (в советских телепередачах изображение разлагалось на 400 000 - 500 000 элементов, в американских - примерно на 200 000 - 300 000, в пере­дачах некоторых французских и бельгийских телецен­тров - почти на 1 000 000). Нетрудно понять, что по этой причине энтропия телевизионного изображения имеет огромную величину. Если даже считать, что человеческий глаз различает лишь 16 разных градаций яркости (значение явно заниженное) и что изображение раз­лагается всего на 200000 элементов, то мы найдем, что «эн­тропия нулевого порядка» здесь равна Н₀ = log 16²⁰⁰⁰⁰⁰ = 800 000 бит. Значение истинной энтропии Н, разумеется, будет меньше, так как телевизионное изображение имеет значительную избыточность Н₀ мы предполагали, что значения яркости в любых двух «точках» изображения являются независимыми между собой, в то время как на самом деле яркость обычно очень мало меняется при пере­ходе к соседним элементам того же (или даже другого, но близкого по времени) изображения. Наглядный смысл этой избыточности R заключается в том, что среди наших 16²⁰⁰⁰⁰⁰ возможных комбинаций значений яркости во всех точках экрана осмысленные комбинации, которые можно назвать «изображениями», будут составлять лишь ничтожно малую часть, а остальное будет представлять собой совершенно беспорядочную совокупность точек разной яркости, весьма далекую от какого бы то ни было «сюжета». Между тем реальная «сте­пень неопределенности» Н телевизионного изображения должна учитывать только те комбинации зна­чений яркости, которые имеют хоть какие-то шансы быть переданными. Для определения точного значения энтропии Н (или избыточности R) телевизионного изображения нужно детально изучить статистические зависимости между яр­костями различных точек экрана. Так, найдены значения энтропий Н₀, Н₁, Н₂ и Н₃ для двух конкретных телеви­зионных изображений, первое из которых (изображение А — парк с деревьями и строениями) было более сложным, а второе (изображение В — довольно темная галерея с прохожими) было более однотонным по цвету и содержа­ло меньше деталей, при этом различали 64 разных градаций яркости элемента телевизионного изображения, поэтому энтропия Н₀ (отнесенная к одному элементу, а не ко всему изображению в целом) здесь оказалась рав­ной Н₀ = log 64 = 6 бит. Далее с помощью специального радиотехнического устройства были подсчитаны для обоих рассматриваемых изображений относительные частоты (вероятности)  всех различимых градаций яркости и определил «энтропию первого порядка»

То же самое радиотехническое устройство было применено затем для вычисления относительных частот p_ij пар соседних (по горизонтали) элементов, в ко­торых первый элемент имеет i-e значение яркости, а вто­рой j-e, а также относительных частот p_ijk троек соседних (также лишь по горизонтали) элементов, в которых первый элемент имел i-e значение яркости, второй j-e, а третий k-е (числа i, j, и k пробегали все значения от 1 до 64). Эти частоты позволили определить «энтропии сложных опытов»

 

и  

а затем и «условные энтропии»

  и  

последняя ив которых, впрочем, была подсчитана лишь для изображения Б. Полученные результаты сведены в сле­дующую таблицу:

	Н0	Н1	Н2	Н3
Изображение А	6	5,7	3,4	—
Изображение Б	6	4,3	1,9	1,5

Избыточность R, оцененная по величине Н₂ для изображения А равна 44%, а для изображения Б - 68%; действительное значение избыточности может быть только больше этого. Что же касается услов­ной энтропии Н₃ при известных яркостях двух предыду­щих элементов той же строки, то она сравнительно мало отличается от Н₂ (изображение Б, 75%); отсюда можно заключить, что знание яркости самого близкого элемента определяет весьма большую часть общей избыточности.

Близкий характер имеет также другой опыт, опирающийся на разбиение возможных значений яркости элемента телевизионного изображения на 8, а не на 64 градаций, для которого вычислены энтропии Н₀ и Н₁ и ряда услов­ных энтропии Н₂, Н₃ и Н₄ одного элемента изображения для следующих четырех спортивных телевизионных сюжетов: А - быстро бегущие баскетболисты, Б - лицо одного зрителя на трибуне стадиона крупным планом, В - панорамирование вида зрителей на трибуне и Г - быстро бегущие футболисты. Будем обозначать циф­рами 1 и 2 соседние с данным по горизонтали и по вер­тикали элементы изображения, цифрой 3 — соседний по диагонали элемент, цифрой 4 — тот же, что и рассматри­ваемый, элемент на предшествующем кадре телевизионной передачи,  цифрой 5 — элемент на той же горизонтали, соседний с элементом 1, и, наконец, цифрой 6 - тот же элемент на кадре, предшествующем тому, который содер­жит элемент 4 (рис 1),

                          а)                                                       б)                                          рис 1.

и будем указывать в обозна­чениях условных энтропий сверху в скобках номера эле­ментов изображения, степень яркости которых считается известной. В таком случае значения энтропии (в битах) могут быть сведены в следующую таблицу:

А	3	1,96	0,69	0,98	-	1,77
Б	3	1,95	0,36	0,36	-	-
В	3	2,78	1,34	1,95	2,78	-
Г	3	2,45	-	-	2,00	2,08

А	0,68	-	0,56	-	-
Б	0,35	-	0,27	0,26	-
В	-	-	1,22	1,18	1,19
Г	-	1,83	-	-	-

Результаты последнего опыта приводят к выводу, что для бедного деталями изображения («лицо») избыточность не меньше, чем 90%, а для изображения, богатого деталями («зрители»), она не меньше, чем 60%. При­чины этого расхождения пока неясны.

Для цветных телевизионных изображений информация по порядку величины сравнима с удвоенной информацией, содержащейся в соответствующем черно-белом изображении.

ЗАКЛЮЧЕНИЕ

В данной работе были поставлены следующие цели и задачи. Цель: изучить принципы кодирования информации Шеннона - Фано и Хафмана и применение их при решении задач. Задача: изучить энтропии и избыточность конкретных типов сообщений для последующего применения к ним принципов Шеннона - Фано и Хафмана.

После выполнения целей и задач дипломной работы были сделаны следующие выводы.

До появления работ Шеннона и Фано, кодирование символов алфавита при передаче сообщения по каналам связи осуществлялось одинаковым количеством бит, получаемым по формуле Хартли. С появлением этих работ начали появляться способы, кодирующие символы разным числом бит в зависимости от вероятности появления их в тексте, то есть более вероятные символы кодируются короткими кодами, а редко встречающиеся символы - длинными (длиннее среднего).

С тех пор, как Д.А.Хаффман опубликовал в 1952 году свою работу "Метод построения кодов с минимальной избыточностью", его алгоритм кодирования стал базой для огромного количества дальнейших исследований в этой области. Стоит отметить, что за 50 лет со дня опубликования, код Хаффмана ничуть не потерял своей актуальности и значимости. Так с уверенностью можно сказать, что мы сталкиваемся с ним, в той или иной форме (дело в том, что код Хаффмана редко используется отдельно, чаще работая в связке с другими алгоритмами), практически каждый раз, когда архивируем файлы, смотрим фотографии, фильмы, посылаем факс или слушаем музыку.

Преимуществами данных методов являются их очевидная простота реализации и, как следствие этого, высокая скорость кодирования и декодирования. Основным недостатком является их неоптимальность в общем случае.

ВВЕДЕНИЕ Новые направления, возникшие в математике в ХХ ве­ке, обычно оперируют со сложными понятиями и представлениями, которые с трудом поддаются попу­ляризации. На этом фоне весьма значительна заслуга выдающегося американского математика и инж

 

• 14:21 05 Июля 2016
  Российско-китайский медуниверситет откроет магистерскую программу по TCM
• 01:21 05 Июля 2016
  На форуме МГУ Россия и Китай обсудят научно-образовательное сотрудничество
• 11:00 04 Июля 2016
  Реморенко: "ЕГЭ-туризм" в России сходит на нет
• 10:52 04 Июля 2016
  Летняя российско-австрийская школа откроется в Москве
• 15:31 01 Июля 2016
  В СПбГУ могут воссоздать географический факультет

Заказать уникальную работу