Lesson 2

Formally, a circuit is a directed acyclic graph where each vertex has in-degree zero or two. Vertices with in-degree zero are called gates and are labeled with variables \(x_{1}, \dotsc, x_{n}\). Vertices with in-degree two are called inputs and are labeled with Boolean operations from \(\Omega\) and given unique identifiers.

We will primarily measure efficiency by the size, that is, the number of gates. In practice, one also considers the depth, defined as the length of the longest directed path from an input to an output, which serves as a crude model of the circuit's delay.

Later in this section, we will synthesize efficient circuits. Below, we discuss the circuit description format using our previous example of the Full Adder.

3 5 2
x1 x2 x3
a x1 x2 0110
b x2 x3 0110
c a b 0111
w0 a x3 0110
w1 c w0 0110
w0 w1

The first three numbers specify the number of inputs, the number of gates, and the number of outputs in the circuit. The second line records the input labels. Each of the following lines specifies the next gate: its label, its two predecessors, and the truth table for the binary operation it computes. Finally, the last line records the labels of the output gates (the gate computing the least significant bit of the sum comes first).