Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Efficient digital-to-analog encoding
Autore:
Gibson, MA; Bruck, J;
Indirizzi:
CALTECH, Pasadena, CA 91125 USA CALTECH Pasadena CA USA 91125CALTECH, Pasadena, CA 91125 USA
Titolo Testata:
IEEE TRANSACTIONS ON INFORMATION THEORY
fascicolo: 5, volume: 45, anno: 1999,
pagine: 1551 - 1554
SICI:
0018-9448(199907)45:5<1551:EDE>2.0.ZU;2-I
Fonte:
ISI
Lingua:
ENG
Soggetto:
COMPUTATION; COMPLEXITY; CIRCUITS;
Keywords:
complexity; construction; decoding; digital-to-analog; encoding;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
5
Recensione:
Indirizzi per estratti:
Indirizzo: Gibson, MA CALTECH, MS 136-93, Pasadena, CA 91125 USA CALTECH MS 136-93 Pasadena CA USA 91125 Pasadena, CA 91125 USA
Citazione:
M.A. Gibson e J. Bruck, "Efficient digital-to-analog encoding", IEEE INFO T, 45(5), 1999, pp. 1551-1554

Abstract

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 recentlyanswered by Wegener, who proved matching lower and upper bounds on the size of the circuit for the encoding function. In particular, it was proven that inverted right perpendicular (3n - 1)/2 inverted left perpendicular 2-input arithmetic gates are necessary and sufficient for implementing the encoding function of n Boolean variables. However, the proof of the upper boundis 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 + inverted right perpendicular log n inverted left perpendicular bits.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 14/07/20 alle ore 19:46:21