Принципиальная схема цифровой системы связи изображена на рисунке

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

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

• кодирование источника;
• кодирование канала.

Приведенная выше схема детализируется:

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

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

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

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

Последовательность входящих информационных символов $ a_1,a_2,\dots $ разбивается на отрезки (блоки), каждый содержащий $ k_{} $ символов: $$ (a_1,\dots,a_k),\ (a_{k+1},\dots,a_{2k}),\dots $$ В кодере производится преобразование каждого отдельного блока в новый блок : $$ \mathfrak C(a_1,\dots,a_k)=(b_1,\dots,b_n), \mathfrak C(a_{k+1},\dots,a_{2k})=(b_{n+1},\dots,b_{2n}),\dots $$ Правило преобразования (функциональная зависимость, обозначенная здесь буквой $ \mathfrak C $) каждого входящего блока не зависит от содержания других входящих блоков; получающиеся в ходе преобразваний блоки $ (b_1,\dots,b_n), (b_{n+1},\dots,b_{2n}), \dots $ называются кодовыми словами. Число $ n\ge k $ называется длиной кода (длиной блока).

Пример 1. Пусть алфавит языка состоит из пяти букв:

а, в, л, о, с . Их кодирование в цифровую последовательность возможно по правилу:
$ \mathfrak C ( $ а $ )=0 $, $ \mathfrak C ( $ в $ )=1 $, $ \mathfrak C ( $ л $ )=2 $, $ \mathfrak C ( $ о $ )=3 $, $ \mathfrak C ( $ с $ )=4 $.
В этом случае длина кода $ n_{}=1 $. Получатель, которому по телефону диктуют цифровые последовательности $$ 423104231042310 \quad \mbox{ или } \quad 201013234 $$ однозначно декодирует их — если знает правило кодирования. Понятно, что для кодирования всего русского алфавита потребуются уже двузначные десятичные числа, т.е. $ n=2_{} $ (и отметим, на всякий случай, что кодирование по правилу
$ \mathfrak C ( $ а $ )=0 $, $ \mathfrak C ( $ б $ )=1 ,\dots, \mathfrak C ( $ я $ )=32 $
уже не будет правильным…). Пока остановимся на примере пятибуквенного алфавита чтобы показать две проблемы. Предположим, что телефонная линия подвержена помехам и какие-то сообщения могут теряться: $$ 4310231042310 $$ или же искажаться $$ 420101204020440 \ . $$ Можно ли восстановить утраченную информацию? — Понятно, что ответ на этот вопрос зависит, в первую очередь, от передающих характеристик самого канала связи.

Переходим к кодированию букв в двоичной системе:
$ \mathfrak C ( $ а $ )=00 $, $ \mathfrak C ( $ в $ )=01 $, $ \mathfrak C ( $ о $ )=10 $, $ \mathfrak C ( $ с $ )=11 $,
забывая пока о пятой букве. Таким образом длина кода $ n_{}=2 $. Предположим, что на каждое передаваемое кодовое слово канал связи дает не более одной ошибки: в каждом блоке длины 2 может менять $ 0_{} $ на $ 1_{} $ или $ 1_{} $ на $ 0_{} $ — но не сразу оба бита (и не «затирает» бит полностью). Что может произойти при передаче закодированного сообщения $$ 11100100 $$ по такому каналу? Получатель может увидеть следующие варианты: $$ 01100100 \quad \mbox{ или } \quad 10110000 \quad \mbox{ или } 01001110 \ , $$ но не получит следующие: $$ 11010101 \quad \mbox{ или } \quad 1010101 \ . $$ Итак, выбор самого экономичного способа кодирования — когда четырем символам алфавита соответствуют четыре двоичных блока — не решает задачу надежной коммуникации. Увеличим длину кода присоединением к двум «информационным» битам нашей экономичной кодировки некоторого количества «служебных» битов; пусть теперь
$ \mathfrak C ( $ а $ )= 00110 $, $ \mathfrak C ( $ в $ )=01101 $, $ \mathfrak C ( $ о $ )=10011 $, $ \mathfrak C ( $ с $ )=11000 $.
Что может произойти с этими кодовыми словами при внесении в них ровно одной ошибки? Составим таблицу всех возможных ситуаций: $$ \begin{array}{c|c|c|c} 00110 & 01101 & 10011 & 11000 \\ \hline 00111 & 01100 & 10010 & 11001 \\ 00100 & 01111 & 10001 & 11010 \\ 00010 & 01001 & 10111 & 11100 \\ 01110 & 00101 & 11011 & 10000 \\ 10110 & 11101 & 00011 & 01000 \end{array} $$ Обратим внимание на то, что столбцы не содержат одинаковых блоков. Таким образом, если условие зашумляемости блока не более чем одной ошибкой выполняется, декодер сможет однозначно восстановить передаваемую букву — достаточно будет найти в таблице столбец, содержащий полученный блок.

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

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

