Simulating Digital Circuits with One Bit Per Wire

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

Conventional digital circuit simulators represent circuits using linked data structures, using one or more pointers per connection. To simulate a circuit of N nodes requires space proportional to N log N bits. Many circuits have a hierarchical or repetitive nature, so their specifications can be significantly smaller than the circuits themselves. This paper shows that such circuits can be simulated in space equal to one bit of memory per wire of the circuit, plus space proportional to the (smaller) size of the specification; that is, the space required is only O(N) bits. The algorithm has been implemented; measurements of its efficiency are given.

Original languageEnglish (US)
Pages (from-to)987-993
Number of pages7
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume7
Issue number9
DOIs
StatePublished - Sep 1988

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Simulating Digital Circuits with One Bit Per Wire'. Together they form a unique fingerprint.

Cite this