Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
1) появления двоичных символов "О" и "1" в закодированном тексте должны быть равновероятными;
2) значения вероятностей появления этих символов не должны зависеть от того, какие именно символы им предшествовали.
Нарушение хотя бы одного их этих условий непременно приводит к тому, что значение / оказывается больше Н, т.е. закодированный текст оказывается неоптимальным, избыточным.
Как уже говорилось выше, при кодировании последовательностей (Bms) букв длины т значение Hm оказывается монотонно убывающей функцией от т. На практике, однако, приходится учесть, что с увеличением т растет также число всевозможных вариантов Bms, что влечет большие затраты машинного времени. Практическое кодирование связного текста сводится к выбору некоторого компромисса, а именно, достижения приемлемого значения / за приемлемый промежуток времени.
Заметим, что указанный метод кодирования можно использовать для уменьшения / даже при независимости значений вероятностей р(і) от того, какие буквы им предшествовали. Как уже говорилось выше, в этих случаях имеет место H = Hm =H1 и для вычисления значения H вместо формулы (2.9) можно пользоваться формулой (2.3).
Рассмотрим пример.
Пусть требуется закодировать текст, записанный на языке, в алфавите которого имеются три буквы. Пусть далее известно, что независимо от того, какие буквы ей предшествовали, значения вероятностей того, что наугад взятая буква окажется буквой А, В или С, соответственно равны:
р( А) = 0,8 /;(В) = 0,1
P(C) = O1I
Пользуясь формулой (2.3), определяем значение
H = -(P(A)Iog2 р(А)+ /?(B)log2 р(В) + p(C)log2 P(C)) = 0,92.
Применительно к этому примеру схемы побуквенного кодирования но Р. Фано и Д. Хаффмэну привели бы к одинаковым результатам:
А О
В 10 С 11
т.е. к значению I, равному / = 0,8 + 2 ¦ 0,2 = 1,2. Поскольку при побук-
45
ГЛАВА 1 венном кодировании значение I = 1,2 оказалось заметно большим значения // = 0,92, то естественно попробовать уменьшить это значение путем кодирования двухбуквенных комбинаций букв. Так как значения появления в тексте тех или иных букв алфавита не зависят от того, какие буквы им предшествовали, то для различных двухбуквенных комбинации получим следующие значения вероятностей:
P(AA) = 0,64 />(ВА) = 0.08 р(СА) = 0,08
/;(АВ) = 0,08 р(ВВ) = 0,01 р(С В) = 0,01
р(АС) = 0,08 /j(BC) = 0,01 р(СС) = 0.01
Рассматривая эти комбинации букв как самостоятельные буквы некоего гипотетического языка с девятью буквами в алфавите, мы сможем пользоваться схемами побуквенного кодирования Р. Фано и Д. Хаффмэна. Применительно к данному случаю эти схемы приводят к одинаковым результатам - среднее число двоичных символов, приходящихся на одну двухбуквенную комбинацию, оказывается равным /=!.92.
Таким образом, среднее число двоичных символов, приходящихся на одну букву, оказывается равным / = 0,96. Поскольку даже по схеме Д. Хаффмэна значение I продолжает оставаться ощутимо большим значения Н, то для дальнейшего его уменьшения следует осуществить кодирование трехбуквенных комбинаций т = 3 и так далее до достижения приемлемого значения I Н.
р . ИЗБЫТОЧНОЕ КОДИРОВАНИЕ. ИЗБЫТОЧНОСТЬ И УЯЗВИМОСТЬ ИНФОРМАЦИИ. ЗАЩИТА ИНФОРМАЦИИ ОТ СЛУЧАЙНЫХ ПОМЕХ. КОД Р. ХЭММИНГА
Говоря об оптимальном (в смысле максимального сжатия) кодировании текстов, мы имели в виду достижение условия / = Н. Если же это условие не было достигнуто, то говорили, что имеет место неоптимальное, т.е. избыточное кодирование. Количественно избыточное і ь можно оценить, например, разностью 5 = I-H или. в процентах, (5/7) 100%. Достижение условия / = H обеспечивает максимально возможное сжатие исходных текстов (избыточность нулевая). При этом закодированный текст оказывается предельно сжатым и поэтому абсолютно беззащитным к случайным ошибкам. Если на уровне хоть одного двоичного символа оптимально закодированного текста произошла ошибка, то мы оказываемся теоретически лишенными возможостн как-то обнаружить ее, а тем более исправить. Интуитивно ясно, что наличие некоторой избыточности создало бы принципиальную возможность обнаруживать (обнаруживающие коды), а в некоторых случаях и
46 исправлять (исправляющие коды) ошибки. Сказанное, однако, не означает, что сам факт наличия некоторой избыточности уже является достаточным для обнаружения или исправления ошибок. Наличие избыточности создает лишь тсретическую, принципиальную возможность обнаружения или исправления ошибок. Для того же. чтобы она "работала на нас", всецело была направлена на обнаружение и исправление ошибок предполагаемого характера, эту избыточность следует специально "конструировать", что, собственно, и является предметом изучения чрезвычайно интересного и увлекательного раздела прикладной математики, занимающегося конструированием кодов, обнаруживающих и исправляющих ошибки. Там же устанавливаются количественные оценки того, на что именно мы вправе рассчитывать (обнаружение одной, двух... и т.д. ошибок, их исправление) при том или ином уровне избыточности.
Рассмотрим пример.