Что произойдет если зашумленность канала оказывается более высокой, чем предполагалось? Возможны ситуации, когда полученный в результате передачи блок будет содержаться в таблице. Например, если на вход подается блок $ 11000 $, а канал портит два бита, то получатель может увидеть блок $ 11011 $, который хоть и содержится в таблице, но декодируется совсем не в ту букву, которая передавалась. А может случиться и так, что на выходе из канала получится блок $ 11110 $, который совсем не содержится в таблице. Эта ситуация иногда более выгодна, чем предыдущая: декодер можно заставить извещать пользователя об обнаружении (неисправимой) ошибки. Можно заложить в декодере одновременно обе возможности — сигнализации об ошибке и ее исправления. На примере полученного блока $ 11110 $ посмотрим, что можно предпринять. Обратим внимание, что этот блок отличается от отправленного $ 11000 = \mathfrak C ( $ а $ ) $ в двух битах, от блока $ 00110=\mathfrak C ( $ в $ ) $ — также в двух битах, а от каждого из блоков $ 10011 = \mathfrak C ( $ о $ ) $ или $ 01101 = \mathfrak C ( $ с $ ) $ — в трех битах. Поэтому, ввиду гипотезы о не более чем двух зашумленных битах, можно при декодировании отбросить два последних варианта, как маловероятные. Иными словами,

декодирование всегда производить в "ближайший" кодовый блок.

Расстоянием Хэмминга между двумя кодовыми словами $ (b_1,\dots,b_n) $ и $ (c_1,\dots,c_n) $ называется число разрядов, в которых эти слова отличаются друг от друга. Как правило, в дальнейшем элементами кодовых слов будут рассматриваться символы двоичного кода, т.е. $ (b_1,\dots,b_n) $ и $ (c_1,\dots,c_n) $ — это векторы, состоящие из нулей и единиц. Расстояние Хэмминга между такими векторами равно $ |b_1-c_1|+\dots+|b_n-c_n| $. Для любого такого вектора $ (b_1,\dots,b_n) $ его весом Хэмминга называется число отличных от нуля координат, т.е. $ b_1+\dots+b_n $.

Пример 2. Расстояние Хэмминга между векторами

$$ (0,1,0,0,1,0) \ \mbox{и} \ (1,1,0,1,1,1) $$ равно $ 3 $. ♦

Введенное определение позволяет дать геометрическую интерпретацию решению примера 1. Таблица кодирования из него заключает в себя все двоичные векторы, состоящие из пяти элементов, расстояние от которых до вектора из верхней строчки и соответствующего столбца равно $ 1_{} $. Можно сказать, что вектор каждого из столбцов содержится в окрестности размера $ 1_{} $ соответствующего вектора $ (11000), (00110), (10011), (01101) $. Последние так удачно подобраны, что эти окрестности не пересекаются. Вектор на выходе из канала проверяется на попадание в какую-то из окрестностей, в случае положительного ответа можно декодировать его в соответствующую букву («центр» окрестности), а вот в случае отрицательного ответа можно попробовать сравнить расстояния Хэмминга до всех этих центров и декодировать в ближний…

Подробнее — в разделе ☞ КОД ХЭММИНГА.

Рассмотренная в предыдущем пункте схема кодирования предполагала преобразование каждого блока входящих информационных символов $ (a_1,\dots,a_k), (a_{k+1},\dots,a_{2k}),\dots $ в кодовые слова с одинаковым количеством разрядов $ n_{} $. Такое правило позволяет легко отделить кодовые слове по прохождении сообщением канала связи. Можно ли осуществить кодирование с переменной длиной кода? Следующий пример указывает на одну серьезную проблему, которая может встретиться при таком способе.

