2.3. Элементы и принципы теории кодирования

Кодом называется система условных знаков (символов) для передачи, обработки и хранения (запоминания) различной информации. Предметом исследования теории кодирования являются отображения конечных или счётных множеств объектов произвольной природы в множества последовательностей из цифр 0,1,…r-1, где r – некоторое положительное число (в частности, r=2). Такие отображения называют кодированиями.

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

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

Приведём примеры кодирований.

1). Двоичное кодирование действительных чисел.

2). Двоичное кодирование цифр почтового индекса.

Каждая десятичная цифра, выделенная отправителем на девяти отрезках шаблона, кодируется для автоматического распознавания словом длины 9 из нулей и единиц, символом 1 отмечаются номера использованных линий. Например, цифре 2 соответствует слово 100100101; цифре 5 – слово 110010011.

Задание 1. Постройте код для 6-значного почтового индекса своего почтового отделения по месту жительства, используя описанные двоичные 9-значные коды цифр.

Пусть буквы алфавита a, b, c, d имеют следующие двоичные коды:

a – 01, b – 100, c – 101, d – 0.

Слово 0100 можно декодировать как db или add; слово 0010100 – как ddcdd, daadd или dadb.

Такое кодирование не удовлетворяет требованию существования однозначного декодирования.

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

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

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

Известны два метода построения кодов, близких к оптимальномым, принадлежащие К. Шеннону и Р. Фано.

Метод Фано, отличающийся чрезвычайной простотой конструкции, заключается в следующем. Упорядоченный в порядке убывания частоты появления на 1000 знаков текста список букв делится на две части так, чтобы суммы частот входящих в них букв как можно меньше отличались друг от друга. Буквам из первой части приписывается символ 0, а буквам из второй части – символ 1. Далее точно так же поступают с каждой из полученных частей, если она содержит по крайней мере две буквы. Этот процесс продолжается до тех пор, пока весь список не разобьётся на части, содержащие по одной цифре.

Построим по методу Фано код для алфавита из восьми букв: a, b, c, d, e, f, g, h. Пусть из опыта известны частоты, с которыми встречаются эти буквы в тексте из 100 букв: a – 30, b – 18, c – 14, d – 14, e – 11, f – 6, g – 5, h – 2. Разделим буквы следующим образом: 1-ая часть содержит буквы a и b, 2-ая – буквы c, d, e, f, g, h. Сумма частот 1-ой части 48, 2-ой – 52. Код букв a и b начинается с 0, а остальных с 1. 1-ую часть делим на две части, в каждой их которых по одной букве; код a – 00, код b – 01. 2-ую часть делим на две части: в первой части буквы c и d (сумма частот 28), во второй – e, f, g, h ( сумма частот 24). Код c и d будет начинаться с 10, а код e, f, g, h – с 11. Часть из букв c и d делим пополам и получаем в каждой части по одной букве, окончательный код c – 100, d – 101. Буквы e, f, g, h делим на две части так: в 1-ой буква e, во 2-ой - f, g, h (сумма частот 13). Код буквы e – 110. Оставшиеся 3 буквы делим на части: в 1-ой f, остальные во 2-ой. Код f – 1110, код g и h начинается с 1111. Последнее деление, и получаем коды последних букв: g – 11110, h – 11111.

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

Пусть все буквы алфавита v1, v2, …vn имеют двузначный код. l(vi) – длина кода буквы vi, pi – относительная частота этой буквы. Стоимостью кода называется

L=p1l(v1)+p2l(v2)+…pnl(vn)

Стоимость построенного кода:

0,30*2+0,18*2+0,14*3+0,14*3+0,11*3+0,06*4+0,05*5+0,02*5=2,72

Если бы в этом примере все буквы имели бы код одинаковой длины, то длина кода каждой буквы была бы 3 и стоимость такого кода тоже 3.

Задание 2. Есть алфавит из пяти знаков: ы, й, ъ, ь, ?, причём на 100 знаков текста «ы» встречается 40 раз, «й» - 20, «ъ» - 15, «ь» - 15, «?» - 10. Постройте два различных кода Фано, вычислите стоимость каждого кода.