Компьютеры и периферийные устройства

Историческая личность

Культурология

История

История экономических учений

Военная кафедра

Теория государства и права

Конституционное (государственное) право зарубежных стран

Химия

Конституционное (государственное) право России

Менеджмент (Теория управления и организации)

Физика

Геодезия, геология

Литература, Лингвистика

Математика

История отечественного государства и права

Космонавтика

География, Экономическая география

Биология

Астрономия

Социология

Сельское хозяйство

Экономическая теория, политэкономия, макроэкономика

Религия

Римское право

История государства и права зарубежных стран

Педагогика

Микроэкономика, экономика предприятия, предпринимательство

Технология

Международные экономические и валютно-кредитные отношения

Музыка

Бухгалтерский учет

Искусство

Криминалистика и криминология

Банковское дело и кредитование

Философия

Страховое право

Гражданская оборона

Физкультура и Спорт

Экономика и Финансы

Государственное регулирование, Таможня, Налоги

Международное право

Пищевые продукты

Уголовное и уголовно-исполнительное право

Экскурсии и туризм

Маркетинг, товароведение, реклама

Медицина

Психология, Общение, Человек

Ценные бумаги

Транспорт

Политология, Политистория

Право

Охрана природы, Экология, Природопользование

Компьютеры, Программирование

Радиоэлектроника

Архитектура

Земельное право

Материаловедение

Здоровье

Административное право

Металлургия

Компьютерные сети

Экологическое право

Финансовое право

Техника

Уголовный процесс

Программное обеспечение

Экономико-математическое моделирование

Гражданское право

Биржевое дело

Теория систем управления

Программирование, Базы данных

Российское предпринимательское право

Нероссийское законодательство

Арбитражно-процессуальное право

Авиация

Геология

Трудовое право

Иностранные языки

Таможенное право

Уголовное право

Ветеринария

Налоговое право

Разное

Правоохранительные органы

Подобные работы

Коды Шеннона – Фано и Хафмана

echo "Исследователи занимались вопросами энтропии, содержимого информации и избыточности. Интересно, что эти первоначальные работы в области сжатия информации велись до появления современного цифрово

Выборочное наблюдение

echo "Выборочный метод обследования, или как его часто называют выборка, применяется прежде всего в тех случаях, когда сплошное наблюдение вообще невозможно. Обследование может быть связано с уничтож

Использование статистических методов в анализе успеваемости ВУЗов

echo "Качество высшего образования понимается как «соответствие норме» в подготовке бакалавров, специалистов и магистров, а норма – требуемый уровень знаний и навыков – зафиксирована, прежде всего, в

Математический анализ. Регрессия

echo "Выдвигается и проверяется гипотеза о том что истинное значение коэффициента регрессии=0. Для проверки гипотезы используется критерий Стьюдента. "; echo ''; echo " "; echo ''; echo " к-т является

Ряд Тэйлора, законы физики и численное интегрирование дифференциальных уравнений

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

Математические софизмы

echo "Исторические сведения» Понятие софизма. Софизм - (от греческого sophisma – уловка, ухищрение, выдумка, головоломка), умозаключение или рассуждение, обосновывающее какую-нибудь заведомую нелепос

Платоновы тела

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

Коды Шеннона – Фано и Хафмана

Коды Шеннона – Фано и Хафмана

Исследователи занимались вопросами энтропии, содержимого информации и избыточности.

Интересно, что эти первоначальные работы в области сжатия информации велись до появления современного цифрового компьютера.

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

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

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

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

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

Происходит оно от латинского « informatio », что означает – разъяснение, сообщение, осведомленность.

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

Философское, и поэтому более широкое определение этого термина дает один из основателей информатики, известный американский ученый Норберт Винер: «Информация – это обозначение содержания, черпаемого нами из внешнего мира в процессе нашего приспособления к нему и приведение в соответствие с ним нашего мышления». Разумеется, это далеко не единственные в своем роде определения информации. В настоящее время этот термин имеет более глубокий и многогранный смысл. Во многом оставаясь интуитивным, он получает разные смысловые наполнения в разных отраслях человеческой деятельности: v v v v Такое разнообразие подходов не случайно, а следствие того, что выявилась необходимость осознанной организации процессов движения и обработки того, что имеет общее название – информация. Для дальнейшего рассмотрения нам необходимо то понятие информации, которое подразумевает передачу информационных сообщений по линиям связи.

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

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

Увеличение числа разных элементарных сигналов позволяет сделать код более сжатым.

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

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

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

