Efficient Digital to Analog Encoding

Abstract

NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract included in .pdf document. An important issue in analog circuit design is the problem of digital to analog conversion, namely, the encoding of Boolean variables into a single analog value which contains enough information to reconstruct the values of the Boolean variables. A natural question is: What is the complexity of implementing the digital to analog encoding function? That question was recently answered in (5), where matching lower and upper bounds on the size of the circuit for the encoding function were proven. In particular, it was proven that [...] 2-input arithmetic gates are necessary and sufficient for implementing the encoding function of n Boolean variables. However, the proof of the upper bound is not constructive. In this paper, we present an explicit construction of a digital to analog encoder that is optimal in the number of 2-input arithmetic gates. In addition, we present an efficient analog to digital decoding algorithm. Namely, given the encoded analog value, our decoding algorithm reconstructs the original Boolean values. Our construction is suboptimal in that it uses constants [...] bits.

Files

Additional details