Canonical Form, CL Design

1Learning Outcomes¶

• Practice translating between the three representations for a combinational logic block: truth table, boolean expression, and gate diagram.

• Practice using laws of Boolean Algebra.

• Practice modular design: compose complex circuits using smaller circuits.

Our goal this lecture is to build combinational logic blocks. We can summarize this approach with the following diagram:

Figure 1 shows the three possible representation for a combinational logic block.

• The truth table form is unique—for every combinational logic block, there is only one truth table. The uniqueness of the truth-table makes it a useful way to clearly define the function of a combinational logic block.

• There are multiple Boolean expressions possible for any combinational logic block. Boolean expressions are useful for algebraic manipulation, particularly simplification.

• Multiple gate level representations for any combinational logic blocks. The gate diagram gives us a prescription for converting to an actual transistor circuit; each gate in the diagram can be replaced by a small transistor circuit that achieves is respective gate level function.

This section discusses how to translate between the diferent representations of a combinational logic block. This section ends with how to compose circuits from smaller blocks.

1.1Example: Majority Circuit¶

The equation

has the corresponding truth table

and has the corresponding gate circuit

The equation says that the output y is the OR ($+$) of three terms, where each term is the AND of two input variables ($\cdot$ or concatenation). The correspondence between (1) and the circuit in Figure 2 should be clear. The three product terms are implemented using AND gates and the final sum by the three input OR gate.

We call this a three-input majority circuit because the output y takes on the value that matches the majority of the input values.

2Canonical Form¶

Let’s go back to the truth table as our definition of a desired function. Starting from a truth table, by inspection, it is possible to write a Boolean expression that matches its behavior. The type of Boolean expression that we will write is called the “sum-of-products” canonical form.

The canonical form gets its name from the fact that it is formed by taking the sum (OR) of a set of terms, each term being a product (AND) of input variables or their complements.

• Every place (row) where a 1 appears in the output, we will use a product (AND) term in the Boolean expression.

• Each AND term includes all the input variables in either complemented or uncomplemented form.

• A variable appears in complemented form if it is a 0 in the row of the truth-table, and as a 1 if it appears as a 1 in the row.

3Example: Truth Table $\rightarrow$ Boolean Expression $\rightarrow$ Gate Diagram¶

Any CL circuit that can be practically specified as a truth-table can be represented with a Boolean expression by writing its canonical form. Following that, through algebraic manipulation, it can be simplified, then translated to a circuit of logic gates.

1. Use the truth table to build the canonical form. The canonical form equation has four product terms, one for each of the 1’s in the output $y$.

2. Simplify using Boolean Algebra laws, if needed.

3. Draw the gate diagram. The circuit specified by the canonical form is one of many circuits that implement the original 3-input function.

4Example: Simplify Circuits¶

Simplifying circuits involves taking a gate diagram and writing its Boolean expression, simplifying it, then translating back to a gate diagram.

5Example: Verify Circuit (Majority Circuit, Revisited)¶

In our three-input majority circuit, we can use the truth table to build the canonical form:

We can then use Boolean algebra to verify that the canonical form is equivalent to the intuitive majority circuit equation:

6Example: Gate Diagram $\rightarrow$ Truth Table¶

To generate a truth table from a given circuit, we just need to evaluate the output for all possible input combinations.

Truth Table:

6.12-Bit Compare¶

After some thought, you may have realized that this combinational logic circuit can be described as a compare: Take two inputs and returns 1 if the two inputs are equal and 0 otherwise. We use this functionality in a later example.^[3]

7Composing Circuits: 32-Bit Comparator¶

We would like to a circuit that compares two 32-bit values; this 32-bit compare circuit can be used in our processor to implement the equality comparison for the RV32I instruction beq rs1 rs2 Label.

We’d therefore like to use the 2-bit compare circuit we built in a previous example. We represent the circuit as a combinational logic block, as below. This block helps abstraction; any time you see the block in Figure 6, know it is implemented as the circuit in Figure 4.

By way of comparison, for the 32-bit compare circuit(Figure 5):

• The value A is a 32-bit value, because of the wire bundle (the wire is marked with a notch). Similarly, value B is 32-bits.

• The value z is a 1-bit value.

Functionally, z is 1 only if all of A’s bits are equal to all of B’s bits. In other words, we can perform 32 bitwise comparisons, then AND them together. The underlying circuit for our compare block is therefore as follows: