A Caltech Library Service

Efficient digital-to-analog encoding

Gibson, Michael A. and Bruck, Jehoshua (1999) Efficient digital-to-analog encoding. IEEE Transactions on Information Theory, 45 (5). pp. 1551-1554. ISSN 0018-9448. doi:10.1109/18.771156.

See Usage Policy.


Use this Persistent URL to link to this item:


An important issue in analog circuit design is the problem of digital-to-analog conversion, i.e., 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 answered by Wegener (see Inform. Processing Lett., vol.60, no.1, p.49-52, 1995), who proved matching lower and upper bounds on the size of the circuit for the encoding function. In particular, it was proven that [(3n-1)/2] 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 of maximum size n log n bits; the nonconstructive proof uses constants of maximum size 2n+[log n] bits.

Item Type:Article
Related URLs:
URLURL TypeDescription
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© Copyright 1999 IEEE. Reprinted with permission. Manuscript received November 1, 1996; revised November 1, 1998. This work was supported in part by a National Science Foundation Graduate Research Fellowship, a National Science Foundation Young Investigator Award CCR-9457811, and a Sloan Research Fellowship. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, MIT, Cambridge, MA, August 16–21, 1998.
Subject Keywords:Complexity, construction, decoding, digital-to-analog, encoding
Issue or Number:5
Record Number:CaltechAUTHORS:GIBieeetit99
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6062
Deposited By: Archive Administrator
Deposited On:16 Nov 2006
Last Modified:08 Nov 2021 20:30

Repository Staff Only: item control page