Synthesis of combinational circuits by means of bi-decomposition of Boolean functions. (English) Zbl 1527.94099
Summary: 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 matrix 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 matrix rows is described.
MSC:
| 94C11 | Switching theory, applications of Boolean algebras to circuits and networks |
| 94D10 | Boolean functions |
Keywords:
synthesis of combinational circuits; Boolean function; decomposition of Boolean functions; ternary matrix; complete bipartite subgraph; two-block coverReferences:
| [1] | Cortadella J., “Timing-driven logic bi-decomposition”, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 22:6 (2003), 675-685 · doi:10.1109/TCAD.2003.811447 |
| [2] | 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), 103-108 |
| [3] | Chang S.-C., Marek-Sadowska M., and Hwang T., “Technology mapping for TLU FPGAś based on decomposition of binary decision diagrams”, IEEE Trans. Computer-Aided Design, 15:10 (1996), 1226-1235 · doi:10.1109/43.541442 |
| [4] | Bibilo P. N., Decomposition of Boolean Functions based on Solving Logical Equations, Belaruskaja Navuka, Minsk, 2009, 211 pp. (in Russian) |
| [5] | 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), v. 1, National Academy of Sciences of Belarus, Institute of Engineering Cybernetics, Minsk, 1997, 36-41 |
| [6] | Pottosin Yu. V., “A method for bi-decomposition of partial Boolean functions”, Prikladnaya Diskretnaya Matematika, 2020, no. 47, 108-116 · Zbl 1455.94233 · doi:10.17223/20710410/47/9 |
| [7] | Pottosin Yu. V. and Shestakov E. A., “Series parallel decomposition of a system of incompletely specified Boolean functions”, Prikladnaya Diskretnaya Matematika, 2010, no. 4(10), 55-63 (in Russian) · Zbl 1517.94217 |
| [8] | Zakrevskiy A. D., Pottosin Yu. V., and Cheremisinova L. D., Combinatorial Algorithms of Discrete Mathematics, TUT Press, Tallinn, 2008, 194 pp. |
| [9] | Zakrevskiy A. D., Pottosin Yu. V., and Cheremisinova L. D., Optimization in Boolean Space, TUT Press, Tallinn, 2009, 242 pp. |
| [10] | Pottosin Yu. V., Combinatorial Problems in Logical Design of Discrete Devices, Belaruskaja Navuka, Minsk, 2021, 175 pp. (in Russian) |
| [11] | Harary F., Graph Theory, Addison-Wesley, Reading, 1969 · Zbl 0182.57702 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
