The problem of combinational circuits synthesis in the basis of two-input gates is considered. Those gates are AND, OR, NAND and NOR. A method for solving this problem by means of Boolean functions bi-decomposition is suggested. The method reduces the problem to the search for a weighted two-block cover of the orthogonality graph of ternary matrice rows representing the given Boolean function by complete bipartite subgraphs (bi-cliques). Each bi-clique in the obtained cover is assigned in a certain way with a set of variables that are the arguments of the function. This set is the weight of the bi-clique. Each of those bi-cliques defines a Boolean function whose arguments are the variables assigned to it. The functions obtained in such a way constitute the required decomposition. The process of combinational circuit synthesis consists in successively applying bi-decomposition to the functions obtained. The method for two-block covering the orthogonality graph of ternary matrice rows is described.
Download file
Counter downloads: 7
- 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
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 60
- Date:
- DOI 10.17223/20710410/60/8
Keywords
synthesis of combinational circuits, Boolean function, decomposition of Boolean functions, ternary matrix, complete bipartite subgraph, two-block coverAuthors
References
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 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2023. № 60. DOI: 10.17223/20710410/60/8
Download full-text version
Counter downloads: 128