Файл: Лабораторная работа 1 Защита документов ms office Цель изучить методы защиты документов ms office, правила создания сложных паролей.pdf

Типом ошибки будем называть некоторое множество видов одиночных ошибок.
Например, ошибка типа {
0→∧, 1→∧, ∧→0, ∧→1} есть выпадение или вставка произвольного символа. Число одиночных ошибок в некоторой их последовательности будем называть
кратностью ошибки. Так, в результате ошибки кратности 3 (вставка 1 перед первым символом, затем выпадение 0 перед пятым и замещение последнего символа) слово 0001101 переводится в слово 1001100.
В дальнейшем особое внимание будет уделено ошибкам типа {(
0→1),
(1→0)}, т.е. замещениям символов.
Далее мы будем рассматривать только случай одиночной ошибки типа замещения.
Возможно экономное
помехоустойчивое кодирование. Идея таких методов заключается в следующем:
На множестве двоичных слов рассматривается некоторая функция. Искомый код определяется как множество слов из В
n
, на которых эта функция принимает некоторое фиксированное значение. Функция подбирается таким образом, чтобы в результате любой одиночной ошибки значение функции изменялось и чтобы по этому изменению и, быть может, самому полученному слову можно было однозначно определить вид и место ошибки.
Мы рассмотрим один пример такого кодирования -
код Хэмминга.
Зафиксируем число n и найдем число l
такое, что 2
l-1
≤
n
≤
2
l
В этом случае l = [log n] + 1. Например, l(5) = l(7) = 3, l(8) = l(10) = l(13) = 4.
Для произвольного слова X = х
1
х
2
...х
n
∈
В
n
положим
Н(Х) представляет собой вектор длины l, полученный в результате сложения векторов, являющихся двоичными записями (с помощью l цифр) номеров единичных символов слова X.
Пример.Пусть n = 6, X = 010101 и Y = 110100. Тогда l= l(6) = 3,
Примечание: при вычислении функции Н(Х) вычисляется сумма по модулю 2 двоичных номеров строк, в которых знак сообщения Х (или Y) равен единице.
Теорема. Код Хэмминга H
n
, состоящий из всех слов X = х
1
х
2
...х
n
∈
В
n
таких, что

Н(Х) = (0,0,…,0), является кодом с исправлением одного замещения.
В рассмотренном выше примере X
∈
Н
6
, Y
∉
Н
6
.
Р.Хэммингом предложен способ кодирования, обеспечивающий простое и удобное декодирование. Для этого кодируемое слово X длины m дополняется l проверочными разрядами (l = log (m + 1)), которые определенным образом рассчитываются при кодировании, и полученное сообщение X состоит из m информационных и l проверочных позиций. Для проверочных разрядов отводятся
1-й, 2-й, 4-й, 8-й и т.д., номера которых являются целыми
степенями числа 2: их двоичные представления содержат ровно одну единицу. На остальные места:
3, 5, 6, 7, 9, 10,... помещают символы кодируемого слова X.
Рассмотрим пример построения кода Хэмминга в следующей задаче:
Для заданного сообщения Х = 0110101 построить код Хэмминга Х
′
.
Внести одиночную
ошибку замещения и произвести декодирование.
Решение:
№ п/п
Алгоритм
Конкретное соответствие задания алгоритму
1 Подготовить строку для сообщения Х
′
, отводя места с номерами, равными
2
k
, для проверочных символов, а остальные разряды – для информационных символов сообщения Х
′
Разряды 1, 2, 4, 8 – проверочные; Разряды 3, 5, 6, 7, 9, 10, 11,… - информационные
11 10 9 8 7 6 5 4 3 2 1 и и и
п и и и п и п п
2 Разместить знаки сообщения Х в информационных разрядах
11 10 9 8 7 6 5 4 3 2 1 3 Построить таблицу с двоичными номерами разрядов и внести в информационные разряды знаки сообщения Х
1 0001 2
0010 3
0011 1
4 0100 5
0101 0
6 0110 1

7 0111 0
8 1000 9
1001 1
10 1010 1
11 1011 0
4
Для каждого из проверочных разрядов с номером
2
k
определить строки, формирующие проверочные знаки кода Х
′
:
1.
информационный знак кода Х
′
равен 1;
2.
в двоичном представлении номера строки k-й разряд равен
1.
Расчет проверочных символов
1 0001
0
p1=p3 ⊕ p9 2
0010
1
p2=p3 ⊕ p6⊕ p10 3
00
11
1 4
0100
1
p4=p6 5
0101 0
6 0
110 1
7 0111 0
8 1000
0
p8= p9 ⊕ p10 9
100
1
1 10 10
10 1
11 1011 0
В таблице выделены жирным шрифтом единицы в тех строках, в которых значение исходного сообщения равно1
(строки 3, 6, 9, 10)
5
Вычислить значения проверочных разрядов
Проверочные символы
p1,
p2,
p4,
p8 вычисляются следующим образом:
р
i
равно сумме по модулю 2 тех
информационных символов, номера которых имеют единицу в двоичном представлении там же, где и номер р i
, т.е. в i- ом разряде справа: p1 - в 1-ом разряде, p2 - во
2-ом, p4 - в 3-ем, p8 – в
4-ом.

6
Объединяя информационные и проверочные разряды, получить искомое сообщение
Х
′
Построенное закодированное по
Хэммингу сообщение Х
′
=
01100101110 (списано снизу вверх поразрядно)
Проверим правильность кодирования,
вычислив значение H(X):
Выпишем в столбец двоичные номера строк, в которых знак сообщения Х
′
равен единице. Сумма по модулю 2 знаков номеров в каждом разряде должна быть равной 0.
№ строки
Двоичное представление номера строки
Знаки сообщения
Х
′
2 00
10 1
3 00
11
1 4
0
100 1
6 0
110 1
9
1001
1 10
1010 1
0000

7
Внести ошибку замещения в один из разрядов и произвести декодирование
Пусть при передаче сообщения Х
′
произошла ошибка замещения в 7-ом разряде, т.е. полученное сообщение Х
′′
= 01101101110
Вычислим значение H(Х
′′
):
1.
Выпишем в столбец двоичные номера строк, в которых знак сообщения Х
′′
равен единице.
2.
Суммируем по модулю 2 знаки номеров в каждом разряде:
00
10 1 00
11 1 0
100 1 0
110 1 0
111 1
1001 1
1010 1
0111
Полученное двоичное число
0111 равно номеру разряда 7, в котором произошла ошибка.
Заменяя в сообщении Х
′′
значение 7-го разряда на противоположное, восстанавливаем Х
′
; вычеркивая из Х
′
проверочные разряды, получаем искомое сообщение Х.
Самостоятельно решить задачи:
1.
Построить код Хэмминга Х
′
для заданного сообщения Х. Внести одиночную
ошибку замещения в i-й разряд и, произведя декодирование, подтвердить место
ошибки: а) Х = 11001010 (i = 6)
б) Х = 10110011 (i = 4)
в) Х = 00110101 (i = 9)
г) Х = 11101001 (i = 10)
д) Х = 1010011 (i = 5)
Примечание: при решении задачи используйте справочный материал к работе.
2.
Принят некоторый код с ошибкой замещения, подтвердить место ошибки:

А) принят код 111100; исправлено 11
0100 – ошибка по корректирующему числу в разряде 4;
Б) принят код 111010; исправлено 1
01010 – ошибка по корректирующему числу в разряде 5;
В) принят код 100000; исправлено
000000 – ошибка по корректирующему числу в разряде 6.
Контрольные вопросы:
1.
Охарактеризуйте понятие «корректирующий код»
2.
Перечислите ошибки, возникающие при передаче информации
3.
Приведите алгоритм построения кода Хэмминга
4.
К какому виду кодирования относится метод Хэмминга?
5.
Поясните алгоритм вычисления функции H(X)
6.
Каким образом можно установить наличие ошибки в сообщении Х?
Как определить место ошибки?
Справочный материал к практической №12
1.
Восьмеричная система счисления
Для представления одной цифры восьмеричной системы используется три двоичных разряда
(триада):
Цифра
0
1
2
3
4
5
6
7
Триада
000 001 010 011 100 101 110 111
2.
Шестнадцатеричная система счисления
Для представления одной цифры шестнадцатеричной системы используется четыре двоичных разряда (тетрада):
Цифра 0
1
2
3
4
5
6
7
Тетрада 0000 0001 0010 0011 0100 0101 0110 0111
Цифра 8
9
А
В
С
D
E
F
Тетрада 1000 1001 1010 1011 1100 1101 1110 1111
3.
Основные логические операции
ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)
Отличается от обычного ИЛИ последней строкой в таблице истинности:
Схема
ИСКЛЮЧАЮЩЕЕ ИЛИ соответствует «сложению по модулю 2» и представлена на рис. 1.

Рис. 1 Схема
ИСКЛЮЧАЮЩЕЕ ИЛИ
Лабораторная работа№13
Корректирующие коды. Циклические коды
Цель: ознакомиться с общими принципами построения и использования корректирующих кодов для контроля целостности информации, распространяемой по телекоммуникационным каналам, изучить принципы построения циклических кодов
Циклические коды
Циклические коды – разновидность систематических кодов и поэтому обладают всеми их свойствами. Характерной особенностью циклического кода, определяющей его название, является то, что
если n – значная кодовая комбинация a
0
a
1
a
2
...a
n-1
a
n
принадлежит
данному коду, то и комбинация a
n
a
0
a
1
a
2
...a
n-1
, полученная циклической перестановкой
знаков, также принадлежит этому коду.
Идея построения циклических кодов базируется на использовании неприводимых многочленов.
Неприводимым называется многочлен, который не может быть
представлен в виде произведения многочленов низших степеней, т.е. такой многочлен,
который делится на самого себя или на единицу.
Неприводимые многочлены при построении циклических кодов играют роль так называемых образующих полиномов, от вида которых, собственно, и зависят основные характеристики полученного кода: избыточность и корректирующая способность. В таблице 1 указаны неприводимые многочлены со степенями k=1, 2, 3, 4
Таблица 1
К
P(x)
P(1, 0)
K=1 X+1 11
K=2 X
2
+X+1 111
K=3 X
3
+X+1 1011
X
3
+X
2
+1 1101
K=4 X
4
+X+1 10011
X
4
+X
3
+1 11001
X
4
+X
3
+X
2
+X+1 11111
Основные принципы кодирования в циклическом коде заключаются в следующем.
Двоично-кодированное n-разрядное число представляется полиномом n-1 – й степени некоторой переменной x, причем коэффициентами полиномов являются двоичные знаки соответствующих разрядов. Запись, чтение и передача кодовых комбинаций в циклическом коде производятся, начиная со старшего разряда. В соответствии с этим правилом в дальнейшем сами числа и соответствующие им полиномы будем записывать так, чтобы старший разряд оказывался справа.
Пример. 1

