Использование корректирующих кодов при защите информации

Тема урока: «Использование корректирующих кодов при защите информации»

Цели урока:

Образовательные:

• Углубить теоретические знания по теме «Программно-аппаратные средства обеспечения информационной безопасности».

• Способствовать применению знаний в решении практических задач по обеспечению информационной безопасности.

Развивающие:

• Развивать навыки индивидуальной и групповой практической работы.

• Развивать способность логически рассуждать, делать выводы.

Воспитательные:

• Формировать умения работать в коллективе и команде, эффективно общаться с коллегами, руководством, клиентами.

Методические:

• Познакомить педколлектив с групповой формой организации деятельности студентов на уроке, освоением методов самостоятельного анализа полученной на уроке информации и самостоятельного решения задач.

Тип урока: урок применения знаний, умений, навыков на практике

Методы проведения:

• решение практических задач с использованием УМК (лабораторного практикума с CD);

• технология парного программирования;

• технология разноуровневого обучения

Ход урока

1. Организационный момент.

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

1. Мотивация учебной деятельности студентов

Осмысление значимости выполняемой работы по изучению темы студентами для осуществления профессиональной деятельности

1. Актуализация опорных знаний

Фронтальный опрос:

1. Перечислите методы контроля целостности программ и данных

2. Поясните, в чем заключается метод использования контрольного суммирования

3. Поясните, в чем заключается метод использования хэш-функции

4. Перечислите виды ошибок, возникающих при передаче информации

5. Поясните, что такое систематический код (корректирующий код)

6. Поясните, в чем заключается идея метода помехоустойчивого кодирования

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

Если студент не отвечает на вопрос, ему помогают товарищи.

1. Ознакомление с методом корректирующих кодов, инструкция по решению задач

1. Работа с презентацией, методическими рекомендациями к выполнению лабораторной работы:

1. Код с проверкой на четность

2. Код Хэмминга: решение задачи на построение кода, проверка правильности, внесение ошибки, исправление ошибки

1. Примеры практического использования метода корректирующих кодов:

1. Сообщение «Разработки Хэмминга» - Багдасарян А.

2. Сообщение «Примеры программной реализации корректирующих кодов» - Собко Н.

Методические рекомендации к выполнению лабораторной работы представлены в Приложении 1.

1. Выполнение лабораторной работы.

1. Самостоятельная работа студентов по группам по решению задач на построение кода Хэмминга – 25 мин

Студенты решают задачу №1 лабораторной работы «Корректирующие коды. Коды Хэмминга» по парам в 5 вариантах. Работа студентов на ПК.

Проверка выполнения в тетрадях с пояснением метода; замечания, корректировка, оценка.

Один любой вариант студенты представляют на демонстрационном экране с пояснением алгоритма решения.

Решения задач представлены в Приложении 2.

1. Индивидуальная самостоятельная работа студентов по решению задач обнаружения ошибки в полученном сообщении и ее исправления – 20 мин.

Студенты решают задачу №2 лабораторной работы «Корректирующие коды. Коды Хэмминга» индивидуально в 3 вариантах. Работа студентов на ПК.

Проверка выполнения в тетрадях с пояснением метода; замечания, корректировка, оценка.

Один любой вариант студенты представляют на демонстрационном экране с пояснением алгоритма решения.

Решения задач представлены в Приложении 2

Дополнительное задание представлено в Приложении 4

1. Проверка выполнения заданий

Обсуждение работ по контрольным вопросам в лабораторной работе

Контрольные вопросы:

1. Охарактеризуйте понятие «корректирующий код»

2. Приведите алгоритм построения кода Хэмминга

3. К какому виду кодирования относится метод Хэмминга?

4. Поясните алгоритм вычисления функции H(X)

5. Каким образом можно установить наличие ошибки в сообщении Х? Как определить место ошибки?

6. Какие ошибки можно исправить с помощью кода Хэмминга?

1. Подведение итогов – 5 мин.

Подведение итогов: преподаватель подводит итог урока, оценивает работу каждого студента с последующей самооценкой студента.

Критерии оценки различных видов работ представлены в Приложении 3

Домашнее задание:

• Подготовить сообщения о методах программной реализации кодов с проверкой на нечетность и других модификаций корректирующих кодов

Рефлексия:

Студенты по очереди высказываются одним предложением, выбирая начало фразы:

1. сегодня я узнал…

2. было интересно…

3. было трудно…

4. я выполнял задания…

5. я понял, что…

6. теперь я могу…

7. я приобрел…

8. я научился…

9. у меня получилось …

Приложение 1

Лабораторная работа

