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 http://resolver.caltech.edu/CaltechAUTHORS:GIBieeetit99
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:GIBieeetit99
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.
|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|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||16 Nov 2006|
|Last Modified:||26 Dec 2012 09:17|
Repository Staff Only: item control page