ГлавнаяАрхивSynthesis of combinational circuits by means of bi-decomposition of Boolean functions

Synthesis of combinational circuits by means of bi-decomposition of Boolean functions | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/8

Рассматривается задача синтеза комбинационных схем в базисе двухвходовых элементов И, ИЛИ, И-НЕ и ИЛИ-НЕ. Предложен метод её решения с помощью применения алгебраической декомпозиции булевых функций. Метод сводит решение задачи к поиску взвешенного двублочного покрытия полными двудольными подграфами (бикликами) графа ортогональности строк троичной матрицы, представляющей заданную булеву функцию. Каждой биклике в полученном покрытии определённым образом приписывается в качестве веса множество переменных, являющихся аргументами заданной функции. Каждая из этих двух биклик определяет булеву функцию с аргументами, приписанными соответствующей биклике. Полученные таким образом функции составляют искомое разложение. Процесс синтеза комбинационной схемы состоит из последовательного применения алгебраической декомпозиции к получаемым функциям. Описан способ получения двублочного покрытия бикликами графа ортогональности строк троичной матрицы.
  • Title Synthesis of combinational circuits by means of bi-decomposition of Boolean functions
  • Headline Synthesis of combinational circuits by means of bi-decomposition of Boolean functions
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 60
  • Date:
  • DOI 10.17223/20710410/60/8
Ключевые слова
синтез комбинационных схем, булева функция, декомпозиция булевых функций, троичная матрица, полный двудольный подграф, двублочное покрытие
Авторы
Ссылки
Cortadella J. Timing-driven logic bi-decomposition. IEEE Trans.Computer-Aided Design of Integrated Circuits and Systems, 2003, vol. 22, no. 6, pp. 675-685.
Mishchenko A., Steinbach B., and Perkowski M. An algorithm for bi-decomposition of logic functions. Proc. DAC'2001, 18-22 June 2001, Las Vegas, USA, pp. 103-108.
Chang S.-C., Marek-Sadowska M., and Hwang T. Technology mapping for TLU FPGAs based on decomposition of binary decision diagrams. IEEE Trans.Computer-Aided Design, 1996, vol. 15, no. 10, pp. 1226-1235.
Bibilo P. N. Dekompozitsiya bulevykh funktsiy na osnove resheniya logicheskikh uravneniy [Decomposition of Boolean Functions based on Solving Logical Equations]. Minsk, Belaruskaja Navuka, 2009. 211 p. (in Russian).
Zakrevskiy A. D. On a special kind decomposition of weakly specified Boolean functions. Proc. Second Int. Conf. CAD DD'97, Minsk, Belarus, 12-14 November 1997, National Academy of Sciences of Belarus, Institute of Engineering Cybernetics, Minsk, 1997, vol. 1, pp. 36-41.
Pottosin Yu. V. A method for bi-decomposition of partial Boolean functions. Prikladnaya Diskretnaya Matematika, 2020, no. 47, pp. 108-116.
Pottosin Yu. V. and Shestakov E. A. Parallel'no-posledovatel'naya kompozitsiya sistemy chastichnykh bulevykh funktsiy [Series parallel decomposition of a system of incompletely specified Boolean functions]. Prikladnaya Diskretnaya Matematika, 2010, no. 4(10), pp. 55-63. (in Russian).
Zakrevskiy A. D., Pottosin Yu. V., and Cheremisinova L. D.Combinatorial Algorithms of Discrete Mathematics. Tallinn, TUT Press, 2008. 194 p.
Zakrevskiy A. D., Pottosin Yu. V., and Cheremisinova L. D. Optimization in Boolean Space. Tallinn, TUT Press, 2009. 242 p.
Pottosin Yu. V. Kombinatornye zadachi v logicheskom proektirovanii diskretnykh ustroystv [Combinatorial Problems in Logical Design of Discrete Devices]. Minsk, Belaruskaja Navuka, 2021. 175 p. (in Russian).
Harary F. Graph Theory. Addison-Wesley, Reading, 1969.
Synthesis of combinational circuits by means of bi-decomposition of Boolean functions | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/8
Synthesis of combinational circuits by means of bi-decomposition of Boolean functions | Прикладная дискретная математика. 2023. № 60. DOI: 10.17223/20710410/60/8