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.