Рассмотрим два независимых опыта и а также сложный опыт и имеет k равновероятных исходов, а опыт имеет l равновероятных исходов.

Очевидно, что неопределенность опыта больше неопределенности опыта здесь добавляется еще неопределенность исхода опыта и Условиям при удовлетворяет только одна функция - Рассмотрим опыт А, состоящий из опытов и имеющих вероятности А будет равна Это последнее число будем называть энтропией опыта и обозначать через Если число букв в «алфавите» равно п, а число используемых элементарных сигналов равно т, то при любом методе кодирования среднее число элементарных сигналов, приходящихся на одну букву алфавита, не может быть меньше чем ; однако он всегда может быть сделано сколь угодно близким к этому отношению, если только отдельные кодовые обозначения сопоставлять сразу достаточно длинными «блоками», состоящими из большого числа букв. Мы рассмотрим здесь лишь простейший случай сообщений, записанных при помощи некоторых п «букв», частоты проявления которых на любом месте сообщения полностью характеризуется вероятностями р 1 , р 2 , … …, р п , где, разумеется, р 1 + р 2 + … + р п = 1, при котором вероятность p i проявления i -й буквы на любом месте сообщения предполагается одной и той же, вне зависимости от того, какие буквы стояли на всех предыдущих местах, т.е. последовательные буквы сообщения независимы друг от друга. На самом деле в реальных сообщениях это чаще бывает не так; в частности, в русском языке вероятность появления той или иной буквы существенно зависит от предыдущей буквы.

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

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

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

Прежде всего среднее число двоичных элементарных сигналов, приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше Н, где Н = - p 1 log p 1 – p 2 log p 2 - … - p n log p n – энтропия опыта, состоящего в распознавании одной буквы текста (или, короче, просто энтропия одной буквы). Отсюда сразу следует, что при любом методе кодирования для записи длинного сообщения из М букв требуется не меньше чем МН двоичных знаков, и никак не может превосходить одного бита. Если вероятности р 1 , р 2 , … …, р п не все равны между собой, то Н 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 2 3 ), и поэтому в нем на каждую букву исходного сообщения приходится ровно 3 элементарных сигнала; при использовании же кода Шеннона – Фано среднее число элементарных сигналов, приходящихся на одну букву сообщения, равно Это значение заметно меньше, чем 3, и не очень далеко от энтропии Аналогично этому для рассмотрения примера 18-буквенного алфавита наилучший равномерный код состоит из пятизначных кодовых обозначений (так как 2 4 5 ); в случае же кода Шеннона – Фано имеются буквы, кодируемые даже семью двоичными сигналами, но зато среднее число элементарных сигналов, приходящихся на одну букву, здесь равно Последнее значение заметно меньше, чем 5, - и уже не намного отличается от величины Особенно выгодно бывает кодировать по методу Шеннона – Фано не отдельные буквы, а сразу целые блоки из нескольких букв.

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

Рассмотрим, например, случай, когда имеются лишь две различные буквы А и Б, имеющие вероятности р(А) = 0,7 и р(Б) = 0,3; тогда H = - 0,7 log 0,7 – 0,3 log 0,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 log 0,89 – 0,11 log 0,11 0,5 дв.зн./букву, а равномерный код (равносильный применению кода Шеннона – Фано к совокупности двух имеющихся букв) требует затраты одного двоичного знака на каждую букву – в два раза больше.

Нетрудно проверить, что применение кода Шеннона – Фано к всевозможным двухбуквенным комбинациям здесь приводит к коду, в котором на каждую букву приходится в среднем 0,66 двоичных знаков, применение к трехбуквенным комбинациям - 0,55, а к четырехбуквенным блокам - в среднем 0,52 двоичных знаков – всего на 4% больше минимального значения 0,50 дв.зн./букву. 1.3 Коды Хафмана.

Близок к коду Шеннона – Фано, но еще выгоднее, чем последний, так называемый код Хафмана.

