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

Ц е л и . Рассматривается задача синтеза комбинационных схем в базисе двухвходовых логических элементов, в качестве которых выступают элементы И, ИЛИ, И-НЕ и ИЛИ-НЕ. Целью работы является исследование возможности применения алгебраической декомпозиции булевых функций  (в  англоязычной литературе bi-decomposition) для синтеза комбинационных схем.

М е т о д ы . Используемый метод алгебраической декомпозиции сводится к поиску в графе двухблочного взвешенного покрытия полными двудольными подграфами (бикликами).

Р е з у л ь т а т ы . Исходная булева функция задается двумя троичными матрицами, одна из которых представляет собой область булева пространства аргументов, где функция имеет значение 1, а другая – область булева пространства, где функция имеет значение 0. Рассматривается граф ортогональности строк троичных матриц, представляющих заданную булеву функцию. Описан способ получения двухблочного взвешенного покрытия бикликами графа ортогональности cтрок троичных матриц. Всем бикликам из получаемого покрытия в качестве веса определенным образом приписывается некоторое множество переменных, представляющих собой аргументы заданной функции. Каждая из этих биклик определяет булеву функцию, аргументами которой являются приписанные к биклике переменные. Полученные таким образом функции составляют разложение исходной функции.

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

1. Cortadella, J. Timing-driven logic bi-decomposition / J. Cortadella // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – 2003. – Vol. 22, no. 6. – P. 675–685.

2. Mishchenko, A. An algorithm for bi-decomposition of logic functions / A. Mishchenko, B. Steinbach, M. Perkowski // Proc. of the 38th Annual Design Automation Conf. (DAC’2001), Las Vegas, USA, 18–22 June 2001. – Las Vegas, 2001. – P. 103–108.

3. Chang, S.-C. Technology mapping for TLU FPGA’s based on decomposition of binary decision diagrams / S.-C. Chang, M. Marek-Sadowska, T. Hwang // IEEE Transactions Computer-Aided Design. – 1996. – Vol. 15, no. 10. – P. 1226–1235.

4. Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.

5. Zakrevskij, A. D. On a special kind decomposition of weakly specified Boolean functions / A. D. Zakrevskij // Second Intern. Conf. on Computer-Aided Design of Discrete Devices (CAD DD’97), Minsk, Belarus, 12–14 Nov. 1997 / National Academy of Sciences of Belarus, Institute of Engineering Cybernetics. – Minsk, 1997. – Vol. 1. – P. 36–41.

6. Поттосин, Ю. В. Эвристический метод алгебраической декомпозиции частичных булевых функций / Ю. В. Поттосин // Информатика. – 2020. – Т. 17, № 3. – С. 44–53.

7. Поттосин, Ю. В. Параллельно-последовательная декомпозиция системы частичных булевых функций / Ю. В. Поттосин, Е. А. Шестаков // Прикладная дискретная математика. – 2010. – № 4(10). – С. 55–63.

8. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.

9. Евстигнеев, В. А. Толковый словарь по теории графов в информатике и программировании / В. А. Евстигнеев, В. Н. Касьянов. – Новосибирск : Наука, 1999. – 291 с.