7. Криптографическое кодирование

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

Метод простой подстановки

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

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

Очевидно, декодирование также возможно при известной таблице соответствия.

Метод Виженера

Разрушить статистические зависимости в закодированных сообщениях и тем самым повысить надежность кодирования можно с помощью метода Виженера.

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

Задаются ключом кодирования – словом в исходном алфавите.

Собственно кодирование (второй этап) выполняется следующим образом: выписывают дискретный сигнал, подлежащее кодированию, и выполняют следующие шаги:

а) под каждым его символом записывают порядковый номер из таблицы соответствия:

б) под сообщением многократно выписывают ключевое слово:

в) под символами ключа выписывают их порядковые номера из таблицы соответствия:

г) порядковые номера символов складываются по модулю, равному числу символов исходного алфавита:

Напомним, что сложение по модулю (обозначается ) выполняется без переноса единицы переноса в старший разряд. Так мы получили при сложении по модулю 33, например, чисел 21 и 20 (сумма равна 41, что на 8 превышает модуль 33) значение 8,

д) полученный числовой ряд преобразуется в символы исходного алфавита по таблице соответствия:

Очевидно, что статистика не поможет декодировать это сообщение, поскольку повторяются совсем не те символы, что в исходном сообщении.

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

8. Эффективное кодирование

Методы эффективного кодирования делятся на две группы - универсальные, применяемые к любым дискретным сигналам, и специальные, ориентированные на дискретные сигналы определенного типа.

Универсальные методы

Для кодирования символов исходного алфавита необходимо знание частоты символов исходного алфавита. При этом строятся двоичные коды переменной длины: чем больше частота символа, тем короче его код. Эффективность кода определяется средним числом двоичных разрядов.

Существуют два универсальных метода эффективного кодирования: методы Шеннона-Фано и Хаффмена. Входными данными для обоих методов является множество исходных символов с частотами; результат - эффективные коды.