Первая теорема Шеннона
Пусть первичный алфавит А состоит из N знаков со средней информацией на знак I(A), а вторичный алфавит B - из М знаков со средней информацией на знак I(B). Пусть также исходное сообщение, представленное в первичном алфавите, содержит п знаков, а закодированное сообщение - т знаков. Если исходное сообщение содержит Ist(A) информации, а закодированное - Ifin(B), то условие обратимости кодирования, т. е. неисчезновения информации при кодировании, очевидно, может быть записано следующим образом:
смысл которого в том, что операция обратимого кодирования может увеличить количество информации в сообщении, но не может его уменьшить. Однако каждая из величин в данном неравенстве может быть заменена произведением числа знаков на среднее информационное содержание знака, т. е.:
или
Отношение т/п, очевидно, характеризует среднее число знаков вторичного алфавита, которое приходится использовать для кодирования одного знака первичного алфавита - будем называть его длиной кода или длиной кодовой цепочки и обозначим К(А, В). Следовательно
Обычно N > М и I(А) > I(В), откуда К(А, В) > 1, т. е. один знак первичного алфавита представляется несколькими знаками вторичного. Поскольку способов построения кодов при фиксированных алфавитах А и В существует множество, возникает проблема выбора (или построения) наилучшего варианта - будем называть его оптимальным кодом.
Первая теорема Шеннона, которая называется основной теоремой о кодировании при отсутствии помех, формулируется следующим образом:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информации на знак первичного и вторичного алфавитов.
Минимально возможным значением средней длины кода будет:
В качестве меры превышения К(А, В) над Kmin(А, В) можно ввести относительную избыточность кода (Q(А, В):
Используя понятие избыточности кода, можно построить иную формулировку теоремы Шеннона:
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором избыточность кода будет сколь угодно близкой к нулю.
Наиболее важной для практики оказывается ситуация, когда М = 2, т. е. для представления кодов в линии связи используется лишь два типа сигналов - технически это наиболее просто реализуемый вариант (например, существование напряжения в проводе (будем называть это импульсом) или его отсутствие (пауза); наличие или отсутствие отверстия на перфокарте или намагниченной области на дискете); подобное кодирование называется двоичным. Знаки двоичного алфавита принято обозначать «О» и «1», но нужно воспринимать их как буквы, а не цифры. Удобство двоичных кодов и в том, что при равных длительностях и вероятностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации (log2 M = 1); тогда из (3.3)
и первая теорема Шеннона получает следующую интерпретацию:
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Для двоичных сообщений источника без памяти при кодировании знаками равной вероятности имеем:
Способы построения двоичных кодов
Алфавитное неравномерное двоичное кодирование сигналами равной длительности. Префиксные коды
Префиксные коды без разделителей знаков
Суть первой проблемы состоит в нахождении такого варианта кодирования сообщения, при котором последующее выделение из него каждого отдельного знака (т. е. декодирование) оказывается однозначным без специальных указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют следующему условию (условию Фано):
Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом*) какого-либо иного более длинного кода.
Префиксный код Шеннона-Фано
Данный вариант кодирования был предложен в 1948-1949 гг. независимо Р. Фано и К. Шенноном и по этой причине назван по их именам. Рассмотрим схему на следующем примере: пусть имеется первичный алфавит А, состоящий из шести знаков а1 ...а6 с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05. Расположим эти знаки в таблице в порядке убывания вероятностей (см. табл. 3.2). Разделим знаки на две группы таким образом, чтобы суммы вероятностей в каждой из них были бы приблизительно равными. В нашем примере в первую группу попадут a1 и а2 с суммой вероятностей 0,5 - им присвоим первый знак кода "0". Сумма вероятностей для остальных четырех знаков также 0,5; у них первый знак кода будет "1". Продолжим деление каждой из групп на подгруппы по этой же схеме, т. е. так, чтобы суммы вероятностей на каждом шаге в соседних подгруппах были бы возможно более близкими. В результате получаем:
Из процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, код является префиксным. Средняя длина кода равна:
I1(A) = 2,390 бит. Подставляя указанные значения в (3.5), получаем избыточность кода Q(A,2) = 0,0249, т. е. около 2,5%. Однако, данный код нельзя считать оптимальным, поскольку вероятности появления 0 и 1 неодинаковы (0,35 и 0,65, соответственно). Применение изложенной схемы построения к русскому алфавиту дает избыточность кода 0,0147.
Префиксный код Хаффмана
Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом. Построение кодов Хаффмана мы рассмотрим на том же примере. Создадим новый вспомогательный алфавит A1, объединив два знака с наименьшими вероятностями (а5 и а6) и заменив их одним знаком (например, а(1)); вероятность нового знака будет равна сумме вероятностей тех, что в него вошли, т. е. 0,15; остальные знаки исходного алфавита включим в новый без изменений; общее число знаков в новом алфавите, очевидно, будет на 1 меньше, чем в исходном. Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака; ясно, что количество таких шагов будет равно N - 2, где N - число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита). В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей. Всю процедуру построения представим в виде таблицы:
Теперь в обратном направлении проведем процедуру кодирования. Двум знакам последнего алфавита присвоим коды 0 и 1 (которому какой - роли не играет; условимся, что верхний знак будет иметь код 0, а нижний - 1). В нашем примере знак а1(4) алфавита A(4), имеющий вероятность 0,6, получит код 0, а a2(4) с вероятностью 0,4 - код 1. В алфавите А(3) знак a1(3) получает от a2(4) его вероятность 0,4 и код (1); коды знаков a2(3) и a3(3), происходящие от знака a1(4) с вероятностью 0,6, будут уже двузначным: их первой цифрой станет код их «родителя» (т. е. 0), а вторая цифра - как условились - у верхнего 0, у нижнего - 1; таким образом, a2(3) будет иметь код 00, а a3(3) - код 01
Из процедуры построения кодов вновь видно, что они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода, как и в предыдущем примере оказывается:
К(А,2) = 0,3 ∙ 2 + 0,2 ∙ 2 + 0,2 ∙ 2 +0,15 ∙ 3 + 0,1 ∙ 4 + 0,05 ∙ 4 = 2,45.
Избыточность снова оказывается равной Q(A, 2) = 0,0249, однако, вероятности 0 и 1 сблизились (0,47 и 0,53, соответственно).
Более высокая эффективность кодов Хаффмана по сравнению с кодами Шеннона-Фано становится очевидной, если сравнить избыточности кодов для какого-либо естественного языка. Применение описанного метода для букв русского алфавита порождает коды, представленные в таблице
Средняя длина кода оказывается равной К(r,2) = 4,395; избыточность кода Q(r,2) = 0,0090, т. е. не превышает 1 %, что заметно меньше избыточности кода Шеннона-Фано.
Код Хаффмана важен в теоретическом отношении, поскольку можно доказать, что он является самым экономичным из всех возможных, т. е. ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана.
Таким образом, можно заключить, что существует способ построения оптимального неравномерного алфавитного кода. Метод Хаффмана и его модификация - метод адаптивного кодирования (динамическое кодирование Хаффмана) - нашли широчайшее применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.
