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

UptoLike

ВУЗ: 

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

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

Рубрика: 

10
1.3.4. Выделение множества существенных импликант
Если в каком – либо столбце импликантной таблицы имеется только
одна метка, то импликанта с этой меткой является существенной и обяза-
тельно входит в минимальное покрытие, поскольку, не используя ее, не-
возможно покрыть все существенные вершины функции. В связи с этим в
минимальное покрытие включаются все
существенные импликанты, а из
импликантной таблицы удаляются строки, соответствующие этим импли-
кантам, и столбцы, соответствующие 0-кубам, покрываемым ими. Множе-
ство всех существенных импликант образует ядро покрытия T(f).
Если после удаления строк и столбцов в упрощенной импликантной
таблице появляются строки, не содержащие ни одной метки, то эти строки
также удаляются.
1.3.5.
Определение минимального покрытия
В упрощенной импликантной таблице выделяется подмножество
простых импликант, которое обеспечивает покрытие оставшихся сущест-
венных вершин с минимальной ценой.
Можно использовать следующие способы решения этой задачи:
1. Метод полного перебора;
2. Формализованный алгебраический метод (метод Петрика);
3. Дальнейшее упрощение импликантной таблицы.
Метод полного перебора достаточно трудоемок и заключается
в вы-
делении всех вариантов покрытий непосредственно по импликантной таб-
лице и выборе из них минимального.
Метод Петрика основан на составлении булева выражения, опреде-
ляющего условие покрытия всех существенных вершин булевой функции
из упрощенной импликантной таблицы. Булево выражение представляет
собой конъюнкцию
дизъюнктивных термов, каждый из которых включает
в себя совокупность всех простых импликант, покрывающих одну суще-
ственную вершину функции. Полученное выражение преобразуется в
дизъюнктивную форму и минимизируется с использованием законов по-
глощения и тавтологии. Каждый конъюктивный терм дизъюнктивной
формы соответствует одному из вариантов покрытия, из которых выбира-
ется минимальное.
Дальнейшее упрощение импликантной
таблицы базируется на приме-
нении двух операций: удаление “лишних” строк (простых импликант) и
удаление “лишних” столбцов (существенных вершин). При этом исполь-
зуются следующие правила:
1. Если множество существенных вершин, покрываемых импликан-
той z
i
, является подмножеством существенных вершин, покрываемых им-
пликантой z
j
и размерность куба, соответствующего z
i
, не больше размер-

Страницы