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!
|
| _version_ | 1850180069492785152 |
|---|---|
| author | S.A. Lozhkin V.S. Zizov |
| author_facet | S.A. Lozhkin V.S. Zizov |
| author_sort | S.A. Lozhkin |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-c2c252e6f3ff40dd9f4ef97278d3f18c |
| institution | OA Journals |
| issn | 2541-7746 2500-2198 |
| language | English |
| publishDate | 2020-09-01 |
| publisher | Kazan Federal University |
| record_format | Article |
| series | Учёные записки Казанского университета: Серия Физико-математические науки |
| spelling | doaj-art-c2c252e6f3ff40dd9f4ef97278d3f18c2025-08-20T02:18:19ZengKazan Federal UniversityУчёные записки Казанского университета: Серия Физико-математические науки2541-77462500-21982020-09-01162332233410.26907/2541-7746.2020.3.322-334Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elementsS.A. Lozhkin0V.S. Zizov1Lomonosov Moscow State University, Moscow, 119991 RussiaLomonosov Moscow State University, Moscow, 119991 RussiaThe 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.https://kpfu.ru/uz-eng-phm-2020-3-7.htmlfunctional elementsswitching elementscellular circuitsareadecoderasymptotic estimates |
| spellingShingle | S.A. Lozhkin V.S. Zizov Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements Учёные записки Казанского университета: Серия Физико-математические науки functional elements switching elements cellular circuits area decoder asymptotic estimates |
| title | Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements |
| title_full | Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements |
| title_fullStr | Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements |
| title_full_unstemmed | Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements |
| title_short | Refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements |
| title_sort | refined estimates of the decoder complexity in the model of cellular circuits with functional and switching elements |
| topic | functional elements switching elements cellular circuits area decoder asymptotic estimates |
| url | https://kpfu.ru/uz-eng-phm-2020-3-7.html |
| work_keys_str_mv | AT salozhkin refinedestimatesofthedecodercomplexityinthemodelofcellularcircuitswithfunctionalandswitchingelements AT vszizov refinedestimatesofthedecodercomplexityinthemodelofcellularcircuitswithfunctionalandswitchingelements |