OPTIMIZATION PROBLEM FOR NUMBER OF LOGIC GATES NEEDED TO IMPLEMENT MULTIPLE BOOLEAN FUNCTIONS USING DECODER

Анотація

Анотація. Контекст. Завдяки комп’ютерним схемам функціонує майже будь-яка електроніка. Можливість оптимізувати схеми знайдено в одному зі способів їх реалізації, що залучає дешифратор. Дешифратори є базовими компонентами схем, поведінка яких дозволяє легко реалізувати кілька булевих функцій. Функції – це лише правила, за якими інформаційні сигнали обробляється в схемі. Щоб реалізувати функцію використовуються Логічні Елементи (ЛЕ). ЛЕ групують кілька вхідних сигналів і обробляють їх за допомогою двійкових логічних операторів, як то AND або NOR.

Мета. Розробити комп’ютерну програму, яка на основі наданих функцій знайде рішення, пов’язане з близькою до мінімальної кількістю Логічних Елементів.

Актуальність. Поширеність схем підвищує цінність невеликих покращень, оскільки будь-яке вдосконалення помножується на мільйони виготовлених схем. Досліджується оптимізація на логічному рівні, яка збереже значення незалежно від фізичних властивостей схеми. Крім того, розроблюється теорія для оптимізації використання ЛЕ, яка полегшить майбутні дослідження.

Методи. Поштовхом для розвитку теорії було розуміння, що вхідні сигнали можна свідомо групувати за допомогою ЛЕ. Таким чином, виходи ЛЕ можна використовувати в більш ніж одній функції, що призводить до зменшення загальної кількості ЛЕ. Стає очевидним, що задачу можна виразити в контексті множин. Виявляється подібність до відомих NP-складних задач, що спонукає до використання існуючих підходів до рішення. Серед них обрано жадібний алгоритм за простоту його програмної реалізації. Зв'язок між задачею та схемотехнікою послаблюється після введення спеціальних оціночних функцій, які працюють із множинами. Отже, задача зводиться до кількох математичних правил, які потім використовуються як відповідні частини жадібного алгоритму. На цьому завершено формулювання знань, необхідних для створення цільової програми.

Результати. Цільова програма успішно реалізована, з нею можна ознайомитись на https://github.com/Gleb-05/MakeFuncForDC. Проведено тести на 1000 наборах з чотирьох псевдовипадкових функцій на вісім елементів. Підраховано, що реалізації, запропоновані цільовою програмою, вимагають у середньому 0,75 від початкової кількості ЛЕ. Середній час роботи становить 2 мілісекунди. В порівнянні, пошук грубою силою для тої ж задачі теоретично потребує тисячі років.

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