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

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

Шеннон [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) $ и $ (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