Корректирующие коды. Коды Хэмминга

Цель: ознакомиться с общими принципами построения и использования корректирующих кодов для контроля целостности информации, распространяемой по телекоммуникационным каналам, изучить метод кодирования по Хэммингу

Кодом называется система условных знаков (символов) для передачи, обработки и хранения (запоминания) различной информации.

Предметом исследования теории кодирования являются отображения конечных или счетных множеств объектов произвольной природы в множества последовательностей из цифр 0, 1,…r-1, где r – некоторое целое положительное число (в частности, r = 2). Такие отображения называются кодированиями.

Большинство задач теории кодирования укладывается в следующую схему:

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

• существование однозначного обратного отображения (декодирования),

• возможность исправления при декодировании ошибок различного типа,

• возможность простой реализации (простота алгоритма) кодирования и декодирования и т.п.

Некоторые виды преобразований двоичных слов, называемых ошибками:

1. Одиночная ошибка вида 01 (10) в слове X - замещение символа,

2. Одиночная ошибка вида 0 (1) в слове X - удаление одного из символов 0 (соответственно 1)

3. Одиночная ошибка вида 0 (1) - вставка символа перед некоторым символом слова или после его последнего символа

4. Одиночная ошибка вида +2i (-2i) в слове X  Вn, где 0  i

Для иллюстрации в таблице 1 приведены слова, полученные из слова 0001101 (двоичная запись числа 13) в результате ошибок рассматриваемых видов.

Таблица 1

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

Способы контроля правильности передачи данных. Код с проверкой на четность

Контроль целостности информации при передаче от источника к приемнику может осуществляться с использованием корректирующих кодов.

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

Пример 1. Рассмотрим код с проверкой на четность, образованный добавлением контрольного разряда к простому двоичному коду:

Такой код обнаруживает все одиночные ошибки и групповые ошибки нечетной кратности, так как четность количества единиц в этом случае будет также нарушаться.

Следует отметить, что при кодировании целесообразно число единиц в кодовой комбинации делать нечетным и осуществлять контроль на нечетность. В этом случае любая комбинация, в том числе и изображающая ноль, будет иметь хотя бы одну единицу, что дает возможность отличить полное отсутствие информации от передачи нуля.

Возможно экономное помехоустойчивое кодирование. Идея таких методов заключается в следующем:

На множестве двоичных слов рассматривается некоторая функция. Искомый код определяется как множество слов из Вn, на которых эта функция принимает некоторое фиксированное значение. Функция подбирается таким образом, чтобы в результате любой одиночной ошибки значение функции изменялось и чтобы по этому изменению и, быть может, самому полученному слову можно было однозначно определить вид и место ошибки.

Н(Х) представляет собой вектор длины k, полученный в результате сложения векторов, являющихся двоичными записями (с помощью k цифр) номеров единичных символов слова X.

Теорема. Код Хэмминга Hn, состоящий из всех слов X = х1х2...хn  Вn таких, что

Н(Х) = (0,0,…,0),

является кодом с исправлением одного замещения.

Примечание: при вычислении функции Н(Х) вычисляется сумма по модулю 2 двоичных номеров строк, в которых знак сообщения Х равен единице.

Р.Хэммингом предложен способ кодирования, обеспечивающий простое и удобное декодирование.

N-значный код Хэмминга имеет m информационных и k контрольных разрядов.

Число контрольных разрядов должно удовлетворять соотношению

k  log2(n+1),

откуда m  n - log2(n+1)

Для этого кодируемое слово X длины m дополняется k контрольными разрядами, которые определенным образом рассчитываются при кодировании, и полученное сообщение Х состоит из m информационных и k контрольных позиций.

Для контрольных разрядов отводятся 1-й, 2-й, 4-й, 8-й и т.д., номера которых являются целыми степенями числа 2: их двоичные представления содержат ровно одну единицу. На остальные места: 3, 5, 6, 7, 9, 10,... помещают символы кодируемого слова X.

Рассмотрим пример построения кода Хэмминга в следующей задаче:

Для заданного сообщения Х = 0110101 построить код Хэмминга Х. Внести одиночную ошибку замещения и произвести декодирование.

Решение:

Самостоятельно решить задачи:

1. Построить код Хэмминга Х для заданного сообщения Х. Внести одиночную ошибку замещения в i-й разряд и, произведя декодирование, подтвердить место ошибки:

а) Х = 11001010 (i = 6) б) Х = 10110011 (i = 4)

в) Х = 00110101 (i = 9) г) Х = 11101001 (i = 10)

д) Х = 1010011 (i = 5)

