On the complexity of encoding in analog circuits

被引：1
|
作者：
Wegener, I
机构：
[1] FB Informatik, LS II, Universität Dortmund
来源：
INFORMATION PROCESSING LETTERS | 1996年 / 60卷 / 01期
关键词：
computational complexity; analog circuits; Boolean functions;
D O I：
10.1016/S0020-0190(96)00137-8
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Fan-in 2 analog circuits over the basis {+, -, *, /} are investigated. The problem of encoding a Boolean vector is the problem of computing a one-to-one mapping f : {0, 1}(n) --> R. It is proved that the optimal encoding formula has size [(3n - 1)/2] and that encoding circuits have at least 5n/4 - 0(1) gates.
引用
收藏
页码：49 / 52
页数：4
相关论文
共 50 条
  • [1] THE COMPLEXITY OF WORD CIRCUITS
    Chen, Xue
    Hu, Guangda
    Sun, Xiaoming
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2010, 2 (04) : 482 - 491
  • [2] Catastrophic Faults Detection of Analog Circuits
    Arabi, Abderrazak
    Bourouba, Nacerdine
    Belaout, Abdesslam
    Ayad, Mouloud
    2015 7th International Conference on Modelling, Identification and Control (ICMIC), 2014, : 186 - 191
  • [3] Constraints generation for analog circuits layout
    Hao, QS
    Dong, SQ
    Chen, S
    Hong, XL
    Su, Y
    Qu, ZY
    2004 INTERNATIONAL CONFERENCE ON COMMUNICATION, CIRCUITS, AND SYSTEMS, VOLS 1 AND 2: VOL 1: COMMUNICATION THEORY AND SYSTEMS, 2004, : 1339 - 1343
  • [4] Constraints generation for analog circuits layout
    Hao, QS
    Chen, S
    Hong, XL
    Su, Y
    Dong, SQ
    Qu, ZY
    2004 INTERNATIONAL CONFERENCE ON COMMUNICATION, CIRCUITS, AND SYSTEMS, VOLS 1 AND 2: VOL 1: COMMUNICATION THEORY AND SYSTEMS - VOL 2: SIGNAL PROCESSING, CIRCUITS AND SYSTEMS, 2004, : 1334 - 1338
  • [5] Diagnostics of Incipient Faults in Analog Circuits
    Li Min
    Long Bing
    Xian Weiming
    Wang Houjun
    PROCEEDINGS OF 2013 IEEE 11TH INTERNATIONAL CONFERENCE ON ELECTRONIC MEASUREMENT & INSTRUMENTS (ICEMI), 2013, : 833 - 838
  • [6] On the Complexity of Hazard-free Circuits
    Ikenmeyer, Christian
    Komarath, Balagopal
    Lenzen, Christoph
    Lysikov, Vladimir
    Mokhov, Andrey
    Sreenivasaiah, Karteek
    JOURNAL OF THE ACM, 2019, 66 (04)
  • [7] On the Complexity of Hazard-Free Circuits
    Ikenmeyer, Christian
    Komarath, Balagopal
    Lenzen, Christoph
    Lysikov, Vladimir
    Mokhov, Andrey
    Sreenivasaiah, Karteek
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 878 - 889
  • [8] The complexity of threshold circuits for parity functions
    Sung, SC
    Nishino, T
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1997, E80D (01) : 91 - 93
  • [9] Time-mode circuits for analog computation
    Ravinuthula, Vishnu
    Garg, Vaibhav
    Harris, John G.
    Fortes, Jose A. B.
    INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONS, 2009, 37 (05) : 631 - 659
  • [10] A Neural Network Diagnosis Approach for Analog Circuits
    Alessandra Fanni
    Alessandro Giua
    Michele Marchesi
    Augusto Montisci
    Applied Intelligence, 1999, 11 : 169 - 186
12345