|
This article is cited in 3 scientific papers (total in 3 papers)
Asymptotically best method for synthesis of Boolean recursive circuits
V. V. Zhukov, S. A. Lozhkin Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics
Abstract:
Models of multi-output and scalar recursive Boolean circuits of bounded depth in an arbitrary basis are considered. Methods for lower and upper estimates for the Shannon function for the complexity of circuits of these classes are provided. Based on these methods, an asymptotic formula for the Shannon function is put forward. Moreover, in the above classes of recursive circuits, upper estimates for the complexity of implementation of some functions and systems of functions used in applications are obtained.
Keywords:
recursive circuits of gates, complexity of Boolean functions, Shannon function, asymptotic estimates.
Received: 26.03.2018 Revised: 03.06.2018
Citation:
V. V. Zhukov, S. A. Lozhkin, “Asymptotically best method for synthesis of Boolean recursive circuits”, Diskr. Mat., 31:1 (2019), 99–110; Discrete Math. Appl., 30:2 (2020), 137–146
Linking options:
https://www.mathnet.ru/eng/dm1511https://doi.org/10.4213/dm1511 https://www.mathnet.ru/eng/dm/v31/i1/p99
|
|