Синтез комбинационных схем. Довгий П.С - 7 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

7
Для получения КДНФ в таблице истинности выделяются наборы ар-
гументов, на которых функция принимает значение, равное единице. Для
каждого из них составляются конституенты единицы. При этом перемен-
ная, принимающая значение, равное единице, входит в конституенту в
прямом виде, а переменная, принимающая нулевое значение - в инверс-
ном. Конституенты единицы объединяются знаками
дизъюнкции, образуя
КДНФ.
Для получения ККНФ выделяются наборы аргументов, на которых
функция принимает значение, равное нулю. Для каждого из них составля-
ются конституенты нуля При этом переменная, принимающая значение,
равное единице, входит в конституенту в инверсном виде, а переменная,
принимающая нулевое значение – в прямом. Конституенты нуля объеди-
няются знаками конъюнкции, образуя
ККНФ.
1.3. Минимизация булевых функций методом Квайна–Мак-
Класки
1.3.1. Основные положения
При проектировании комбинационной схемы возникает задача мини-
мизации оборудования, используемого в схеме. Простейшей оценкой за-
трат оборудования на построение схемы, реализующей заданную функ-
цию, является цена схемы по Квайну S
Q
,
которая
представляет собой сум-
марное количество входов во все логические элементы схемы. Задача ми-
нимизации цены схемы связана с задачей минимизации булевой функции,
описывающей закон функционирования этой схемы.
Обычно задача минимизации булевых функций решается с примене-
нием нормальных форм (ДНФ или КНФ). Нормальная форма булевой
функции, содержащая минимальное количество букв, называется мини
-
мальной нормальной формой (МДНФ или МКНФ). Нахождение мини-
мальных форм булевой функции методом Квайна-Мак-Класки базируется
на ее кубическом представлении [2-4]. При этом куб минимальной размер-
ности (0-куб) отождествляется с набором аргументов булевой функции, на
котором он принимает значение, равное единице. Над кубами одинаковой
размерности определена операция склеивания, соответствующая правилу
склеивания конъюнктивных термов. Склеивание двух k-кубов (размер-
ность k куба определяется числом независимых координат, отмечаемых в
записи куба символом Х) в результате дает один (k+1)-куб. Проводя все-
возможные операции склеивания между кубами можно получить множест-
во кубов различных размерностей, образующих кубический комплекс K(f)
заданной функции f(x). С использованием
кубического представления бу-
левой функции решение задачи минимизации сводится к получению так
называемого минимального покрытия, т.е. покрытия, обладающего мини-

Страницы