Симметричные и асимметричные криптосистемы

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

Оставаясь в рамках симметричной системы, необходимо иметь надежный канал связи для передачи секретного ключа. Но такой канал не всегда бывает доступен, и потому американские математики Диффи, Хеллман и Меркле разработали в 1976 г. концепцию открытого ключа и асимметричного шифрования.

В таких криптосистемах общедоступным является только ключ для процесса шифрования, а процедура дешифрования известна лишь обладателю секретного ключа. Например, когда я хочу, чтобы мне выслали сообщение, то генерирую открытый и секретный ключи. Открытый посылаю вам, вы шифруете им сообщение и отправляете мне. Дешифровать сообщение могу только я, так как секретный ключ я никому не передавал. Конечно, оба ключа связаны особым образом (в каждой криптосистеме по-разному), и распространение открытого ключа не разрушает криптостойкость системы.

В асимметричных системах должно удовлетворяться следующее требование: нет такого алгоритма (или он пока неизвестен), который бы из криптотекста и открытого ключа выводил исходный текст.

Основные современные методы шифрования

Среди разнообразнейших способов шифровании можно выделить следующие основные методы:

• Алгоритмы замены или подстановки — символы исходного текста заменяются на символы другого (или того же) алфавита в соответствии с заранее определенной схемой, которая и будет ключом данного шифра. Отдельно этот метод в современных криптосистемах практически не используется из-за чрезвычайно низкой криптостойкости.

• Алгоритмы перестановки — символы оригинального текста меняются местами по определенному принципу, являющемуся секретным ключом. Алгоритм перестановки сам по себе обладает низкой криптостойкостью, но входит в качестве элемента в очень многие современные криптосистемы.

• Алгоритмы гаммирования — символы исходного текста складываются с символами некой случайной последовательности. Самым распространенным примером считается шифрование файлов «имя пользователя.рwl», в которых операционная система Microsoft Windows 95 хранит пароли к сетевым ресурсам данного пользователя (пароли на вход в NT-серверы, пароли для DialUр-доступа в Интернет и т.д.). Когда пользователь вводит свой пароль при входе в Windows 95, из него по алгоритму шифрования RC4 генерируется гамма (всегда одна и та же), применяемая для шифрования сетевых паролей. Простота подбора пароля обусловливается в данном случае тем, что Windows всегда предпочитает одну и ту же гамму.

• Алгоритмы, основанные на сложных математических преобразованиях исходного текста по некоторой формуле. Многие из них используют нерешенные математические задачи. Например, широко используемый в Интернете алгоритм шифрования RSA основан на свойствах простых чисел.

• Комбинированные методы. Последовательное шифрование исходного текста с помощью двух и более методов.

Алгоритмы шифрования

Рассмотрим подробнее методы криптографической защиты данных

1. Алгоритмы замены(подстановки)

2. Алгоритм перестановки

3. Алгоритм гаммирования

4. Алгоритмы, основанные на сложных математических преобразованиях

5. Комбинированные методы шифрования

Алгоритмы 1-4 в «чистом виде» использовались раньше, а в наши дни они заложены практически в любой, даже самой сложной программе шифрования. Каждый из рассмотренных методов реализует собственный способ криптографической защиты информации и имеет собственные достоинства и недостатки, но их общей важнейшей характеристикой является стойкость. Под этим понимается минимальный объем зашифрованного текста, статистическим анализом которого можно вскрыть исходный текст. Таким образом, по стойкости шифра можно определить предельно допустимый объем информации, зашифрованной при использовании одного ключа. При выборе криптографического алгоритма для использования в конкретной разработке его стойкость является одним из определяющих факторов.

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

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

Стойкость простой полиалфавитной подстановки (из подобных систем была рассмотрена подстановка по таблице Вижинера) оценивается значением 20n, где n — число различных алфавитов используемых для замены. При использовании таблицы Вижинера число различных алфавитов определяется числом букв в ключевом слове. Усложнение полиалфавитной подстановки существенно повышает ее стойкость.

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

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

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

