Факторизация системы булевых функций

 

Применительно к системе булевых функций задача факторизации состоит в выделении общих термов или их частей для отдельных функций системы с целью уменьшения цены схемы, реализующей эту систему. Сходная задача уже решается при совместной минимизации функций системы при выделении общих термов для минимальных форм булевых функций системы, когда некоторые кубы покрытия системы являлись общими для нескольких функций, однако, совместная минимизация не исключает применения дальнейшей факторизации. Особенно актуальной задача факторизации становится при раздельной минимизации функций системы. Совместная факторизация функций системы не исключает раздельной факторизации в рамках каждой функции.

Пример 3.10. Выполним факторизациюсистемы булевых функций:

   

Введем общий терм z:

                

Эффект факторизации системы булевых функций – нулевой. Проведем раздельную факторизацию:

В результате раздельной факторизации цена схемы уменьшилась на два. Эффект возник в результате того, что в выражениях функций переменные выносились из всех термов и после вынесения появились однобуквенные термы. Заметим, что раздельная факторизация исходной системы эффекта бы не дала.

 

Пример 3.11. Для функции примера 3.8. проведем факторизацию функции y ₃. Получим:

   

 

Замечание. Порядок проведения двух видов факторизации совместной и раздельной в большинстве случаев безразличен.

 

Декомпозиция системы булевых функций

 

    Декомпозиция системы булевых функций – представляет собой выражение одних функций через другие. В некоторых случаях декомпозиция позволяет уменьшить цену комбинационной схемы дополнительно к решению задач минимизации и факторизации

 

Пример 3.12. Синтезировать комбинационную схему одноразрядного сумматора с однофазными входами.

Одноразрядный комбинационный сумматор выполняет функцию сложения одноименных двоичных разрядов многоразрядных слагаемых. Сложение в каждом k-ом разряде n -разрядных слагаемых осуществляется с учетом переноса из предыдущего (k - 1)-го младшего разряда (k=1, 2, …, n-1). Результатами сложения одноразрядных двоичных чисел являются значение суммы в k-ом разряде и переноса из k-ого разряда в следующий (k+1)-ый старший разряд.

Обобщенное представление одноразрядного комбинационного сумматора приведено на рис. 3.23.

                           

 

Рис. 3.23. Условно-графическое изображение одноразрядного сумматора

Входными переменными сумматора являются:

a, b – слагаемые и p –перенос из предыдущего разряда.

Выходными переменными являются:

S – сумма и q – перенос в следующий разряд.

Замечание. Для младшего разряда сумматора при отсутствии в нем цепи циклического переноса, которая передает перенос из старшего разряда сумматора в младший и используется при сложении в обратном коде, вход p может отсутствовать, либо на него подается значение p=0.

Закон функционирования одноразрядного сумматора представляется в виде следующей системы булевых функций:

 

 

В соответствии с принципами двоичного сложения составим таблицу истинности синтезируемой схемы (табл. 3.1).

 

 

a	b	p	S	q
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

 

 

    

 

 

Таблица 3.1. Таблица истинности одноразрядного сумматора

 

Прежде чем показать преимущества применения декомпозиции, предварительно решим задачи минимизации и факторизации применительно к системе функций.

 

Раздельная минимизация

На рис. 3.24 показаны результаты раздельной минимизации функций системы на картах Карно.

   bp                                     bp

	00	01	11	10
0		1		1
1	1		1

	00	01	11	10
0			1
1		1	1	1

a                                                                                                                 a

S       q q               

Рис. 3.24. Раздельная минимизация функций системы

                     

                   

           

 

Раздельная факторизация

Решим задачу факторизации применительно к функциям системы, вынося общие термы (в данном примере они однобуквенные) за скобки:

 

За счет раздельной факторизации цена схемы, реализующей функцию переноса – q, уменьшилась на единицу, а цена схемы, реализующей функцию суммы – S, увеличилась на два, так что для системы функций {S, q} факторизация оказалась невыгодна. Тем не менее, факторизованная функция S позволяет применить к ней декомпозицию (по аналогии с примером 3.5 в разделе 3.9), так как выражения в скобках взаимно инверсны.

Обозначим первую скобку в скобочной форме функции S вспомогательной переменной z. С учетом того, что вторая скобка представляет собой инверсию переменной z, выражение для системы функций {S, q} примет вид:

 

По сравнению с результатом раздельной факторизации функций системы {S, q} последняя декомпозиция функции S позволила существенно уменьшить цену схемы.

Нетрудно заметить, что в системе функций (3) имеются:

· во-первых, общий член ab для вспомогательной функции z и функции переноса – q;

· во-вторых, во вспомогательной функции z имеется конъюнктивный терм aÚ b, содержащийся также в функции q.

С учетом этого введем еще две вспомогательные функции: . В результате система функций (3) приводится к следующему виду:

      

 

 

В результате проведенных действий цена комбинационной схемы уменьшилась до 18.

 

⇐ Предыдущая891011121314151617Следующая ⇒

Поделиться: