𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of encoding in analog circuits

✍ Scribed by Ingo Wegener

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
329 KB
Volume
60
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

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)" + R. It is proved that the optimal encoding formula has size [( 3n -1)/21 and that encoding circuits have at least 5n/4 -0( 1) gates.

πŸ“œ SIMILAR VOLUMES

On the Computation of Boolean Functions
On the Computation of Boolean Functions by Analog Circuits of Bounded Fan-In
✍ GyΓΆrgy TurΓ‘n; Farrokh Vatan πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 741 KB

We consider the complexity of computing Boolean functions by analog circuits of bounded fan-in, i.e., by circuits of gates computing real-valued functions, either exactly or as sign-representation. Sharp upper bounds are obtained for the complexity of the most difficult n-variable function over cert