Алгоритм DES был утвержден еще долее 20 лет назад, однако за это время компьютеры сделали немыслимый скачок в скорости вычислений, и сейчас не так уж трудно сломать этот алгоритм путем полного перебора всех возможных вариантов ключей (а в DES используется всего 8-байтный ),что недавно казалось совершенно невозможным.

ГОСТ 28147-89 был разработан еще спецслужбами Советского Союза, и он моложе DES всего на 10 лет; при разработке в него был заложен такой запас прочности, что данный ГОСТ является актуальным до сих пор.

Рассмотренные значения стойкости шифров являются потенциальными величинами. Они могут быть реализованы при строгом соблюдении правил использования криптографических средств защиты. Основными из этих првил являются: сохранение в тайне ключей, исключения дублирования(т.е. повторное шифрование одного и того же отрывка текста с использованием тех же ключей) и достаточно частая смена ключей.

Заключение по первому разделу:

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

Наиболее простой критерий такой эффективности - вероятность раскрытия ключа или мощность множества ключей (М). По сути это то же самое, что и криптостойкость. Для ее численной оценки можно использовать также и сложность раскрытия шифра путем перебора всех ключей. Однако, этот критерий не учитывает других важных требований к криптосистемам:

· невозможность раскрытия или осмысленной модификации информации на основе анализа ее структуры,

· совершенство используемых протоколов защиты,

· минимальный объем используемой ключевой информации,

· минимальная сложность реализации (в количестве машинных операций), ее стоимость,

· высокая оперативность.

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

Практическая часть:

Задание 1.

1.1.

1) Заполняем поле X выполнив

1.1 Задаем вручную первое значение

1.2 Выполняем Правка->Заполнить->Прогрессия (по столбцам, арифметическая, шаг, предельное значение) при х [-2;2]

2) Заполняем поле значений функции g =

Рисунок 1.1. – Формула функции g(x)

2.1) Просчитываем значения функций

3) Построение графиков

3.1) Выделяем ячейки с значениями Функций g

3.2) Выбираем мастер диаграмм

Далее

Рисунок 1.2 – Мастер диаграмм - График

Далее ->ряд

Рисунок 1.3 – Мастер диаграмм – подпись осей

Выделяем значение оси X

Нажимаем Ввод (enter)

3.3) Даем имена графикам

3.4) Выделяем ячейку с формулой графика

Нажимаем ввод (enter) , потом тоже самое проделываем со вторым рядом

3.5) нажимаем далее -> Заголовки (Задаем названия диаграммы, названия осей)

3.6) Выбираем закладку ->Линии сетки, выставляем

X промежуточные линии, Y Основные линии ->Далее

3.7) Помещаем график функции на имеющемся листе -> (Готово)

4) В итоге получаем (Рис.1.4)

Рисунок 1.4 – График функции g(x)

1.2.

1) Определяем в полях таблицы функции будущих графиков

Рисунок 1.5 – Подпись функций будущих графиков

2) Заполняем поле X выполнив:

2.1 Задаем вручную первое значение

2.2 Выполняем Правка->Заполнить->Прогрессия (по столбцам, арифметическая, шаг, предельное значение) при х [-2;2]

3) Просчитываем значения функций y=2sin( x) – 3cos( x), z = cos²(2 x) – 2sin( x).

Рисунок 1.6 – Формулы функций y(x) и z(x)

4) Построение графиков

4.1Выделяем ячейки с значениями Функций y и z

Выбираем мастер диаграмм

Далее

Рисунок1.7 - Мастер диаграмм - График

Далее ->ряд

Выделяем значение оси X

Нажимаем Ввод (enter)

4.2) Даем имена графикам

4.3) Выделяем ячейку с формулой графика

Нажимаем ввод (enter) , потом тоже самое проделываем со вторым рядом

4.4) нажимаем далее -> Заголовки (Задаем названия диаграммы, названия осей)

4.5) Выбираем закладку ->Линии сетки, выставляем

