Курс: Теория кодирования и криптография Лектор – Латыпов Рустам Хафизович. - презентация

1 Курс: Теория кодирования и криптография Лектор – Латыпов Рустам Хафизович

2 Тема: Кодирование информации Эффективное кодирование Помехоустойчивое кодирование Криптография Лекция 1

3 Виды преобразований Кодирование - это частный случай преобразования информации. эффективное (оптимальное) кодирование; помехоустойчивое кодирование криптография (кодирование с засекречиванием информации).

4 Клод Элвуд Шеннон ( )

5 Модель передачи сообщений В схеме передачи сообщений представлены все виды кодирования и соответствующие им кодирующие устройства на передающей стороне (кодеры) и декодирующие устройства на приемной стороне (декодеры). Сокращения: К - криптографический; Э - эффективный; П - помехоустойчивый.

6 Эффективное кодирование Речь идет о сокращении объема передаваемой информации Количество информации принято связывать с понятием энтропии.

7 Эффективное кодирование Эффективное, или экономичное, кодирование означает достижение минимального значения средней длины кода символа В телеграфии широко известна азбука Морзе. Сокращение n ср здесь достигается за счет назначения часто встречающимся символам коротких кодов (одна «точка» или одно «тире»). Наоборот, редкие символы имеют длинные коды.

8 Эффективное кодирование Кодирование по методу Хаффмена (А.Д. Хаффмен – американский математик; работа – 1952 г.) гарантирует оптимум для заданного множества {р i }. 1. Символы z i упорядочиваются по убыванию вероятности pi. 2. Два последних (нижних в табл.1) символа объединяются в группу-пару, соответствующую вспомогательному символу с суммарной вероятностью. Если суммируемые вероятности представляют исходные значения p i, это специально отмечается («*»). Здесь – конец формирования кода соответствующего символа. Далее пп. 1 и 2 повторяются. При этом в общем случае происходит переупорядочивание вероятностей p i. В конце концов суммарная вероятность достигает значения 1 и процесс заканчивается.

9 Эффективное кодирование Таблица 1 Пример кодирования но Хаффмену

10 Эффективное кодирование Теперь строится кодовое дерево. Вершины дерева отмечены соответствующими вероятностями (меньшая - слева). Теперь по кодовому дереву могут быть сформированы коды всех символов – спуск из корневой вершины, где вероятность 1.00 (табл.2).

11 Эффективное кодирование Таблица 2 Кодирование Хаффмена ZiZi pipi Кодnini nipinipi Z1Z Z2Z Z3Z Z4Z Z5Z Z6Z Z7Z Z8Z

12 Эффективное кодирование n ср = 2,75 < 3. Сжатие данных по Хаффману применяется при сжатии фото- и видеоизображений (JPEG, стандарты сжатия MPEG), в архиваторах (PKZIP, LZH и др.), в протоколах передачи данных MNP5 и MNP7.JPEGMPEGPKZIPLZH

13 Помехоустойчивое кодирование Защита сообщения от помех (ошибок)

14 Избыточность естественного языка Бу** мг**ю **бо к**ет **хри **ежн** кру** Буря мглою небо кроет вихри снежные крутя

15 Помехоустойчивое кодирование Борьба с помехами, вносимыми в линию связи (рис.1), требует введения избыточности в кодовую комбинацию (КК): кроме информационных разрядов формируются и передаются контрольные (проверочные) разряды. Пусть при длине n двоичного сообщения m разрядов - информационные, k – проверочные. Тогда избыточность помехоустойчивого (корректирующего) кода составит Значения R заключены в диапазоне от 0 (k = 0) до почти 1 (k >>m).

16 Помехоустойчивое кодирование Корректирующая способность помехоустойчивого кода оценивается двумя параметрами: кратность обнаруживаемых ошибок. Q обн ; кратность исправляемых ошибок, Q испр. Наиболее простыми способами помехоустойчивого кодирования являются: многократная передача (дублирование) контроль по нечетности (четности)

17 Помехоустойчивое кодирование В первом способе кодовая комбинация передается минимум 2 раза. Если принятые значения совпадают, все в порядке. Если нет, запрашивается еще 1 передача, и далее действует мажоритарный принцип – решение принимается по большинству (2 > 1 и т.п.). Способ многократной передачи – самый избыточный. Элемент его – перезапрос кодовой комбинации присутствует и в других способах помехоустойчивого кодирования - когда ошибка только обнаруживается, но не исправляется.

18 Помехоустойчивое кодирование Контроль по нечетности (четности)- один из самых простых и распространенных. Обычно в каждый байт (8 двоичных информационных разрядов) вводится разряд-бит проверки на четность (parity bit). Значение этого разряда получается как дополнение количества единиц в байте до четного (нечетного) числа. Например, слово содержит 4 (четное) число единиц, поэтому при контроле по четности в проверочном разряде - единица:

19 Помехоустойчивое кодирование Избыточность кода нечетности-четности невелика: R = 1/8 = 0,125. Невелика и корректирующая способность этого кода – ошибки могут только обнаруживаться, причем нечетной кратности (1, 3, 5, 7), но не исправляются (Q испр = 0). Еще один недостаток – ложная тревога. Ошибка случилась в контрольном разряде, информационные - в порядке. Но несмотря на это, будет сделан перезапрос кодовой комбинации.

20 Криптография Засекречиванием информации люди занимались еще в глубокой древности. В средние века было принято зашифровывать научные результаты при первой публикации, с тем чтобы закрепить приоритет открытия – только посте этого считалось возможным сообщение расшифровать.

21 Криптография Так, Г.Галилей (1564 – 1642 гг.), используя свой телескоп с 32-кратным увеличением, впервые наблюдал кольцо (кольца) Сатурна. Правда, вместо кольца он увидел своеобразные «придатки» - два спутника: «Altissimum planetam tergeminum observavi» («Высочайшую планету тройную наблюдал»). Здесь «высочайший» Сатурн – бог Времени и Судьбы. Зашифрованная опубликованная запись (анаграмма) представляла «фразу» на латинском языке: Smaismrmielmepcttaleumibuvnenugttaviras

22 Криптография Кстати, попытка расшифровки путем полного перебора вариантов столкнулась бы с такой оценкой количества перестановок с повторениями 39!/(5! 3! 2! 2! 5! 2! 4! 2! 3! 3! 3! 4!) И. Кеплер (1571 – 1630 гг.) опустив 2 буквы, получил: «Salve, umbistineum geminatum Martia proles» («Привет вам, близнецы, Марса порождение»)

23 Общие понятия Он считал, что Галилей открыл спутники Марса, – по аналогии: у Земли – один спутник, у Юпитера – четыре (фактически 16), значит, у Марса их два (так и фактически, но только через 300 лет). Кстати, Галилей действительно включил две дополнительные буквы – для затруднения расшифровки Наконец. X. Гюйгенс (1629 – 1695 гг.) через 50 лет после Галилея распознал кольцо Сатурна и опубликовал такую анаграмму: Aaaaaaa, ccccc, d, еееее, g, h, iiiiiii. (расшифровка вряд ли вообще возможна).

24 Криптография Лишь через 3 года, окончательно убедившись в правильности своих первоначальных заключений, Гюйгенс сообщил действительный смысл анаграммы: «Annulo cingitur, tenui plano, nusquam cohaerente, ad eclipticam inclinato» («Кольцом окружен тонким, плоским, нигде не прикасающимся, к эклиптике наклоненным»).