лекції, навчальні посібники - лекція №12 булева алгебра - ЛЕКЦІЯ12

Факторизація булевих функцій.

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

У результаті факторизації отримано дві форми з однаковою ціною (=10) та з різними затримками. У принципі перевагу слід надавати формі з меншою затримкою.

Схема в булевому базисі з парафазними входами:

Приклад факторного перетворення для МКНФ.

Оцінка ефекту факторизації.

Цей ефект визначається різницею цін схем до та після факторизації. Для одноразової факторизації значення її ефекту можна оцінити за допомогою виразу: Sq= Sq до факториз-Sq після факториз =m(k-1)+p-

Деm- кількість літер, що виносять, к – кількість термів, з яких проводиться винесення, р – кількість термів, в яких після винесення залишається одна буква.=1, якщо винесення проводиться з усіх термів,=2, якщо не з усіх.

Для ефективного вирішення задачі факторизації необхідно враховувати такі моменти:

За наявності у булевої функції кількох мінімальних форм доцільно вибирати з них такі, для яких застосування факторизації дасть максимальний виграш у ціні схеми.

При мінімізації не повністю певної булевої функції може виявитися, що максимальний ефект за рахунок факторизації дає нормальна форма, яка не є мінімальною.

---