X промежуточные линии, Y Основные линии ->Далее

4.6) Помещаем график функции на имеющемся листе -> (Готово)

5) В итоге получаем (Рис.1.8)

Рисунок 1.8 – Графики функций y(x) и z(x)

Задание 2.

· Создание списка «Отдела кадров»

Рисунок 2.1 Список «Отдела кадров»

· Сортировка

Рисунок 2.2 – Сортировка по полю Имя

В итоге получаем (Рис.2.3)

Рисунок 2.3 – Отсортированная таблица «Отдел кадров»

· Поиск информации с помощью автофильтра (получить информацию о мужчинах, имя которых начинается на букву Буква, отчество – «Иванович», с окладом Оклад);

Рисунок 2.4 - Автофильтр

· Поиск информации с помощью расширенного фильтра (найти информацию из отдела Отдел1 в возрасте Возраст1 и Возраст2, и о женщинах из отдела Отдел2 в возрасте Возраст3);

1) Вводим критерии для расширенного фильтра 1

В итоге получаем (Рис.2.5)

Рисунок 2.5 – Расширенный фильтр 1

2) Вводим критерии для расширенного фильтра 2.

В итоге получаем(Рис.2.6)

Рисунок 2.6 – Расширенный фильтр 2

· Подведение итогов (определить количество и средний возраст сотрудников в каждом отделе);

Рисунок 2.7 - Итоги

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

Функция ДМИН- Возвращает наименьшее число в поле (столбце) записей списка или базы данных, которое удовлетворяет заданным условиям.

Рисунок 2.8 – Анализ списка с помощью функции ДМИН

Задание 3.

Создаём две связанные таблицы Сессия(рис.3.2) и Студенты(рис.3.4)

Рисунок 3.1- Конструктор таблицы Сессия

Рисунок 3.2- Таблица Сессия

Рисунок 3.3 – Конструктор таблицы Студенты

Рисунок 3.4 – Таблица Студенты

1) Используя таблицу Студенты, создать три запроса, по которым из базы данных будут поочередно отобраны фамилии и имена студентов групп 1-Э-1, 1-Э-2, 1-Э-3.

Рисунок 3.5– Конструктор Запроса 1.1

Рисунок 3.6 – Запрос 1.1

Рисунок 3.7– Конструктор Запроса1.2

Рисунок 3.8- Запрос 1.2

Рисунок 3.9– Конструктор Запроса 1.3

Рисунок 3.10 – Запрос 1.3

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

Рисунок 3.11– Конструктор Запроса 2.1

Рисунок 3.12 – Запрос 2.1

Рисунок 3.13 – Конструктор Запроса 2.2

Рисунок 3.14 – Запрос 2.2

3)Использую таблицу Студенты, создать два запроса, по которым из базы данных будут поочередно отобраны фамилии и имена женщин группы 1-Э-2, а затем-мужчин группы 1-Э-1.

Рисунок 3.15– Конструктор Запроса 3.1

Рисунок 3.16 – Запрос 3.1

Рисунок 3.17– Конструктор – 3.2

Рисунок 3.18 – Запрос 3.2

4) Используя связанные таблицы Студенты и Сессия,создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток и оценки по математике студентов группы 1-Э-2.

Рисунок 3.19– Конструктор Запроса 5

Рисунок 3.20 – Запрос 5

5) Используя связанные таблицы Студенты и Сессия,создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток и оценки по философии студентов (мужчин) группы 1-Э-2.

Рисунок 3.21– Конструктор Запроса 8

Рисунок 3.22 – Запрос 8

6) Используя связанные таблицы Студенты и Сессия,создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток студентов, получивших оценку «удовлетворительно» (3) по философии.

Рисунок 3.23– Конструктор Запроса 10

Рисунок 3.24 – Запрос 10

7) Используя связанные таблицы Студенты и Сессия,создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток студентов, получивших оценку «хорошо» (4) одновременно по двум предмета: философии и математике.

