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

UptoLike

ВУЗ: 

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

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

Рубрика: 

11
ности куба, соответствующего z
j ,
то импликанта
z
i
является “лишней", так
как существенные вершины, покрываемые ею, могут быть покрыты им-
пликантой z
j.
2. Если множество импликант, покрывающих существенную верши-
ну t
i
, является подмножеством импликант, покрывающих существенную
вершину t
j
, то вершина t
j
является “лишней", так как ее покрытие обеспе-
чивается любой из импликант, покрывающих оставшуюся в таблице вер-
шину t
i
.
После вычеркивания "лишних" импликант и вершин могут появиться
новые существенные импликанты. Упрощение таблицы продолжается до
тех пор, пока это возможно.
1.4. Минимизация булевых функций на картах Карно
Карты Карно являются одним из способов таблично-графического
представления булевых функций. Они используются для минимизации бу-
левых функций от небольшого числа
переменных (как правило, от трех до
шести). С использованием карт Карно достаточно просто выделяется ми-
нимальное покрытие функции, по которому составляется МДНФ (для еди-
ничного покрытия) или МКНФ (для нулевого). Для этой цели на карте вы-
деляются максимальные кубы, представляемые прямоугольниками из кле-
ток, отмеченных единицами или нулями. Две соседние клетки
карты обра-
зуют 1-куб, четыре - 2-куб, восемь - 3-куб и т.д.
Покрытие с минимальной ценой формируется, если каждая сущест-
венная вершина будет покрыта максимальным кубом наибольшей размер-
ности и для покрытия всех существенных вершин будет использовано
наименьшее число кубов.
1.5. Факторизация и декомпозиция булевых функций
Факторизация булевой функции состоит
в вынесении общих частей
из термов с целью уменьшения цены схемы. В некоторых случаях факто-
ризация может привести и к увеличению цены схемы.
Если булева функция имеет несколько минимальных форм, для наи-
более эффективного факторного преобразования необходимо выбрать та-
кую форму, у которой удастся вынести наибольшее число букв из наи-
большего
числа термов.
Задача декомпозиции булевой функции f(x) в простейшем случае, на-
зываемом разделительной декомпозицией, состоит в разбиении множества
аргументов Х на ряд подмножеств, в частном случае на два – V и W – таким
образом, чтобы V∪W = X и f(x) = f(
ϕ
(V), W), где
ϕ
(V) – вспомогательная
булева функция. В некоторых случаях применение декомпозиции позволя-
ет уменьшить цену схемы.

Страницы