4.9. Синтез комбинационных логических цепей
Процесс синтеза комбинационных логических цепей можно проводить в следующей последовательности. Вначале составляется таблица функционирования логической цепи (таблица истинности). Эта таблица показывает, чему равен выходной сигнал цепи (значение логической функции) при различных возможных сочетаниях входных сигналов. Затем, исходя из таблицы функционирования, записывается логическая функция в виде совершенной дизъюнктивной или совершенной конъюнктивной формы. После этого логическая функция минимизируется и преобразуется к виду, удобному для реализации на логических функциях заданного типа, т.е. в заданном базисе функций.
Пример 4.4.
Пороговая ячейка. Составим логическую цепь трехвходовой комбинационной логической цепи, сигнал на выходе которой будет равен единице только тогда, когда на ее входах присутствует не менее двух единичных сигналов («машина для голосования»).
Заполняем вначале таблицу функционирования (табл. 4.9). Поскольку в данном случае имеются три входных сигнала х1, х2 и х3, каждый из которых может принимать одно из двух возможных значений (0 или 1), то всего может быть восемь различных комбинаций этих сигналов.
Таблица 4.9
|
х1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
х2 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
х3 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
f(х1,х2,х3) |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
Четырем из этих комбинаций, в которых содержатся две или три единицы, будет соответствовать выходной сигнал f(х1,х2,х3), равный единице. Пользуясь табл.4.9, можно написать логическую функцию, которую должна реализовать синтезируемая цепь. Для этого нужно представить эту функцию в виде СДНФ, т.е. логической суммы элементарных конъюнкций (минтермов), соответствующих тем строкам табл. 4.9, для которых значение функции f равно единице. При записи минтермов, т. е. конъюнкций, в которые входят все аргументы функции (в данном случае х1, х2 и х3), следует брать соответствующий аргумент с инверсией или без инверсии в зависимости от того, чему он равен в данной строке таблицы функционирования – нулю или единице. Таким образом, в данном случае получим:
Отметим, что полученная СДНФ представлена в базисе И, ИЛИ, НЕ.
Следующий этап в синтезе логической цепи – минимизация логического выражения, представленного СДНФ, т.е. отыскание такого аналитического выражения этой функции, которое содержит только знаки {Ù, Ú,` }, и общее число этих элементов минимально.
Одним из методов, применяемых для решения этой задачи, является метод Квайна. Последовательность операций в этом методе такова. Проводятся все возможные сокращения членов совершенной формы путем использования тождества
где А может быть конъюнкцией нескольких переменных.
Затем эта же операция проделывается по отношению ко всем конъюнкциям, полученным в результате первого сокращения и т. д. до тех пор, пока дальнейшее сокращение станет невозможным. Пары конъюнкций (из числа членов совершенной формы и полученных в результате сокращений), к которым упрощающее тождество (4.17) нельзя применить, называются простыми импликантами f. Квайном доказано, что любое минимальное дизъюнктивное нормальное выражение f есть дизъюнкция некоторых простых импликантов f. Поэтому следующим этапом нахождения минимальных выражений f является определение комбинаций простых импликантов, дизъюнкции которых давали бы минимальные выражения. Для этого с помощью некоторых искусственных приемов строятся такие комбинации простых импликантов f, дизъюнкция которых эквивалентна f и удаление из дизъюнкции хотя бы одного простого импликанта нарушило бы условие эквивалентности f. Такие дизъюнкции называются «тупиковыми» выражениями f. Затем в каждом из тупиковых выражений подсчитывается число знаков {Ù, Ú,` } и отбираются те из них, у которых суммарное число этих знаков наименьшее. Эти выражения и являются минимальными (при принятом критерии минимальности).
Для реализации описанного метода преобразуем (4.16), добавив в него элементарную конъюнкцию х1 х2 х3 два раза (используя свойство идемпотентности):
Затем, использовав свойства ассоциативности и коммутативности, получим
В результате применения (4.17) получим конъюнкции (х1 х2 , х1 х3, х2х3 ), не допускающие дальнейших сокращений. Они же являются единственными конъюнкциями, не давшими ни одного последующего сокращения. Значит все они – простые импликанты f. Следовательно,
- тупиковое выражение.
Если при реализации логической цепи предполагается использовать только элементы «И – НЕ» (т.е. использовать базис Шеффера), то, использовав правила де Моргана, получаем следующее эквивалентное выражение:
Схема синтезированной логической цепи приведена на рис. 4.1.
Пример 4.5.
Пусть задана булева функция
В результате всех возможных попарных сокращений членов формы (причем каждый из членов дизъюнктивной формы может входить более чем в одну пару) получаем простые импликанты
Хотя дизъюнкция всех простых импликантов эквивалентна f , непосредственной проверкой можно установить, что исключение конъюнкции `х1 х3 не нарушает условия эквивалентности и нельзя исключить никакую конъюнкцию из числа оставшихся, не нарушив эквивалентности. Следовательно,
- одно из тупиковых выражений. Можно показать также, что
- тоже тупиковое выражение. Других тупиковых выражений у этой функции нет. Сравнение тупиковых выражений показывает, что оба они имеют одинаковое число знаков {Ù, Ú,` } и, следовательно, в равной степени минимальны.
Алгоритм Квайна позволяет получить минимальные дизъюнктивные нормальные выражения заданных функций. Однако в ряде случаев минимальные конъюнктивные нормальные выражения оказываются «меньше» дизъюнктивных. Поэтому для получения минимальных нормальных выражений необходимо получить как дизъюнктивные, так и конъюнктивные нормальные выражения и выбрать из них наименьшие. Методы получения минимальных конъюнктивных нормальных выражений двойственны методам получения минимальных дизъюнктивных выражений.