Число (нумерация разрядов согласно выше приведенному правилу, ведется слева направо от 0 до 5) будет представлено полиномом пятой степени:
0 1 2 3 4 5
1 1 0 1 0 1 1+Х+Х
3
+Х
5
Следует отметить, что циклическая перестановка разрядов в двоичном представлении числа соответствует умножению полинома на x, при котором x
n
заменяется единицей и переходит в начало полинома.
Пример 2.
Выполним умножение полинома, полученного в предыдущем примере, на X. Новый полином
Х+Х
2
+Х
4
+Х
6
преобразуем, заменив X
6
на 1.
Окончательно получим 1+Х+Х
2
+Х
4
, что соответствует числу
111010
Циклический код n-значного числа, как и всякий систематический код, состоит из m информационных и
к контрольных знаков, причем последние занимают к младших разрядов.
Поскольку последовательная передача кодовых комбинаций производится, как уже указывалось, начиная со старших разрядов, контрольные знаки передаются в конец кода.
Образование кода выполняется при помощи так называемого порождающего

полинома Р(х) степени к, видом которого определяются основные свойства кода -
избыточность и корректирующая способность.
Кодовым полиномом F(x) является полином степени, меньшей (т+к), если он
делится без остатка на порождающий полином Р(х). После передачи сообщения декодирование состоит в выполнении деления полинома Н(х), соответствующего принятому коду, на Р(х). При отсутствии ошибок Н(х) = F(x), и деление выполняется без остатка. Наличие ненулевого остатка указывает на то, что при передаче или хранении произошли искажения информации.
Для получения систематического циклического кода используется следующее соотношение где G(x) - полином, представляющий информационные символы
(информационный полином);
R(x) - остаток от деления X
k
G(x) на Р(х).
Правило деления полиномов:
деление полиномов производится по правилам
деления степенных
функций, при этом операция вычитания заменяется суммированием по mod2.
Еще раз напомним, что при сложении по mod2 сумма двух единиц (то есть двух элементов полинома с одинаковыми степенями) будет равна нулю, а не привычным в

десятичной системе счисления двум. И, кроме этого, операции вычитания и сложения по mod2 совпадают.
Пример 3.
Рассмотрим кодирование восьмизначного числа
10110111.
Пусть для кодирования задан порождающий полином третьей степени
Р(х) = 1+Х+Х
3
.
Делим X
3
G(x) на Р(х):
G(x) = 1+Х
2
+Х
3
+Х
5
+Х
б
+Х
7
;
X
3
G(x) =Х
3
+Х
5
+Х
6
+Х
8
+Х
9
+Х
10
Используя соотношение для получения систематического циклического кода, находим F(x):
F(x) = (Х
3
+Х
5
+Х
6
+Х
8
+Х
9
+Х
10
)ФХ
2
Таким образом, окончательно кодовая комбинация, соответствующая
F(x), имеет вид
00010110111
Контрольные разряды
001
00110110111
Практически применяемая процедура кодирования еще более проста. Так как нас интересует только остаток, а частное в конечном результате не используется, то можно производить последовательное вычитание по mod 2 делителя из делимого и полученных разностей до тех пор, пока разность не будет иметь более низкую степень, чем делитель. Эта разность и есть остаток. Такой алгоритм может быть реализован аппаратно при помощи к- разрядного сдвигающего регистра, имеющего обратные связи. Очевидно, что полученный этим способом циклический код будет являться систематическим.
Выполнить практическое задание:
1.
С использованием кода, задаваемого порождающим полиномом Р(х) =
1+х+х
3
, закодировать последовательность т = 0111.
2.
Построить кодовую комбинацию для числа
00011111 с помощью циклических кодов, если порождающий полином третьей степени Р(1,0) задан комбинацией:
А) 1011
Б)1101
Контрольные вопросы:
1.
Поясните понятие «циклический код»
2.
Дайте определение неприводимого многочлена
3.
Поясните алгоритм записи порождающего полинома в соответствии с таблицей 1 4.
Каким полиномом будут представлены числа 1101; 010101; 111001?
5.
Дайте определение кодового полинома
6.
Поясните алгоритм деления полиномов