Name
Abstract | ||
|---|---|---|
It is well-known that all Boolean functions of n variables can be computed by a logic circuit with O(2n/n) gates (Lupanov's theorem) and that there exist Boolean functions of n variables which require logic circuits of this size (Shannon's theorem). We present corresponding results for Boolean functions computed by VLSI circuits, using Thompson's model of a VLSI chip. We prove that all Boolean functions of n variables can be computed by a VLSI circuit of O(2n) area and period 1, and we prove that there exist Boolean functions of n variables for which every (convex) VLSI chip must have (2n) area. |
Year | DOI | Venue |
|---|---|---|
1983 | 10.1007/3-540-13331-3_55 | Logic and Machines |
Keywords | Field | DocType |
chip,boolean function,and phrases: logic circuit,area,lupanov's theorem,shannon's theorem,period.,vlsi,vlsi complexity | Boolean function,Discrete mathematics,Boolean circuit,Circuit complexity,Computer science,Combinational logic,Boolean expression,Very-large-scale integration,And-inverter graph,Circuit minimization for Boolean functions | Conference |
Volume | ISSN | ISBN |
171 | 0302-9743 | 3-540-13331-3 |
Citations | PageRank | References |
4 | 0.54 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark R. Kramer | 1 | 6 | 2.37 |
| Jan Van Leeuwen | 2 | 2002 | 521.25 |