- •1. Понятие информатики
- •2. Понятие и характерные черты информации
- •Свойства информации
- •3. Виды сигнала как материального носителя информации
- •Преобразования сигнала
- •4. Системы счисления
- •5. Правила перевода чисел
- •Правила перевода целых чисел
- •Правила перевода правильных дробей
- •Правило перевода неправильных дробей
- •6. Кодирование по образцу
- •0001011101000011
- •0010 0000 0001 0010
- •2 0 1 2
- •00010100
- •Ascii-коды
- •Коды, учитывающие частоту информационных элементов
- •Коды Грея
- •7. Криптографическое кодирование
- •Метод простой подстановки
- •Метод Виженера
- •8. Эффективное кодирование
- •Универсальные методы
- •Метод Шеннона-Фано
- •Метод Хаффмена
- •9. Повышение эффективности кодирования универсальными кодами
- •Декодирование эффективных кодов
- •10. Специальные методы эффективного кодирования
- •Методы эффективного кодирования числовых последовательностей
- •2 14 18 27 34
- •2 12 4 9 7.
- •55556666888888
- •5(4)6(4)8(6),
- •Методы эффективного кодирования словарей
- •Методы эффективного кодирования естественно-языковых текстов
- •11. Помехозащитное кодирование
- •Искажение кодовых комбинаций
- •Кодовое расстояние и корректирующая способность кода
- •12. Коды, исправляющие ошибки
- •13. Измерение дискретного сигнала
- •Структурный подход к измерению информации
- •Геометрическая мера
- •Комбинаторная мера
- •Аддитивная мера
- •14. Статистический подход к измерению информации
- •Семантический подход к измерению информации
- •Полезность информации
- •Истинность информации
- •15. Структура компьютера и принципы его функционирования
- •16. Устройство управления
- •17. Арифметико-логическое устройство
- •18.Формы представления целых чисел
- •Формы представления вещественных чисел
- •Коды представления числовых данных
- •19.При сложении целых чисел последовательность шагов следующая:
- •20.Правило сложения вещественных чисел.
7. Криптографическое кодирование
В качестве символов кодирования могут использоваться как символы произвольного алфавита, так и двоичные коды.
Метод простой подстановки
Простейшим случаем такого кодирования является простая подстановка. Первый этап кодирования – построение кодовой таблицы – сводится к следующему: каждому символу исходного алфавита ставится в соответствие произвольный символ кодирования из какого-либо другого алфавита или из исходного – получается таблица соответствия. Само кодирование дискретного сообщения (второй этап) заключается в замене символов в сообщении в соответствии с полученной таблицей.
Данный метод кодирования является ненадежным, так как при достаточно большой выборке закодированных сообщений при известных частотах символов исходного алфавита можно с определенной долей погрешности выполнить декодирование.
Очевидно, декодирование также возможно при известной таблице соответствия.
Метод Виженера
Разрушить статистические зависимости в закодированных сообщениях и тем самым повысить надежность кодирования можно с помощью метода Виженера.
Первый этап кодирования (построение кодовой таблицы) сводится к тому, что символы исходного алфавита нумеруются, начиная с нуля, например, для кириллицы:
Задаются ключом кодирования – словом в исходном алфавите.
Собственно кодирование (второй этап) выполняется следующим образом: выписывают дискретный сигнал, подлежащее кодированию, и выполняют следующие шаги:
а) под каждым его символом записывают порядковый номер из таблицы соответствия:
б) под сообщением многократно выписывают ключевое слово:
в) под символами ключа выписывают их порядковые номера из таблицы соответствия:
г) порядковые номера символов складываются по модулю, равному числу символов исходного алфавита:
Напомним, что сложение по модулю (обозначается ) выполняется без переноса единицы переноса в старший разряд. Так мы получили при сложении по модулю 33, например, чисел 21 и 20 (сумма равна 41, что на 8 превышает модуль 33) значение 8,
д) полученный числовой ряд преобразуется в символы исходного алфавита по таблице соответствия:
Очевидно, что статистика не поможет декодировать это сообщение, поскольку повторяются совсем не те символы, что в исходном сообщении.
Для декодирования подобных сообщений требуется таблица соответствия и ключ. Тогда выполняют описанные выше процедуры кодирования в обратном порядке. Сложность может представлять только операция вычитания с учетом модуля. При этом следует помнить, что не должны получаться отрицательные значения. Если такое происходит, нужно занять число, соответствующее модулю.
8. Эффективное кодирование
Методы эффективного кодирования делятся на две группы - универсальные, применяемые к любым дискретным сигналам, и специальные, ориентированные на дискретные сигналы определенного типа.
Универсальные методы
Для кодирования символов исходного алфавита необходимо знание частоты символов исходного алфавита. При этом строятся двоичные коды переменной длины: чем больше частота символа, тем короче его код. Эффективность кода определяется средним числом двоичных разрядов.
Существуют два универсальных метода эффективного кодирования: методы Шеннона-Фано и Хаффмена. Входными данными для обоих методов является множество исходных символов с частотами; результат - эффективные коды.