(pdf version)

The model of Celullar circuit in standard basis of functional and commutation elements had been proposed for the first time by Kravcov S.S. in 1967 in the work [1], where the complexity of the Celullar circuit was understood as its area. In general the Celullar circuit of functional and commutation elements (Celullar circuit) is a mathematical model of integrated circuits (IC), which takes into account the features of their physical synthesis [2].

Albrecht A. showed in his work [3] that the Shannon function in the model [1] has asymptotically tight bound \(\sigma2^n\), where \(\sigma\) is some constant. Herewith the exact value of the constant \(\sigma\) remains unknown, although it follows from works [3] and [1] that it is in the segment \([\frac{1}{4}, \frac{9}{2}]\).

Main result of present work is more accurate estimates of Shannon function in model of cellular circuit model. In base works of Albrecht model was considered to be compiled of single squares. If we observe it as combination of blocks of fixed size (4x4, 2x8, etc), then we can estimate area of cellular circuit more precisely due to combinatorial enumeration of its variants.

References

1. Kravcov S.S. Realization of Boolean functions in a class of circuits of functional and switching elements // Problems of Cybernetics M.: Nauka 1967. V. 19. pp. 285-–292 (in Russian)

2. Thompson Clark D. A complexity theory for VLSI (1980)

3. A. Albrecht On circuits of cellular elements // Problemi Kibernetiki, 33 (1978), 209–214 (in Russian)