2. Basics of Logic Design

This lab serves as a crash course on the basics of logic design, i.e. truth tables, Boolean equations and schematics of logic circuits. Section 2.4 closes the lab by discussing the timing of three alternative circuits for the exclusive-or function.

2.1. Boolean Algebra

We use Boolean algebra to express, manipulate, and potentially simplify logic functions. This section briefly introduces helpful laws of Boolean algebra. We’ll prove a few of these laws ourselves. To do so, we use perfect induction and apply the axioms in Table 2.1.1 step by step.

Afterward, we accept the remaining laws in Table 2.1.2 and use them to simplify a Boolean expression. Although our discussion is theoretical at this point, circuit functionality can be expressed through Boolean functions. Consequently, these manipulations and optimizations carry over to hardware design.

Table 2.1.1 Axioms of Boolean algebra.

Name	Axiom	Dual
Boolean domain	\(A=0\;\text{if}\;A\neq1\)	\(A=1\;\text{if}\;A\neq0\)
NOT	\(\bar{0}=1\)	\(\bar{1}=0\)
OR/AND	\(0+0=0\)	\(1\cdot1 = 1\)
OR/AND	\(1+1=1\)	\(0\cdot0 = 0\)
OR/AND	\(0+1 = 1+0=1\)	\(0\cdot1 = 1\cdot0 = 0\)

Table 2.1.2 Helpful laws of Boolean algebra.

Name	OR Form	AND Form
Identity	\(A+0=A\)	\(A \cdot 1=A\)
Null Element	\(A+1=1\)	\(A \cdot 0 = 0\)
Idempotency	\(A+A=A\)	\(A \cdot A = A\)
Inverse	\(A+\bar{A}=1\)	\(A \cdot \bar{A}=0\)
Double Complement	\(\bar{\bar{A}} = A\)
Commutativity	\(A+B=B+A\)	\(A \cdot B = B \cdot A\)
Associativity	\(A+(B+C)=(A+B)+C\)	\(A \cdot (B \cdot C) = (A \cdot B) \cdot C\)
Distributivity	\(\begin{align}&A \cdot (B+C) \\= &(A \cdot B) + (A \cdot C )\end{align}\)	\(\begin{align}&A+(B \cdot C) \\= &(A+B) \cdot (A+C)\end{align}\)
DeMorgan	\(\overline{A + B} = \bar{A} \cdot \bar{B}\)	\(\overline{A \cdot B} = \bar{A} + \bar{B}\)

Tasks

1. Prove \(A + \bar{A} = 1\) using perfect induction. Apply only one axiom per step and name it.

2. Prove \(A \cdot A = A\) using perfect induction. In every step apply only a single axiom. State which axiom you are using.

3. Prove \(\overline{A + B} = \bar{A} \cdot \bar{B}\) using perfect induction. In every step apply only a single axiom. State which axiom you are using.

4. Simplify \(\bar{A}(A+B) + (B+A)(A+\bar{B})\). State the law used in each step.

2.2. Wires and Gates

In this example, we implement the Boolean function \(\mathcal{F}(A,B,C) = (D, E, F)\) with the three inputs A, B, and C, and the three outputs D, E and F. The function is defined through the following textual description:

• D is true if all three inputs are true.

• E is true if at least one input is true.

• F is true if exactly two inputs are true.

We may encode the same function in different ways. One option is a truth table which defines the respective outputs for every possible combination of the inputs. An incomplete truth table for the studied function \(\mathcal{F}\) is provided in Table 2.2.1.

Table 2.2.1 Incomplete truth table for the studied function \(\mathcal{F}\).

\(A\)	\(B\)	\(C\)	\(D\)	\(E\)	\(F\)
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0
0	1	1	0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Another possible option are Boolean equations. For example, we could define \(D\) as \(D(A,B,C) = A \cdot B \cdot C\). Lastly, we may consider using schematics and express our function by the means of gates and connecting wires. This gate-based representation will lead to actual hardware designs as discussed in the labs to come.

Tasks

1. Complete Table 2.2.1.

2. Formulate function \(\mathcal{F}(A,B,C) = (D, E, F)\) through Boolean equations, i.e., find Boolean equations which encode the provided textual descriptions.

3. Design a combinational circuit in Digital that implements the function \(\mathcal{F}\). Label the inputs (A, B and C) and outputs (D, E, F). Verify the circuit by comparing Digital’s truth table with yours.

4. If not already done in the previous task: Design a similar circuit which only uses two-input gates.

2.3. Universal Gates

As discussed in the lectures, {NAND} and {NOR} are universal, i.e. any Boolean function can be expressed using only NAND gates or only NOR gates. We have already proved that {NAND} is universal, let’s do the same for {NOR}!

Tasks

1. Prove the universality of {NOR} using Boolean equations.

2. In Digital, implement the logical operations AND, OR and NOT using only two-input NOR gates.

2.4. Equality Comparator

Fig. 2.4.1 4-bit equality comparator.

Fig. 2.4.1 shows the symbol of a 4-bit equality comparator. An N-bit equality comparator determines if two N-bit inputs are equal or not. The output is 1 if the inputs are equal, and 0 otherwise.

Tasks

1. Implement an equality comparator for the two 4-bit inputs \(A_{[3:0]}\) and \(B_{[3:0]}\) in Digital.

2. Showcase your design by running a simulation with the following inputs:

   1. \(A_{[3:0]} = 1011_2\) and \(B_{[3:0]} = 1001_2\), and

   2. \(A_{[3:0]} = 1101_2\) and \(B_{[3:0]} = 1101_2\).

2.5. Timing Analysis

This exercise analyzes three alternative circuits that implement the two-input XOR (exclusive or) function. The circuit schematics are shown in Fig. 2.5.1.

Fig. 2.5.1 Schematics of three circuits implementing the two-input XOR function.

Assume that we got our hands on a bunch of gates. Which circuit should we prefer, and why? Possible criteria include assembly costs, power, or area in our final piece of hardware. We define the “best” circuit as the one with the shortest propagation delay \(t_\text{cd}\). Further, we’ll derive the contamination delays of the circuits for completeness. The gates’ delays are given in Table 2.5.1.

Table 2.5.1 Assumed gate delays used to derive the contamination and propagation delays of the circuits in Fig. 2.5.1.

Gate	\(t_\text{cd}\)	\(t_\text{pd}\)
NOT	10 ps	15 ps
AND	25 ps	30 ps
OR	30 ps	40 ps
NOR	25 ps	30 ps

Tasks

1. For each circuit in Fig. 2.5.1, derive the contamination delay \(t_\text{cd}\).

2. For each circuit in Fig. 2.5.1, derive the propagation delay \(t_\text{pd}\).