Efficient digital-to-analog encoding

An important issue in analog circuit design is the problem of digital-to-an alog conversion, i.e., the encoding of Boolean variables into a single anal og value which contains enough information to reconstruct the values of the Boolean variables. A natural question is: What is the complexity of implem enting the digital-to-analog encoding function? That question was recently answered by Wegener, who proved matching lower and upper bounds on the size of the circuit for the encoding function. In particular, it was proven tha t inverted right perpendicular (3n - 1)/2 inverted left perpendicular 2-inp ut arithmetic gates are necessary and sufficient for implementing the encod ing 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 e ncoder that is optimal in the number of 2-input arithmetic gates. In additi on, we present an efficient analog-to-digital decoding algorithm. Namely, g iven the encoded analog value, our decoding algorithm reconstructs the orig inal Boolean values. Our construction is suboptimal in that it uses constan ts of maximum size n log n bits; the nonconstructive proof uses constants o f maximum size 2n + inverted right perpendicular log n inverted left perpen dicular bits.