An And-Inverter Graph (AIG) builds every function from two-input AND nodes plus optional inversion on the edges. OR and NAND become AND nodes with inverted inputs or outputs.
One uniform node type makes rewriting simple. The tool matches small AND-inverter patterns and replaces them with cheaper equivalents.
Depth is the longest chain of nodes from an input to the output. It bounds delay: more levels mean more gate delays in series.
Balancing a chain into a tree keeps the gate count and cuts the depth. The calc block uses an EXAMPLE gate delay of 2.0 time units per AND2.
4-wide AND of a, b, c, d
chain: (((a & b) & c) & d) -> 3 AND2 in series, depth 3
tree: (a & b) & (c & d) -> 2 AND2 in parallel then 1 AND2, depth 2
EXAMPLE delay per AND2 = 2.0 time units
chain arrival = 3 x 2.0 = 6.0 time units
tree arrival = 2 x 2.0 = 4.0 time units
gates both ways = 3 AND2 = 3 x 3 = 9 area unitsSharing cuts area by reusing nodes across outputs. Duplication cuts depth by giving each output its own cone, which costs area.
Move | Area effect | Depth effect |
|---|---|---|
Share a sub-expression | Down: built once | Unchanged or up: shared node serves several paths |
Duplicate for speed | Up: one cone per output | Down: each path shortens |
Balance a chain | Same gate count here | Down: levels fall from 3 to 2 |
No rewrite helps on every circuit. Sharing on the critical path can add load, and duplication off it only adds area.
Depth falls from 3 to 2 while the gate count stays at 3. Arrival drops from 6.0 to 4.0 EXAMPLE time units.
The shared node drives extra load, which can slow the critical path. Duplicating it off the path may be cheaper in delay.