Построение этого кода опирается на простое преобразование используемого алфавита, называемое сжатием алфавита. Пусть мы имеем алфавит А, содержащий буквы Условимся теперь не различать между собой две наименее вероятные буквы нашего алфавита, т.е. будем считать, что а п -1 и а п – это одна и та же буква b нового алфавита А 1 , содержащего теперь уже буквы и b (т.е. а п -1 или а п ), вероятности появления которых в сообщении соответственно равны и р п -1 + р п . Алфавит А 1 и называется полученным из алфавита А с помощью сжатия (или однократного сжатия). Расположим буквы нового алфавита А 1 в порядке убывания их вероятностей и подвергнем сжатию алфавит А 1 ; при этом мы придем к алфавиту А 2 , который получается из первоначального алфавита А с помощью двукратного сжатия (а из алфавита А 1 – с помощью простого или однократного сжатия). Ясно, что алфавит А 2 будет содержать уже всего п – 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 = А 0 – это исходный алфавит А), сохранившимся и в алфавите 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 1 + p 2 + … + 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 1 , l 2 , …, l n , удовлетворяющих неравенству являются длинами кодовых обозначений некоторого т-ичного кода для п-буквенного алфавита.

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

Отсюда ясно, что если по линии связи за единицу времени можно передать L элементарных сигналов (принимающих т различных значений), то скорость передачи сообщений по такой линии не может быть большей, чем букв/ед. времени; однако передача со скоростью, сколь угодно близкой к v (но меньшей v !), уже является возможной.

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

Понятие пропускной способности играет важную роль в теории связи. 2.2 Энтропия и информация конкретных типов сообщений. 2.2.1 Письменная речь Для передачи М-буквенного сообщения допускающей m различных элементарных сигналов, требуется затратить не меньше чем сигналов, где n — число букв «алфавита. Так как русский «телеграфный» алфавит содержит 32 буквы (не различаются букв е и ё, ь и ъ, но причисляются к числу букв и «нулевая буква» — пустой промежуток между словами), то на передачу М-буквенного сообщения надо затратить элементарных сигналов. Здесь Н 0 = 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 Приравняв эти частоты вероятностям появления соответствующих букв, получим для энтропии одной буквы русского текста приближенное значение ): Из сравнения этого значения с величиной Н 0 = 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 2 урн, в каждой из которых лежат бумажки, начинающиеся на одни и те же две буквы (или опыт с русской книгой, в которой много раз наудачу отыскивается первое повторение последнего уже выписанного двухбуквенного сочетания и выписывается следующая за ним буква), приводит к «фразе» вроде следующей: ПОКАК ПОТ ДУРНОСКАКА НАКОНЕПНО ЗНЕ СТВОЛОВИЛ СЕ ТВОЙ ОБНИЛЬ, еще более близкой к русской речи, чем предыдущая.

Аналогично этому можно определить и энтропию отвечающую опыту по определению буквы русского текста при условии знания трех предшествующих букв. Он состоит в извлечении бумажек из 32 3 урн с четырехбуквенными сочетаниями (или — аналогичный описанному выше эксперимент с русской книгой), приводит к «фразе» вроде следующей: ВЕСЕЛ ВРАТЬСЯ НЕ СУХОМ И НЕПО И КОРКО, Еще лучшее приближение к энтропии буквы осмысленного русского текста дают величины при N = 5,6, .... Нетрудно видеть, что с ростом N энтропия Н N может только убывать. Если еще учесть, что все величины Н N положительны, то отсюда можно будет вывести, что величина при стремится к определенному пределу Нам уже известно, что среднее число элементарных сигналов, необходимое для передачи одной буквы русского текста, не может быть меньшим Разность к величине Избыточность R является весьма важной статистической характеристикой языка, но ее численное значение пока ни для одного языка не определено с удовлетворительной точностью. В отношении русского языка, в частности, имеются лишь данные о значениях величин Н 2 и Н 3 .

Н 0 Н 1 Н 2 Н 3
log 32 = 5 4,35 3,52 3,01
(для полноты мы здесь привели также и значения энтропии Н 0 и Н 1 ). Отсюда можно только вывести, что для русского языка R значительно больше этого числа. Ясно, что для всех языков, использующих латинский алфавит, максимальная информация Н 0 , которая могла бы приходиться па одну букву текста, имеет одно и то же значение: (26 различных букв алфавита и 27-я «буква» — пустой промежуток между словами). Использовав таблицы относительных частот различных букв в английском, немецком, французском и испанском языках, можно показать, что энтропия Н 1 для этих языков равна (в битах):
язык англ. немецк. франц. испанск.
Н 1 4,03 4,10 3,96 3,98
Мы видим, что во всех случаях величина Н 1 заметно меньше, чем Н 0 = log 27 4,76 бит, причем ее значения для различных языков не очень сильно разнятся между собой.

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

Н 0 Н 1 Н 2 Н 3 Н 5 Н 8
4,76 4,03 3,32 3,10 2,1 1,9
Отсюда можно заключить, что для английского языка избыточность R во всяком случае не меньше, чем Подсчет величин Н 9 , Н 10 и т. д. по известной нам формуле невозможенен, так как уже для вычисления Н 9 требуется знание вероятностей всех 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 предыдущим.