Пример. Пусть кодирование производится по правилу:

$ \mathfrak C ( $ а $ )=1 $, $ \mathfrak C ( $ в $ )=01 $, $ \mathfrak C ( $ о $ )=010 $, $ \mathfrak C ( $ с $ )=001 $.
Кодирование сообщения
а о в а о о с
дает кодовую последовательность
$ 1010011010010001 $.

Попытаемся ее декодировать. Первая цифра однозначно декодируется в а (поскольку ни одно другое кодовое слово не начинается с $ 1_{} $). Следующая цифра в коде — $ 0_{} $, она может быть начальной цифрой кодового слова для любой из трех букв в , о или с . Следующая за ней цифра — $ 1_{} $. Пара $ (0,1) $ может быть кодовым словом для буквы в , либо же быть начальным отрезком (блоком) для кодового слова, соответствующего букве о . Берем следующую цифру кода — $ 0_{} $. И здесь декодер сталкивается с неоднозначностью толкования: либо кодовую последовательность следует разбить как $ 1_{} $ | $ 010 $ | $ 01 \dots $, либо же — как $ 1_{} $ | $ 01 $ | $ 001 \dots $ — и оба варианта имеют право на существование! ♦

Код $ \mathfrak C_{} $ называется префиксным¹⁾ если ни одно его кодовое слово не совпадает с начальным отрезком какого-то другого кодового слова.

Пример. Код

$ \mathfrak C ( $ а $ )=1 $, $ \mathfrak C ( $ в $ )=01 $, $ \mathfrak C ( $ о $ )=000 $, $ \mathfrak C ( $ с $ )=001 $ является префиксным. Префиксность кода позволяет декодеру разбить поток закодированного сообщения на отдельные кодовые слова единственно возможным способом, так что сообщение
$ 1000011000000001 $ разбивается на блоки $ 1_{} $ | $ 000_{} $ | $ 01 $ | $ 1_{} $ | $ 000 $ | $ 000 $ | $ 001 $. ♦

Очевидно, что для любого набора двоичных символов $ (b_1,\dots,b_s) $, не входящего в состав префиксного кода $ \mathfrak C_{} $, возможно два варианта:

1. в $ \mathfrak C_{} $ нет кодового слова вида $ (b_1,\dots,b_s,b_{s+1},\dots) $, т.е. такого, у которого начальный отрезок совпадал бы с данным;

2. в $ \mathfrak C_{} $ существует кодовое слово с указанным свойством.

В последнем случае наборы $ (b_1,\dots,b_s,0) $ и $ (b_1,\dots,b_s,1) $ будут либо кодовыми словами либо начальными отрезками кодовых слов кода $ \mathfrak C_{} $.

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

Приведите пример непримитивного префиксного кода.

Пример. Закодируем $ 10_{} $ букв русского алфавита по таблице.

Легко проверить, что этот код — примитивный префиксный. Его можно изобразить в виде особого графа — дерева, у которого из корня и любой вершины, кроме свободных, выходят по две ветви. Если мы условимся всегда сопоставлять каждой верхней ветви $ 0_{} $, а каждой нижней ветви — $ 1_{} $, то каждой свободной вершине дерева будет однозначно соответствовать набор нулей и единиц, показывающий, в каком порядке нужно сворачивать вверх или вниз, добираясь до этой вершины из корня дерева. ♦

Граф кода называется его деревом, отсюда идет другое название префиксных кодов — древовидные.

Теорема. Пусть в примитивном префиксном коде число кодовых слов, состоящих из $ k_{} $ двоичных знаков, обозначается $ N_k $, а $ r_{} $ означает число знаков в самом длинном кодовом слове. Тогда справедливо равенство

$$ \sum_{j=1}^{r} \frac{N_j}{2^j} = \frac{N_1}{2}+\frac{N_2}{2^2}+\dots+\frac{N_r}{2^r}=1 \ . $$

