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

UptoLike

ВУЗ: 

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

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

Рубрика: 

9
МКНФ булевой функции представляет собой конъюнкцию простых им-
плицент соответствующих максимальным кубам минимального нулевого
покрытия этой функции.
Решение задачи минимизация булевых функций методом Квайна-
Мак-Класки состоит из определенной последовательности этапов.
1.3.2. Определение множества простых импликант
Все 0-кубы комплекса K
0
(f) сравниваются между собой попарно. Если
два 0-куба различаются только по одной координате (т.е. являются сосед-
ними), то они вступают в операцию склеивания и образуют один 1-куб (0-
кубы, образующие 1-кубы, отмечаются). После получения всех 1-кубов,
образующих комплекс K
1
(f), производится получение 2-кубов путем
склеивания соседних 1-кубов и т.д. При получении r-кубов, все (r-1)-кубы,
образующие r-кубы, отмечаются. Этап заканчивается получением ком-
плекса K
r
(f), когда ни один (r+1)-куб не может быть получен. Все неотме-
ченные кубы комплекса K(f) являются простыми импликантами и образу-
ют покрытие Z(f) функции f, которое, в частном случае, может быть мини-
мальным.
Очевидно, что 1-куб может быть образован двумя 0-кубами с числом
единичных координат, отличающимся на единицу. Поэтому для
сокраще-
ния числа попарных сравнений упорядочим 0-кубы, объединяя их в груп-
пы по числу единичных координат. Очевидно, что 1-куб может быть обра-
зован склеиванием 0-кубов, относящихся только к двум соседним груп-
пам. То же самое относится и к кубам большей размерности.
При минимизации не полностью определенной функции осуществля-
ется ее
доопределение единицей на всех безразличных (несущественных)
наборах, что позволяет получить кубы большей размерности. Поэтому
комплекс K
0
(f)
на данном этапе дополняется комплексом N(f) безразлич-
ных наборов.
1.3.3. Составление импликантной таблицы
Для отображения покрытия простыми импликантами существенных
вершин функции (0-кубов) составляется таблица, в которой каждая строка
соответствует простой импликанте, а каждый столбец - 0-кубу. На пересе-
чении i-й строки и j-го столбца ставится метка, если i-я
импликанта покры-
вает j-й 0-куб, т.е. отличается от него только независимыми координатами.
Для не полностью определенных функций в столбцы импликантной
таблицы включаются только существенные вершины и не включаются
безразличные наборы, т.е. на этом этапе булева функция доопределяется
нулем на безразличных наборах.

Страницы