Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements
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 va...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kazan Federal University
2020-09-01
|
| Series: | Учёные записки Казанского университета: Серия Физико-математические науки |
| Subjects: | |
| Online Access: | https://kpfu.ru/uz-eng-phm-2020-3-7.html |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2541-7746 2500-2198 |