Для последнего рассмотренного примера имеем $$ N_1=0, N_2=2,N_3=2,N_4=3,N_5=1,N_6=2 \quad \mbox{ и } $$ $$ \frac{2}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\frac{1}{2^5}+\frac{2}{2^6}=1 \ . $$

Сколько существует различных префиксных кодов, состоящих из $ n_{} $ кодовых слов? Этот вопрос можно переформулировать в вопрос о количестве деревьев с $ n_{} $ «листьями» (их принято называть висячими вершинами), построенных по указанному в примере правилу. В таком виде (и в различных ее обобщениях и приложениях) задача впервые была поставлена в XIX веке Артуром Кэли [3].

Теорема. Количество различных префиксных кодов, состоящих из $ n_{} $ кодовых слов, равно

$$\frac{1}{n} C_{2n-2}^{n-1} \ . $$ Здесь $ C_{2n-2}^{n-1} $ — биномиальный коэффициент.

Пример. Для $ n=10 $ это число равно $ 4862 $.

Подробнее ☞ ЗДЕСЬ.

Чем префиксные коды лучше блочных? Если подсчитать общее количество двоичных символов, необходимых для кодирования четырех букв в префиксном коде

$ \mathfrak C ( $ а $ )=1 $, $ \mathfrak C ( $ в $ )=01 $, $ \mathfrak C ( $ о $ )=000 $, $ \mathfrak C ( $ с $ )=001 $ и сравнить его с совершенно очевидным двухбитным
$ \mathfrak C ( $ а $ )=00 $, $ \mathfrak C ( $ в $ )=01 $, $ \mathfrak C ( $ о $ )=10 $, $ \mathfrak C ( $ с $ )=11 $, то сравнение будет не в пользу первого: $ 9>8 $. Заметим, кстати, что второй код также является префиксным, поскольку удовлетворяет формальному определению! В чём же преимущество способа кодирования, при котором кодовые слова имеют различные длины?

— В вероятности. В больших массивах входящих информационных символов $ a_1,a_2,\dots $ некоторые символы имеют обыкновение встречаться чаще других. Тогда при кодировании имеет смысл сопоставлять им самые короткие слова префиксного кода:

чаще встречаемость - короче кодовая последовательность.

Пример. Рассмотрим пример из предыдущего пункта с кодированием $ 10_{} $ букв русского алфавита. Возьмем достаточно длинный отрывок литературного произведения и выбросим из текста все оставшиеся буквы, знаки препинания и пробелы. Получим нечто такое:

адитгдавгеаиигдеказапизваввзивекивеаидекгдавзваакаиииеааваиаавазиаавиаеадизкгдеиеазве

каиебеедиквикегеевжиаикакиизабаииаиаваед…

Исходный текст и его обработка ☞ ЗДЕСЬ. Результат:

Такое ранжирование по частоте встречаемости требует переделки таблицы кодирования; она будет заполняться по намеченному выше принципу: «чаще встречаемость — короче кодовое слово».

Стоимость кодирования приведенного текста по такой таблице равна $$ 236\cdot 2+231\cdot 2+195 \cdot 3+111 \cdot 3+94 \cdot 4+94 \cdot 4+46 \cdot 4+42 \cdot 5+40 \cdot 6+30 \cdot 6=3418 \mbox{ бит, } $$ то есть, в среднем, $ 3.05_{} $ бита на букву. Это результат очень приятен в сравнении с блочным кодом, которому для кодирования $ 10_{} $ букв требуются (не менее чем) $ 4_{} $-хбитные кодовые слова.

Попробуем теперь уменьшить полученную оценку, выбирая различные префиксные коды. Увеличиваем количество $ 3_{} $-хбитных слов за счет уменьшения количества $ 4_{} $-хбитных (левая схема):

$$ 236\cdot 2+231\cdot 2+195 \cdot 3+111 \cdot 3+94 \cdot 3+94 \cdot 5+46 \cdot 5+42 \cdot 5+40 \cdot 6+30 \cdot 6=3464 \mbox{ бит } \quad \Rightarrow \quad 3.10 \ \mbox{ бит/буква } \ . $$

Сокращаем размеры самых длинных кодовых слов (правая схема):

