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)|
|Number of pages||7|
|Journal||IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems|
|State||Published - Sep 1988|
All Science Journal Classification (ASJC) codes
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering