Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements

Abstract

The model of cellular circuits was considered in a single basis of functional and switching elements, which is built in accordance with the standard basis B0 consisting of Boolean functions x1 & x2, x1 ∨ x2, ˉx1. In this model, both inputs and outputs of the cellular circuit Σ associated with various input and output Boolean variables, respectively, are irreversibly located on the border of the corresponding rectangular lattice, and the cellular circuit Σ itself corresponds, structurally and functionally, to a scheme of functional elements S in the basis B0 with the same sets of input and output Boolean variables. We studied the complexity (area) of cellular circuits with n inputs and 2n outputs that implements a system of all 2n elementary conjunctions of rank n from input Boolean variables, i.e., a binary decoder with power n . It was proved that the smallest possible area of a cellular circuit implementing such a decoder, provided that n = 1, 2,…, is equal to n2n−1(1+O(1/n)). This is the first time when so-called asymptotic estimates of a high degree of accuracy, i.e., estimates with a relative error O(1/n), were obtained for it.

Keywords

• functional elements
• switching elements
• cellular circuits
• area
• decoder
• asymptotic estimates