Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.3. Кодирование, автоматы и группы на графах

Типы и назначение кодирования

Кодирование производится с целью:
1) сокращения символьного текста при ограниченном количестве кодовых символов — оптимальное кодирование;
2) обнаружения и исправления ошибок при передаче и хранении информации — корректирующее кодирование;
3) защиты информации от несанкционированного доступа — секретное кодирование.

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

Предположим, нужно передать четыре сообщения — a₁, a₂, a₃, a₄. Эти сообщения можно закодировать так, как показано в табл. 3.10.

Таблица 3.10

Сообщения	a1	a2	a3	a4
Коды	00	01	10	11

При таком кодировании вероятность появления сообщений не учитывалась или предполагалась одинаковой для всех четырех сообщений (p = 0.25). Между тем их появление в информационном тексте может происходить с различной частотой,например, такой: p₁ = 0.5, p₂ = 0.25, p₃ = 0.125, p₄ = 0.125. Фано, учитывая вероятность сообщений, предложил более оптимальное кодирование (табл. 3.11).

Таблица 3.11

Сообщения	a1	a2	a3	a4
Коды	1	01	001	000

Показателем экономичности кода служит средняя длина кодового слова, которая определяется как

,

где l_i — длина кодового слова a_i , p_i — вероятность появления a_i, n — число сообщений.

Для кодировки сообщений по табл. 3.10 средняя длина равна 2, а по табл. 3.11 — 1.75. Следовательно, закодированный по методике Фано информационный текст окажется короче.

На первый взгляд, кодирование по методу Фано кажется избыточным, поскольку коды, представленные табл. 3.11, можно сократить, например так, как это показано в табл. 3.12.

Таблица 3.12

Сообщения	a1	a2	a3	a4
Коды	1	0	01	00

Теперь возьмем следующий закодированный текст: 00101000. Согласно табл. 3.12, данный текст не может быть однозначно дешифрован, так как непонятно, что, собственно, подразумевается: сообщения вида — a₂, a₃, a₃, a₄, a₂; или — a₄, a₁, a₃, a₂, a₂, a₂; или — a₂, a₂, a₁, a₂, a₁, a₂, a₄ и т.д. Расшифровка же текста по табл. 3.11 производится однозначно — a₃, a₂, a₄. Из-за этого замечательного свойства код Фано называется префексным. Никакое кодовое слово префексного кода не является началом другого кодового слова. Наряду с методом Фано, существует префексное кодирование по методу Хаффмана, экономичность которого выше первого.

Для защиты передаваемых текстов от помех используются корректирующие коды, которые основываются на информационной избыточности. Самый простой способ создания избыточности достигается многократным дублированием передаваемых символов, т.е. образование символьных блоков: 0 → 000, 1 → 111. В случае сбоя, решение при дешифровке принимается по большинству оставшихся однотипных символов в блоке. Сами блоки могут включать большее (чем 3) число символов, тогда степень защищенности текста окажется выше. Если длину блока выбрать заранее достаточно большой, то практически любые ошибки можно исключить, правда, при этом скорость передачи информации упадет пропорционально количеству символов в блоке.

Существует очень простая, но эффективная защита информационного текста от одиночного сбоя, которая требует минимальной избыточности в один дополнительный символ. Это — проверка на четность. При шифровке к тексту добавляется 0 или 1 в зависимости от четности или нечетности суммы единиц в тексте. Если при дешифровке обнаружится нечетное число единиц, значит, текст был передан неверно; если четное — ошибки при передаче не было. Корректирующий код можно построить с помощью квадратной матрицы, которая не только обнаруживает одиночную ошибку, но и определяет ее местонахождение. Пусть требуется передать девятиразрядное информационное слово a = a₁₁ ... a₃₃. Тогда к нему прибавляют семиразрядное корректирующее слово a' = a₄₁ ... a₁₄, символы которого удовлетворяют совокупности проверочных соотношений:

A = ,

(суммирование осуществляется по mod (2)).

Предположим, получено следующее закодированное сообщение:

A = a a' = 011001011 1010000.

Размещаем его в матрице 4 ´ 4 и составляем проверочные равенства:

A = ,

Проверочные соотношения для a₂₄, и a₄₁ ошибочны; следовательно, вместо a₂₁ = 0, нужно брать a₂₁ = 1; исходная последовательность должна была выглядеть как 011101011 1010000.

Для засекречивания информации исходные сообщения могут кодироваться с помощью адресной матрицы. Дело в том, что любое сообщение хранится на информационном носителе по определенному адресу и считывается по определенному коммуникационному каналу. Пусть сообщение a хранится по адресу A, который выражается трехзначным числом — A₀A₁A₂. Коммуникационные каналы обозначим как c₁, c₂, c₃ и c₄. Адресная матрица программируется так, чтобы на ней происходило смешивание адресов и коммуникационных каналов, например, в следующем конкретном виде:

c₁' = c₁A₀A₁A₂ + c₄A₀A₁A₂ + c₃A₀A₁A₂ + c₂A₀A₁A₂,
c₂' = c₄A₀A₁A₂ + c₂A₀A₁A₂ + c₁A₀A₁A₂ + c₃A₀A₁A₂,
c₃' = c₃A₀A₁A₂ + c₁A₀A₁A₂ + c₂A₀A₁A₂ + c₄A₀A₁A₂,
c₄' = c₂A₀A₁A₂ + c₃A₀A₁A₂ + c₄A₀A₁A₂ + c₁A₀A₁A₂.

Если информационное сообщение имеет адрес 100 (A₀A₁A₂), то коммуникационный канал c₁' подключается к каналу c₁, канал c₂' — к инверсному каналу c₄, c₃' — к инверсному c₃ и, наконец, c₄' — к c₂; если идет сообщение с адресом 101 (A₀A₁A₂), то осуществляется подключение канала c₁' к инверсному c₄ и т.д. В результате перемешивания каналов информационные сообщения попадают на чужие адресные места, так что несанкционированное считывание становится невозможным.