1. Принят некоторый код, проверить правильность кода, при необходимости исправить ошибку. Выполнить декодирование, получить исходное сообщение Х

а) принят код 111100

б) принят код 111010

в) принят код 100000

Примечание: при решении задач используйте справочный материал к работе, оформите решения средствами MS Excel или MS Word.

Выполните конспект работы в тетради.

Контрольные вопросы:

1. Охарактеризуйте понятие «корректирующий код»

2. Приведите алгоритм построения кода Хэмминга

3. К какому виду кодирования относится метод Хэмминга?

4. Поясните алгоритм вычисления функции H(X)

5. Каким образом можно установить наличие ошибки в сообщении Х? Как определить место ошибки?

6. Какие ошибки можно исправить с помощью кода Хэмминга?

Справочный материал к лабораторной работе

1. Восьмеричная система счисления

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

1. Шестнадцатеричная система счисления

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

1. Основные логические операции

ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)

Отличается от обычного ИЛИ последней строкой в таблице истинности:

Схема ИСКЛЮЧАЮЩЕЕ ИЛИ соответствует «сложению по модулю 2» и представлена на рис. 1.

Рис. 8 Схема ИСКЛЮЧАЮЩЕЕ ИЛИ

Приложение 2

Решения задач лабораторной работы

1. Построить код Хэмминга Х для заданного сообщения Х. Внести одиночную ошибку замещения в i-й разряд и, произведя декодирование, подтвердить место ошибки:

а) Х = 11001010 (i = 6) б) Х = 10110011 (i = 4)

в) Х = 00110101 (i = 9) г) Х = 11101001 (i = 10)

д) Х = 1010011 (i = 5)

Решение №1 (а):

Построить код Хэмминга Х для заданного сообщения Х. Внести одиночную ошибку замещения в i-й разряд и, произведя декодирование, подтвердить место ошибки:

а) Х = 11001010 (i = 6)

1. Размещение знаков сообщения в информационных разрядах

Рис. 9. Первый этап решения: информационные знаки

Решение №1 (б):

Построить код Хэмминга Х для заданного сообщения Х. Внести одиночную ошибку замещения в i-й разряд и, произведя декодирование, подтвердить место ошибки:

б) Х = 10110011 (i = 4)

1. Размещение знаков сообщения в информационных разрядах

Рис. 13. Первый этап решения: информационные знаки

Решение №1 (в):

Построить код Хэмминга Х для заданного сообщения Х. Внести одиночную ошибку замещения в i-й разряд и, произведя декодирование, подтвердить место ошибки:

в) Х = 00110101 (i = 9)

1. Размещение знаков сообщения в информационных разрядах

Рис. 17. Первый этап решения: информационные знаки

Решение №1 (г):

Построить код Хэмминга Х для заданного сообщения Х. Внести одиночную ошибку замещения в i-й разряд и, произведя декодирование, подтвердить место ошибки:

г) Х = 11101001 (i = 10)

1. Размещение знаков сообщения в информационных разрядах

Рис. 21. Первый этап решения: информационные знаки

Решение №1 (д):

Построить код Хэмминга Х для заданного сообщения Х. Внести одиночную ошибку замещения в i-й разряд и, произведя декодирование, подтвердить место ошибки:

д) Х = 1010011 (i = 5)

1. Размещение знаков сообщения в информационных разрядах

Рис. 25. Первый этап решения: информационные знаки

Решение задачи №2

Принят некоторый код, проверить правильность кода, при необходимости исправить ошибку. Выполнить декодирование, получить исходное сообщение Х

А) принят код 111100

Б) принят код 111010

В) принят код 100000

Решение №2 (а)

Принят некоторый код, проверить правильность кода, при необходимости исправить ошибку. Выполнить декодирование, получить исходное сообщение Х

А) принят код 111100

1. Размещение знаков сообщения в информационных разрядах

Рис. 29. Запись разрядов кода

Решение №2 (б)

Принят некоторый код, проверить правильность кода, при необходимости исправить ошибку. Выполнить декодирование, получить исходное сообщение Х

Б) принят код 111010

1. Размещение знаков сообщения в информационных разрядах

Рис. 32. Запись разрядов кода

Решение №2 (в)

Принят некоторый код, проверить правильность кода, при необходимости исправить ошибку. Выполнить декодирование, получить исходное сообщение Х

В) принят код 100000

1. Размещение знаков сообщения в информационных разрядах

Рис. 35. Запись разрядов кода

Приложение 3

Критерии оценки различных видов работ

В результате выводится средняя оценка каждому студенту.

Дополнительное задание оценивается отдельно, студент получает вторую оценку на занятии.

30