$$ 236\cdot 2+231 \cdot 2+194\cdot 3+111\cdot 3+94\cdot 4+93\cdot 4+46\cdot 5+42\cdot 5+41\cdot 5+31\cdot 5 =3394 \mbox{ бит } \quad \Rightarrow \quad 3.03 \ \mbox{ бит/буква } \ , $$ то есть эта схема кодирования получилась самой дешевой! ♦

Следующее замечание можно пропустить без ущерба для понимания дальнейшего материала.

Для сравнения укажем величину энтропии данного набора вероятностей:

$$ H(P_1,\dots,P_{10})=- \sum_{j=1}^{10} P_j \log_2 P_j \approx 2.991 \ . $$

Как построить самый экономичный префиксный код? Ответ на этот вопрос дается алгоритмом, предложенным Хаффманом в 1952 г.

Пример. Пусть алфавит состоит из $ 5_{} $ букв, с вероятностями вхождения в кодируемое сообщение равными

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

Удаляем две последние (имеющие минимальные вероятности) буквы из списка, а вместо них вставляем в него слово ас с приписанной ему вероятностью $ 0.4 $:

В полученном списке объединяем о и вл:

Последним шагом объединяем двухбуквенное и трехбуквенное слова в одно единое овлас с приписанной ему вероятностью $ 1_{} $. Схематично: Эту схему сокращенно записываем в виде дерева: Теперь начинаем двигаться по этому дереву в обратном направлении — от корня (пятибуквенного слова) к листьям (буквам). При прохождении каждого узла верхнюю ветвь нумеруем $ 0_{} $, а нижнюю — $ 1_{} $: В результате каждый лист дерева оказывается пронумерован:

Видим, что основой принцип экономичности — длина кодового слова соответствует частоте кодируемого символа в сообщении — соблюден. ♦

Посмотрим что даст применение предложенного алгоритма к более сложному примеру.

Пример. Рассмотрим $ 10_{} $-тибуквенный алфавит из примера, приведенного в начале пункта. Начинаем построение схемы так же, как и в предыдущем примере — ранжируем буквы по убыванию частот. Однако, в отличие от предыдущего примера, не будем ранжировать результаты, а будем сразу строить дерево в направлении «от листьев к корню». Последовательные стадии этого строительства:

Теперь нумеруем ветви дерева нулями и единицами:

Результатом оказывается таблица

которая похожа на ту, что получили случайным экспериментированием в начале пункта: то же соответствие длин кодовых слов буквам алфавита и, следовательно, та же усредненная длина кодового слова в $ 3.03 $ бита на букву. ♦

Для заданного распределения вероятностей кодируемых символов могут существовать несколько самых экономичных вариантов кодирования; код Хаффмана дает один из возможных²⁾.

Альтернативный способ построения префиксных кодов ☞ КОД ШЕННОНА-ФАНО.

Подведем краткий итог рассмотрения двух подходов к кодированию. Из поставленных в начале раздела задач кодирования — кодирование канала и кодирование источника, блочые коды, исправляющие ошибки, следует рассматривать как решающие первую задачу — кодирования канала, в то время как коды Хаффмана (с переменной длиной кода) являются решением задачи кодирования источника. Есть и еще одно направление теории кодирования, которое следует выделить в отдельный ☞ ПУНКТ.

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

☞ АЛГОРИТМ LZW

Вплоть до 70-х годов XX века слова шифрование и кодирование были синонимами. Самая известная книга по истории криптографии [5] в названии содержит выражение «взломщики кодов». В самом общем смысле, шифрование — как преобразование информации в новую форму согласно определенному правилу — можно рассматривать как частный случай кодирования.

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

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

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

Подробнее — в разделе ☞ КРИПТОГРАФИЯ.

[1]. Шеннон К. Математическая теория связи. (Shannon C.E. A Mathematical Theory of Communication. Bell System Technical Journal. — 1948. — Т. 27. — С. 379-423, 623–656.)

[2]. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.Мир. 1976.

[3]. Реньи А. Трилогия о математике. М.Мир.1980.

[4]. Сэломон Д. Сжатие данных, изображений и звука. М.Техносфера.2006.

[5]. Kahn D. The Codebreakers — The Story of Secret Writing. Simon & Schuster Adult Publishing Group. 1996