Отсюда можно сделать вывод, что Н 15 ощутимо больше, чем Н 100 , т. е. что Н 15 никак еще нельзя отождествить с предельным значением N = 1, 2, 4, 8, 16, 32, 64, 128 и N 10 00. Из полученных данных можно заключить, что величина Н 32 (так же как и H 64 и Н 128 ) практически не отличается от Н 10000 , в то время как «условная энтропия» Н 16 еще заметно больше этой величины. Таким образом, можно предположить, что при возрастании N величина H N убывает вплоть до значений N = 30, но при дальнейшем росте N она уже практически не меняется; поэтому вместо «предельной энтропии» можно говорить, например, об условной энтропии H 30 или H 40 . Эксперименты по отгадыванию букв не только позволяют судить о сравнительной величине условных энтропии H N при разных N, но дают также возможность оцепить и сами значения Н N . По данным таких экспериментов можно определить не только среднее число Q N попыток, требующихся для отгадывания N-й буквы текста по N — 1 предшествующим, но и вероятности (частоты) того, что буква будет правильно угадана с 1-й, 2-й, 3-й, ..., n-й попытки (где п = 27 - число букв алфавита; Q N = равны вероятностям букв алфавита, расположенных в порядке убывания частот. В самом деле, если ни одна из букв, предшествующих отгадываемой букве х, нам не известна, то естественно прежде всего предположить, что х совпадает с самой распространенной буквой a 1 (причем вероятность правильно угадать здесь будет равна р(а 1 )); затем следует предположить, что х совпадает с а 2 (вероятность правильного ответа здесь будет равна р(а 2 )) и т. д.

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

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

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

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

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

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

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

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

Ударение чаще всего падает на наиболее редко употребляемые слова (что, впрочем, довольно естественно - ясно, что вряд ли кто будет выделять логическим ударением наиболее распространенные слона - например, предлоги или союзы). Если вероятность того, что данное слово W r находится под ударением, мы обозначим через q r , то средняя информация, заключающаяся в сведениях о наличии или отсутствии ударения на этом слове, будет равна Пусть теперь - вероятности (частоты) всех слов W 1 , W 2 , . . ., W K (здесь К - общее число всех употребляемых слов. В таком случае для средней информации Н, заключенной в логическом ударении, можно написать следующую формулу: C редняя информация, которую мы получаем, выяснив, на какие слова падает логическое ударение, по порядку величины близка к 0,65 бит/слово. Во время разговора отдельные буквы никогда не произносятся, а произносятся звуки, существенно отличающиеся от букв.

Поэтому основным элементом устной речи надо считать отдельный звук - фонему.

Осмысленная устная речь составляется из фонем точно так же, как осмысленная письменная речь составляется из букв.

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

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

Н 0 Н 1 Н 2 Н 3
log 42 5,38 4,77 3,62 0,70
Если сравнить эти значения со значениями величин Н 0 , Н 1 , Н 2 , H 3 для письменной русской речи, то убывание ряда условных энтропии для фонем происходит заметно быстрее, чем в случае букв письменного текста. Для определения избыточности R (слова) , можно установить связь между избыточностями устной и письменной речи. Из того, что устная речь может быть записана, а письменная - прочитана, следует, что «полная информация», содержащаяся в определенном тексте, не зависит от того, в какой форме - устной или письменной - этот текст представлен, т. е. что Отсюда вытекает, что где есть среднее число букв, приходящихся на одну фонему («средняя длина фонемы»). Эта величина является важной статистической характеристикой языка, связывающей устную и письменную речь. Из последней формулы следует также, что или где k - общее число фонем, а п - число букв; за здесь естественнее принимать 2.2.3 Музыка.

Исследования того же рода могут быть проведены и в отношении музыкальных сообщений.

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

Какова же та избыточность, при которой может получиться «хорошая» музыка? Избыточность простых мелодий никак не меньше, чем избыточность осмысленной речи.

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

Подсчитав частоты (вероятности) отдельных нот во всех 39 анализируемых песенках, находим, что С помощью найденных вероятностей сочетаний из двух нот, можно подсчитать также условную энтропию Н 2 , она оказывается близкой к 2,42 . По одним только значениям Н 1 и Н 2 еще очень мало что можно сказать о степени избыточности рассматриваемых, по-видимому, она заметно выше, чем 2.2.4 Передача телевизионных изображений. Наш глаз способен различить лишь конечное число степеней яркости изображения и лишь не слишком близкие его участки, поэтому любое изображение можно передавать «по точкам», каждая из которых является сигналом, принимающим лишь конечное число значений. Необходимо учитывать значительное число (несколько десятков) градаций степени почернения («яркости») каждого элемента, кроме того, на телеэкране ежесекундно сменяется 25 кадров, создавая впечатление «движения». Однако, по линии связи фактически передается не исход опыта может иметь уже лишь конечное число исходов, и мы можем измерить его энтропию Н. Общее число элементов («точек») для черно-белого телевидения, на которые следует разлагать изображение, определяется в первую очередь так называемой «разрешающей способностью» глаза, т. е. его способностью различать близкие участки изображения. В современном телевидении это число обычно имеет порядок нескольких сотен тысяч (в советских телепередачах изображение разлагалось на 400 00 - 500 000 элементов, в американских - примерно на 200 00 - 300 000, в передачах некоторых французских и бельгийских телецентров - почти на 1 000 000). Нетрудно понять, что по этой причине энтропия телевизионного изображения имеет огромную величину. Если даже считать, что человеческий глаз различает лишь 16 разных градаций яркости (значение явно заниженное) и что изображение разлагается всего на 200000 элементов, то мы найдем, что «энтропия нулевого порядка» здесь равна Н 0 = log 16 200000 = 800 000 бит.

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

Наглядный смысл этой избыточности R заключается в том, что среди наших 16 200000 возможных комбинаций значений яркости во всех точках экрана осмысленные комбинации, которые можно назвать «изображениями», будут составлять лишь ничтожно малую часть, а остальное будет представлять собой совершенно беспорядочную совокупность точек разной яркости, весьма далекую от какого бы то ни было «сюжета». Между тем реальная «степень неопределенности» Н телевизионного изображения должна учитывать только те комбинации значений яркости, которые имеют хоть какие-то шансы быть переданными. Для определения точного значения энтропии Н (или избыточности R ) телевизионного изображения нужно детально изучить статистические зависимости между яркостями различных точек экрана. Так, найдены значения энтропий Н 0 , Н 1 , Н 2 и Н 3 для двух конкретных телевизионных изображений, первое из которых (изображение А — парк с деревьями и строениями) было более сложным, а второе (изображение В — довольно темная галерея с прохожими) было более однотонным по цвету и содержало меньше деталей, при этом различали 64 разных градаций яркости элемента телевизионного изображения, поэтому энтропия Н 0 (отнесенная к одному элементу, а не ко всему изображению в целом) здесь оказалась равной Н 0 = log 64 = 6 бит. Далее с помощью специального радиотехнического устройства были подсчитаны для обоих рассматриваемых изображений относительные частоты (вероятности) всех различимых градаций яркости и определил «энтропию первого порядка» То же самое радиотехническое устройство было применено затем для вычисления относительных частот p i j пар соседних (по горизонтали) элементов, в которых первый элемент имеет i-e значение яркости, а второй j-e, а также относительных частот p i jk троек соседних (также лишь по горизонтали) элементов, в которых первый элемент имел 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 , оцененная по величине Н 2 для изображения А равна 44%, а для изображения Б - 68%; действительное значение избыточности может быть только больше этого. Что же касается условной энтропии Н 3 при известных яркостях двух предыдущих элементов той же строки, то она сравнительно мало отличается от Н 2 (изображение Б, 75%); отсюда можно заключить, что знание яркости самого близкого элемента определяет весьма большую часть общей избыточности.

Близкий характер имеет также другой опыт, опирающийся на разбиение возможных значений яркости элемента телевизионного изображения на 8, а не на 64 градаций, для которого вычислены энтропии Н 0 и Н 1 и ряда условных энтропии Н 2 , Н 3 и Н 4 одного элемента изображения для следующих четырех спортивных телевизионных сюжетов: А - быстро бегущие баскетболисты, Б - лицо одного зрителя на трибуне стадиона крупным планом, В - панорамирование вида зрителей на трибуне и Г - быстро бегущие футболисты. Будем обозначать цифрами 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 лет со дня опубликования, код Хаффмана ничуть не потерял своей актуальности и значимости. Так с уверенностью можно сказать, что мы сталкиваемся с ним, в той или иной форме (дело в том, что код Хаффмана редко используется отдельно, чаще работая в связке с другими алгоритмами), практически каждый раз, когда архивируем файлы, смотрим фотографии, фильмы, посылаем факс или слушаем музыку.