Рисунок 3.25– Конструктор Запроса 14

Рисунок 3.26 – Запрос 14

8) Используя связанные таблицы Студенты и Сессия,создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток студентов, получивших оценку «неудовлетворительно» (2) по одному из двух предметов: по математике или информатике.

Рисунок 3.27– Конструктор Запроса 18

Рисунок 3.28 – Запрос 18

9) Используя связанные таблицы Студенты и Сессия,создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток студентов, получивших оценку «хорошо» (4) по всем предметам.

Рисунок 3.29– Конструктор Запроса 22

Рисунок 3.30 – Запрос 22

10) Используя таблицу Сессия, создать запрос с именем Средний балл для расчёта среднего балла каждого студента по результатам сдачи четырёх экзаменов. Запрос обязательно должен содержать поле Зачётка, которое впоследствии будет использовано для связывания нескольких таблиц.

Рисунок 3.31 – Конструктор таблицы Сессия

Рисунок 3.32- Запрос Средний балл

11) Используя связанные таблицы Студенты, Сессия и запрос Средний балл, создать запрос, по которому из базы данных будут отобраны фамилии, имена, номера зачёток, номера групп студентов, имеющих средний балл 3,25.

Рисунок 3.33 – Конструктор Запроса 25

Рисунок 3.34 – Запрос 25

12) Используя связанные таблицы Студенты, Сессия и запрос Средний балл, создать запрос, по которому из базы данных будут отобраны оценка по математике, средний балл и номер группы студента Иванова.

Рисунок 3.35– Конструктор Запроса 29

Рисунок 3.36 – Запрос 29

13) Используя связанные таблицы Студенты, Сессия и запрос Средний балл, создать запрос, по которому из базы данных будут отобраны фамилии, имена студентов имеющих средний балл менее 3,75.

Рисунок 3.37– Конструктор Запроса 33

Рисунок 3.38 – Запрос 33

14) Используя таблицу Студенты, определить фамилию, имя и номер зачетки студентки, если известно, что её отчество Викторовна.

Рисунок 3.39– Конструктор Запроса 35

Рисунок 3.40 – Запрос 35

Задание 4.

Для перевода числа из десятичной системы счисления в систему счисления с другим основанием поступают следующим образом:

а) Для перевода целой части числа его делят нацело на основание системы, фиксируя остаток. Если неполное частное не равно нулю продолжают делить его нацело. Если равно нулю остатки записываются в обратном порядке.

б) Для перевода дробной части числа ее умножают на основание системы счисления, фиксируя при этом целые части полученных произведений. Целые части в дальнейшем умножении не участвуют. Умножение производиться до получения 0 в дробной части произведения или до заданной точности вычисления.

в) Ответ записывают в виде сложения переведенной целой и переведенной дробной части числа.

49812,22₁₀ = 1100001010010100,001₂ 49812,22₁₀ = 141224,160₈

0,

0,

49812,22₁₀ = С294, 385₁₆

0,

Задание 5.

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

А) 10101001,11001₂ = 1*2^7+1*2^5+1*2^3+1*2^0+1*2^(-1)+1*2^(-2)+1*2(-5)= 169,78125₁₀

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

Таблица 5.1 – Перевод чисел

Десятичная система счисления	Двоичная система счисления	Восьмеричная система счисления	Шестнадцатеричная система счисления
Триады (0-7)	Тетрады (0-15)
				A
				B
				C
				D
				E
				F

Б) 674,7₈ = 110111100,111₂=1*2^2+1*2^3+1*2^4+1*2^5+1*2^7+1*2^8+ +1*2^(-1) +1*2^(-2) +1*2^(-3)= 443,875₁₀

6 7 4 . 7

110 111 100. 111₂

В) EDF,51₁₆ = 111011011111,01010001₂= 1*2^0+1*2^1+1*2^2+1*2^3+ +1*2^4+1*2^6+ +1*2^7+1*2^9+ +1*2^10+1*2^11+1*2^(-2) 1*2^(-4) 1*2^(-8)= 3807,31640625₁₀

