Метод Вижинера
Разрушить статистические зависимости в закодированных сообщениях и тем самым повысить надежность кодирования можно с помощью метода Вижинера. Алгоритм применения этого метода приведен ниже:
1) символы исходного алфавита нумеруются, начиная с нуля, например:
А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я Ь Ъ Ы
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Получают таблицу соответствия;
2) задаются ключом кодирования – словом в исходном алфавите, например, АСУ;
3) выписывают сообщение, подлежащее кодированию, например, пусть это будет сообщение ИНФОРМАТИКА, и выполняют следующие шаги:
а) под каждым его символом записывают порядковый номер из таблицы соответствия:
И Н Ф О Р М А Т И К А
8 12 19 13 15 11 0 17 8 9 0
б) под сообщением выписывают ключевое слово, а под символами ключа выписывают их порядковые номера из таблицы соответствия:
А С У А С У А С У А С
0 16 18 0 16 18 0 16 18 0 16
в) порядковые номера символов складываются по модулю, равному числу символов исходного алфавита (в нашем случае – 31):
8 28 6 13 0 29 0 2 26 9 16
Напомним, что сложение по модулю (обозначается ⊕) выполняется без переноса единицы переноса в старший разряд. Так мы получили при сложении по модулю 31, например, чисел 17 и 16 (сумма равна 33, что на 2 превышает модуль 31) значение 2;
4) полученный числовой ряд преобразуется в символы исходного алфавита по таблице соответствия. Так имеем:
И Ь Ж О А Ъ А В Ю К С.
Очевидно, что статистика не поможет декодировать это сообщение, поскольку повторяются совсем не те символы, что в исходном сообщении.
Для декодирования подобных сообщений требуется таблица соответствия и ключ. Тогда выполняют описанные выше процедуры кодирования в обратном порядке. Сложность может представлять только операция вычитания с учетом модуля. При этом следует помнить, что не должны получаться отрицательные значения. Если такое происходит, нужно занять число, соответствующее модулю.
Пример 1. Декодировать сообщение И Ь Ж О А Ъ А В Ю К С, задавшись ключом АСУ и зная таблицу соответствия.
Решение:
а) выписываем под закодированным сообщением порядковые номера символов из таблицы соответствия (см. выше):
И Ь Ж О А Ъ А В Ю К С
8 28 6 13 0 29 0 2 26 9 16
б) выписываем под сообщением ключ с порядковыми номерами символов:
А С У А С У А С У А С
0 16 18 0 16 18 0 16 18 0 16
в) вычитаем с учетом модуля 31 из чисел в закодированном сообщении числа для ключа:
8 12 19 13 15 11 0 17 8 9 0
г) преобразуем числа в символы по таблице соответствия:
И Н Ф О Р М А Т И К А
При декодировании возникла сложность в получении кодов символов Т, Ф, Р. В самом деле, при вычитании из 2 числа 16 получалось –14. Тогда к 2 прибавили модуль 31, получили 33 и уже из 33 вычли 16. Получили 17 – порядковый номер символа Т. Аналогично поступили и с символами Ф и Р.
Эффективное кодирование
Этот вид кодирования используется для уменьшения объемов информации на носителе - сигнале.
Для кодирования символов исходного алфавита используют двоичные коды переменной длины: чем больше частота символа, тем короче его код. Эффективность кода определяется средним числом двоичных разрядов для кодирования одного символа – lср по формуле
где k – число символов исходного алфавита;
ns – число двоичных разрядов для кодирования символа s;
fs – частота символа s; причем
При эффективном кодировании существует предел сжатия, ниже которого не «спускается» ни один метод эффективного кодирования - иначе будет потеряна информация. Этот параметр определяется предельным значением двоичных разрядов возможного эффективного кода – lпр:
где n – мощность кодируемого алфавита,
fi – частота i-го символа кодируемого алфавита.
Существуют два классических метода эффективного кодирования: метод Шеннона-Фано и метод Хаффмена. Входными данными для обоих методов является заданное множество исходных символов для кодирования с их частотами; результат - эффективные коды.