Simulating Digital Circuits with One Bit Per Wire

Andrew W. Appel

doi:10.1109/43.7796

Simulating Digital Circuits with One Bit Per Wire

Andrew W. Appel

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	987-993
Number of pages	7
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	7
Issue number	9
DOIs	https://doi.org/10.1109/43.7796
State	Published - Sep 1988

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1109/43.7796

Cite this

@article{12b93212d11c4cfb87b5a482b5205db2,

title = "Simulating Digital Circuits with One Bit Per Wire",

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.",

author = "Appel, {Andrew W.}",

note = "Funding Information: Manuscript received April 29. 1987; revised November 17. 1987 and February 23. 1988. This work was supported in part by the National Science Foundation under Grant DCR-8603453 and in part by a Digital Equipment Corporation Faculty Incentive Grant. The review of thih paper was ;irrnnged by Associate Editor M. R. Lightner. Copyright: Copyright 2015 Elsevier B.V., All rights reserved.",

year = "1988",

month = sep,

doi = "10.1109/43.7796",

language = "English (US)",

volume = "7",

pages = "987--993",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "9",

}

TY - JOUR

T1 - Simulating Digital Circuits with One Bit Per Wire

AU - Appel, Andrew W.

N1 - Funding Information: Manuscript received April 29. 1987; revised November 17. 1987 and February 23. 1988. This work was supported in part by the National Science Foundation under Grant DCR-8603453 and in part by a Digital Equipment Corporation Faculty Incentive Grant. The review of thih paper was ;irrnnged by Associate Editor M. R. Lightner. Copyright: Copyright 2015 Elsevier B.V., All rights reserved.

PY - 1988/9

Y1 - 1988/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0024070316&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024070316&partnerID=8YFLogxK

U2 - 10.1109/43.7796

DO - 10.1109/43.7796

M3 - Article

AN - SCOPUS:0024070316

SN - 0278-0070

VL - 7

SP - 987

EP - 993

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 9

ER -

Simulating Digital Circuits with One Bit Per Wire

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this