E D F . 5 1

1110 1101 1111 . 0101 0001₂

Задание 6.

В основе сложения чисел в двоичной системе лежит таблица сложения одноразрядных двоичных чисел.

0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10
Сложение многоразрядных двоичных чисел осуществляется в соответствии с этой таблицей с учетом возможных переносов из младшего разряда в старшие. В восьмеричной системе счисления, как и в любой другой позиционной, действуют собственные правила сложения чисел, представляющиеся правилами сложения цифр с равными порядками, относящихся к двум складываемым числам. Эти правила видны из табл.6.1. Появляющийся при сложении некоторых цифр данного разряда перенос, показан символом '↶'.   Таблица 6.1 - Сложение в 8–ой системе счисления
+
								↶0
							↶0	↶1
						↶0	↶1	↶2
					↶0	↶1	↶2	↶3
				↶0	↶1	↶2	↶3	↶4
			↶0	↶1	↶2	↶3	↶4	↶5
		↶0	↶1	↶2	↶3	↶4	↶5	↶6

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

+ 6 8 5 , 3 2 2 A ₁₆ + 1 0 1 0 1 0 0 1 0 , 1 0 ₂ + 4 7 7 , 6₈

D A 4 8 5 , 4 4 6 0 ₁₆ 1 1 0 0 0 0 1 1 0 , 1 1 0 1 0₂6 5 1 , 5 6₈

D A B 0 A , 7 6 8 A₁₆ 1 0 1 1 0 1 1 0 0 1 , 0 1 0 1 0₂ 1 3 5 1 ,3 6₈

Таблица 6.2 - Сложение в 16-ой системе счисления

+

A

B

C

D

E

F

A

B

C

D

E

F

A

B

C

D

E

F

↶0

A

B

C

D

E

F

↶0

↶1

A

B

C

D

E

F

↶0

↶1

↶2

A

B

C

D

E

F

↶0

↶1

↶2

↶3

A

B

C

D

E

F

↶0

↶1

↶2

↶3

↶4

A

B

C

D

E

F

↶0

↶1

↶2

↶3

↶4

↶5

A

B

C

D

E

F

↶0

↶1

↶2

↶3

↶4

↶5

↶6

A

B

C

D

E

F

↶0

↶1

↶2

↶3

↶4

↶5

↶6

↶7

A

B

C

D

E

F

↶0

↶1

↶2

↶3

↶4

↶5

↶6

↶7

↶8

A

A

B

C

D

E

F

↶0

↶1

↶2

↶3

↶4

↶5

↶6

↶7

↶8

↶9

B

B

C

D

E

F

↶0

↶1

↶2

↶3

↶4

↶5

↶6

↶7

↶8

↶9

↶A

C

C

D

E

F

↶0

↶1

↶2

↶3

↶4

↶5

↶6

↶7

↶8

↶9

↶A

↶B

D

D

E

F

↶0

↶1

↶2

↶3

↶4

↶5

↶6

↶7

↶8

↶9

↶A

↶B

↶C

E

E

F

↶0

↶1

↶2

↶3

↶4

↶5

↶6

↶7

↶8

↶9

↶A

↶B

↶C

↶D

F

F

↶0

↶1

↶2

↶3

↶4

↶5

↶6

↶7

↶8

↶9

↶A

↶B

↶C

↶D

↶E

Задание 7.

Используя таблицу сложения восьмеричных чисел, можно выполнять их вычитание. Пусть требуется вычислить разность двух восьмеричных чисел. Найдём в первом столбце табл. 6.1 цифру, соответствующую последней в вычитаемом, и в её строке отыщем последнюю цифру уменьшаемого — она расположена на пересечении строки вычитаемого и столбца разности. Так мы найдём последнюю цифру разности. Аналогично ищется каждая цифра разности.

а) _ 2 5 1 5 1 4 , 4 0₈

5 4 2 5 , 5 5₈

2 4 3 0 6 6 , 6 3₈

б) _1 0 1 1 0 1 1 0 0 0 , 1 0 0 0 0₂

1 0 1 0 0 1 0 0 1 , 1 0 0 1 1₂

1 0 1 1 0 0 1 0 0 1 1 , 0 0 0 0 1₂

в) _E 3 1 6 , 2 5 0₁₆

5 8 8 1 , F D C₁₆

8 А 9 4 , 2 7 4

Задание 8.

В основе умножения чисел в двоичной системе лежит таблица умножения одноразрядных двоичных чисел.

0 · 0 = 0
0 · 1 = 0
1 · 0 = 0
1 · 1 = 1

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

Собственная таблица умножения, как у нас уже была возможность убедиться, имеется в каждой позиционной системе счисления. В двоичной она самая маленькая , в восьмеричной (табл.8.1) и десятичной уже более обширная. Среди часто используемых систем счисления из рассмотренных нами самой крупной таблицей умножения располагает шестнадцатеричная (табл. 8.2).

Таблица 8.1. – Умножение в 8-ой системе

×

а) 1 0 1 0 0 1₂

* 1 1 1 0 1 1₂

1 0 1 0 0 1

1 0 1 0 0 1

1 0 1 0 0 1

1 0 1 0 0 1

1 0 1 0 0 1 .

1 0 0 1 0 1 1 1 0 0 1 1₂

б) 1 0 1 1 1 0 0₂

* 1 1 0 1 1₂

1 0 1 1 1 0 0

1 0 1 1 1 0 0

1 0 1 1 1 0 0

1 0 1 1 1 0 0 .

1 0 0 1 1 0 1 1 0 1 0 0₂

в) B C D , 5₁₆

* D5A₁₆

9 D 9 3 3 E 2₁₆

Таблица 8.2 – Умножение в 16-ой системе

×

A

B

C

D

E

F

A

B

C

D

E

F

A

C

E

1A

1C

1E

C

F

1B

1E

2A

2D

C

1C

2C

3C

A

F

1E

2D

3C

4B

C

1E

2A

3C

4E

5A

E

1C

2A

3F

4D

5B

1B

2D

3F

5A

6C

7E

A

A

1E

3C

5A

6E

8C

B

B

2C

4D

6E

8F

9A

A5

C

C

3C

6C

9C

A8

B4

D

D

1A

4E

5B

8F

9C

A9

B6

C3

E

E

1C

2A

7E

8C

9A

A8

B6

C4

D2

F

F

1E

2D

3C

4B

5A

A5

B4

C3

D2

E1

Задание 9.

Прямой код — способ представления двоичных чисел с фиксированной запятой в компьютерной арифметике. При записи числа в прямом коде старший разряд является знаковым разрядом. Если его значение равно 0 — то число положительное, если 1 — то отрицательное.

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

Дополнительный код (англ. two’s complement, иногда twos-complement) — наиболее распространённый способ представления отрицательных целых чисел в компьютерах. Он позволяет заменить операцию вычитания на операцию сложения и сделать операции сложения и вычитания одинаковыми для знаковых и беззнаковых чисел, чем упрощает архитектуру ЭВМ. При записи числа для положительного числа совпадает с прямым кодом, а для отрицательного числа дополнительный код обуславливается получением обратного кода и добавлением 1.

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

Если результат арифметических действий является кодом отрицательного числа необходимо преобразовать в прямой код. Обратный код преобразовать в прямой заменой цифр во всех разрядах кроме знакового на противоположных. Дополнительный код преобразовывается в прямой прибавлением 1.

A)X =10111

Y= -11110

Прямой код:

X=0,0010111 1,0011110

Y=1,0011110 0,0010111

1,0000111

Обратный код:

X=0,0010111 0,0010111

Y=1,1100001 1,1100001

1,1111000 1,0000111

Дополнительный код:

X=0,0010111 0,0010111

Y=1,1100010 1,1100010

1, 1111001 1,0000110

1

1,0000111

