Обзор методов логического проектирования и минимизации
Практическая работа №4
Дисциплина «Архитектура ЭВМ» специальности 230115
Составление комбинаций из логических элементов ЭВМ.
Постановка задачи.
1.Зарисовать схемы основных логических элементов компьютера и таблицы истинности
2.Составить комбинации элементов, таблицы истинности и начертить полученные схемы.
Цель работы. Закрепление навыков по составлению логических схем, закрепление знаний о простейших логических элементах компьютера.
Обзор методов логического проектирования и минимизации
Термин “логическое проектирование” охватывает целый комплекс проблем, возникающих на одной из ранних стадий создания цифрового автомата. Одним из этапов логического проектирования является синтез его так называемых комбинационных устройств, который заключается в определении таких способов соединения некоторых простейших схем, называемых логическими элементами, при которых построенное устройство реализует поставленную задачу по преобразованию входной двоичной информации. В частности логическими элементами являются инвертор, конъюнктор и дизъюнктор. Поскольку эти элементы образуют функционально полный набор, то с их помощью можно построить комбинационное устройство (то есть устройство не обладающее памятью, в котором выходной сигнал в любой момент времени определяется только комбинацией входных сигналов), реализующее любой наперёд заданный закон преобразования двоичной информации .
Обычно логическое проектирование выполняется в следующей последовательности:
1) составление таблицы истинности синтезируемого узла согласно его определению, назначению и (словесному) описанию принципа работы ;
2) составление математической формулы для логической функции, описывающей работу синтезирующего узла, согласно имеющейся таблице истинности ;
3) анализ полученной функции с целью построения различных вариантов её математического выражения (на основании законов булевой алгебры) и нахождения наилучшего из них в соответствии с тем или иным критерием ;
4) составление функциональной (логической) схемы узла из заранее заданного набора логических элементов .
1.1 Нормальные формы логических функций
Синтез комбинационных устройств обычно начинается с табулирования значений истинности всех входных и выходных величин. Табличное задание закона функционирования некоторого устройства является наиболее наглядным и универсальным средством описания его работы. Результатом рассматриваемого этапа является таблица истинности, связывающая все возможные комбинации значений аргументов и функций. Пусть, например, требуется синтезировать цифровое устройство, реализующее сложение двух двоичных цифр (полусумматор) .
1-й этап синтеза - даётся словесное описание полусумматора и принципа его работы. Он должен анализировать все комбинации входных сигналов (т. е. двоичных цифр 00, 01, 10, 11) и в соответствии с ними формировать на выходе двухразрядные суммы. В первом разряде результата формируется цифра переноса, а во втором - цифра многоразрядной суммы. Следовательно, синтезируемый полусумматор должен иметь два входа (n=2) и два выхода. Далее от нестрогого словесного описания переходим к строгому формальному описанию работы полусумматора на табличном языке. Таблица истинности (см. табл. 1.1) в общем случае при n входах имеет 2 в степени n комбинаций значений аргументов .
Таблица 1.1
Таблица истинности полусумматора.
| 1-я цифра слагаемое Х1 | ||||
| 2-я цифра слагаемое Х2 | ||||
| Цифра переноса р | ||||
| Цифра суммы s |
2-й этап синтеза - для того чтобы показать методику перехода от таблицы истинности к аналитическому выражению, рассмотрим некоторую обобщённую таблицу истинности двух аргументов f(X1,X2) (см. табл. 1.2). Ограничение на число аргументов не является в данном случае существенным, но значительно упрощает все рассуждения .
Таблица 1.2
Обобщённая таблица истинности функции двух аргументов.
| 1-й логический аргумент Х1 | ||||
| 2-й логический аргумент Х2 | ||||
| Логическая функция f(X1,X2) | f0 | f1 | f2 | f3 |
Здесь f0=f(0,0); f1=(0,1); f2=(1,0); f3=(1,1) - конкретные реализации функции f(X1,X2) при определённых частных значениях аргументов X1 и X2. Они также являются двоичными переменными. Десятичные индексы при их символах числено равны тем двоичным числам, которые образуются соответствующими частными значениями аргументов. Кроме того, каждый десятичный индекс можно трактовать как номер некоторого столбца в Таблице 1.2, изменяющийся в пределах от 0 до 2n -1, так как обычно значения аргументов в таблице записываются таким образом, чтобы получающееся из них по вертикали двоичное число было равно номеру столбца. Исходя из вышеизложенного, уже можно перейти от табличной записи логической функции f(X1,X2) к аналитической :
f(X1,X2) = f0 при, х1=0, х2=0 ;
f1 при, х1=0, х2=1 ; (1.1)
f2 при, х1=1, х2=0 ;
f3 при, х1=1, х2=1 ;
Такая запись несколько удобнее и компактнее таблицы, однако она всё-таки громоздка и плохо обозрима (особенно в случае большого числа аргументов). Но от неё можно перейти к записи другого вида, более удобной и компактной :
f(x1,x2)= x1x2f0+ x1x2f1+ x1x2f2+ x1x2f3 (1.2)
Правило построения каждого члена в этом предложении несложно; производится логическое умножение элементов каждого столбца табл.1.2, причём вместо 1 берётся символ соответствующего аргумента, а вместо 0 - его отрицание. Равносильность соотношений (1.1) и (1.2) простой подстановкой в выражение (1.2) всех возможных комбинаций значений аргумента xi .
Обобщив вышеизложенное можно сформулировать правило получения аналитической записи логической функции для некоторого комбинационного узла :
- для того чтобы получить аналитическое выражение функции, заданной таблично, нужно составить сумму конституент(см. ниже) единицы для тех наборов значений входных двоичных переменных, для которых реализации функции fi равны 1, причём символ любой переменной в некоторой конституенте берётся со знаком отрицания, если конкретное значение переменной xi в рассматриваемом наборе имеет значение 0 .
Поскольку логическая сумма всех элементарных произведений наивысшего ранга n обязательно равна 1, какой бы набор значений входных переменных ни рассматривался, то эти произведения вполне логично называть конституентами (составляющими) единицы. Аналогично объясняется и название конституенты (составляющей) нуля, так как известно, что логическое произведение всех элементарных сумм наивысшего ранга тождественно равно нулю .
Все функции, полученные в соответствии с вышеизложенным правилом получения аналитической записи логической функции для некоторого комбинационного узла, независимо от числа аргументов имеют много общего в своей структуре. Таким образом это правило определяет канонический вид любой логической функции. В этом случае говорят, что функция задана (записана) в совершенной дизъюнктивной нормальной форме (СДНФ). Нормальной эта форма называется потому, что члены функции в данном случае имеют вид элементарных конъюнкций. Вследствие того что все члены соединены в одну функцию знаком дизъюнкции, форма носит название дизъюнктивной. И, наконец, форма называется совершенной, так как все её члены имеют высший ранг, являясь конституентами единицы .
Поскольку алгебра логики симметрична, то вышеприведённые рассуждения можно применить для вывода ещё одной канонической формы логических функций - совокупности конституент нуля, соединённых знаком конъюнкции. Таким образом сформулируем второе правило :
- для того чтобы получить аналитическое выражение функции, заданной таблично, в совершенной конъюктивной нормальной форме, нужно составить логическое произведение конституент нуля для тех наборов значений, входных двоичных переменных, для которых реализация функции fi равна 0, причём символ любой переменной в некоторой конституенте берётся со знаком отрицания, если её конкретное значение xi в рассматриваемом наборе равно 1 .
В общем случае переход к совершенной нормальной форме производится за три шага .
1-й шаг - с помощью многократного применения законов инверсии снимаются общие и групповые отрицания так, чтобы отрицания оставались только у одиночных переменных .
2-й шаг - с помощью распределительных законов производится переход к одной из нормальных форм функции.
3-й шаг - производится преобразование членов ДНФ или КНФ в соответствующие конституенты с помощью правила развёртывания .
Пользуясь сформулированными правилами и таблицей 1.1 для полусумматора записываем :
p(x1,x2) = x1x2
s(x1,x2)= x1x2 +x1x2 СДНФ (1.3)
p(x1,x2) = (x1+ x2) (x1 +x2) (x1+x2)
s(x1,x2) = (x1+ x2) (x1 +x2) СКНФ (1.4)
3-й этап синтеза - анализ и оптимизация (минимизация) логических функций являются весьма важными компонентами синтеза цифровых автоматов без памяти. Поэтому методы анализа и оптимизации будут рассмотрены отдельно .
4-й этап синтеза - к построению функциональной схемы синтезируемого узла в принципе можно переходить сразу же, как только становится известным аналитическое описание его работы. Построение схемы основано на прямом замещении элементарных произведений, сумм и отрицаний соответственно конъюнкторами, дизъюнкторами и инверторами. Пользуясь соотношениями (1.3), (1.4) можем построить для полусумматора две функциональные схемы.
СДНФ.
СКНФ.
Рис. 1.1 Функциональная схема полусумматора .
С функциональной точки зрения обе схемы полностью тождественны, хотя по структурной сложности они значительно различаются.
Практическое задание.
1. Перечислите и зарисуйте условные обозначения и таблицы истинности простейших логических элементов: повторителей и инверторов. Указать их назначение.
2. Объяснить принцип работы элементов, реализующих конъюнкцию и дизъюнкцию. Составить таблицу истинности и пояснить принципы её формирования.
3. Составить самостоятельно таблицу двух функций и назвать главные элементы, которые могут работать согласно ей.
4. Составить и зарисовать схему двух параллельно соединённых конъюнкторов. Составить таблицу истинности получившегося элемента.
5. Составить и зарисовать схему двух параллельно соединённых дизъюнкторов. Составить таблицу истинности получившегося элемента.
6. Проделать то же самое для последовательных соединений.
7. Соединить параллельно конъюнктор и дизъюнктор. Зарисовать и составить таблицу истинности.
Форма отчета.
Заголовок: Практическая работа № .
Название.
Цель работы.
Оборудование (приборы и материалы).
Таблица. Схема.
Вычисления (построение алгоритмов для решения данной задачи), обработка результатов.
Вывод.