Geodesic
Synthesis of combinational circuits by means of bi-decomposition of Boolean functions
Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 95-105.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: synthesis of combinational circuits, Boolean function, decomposition of Boolean functions, ternary matrix, complete bipartite subgraph, two-block cover. 
@article{PDM_2023_2_a7,
     author = {Yu. V. Pottosin},
     title = {Synthesis of combinational circuits by means of bi-decomposition of {Boolean} functions},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {95--105},
     publisher = {mathdoc},
     number = {2},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2023_2_a7/}
}
TY  - JOUR
AU  - Yu. V. Pottosin
TI  - Synthesis of combinational circuits by means of bi-decomposition of Boolean functions
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2023
SP  - 95
EP  - 105
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2023_2_a7/
LA  - en
ID  - PDM_2023_2_a7
ER  - 
%0 Journal Article
%A Yu. V. Pottosin
%T Synthesis of combinational circuits by means of bi-decomposition of Boolean functions
%J Prikladnaâ diskretnaâ matematika
%D 2023
%P 95-105
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2023_2_a7/
%G en
%F PDM_2023_2_a7
Yu. V. Pottosin. Synthesis of combinational circuits by means of bi-decomposition of Boolean functions. Prikladnaâ diskretnaâ matematika, no. 2 (2023), pp. 95-105. http://geodesic.mathdoc.fr/item/PDM_2023_2_a7/

[1] Cortadella J., “Timing-driven logic bi-decomposition”, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 22:6 (2003), 675–685 | DOI

[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

[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 | MR

[6] Pottosin Yu. V., “A method for bi-decomposition of partial Boolean functions”, Prikladnaya Diskretnaya Matematika, 2020, no. 47, 108–116 | DOI | MR | Zbl

[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)

[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 | MR | Zbl