Asymptotically Best Synthesis Methods for Reflexive-Recursive Circuits
- PDF / 339,215 Bytes
- 15 Pages / 594 x 792 pts Page_size
- 30 Downloads / 148 Views
ASYMPTOTICALLY BEST SYNTHESIS METHODS FOR REFLEXIVE-RECURSIVE CIRCUITS V. V. Zhukov We introduce the notion of reflexive-recursive circuits and consider classes of many-output and scalar reflexive-recursive circuits of bounded depth in an arbitrary basis. Methods are proposed for deriving lower and upper bounds on the Shannon function for the complexity of circuits from these classes and asymptotic expressions are established. We also derive upper bounds for the realization complexity in these classes of circuits for some functions and systems of functions occurring in applications. Keywords: recursive circuits of functional elements, complexity of Boolean functions, Shannon function, asymptotic bounds.
Introduction The synthesis problem first considered by Shannon (see, e.g., [1]) involves the construction of an optimal method for the synthesis of circuits of a certain class for an arbitrary Boolean function or a system of such functions. The optimality of the synthesis method is assessed by the Shannon function, which for a given n is equals the maximum complexity of the Boolean function of n variables. The circuit complexity is usually understood as the number of circuit elements or their total “weight”, and the function complexity is the minimum complexity of the circuits realizing this function. Shannon function can thus be defined for a delay. Lupanov [2] has proposed the asymptotically best method of circuit synthesis in arbitrary complete finite bases. This method has established that the asymptotic behavior of the Shannon function for circuits of functional elements (CFEs) in a standard basis consisting of conjunction, disjunction, and inversion is 2n /n, whereas in an arbitrary finite complete basis B it is ⇢B · 2n /n, where ⇢B is a basis-dependent constant. The asymptotically best method for the synthesis of circuits from blocks — many-output functional elements — has been described in [3]. High-accuracy asymptotic bounds (HAAB) of the Shannon function L(n) for functional element circuits in a standard basis have been obtained in [4, 5]:1 2n L(n) = n
✓
◆ log n ± O(log log n) 1+ , n
and also bounds close to HAAB for the Shannon function in CFEs in an arbitrary basis. Some authors (e.g., [6, 7]) have considered a model of circuits of functional elements in infinite bases, when the order of growth of the Shannon function is 2n/2 . A 2 · 2n/2 asymptotic growth of the Shannon function has been obtained in [8] for circuits in which the basis consists of many-input conjunction and disjunction elements with variables or their inverters on the inputs. In addition to complexity defined as the number or total “weight” of circuit elements, many authors (see, e.g., [9–12]) have considered the power consumption of the circuits. These authors deal, for instance, with the static Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia; e-mail: zhvv117@ gmail.com. 1 All logs in this article are to the base 2. Translated from Prikladnaya Matematika i Informatika, No. 63,
Data Loading...
