Page 20 - 4128

1.5 Синтез кс з урахуванням обмеження на К .
об

Представленню функції у вигляді ДНФ відповідає
дворівнева КС (якщо вважати, що на її вхід можуть поступати
як прямі, так і інверсні вхідні сигнали), на першому рівні якої
елементи І, а їх виходи об'єднуються на другому рівні
елементом АБО. Така побудова КС забезпечує її максимальну
швидкодію, оскільки ранг схеми мінімальний. Проте, не
завжди можливо на першому рівні і, особливо, на другому
вибрати логічні елементи з необхідним К , оскільки може
об
виявитися, що ЛЕ з таким К не випускаються
об
промисловістю. В цьому випадку необхідно за допомогою
декількох елементів з меншим К одержати еквівалент з
об
великим К , або перетворити БФ, перейшовши від ДНФ до
об
дужкової форми. Цей перехід супроводжується зменшенням
К логічних елементів, що вимагається для побудови схеми.
об
Здійснити такий перехід можна за допомогою факторного
алгоритму, суть якого розглянемо на прикладі.
Нехай задана деяка булева функція у вигляді
Y  X X X X  X X X X X  X X X X  X X X X
1 2 3 4 1 2 3 5 6 1 3 5 6 1 2 3 4
Для реалізації цієї функції за приведеним виразом
необхідно використовувати 3 логічні елементи 4І, один
логічний елемент 5І, один логічний елемент 4АБО.
За допомогою факторного алгоритму одержимо
дужкову форму для заданої функції. Для цього позначимо всі
кон'юнкції буквами:

A  X X X X , B  X X X X X , C  X X X X ,
1 2 3 4 1 2 3 5 6 1 3 5 6
D  X X X X .
1 2 3 4
і розглядатимемо їх як деякі множини. Знаходимо попарні
перетини множин:

A B  X X X , A C  X , A D  X X , B C  X ,
1 2 3 1 1 3 1
B  D  X X , C  D  X .
1 2 1
19