Б)X=110110

Y=101110

Прямой код:

X=0,110110

Y=0,101110

Обратный код:

X=0,110110 0,0110110

Y=0,101110 0,0101110

0,1100100

Дополнительный код:

X=0,110110 0,0110110

Y=0,101110 0,0101110

0,1100100

Задание 10.

Логические элементы

1. Логический элемент НЕ выполняет логическое отрицание. Он имеет один вход и один выход. Отсутствие сигнала (напряжения) обозначим через «0», а наличие сигнала через «1». Сигнал на выходе всегда противоположен входному сигналу. Это видно из таблицы истинности, которая показывает зависимость выходного сигнала от входного.

Условное обозначение Таблица истинности

X Y

2. Логический элемент ИЛИ выполняет логическое сложение. Он имеет несколько входов и один выход. Сигнал на выходе будет, если есть сигнал хотя бы на одном входе.

Условное обозначение Таблица истинности

X

Z

Y

3. Логический элемент И выполняет логическое умножение. Сигнал на выходе этого логического элемента будет только в том случае, если есть сигнал на всех входах.

Условное обозначение Таблица истинности

X

Z

Y

F=(A v B ) ʌ (C v D)

Таблица 10.1 – Таблица истинности

A	B	C	D	A	B	C	D	(A v B )	(C vD)	F=(A v B ) ʌ (C v D)

A

B

F

C

D

Задание 11.

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

1. Закон двойного отрицания: (А) = А

Двойное отрицание исключает отрицание.

2. Переместительный (коммутативный) закон:

— для логического сложения: A V B = B V A

— для логического умножения: A&B = B&A

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

3. Сочетательный (ассоциативный) закон:

— для логического сложения: (A v B) v C = A v (Bv C);

— для логического умножения: (A&B)&C = A&(B&C).

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

4. Распределительный (дистрибутивный) закон:

— для логического сложения: (A v B)&C = (A&C)v(B&C);

— для логического умножения: (A&B) v C = (A v C)&(B v C).

Определяет правило выноса общего высказывания за скобку.

5. Закон общей инверсии (законы де Моргана):

— для логического сложения: (Av B) = A & B;

— для логического умножения: (A& B) = A v B;

6. Закон идемпотентности

— для логического сложения: A v A = A;

— для логического умножения: A&A = A.

Закон означает отсутствие показателей степени.

7. Законы исключения констант:

— для логического сложения: A v 1 = 1, A v 0 = A;

— для логического умножения: A&1 = A, A&0 = 0.

8. Закон противоречия: A& A = 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

9. Закон исключения третьего: A v A = 1.

10. Закон поглощения:

— для логического сложения: A v (A&B) = A;

— для логического умножения: A&(A v B) = A.

11. Закон исключения (склеивания):

— для логического сложения: (A&B) v (A &B) = B;

— для логического умножения: (A v B)&( A v B) = B.

12. Закон контрапозиции (правило перевертывания):

(A v B) = (Bv A).

(А→В) = А&В

А&(АvВ)= А&В

Аv А&В=АvВ

Формула имеет нормальную форму, если в ней отсутствуют знаки эквивалентности, импликации, двойного от­рицания, при этом знаки отрицания находятся только при переменных.

F= B ʌ ((B A) ʌ ((BʌA) (BʌA))) = B ʌ ((BvA) ʌ ((BʌA) v (BʌA))) = B ʌ ((B v A) ʌ (B v A v B ʌ A)= B ʌ (((B v A) ʌ B) v ((B v A) ʌ A) v ((B v A) ʌ (B v A)))= B ʌ (⌐B v (A ʌ ⌐B) v(⌐A ʌ ⌐B) v(A ʌ ⌐A)v(⌐BʌA))= B ʌ (⌐B v(A ʌ ⌐B) v(⌐A ʌ ⌐B)) = B ʌ(⌐B v ⌐B ʌ (A v⌐A))= B ʌ⌐B = 0

Таблица 11.1 – Таблица истинности