Маска
Битовые строки
Роль математики и логики в создании КС.
Для формального описания работы цифровых схем применяют аппарат алгебры логики, где используют понятия логическая переменная, логическая функция. Переменная принимает только 2 значения(0 или 1). Логическая функция включает несколько логических переменных, связанных математическими знаками операции алгебры логики. Существуют различные способы представления логических функций(аналитические, табличные). Используют функции конъюнкции, дизъюнкции, отрицание, импликации, эквиваленции.
Таблица истинности – это функциональная взаимозависимость значений выходной величины Yi логического устройства, с каждой из взаимных итых операций входных переменных, представленных в табличной форме.
Простейшие преобразователи
Наименование формы | Вид логической операции | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Дизъюнкция | конъюнкция | инверсия | Ф. Шеффера | Ф. Пирса | |||||||||||||||||||||||||||||||||||||||||||||||||||||
Символическая | V,+ | ^,* | x | | | ↓ | ||||||||||||||||||||||||||||||||||||||||||||||||||||
Буквенная | или | и | не | И-не | Или-не | ||||||||||||||||||||||||||||||||||||||||||||||||||||
Условная(УГО) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Аналитическая | Yд=x1vx2 | Yк=X1^x2 | Yи= | Yш=X1|x2 | Yп=X1x2 | ||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблица истинности |
Для каждой системы кодирования характерно свое деление ячейки на поля(части и интерпретация этих полей. Например, при записи чисел с ПТ, ячейка делится на 3 поля: поле знака, поле порядка, поле мантиссы.
Понятие битовых строк распространяется на наборы, в которых отдельные последовательности битов объединены в группы, т.е. вводит любое нестандартное для данной компьютерной системы деление ячейки на поля.
Операции с битовыми строками
Самая простая машинная операция – пересылка, суть которой копирование одной ячейки памяти в другую. Операции с битовыми строками относятся к числу простых.
Логические сдвиги – ячейка из n битов содержит битовую строку А в виде аn-1an-2…а0
Операция «сдвиг влево логический» превращает строку А в новую строку А’-> аn-2an-3…а00
При этом бит крайний левой выходит за пределы ячейки и теряется. К краткое применение операции приведет к сдвигу исходной строки на К позиций, при К=n битовая строка превратится в нулевую.
Операция «сдвиг вправо логический» выполняется аналогично и переводит битовую строку в А’’->0an-1an-2…a1
SLL A, K- сдвиг строки А влево на К позиций
SPL A, K – сдвиг строки а вправо на К позиций
SLC A, K – сдвиг влево циклический
аn-2an-3…а0аn-1
Часто, при шифровании информации используют шаблон – маску, таким образом, прочитать информацию можно только с помощью этого шаблона. В КС в качестве маски может быть использована любая битовая строка. Единицы играют роль прорезей в шаблоне.
А7 А6 А5 А4 А3 А2 А1 А0 – битовая строка
0 0 0 1 0 0 1 0 - маска
0 0 0 А4 0 0 A1 0 – результат
Данная операция эквивалентна логическому умножению байта на маску и называется прочитать по маске. Есть операция «собрать по маске». Она заключается в том, что нужно прочитать по маске и сдвинуть результат в левый край байта. Остальные биты заполняются нулями.
Пример:
11011000 – исходная строка
00101000 – маска
00001000 – прочитать по маске
01000000 – собрали по маске(разобрать по маске – вернуться на 1 шаг назад)
Нормальные формы – эти формы представляют дизъюнкции элементарных конъюнкций или конъюнкции элементарных дизъюнкций.
)
Любая функция имеет несколько ДНФ или КНФ. Однозначность представления функции возможна только при записи ее в совершенных нормальных функциях.
СДНФ – это логическая сумма всех переменных, для которых функция равна 1.
СКНФ – то логическое произведение всех переменных, для которых функция равна 0.
Х1 | Х2 | Х3 | F(x1, x2, x3) | Хсднф и Хскнф |
Минимализация функции алгебры логики (ФАЛ)
Логическую схему, реализующую заданный алгоритм, можно синтезировать по выражению СДНФ или СКНФ. Однако, полученная схема не оптимальна с точки зрения реализации. Исходное выражение минимализируют, цель – снижение стоимости реализации. Основной критерий – уменьшение количества элементарных элементов при разработке схемы, а также использование только однородных элементов типа и-не, или-не.
Минимализация – упрощение логического выражения с целью уменьшения числа членов и уменьшение числа аргументов в каждом члене. Выполнение процесса минимализации позволяет уменьшить число логических элементов на одном кристалле.
Минимализация возможна двумя основными путями:
1) алгебраическая минимализация логических функций состоит в использовании аксиом, законов и тождеств алгебры логики.
Аксиомы: 1+А=А, А + А=А, 0*А=0, А*А=0
Основные законы: А) дистрибутивные А(В+С)=АВ+АС
Б) Двойственности (Де Моргана) А+В=А*В, А*В=А+В
В) Соотношения: 1. поглощения А+А*В=А, А(А+В)=А
2. склеивания А*В+А*В=А, (А+В)(А+В)=А
2) Метод минимизации графический
Процедуру минимизации ФАЛ можно формализировать, если воспользоваться представлением в виде карт макстермов и минтермов. Распространение получили карты Карно или Вейче.
Карта – это таблица, число клеток которой соответствует числу переменных функции 2n. Каждому минтерму соответствует своя клетка, если нужно представить на карте логическую функцию, заданную в СДНФ, то в соответствующей клетке заносится 1, остальные заполняют 0.
Функция 2х переменных
Функция 3х переменных
Понятие «Базис»
При составлении схем из логических элементов, решаются задачи анализа и синтеза. Задача синтеза – выбор типов элементов, на которых будут реализованы заданные функции. Минимальный набор логических элементов, образующих функционально полную систему элементов, называют базис, т.е. с помощью элементов базиса можно реализовать сколь угодно сложную логическую функцию.
1. Основной базис (базис Буль)
Элементы И, ИЛИ, НЕ
2. Базис Шеффера
Элемент И-НЕ
3. Базис Пирса
Элементы ИЛИ-НЕ
1)y=A*B+A*B