Читайте также:
|
Под задачей минимизации ЛФ понимается задача упрощения этих функций в целях уменьшения затрат на их аппаратурную реализацию. Минимальной будет считаться такая разновидность функции, которая состоит из наименьшего количества дизъюнктивных членов при наименьшем суммарном числе символов переменных. В основе методов минимизации ЛФ летит операция склеивания, а в качестве исходной формы ЛФ, как правило, выбирают СДНФ.
Введем некоторые определения.
Смежными или соседними называют минтермы, которые отличаются друг от друга формой вхождения только одной переменной.
Например, соседними являются минтермы Х1·Х2·Х3 и Х1·Х2·Х3, которые 
отличаются только формой вхождения Х3.
Минтермы Х1·Х2·Х3 и Х1·Х2·Х3 - не являются соседними.
Два соседних минтерма могут быть склеены. В результате получаем импликанту т.е. конъюкцию, число аргументов в которой на один меньше, чем в исходном минтерме.
При этом импликанта принимает значение 1 на тех же наборах переменных, что и исходная функция.
__ __ __ __ __ __
Х1·Х2·Х3 Ú Х1·Х2·Х3 = Х1·Х2·(Х3·Х3) = Х1·Х2; (Х3·Х3 = 1),
__
импликанта Х1·Х2 не зависит от Х3.
Процесс склеивания может быть продолжен и для импликант, если они смежные:__ __ __ __ __ __ __ __
(Х1·Х2·Х3·Х4 Ú Х1·Х2·Х3·Х4) Ú (Х1·Х2·Х3·Х4 Ú Х1·Х2·Х3·Х4) =
__ __ __
I - й этап: = Х1·Х2·Х4 Ú Х1·Х2·Х4 = (склеивание по Х3)
__
II - й этап: = Х1·Х2; (склеивание по Х4).
Итак, при склеивании двух соседних минтермов от n переменных получаем импликанту, которая зависит от (n-1) переменных, при склеивании четырех минтермов - от (n-2) переменных, восьми минтермов - от (n-3) переменных и, в общем случае, при склеивании (2 в степени m) соседних минтермов получаем импликанту от (n-m) переменных. Процесс многоступенчатого склеивания приводит к получению импликант, которые не склеиваются с другими. Такие импликанты называются простыми. Вместе с исходными минтермами, которые не имели соседних и не подвергались процессу склеивания, простые импликанты входят в результирующую ДНФ логической функции, которую называют сокращенной ДНФ.
Простые импликанты, наличие или отсутствие которых в сокращенной ДНФ
не сказывается на значении функции, называются избыточными.
Если из сокращенной ДНФ удалить все избыточные импликанты, то получим ДНФ, которую называют тупиковой. Логическая функция может иметь несколько тупиковых ДНФ. Искомая минимальная ДНФ совпадает (соответствует) с той тупиковой ДНФ, которая содержит минимальное число вхождений аргументов (букв).
Среди методов минимизации ЛФ наибольшее распространение получили метод Квайна и метод карт Карно.
Дата добавления: 2015-07-11; просмотров: 134 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| КАРТЫ КАРНО | | | Метод Квайна |