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 may use Boolean algebra to express, manipulate and potentially simplify logic functions. This section serves as a short introduction for some helpful laws of Boolean algebra. We’ll proof a few of those laws ourselves. For this we use perfect induction and step-by-step apply the axioms given in Table 2.1.1.
Once accomplished, we accept the remaining laws of Table 2.1.2 and use them to simplify a Boolean expression. While our considerations are purely theoretical at this point, it’s key to realize that the functionality of circuits can be expressed through boolean functions. Consequently, respective manipulations and optimizations transfer to hardware design.
Name |
Axiom |
Dual |
|---|---|---|
Binary Field |
\(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\) |
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
Proof \(A + \bar{A} = 1\) using perfect induction. In every step apply only a single axiom. State which axiom you are using.
Proof \(A \cdot A = A\) using perfect induction. In every step apply only a single axiom. State which axiom you are using.
Proof \(\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.
Simplify the expression \(\bar{A}(A+B) + (B+A)(A+\bar{B})\). In each step, state which laws you are using.
2.2. Wires and Gates
In this example we’ll 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 inputs are true.
E is true if at least one of the inputs is true.
F is true if exactly two of the inputs are true.
We may encode the same function in different ways. One such option are truth tables which define 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.
\(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
Finish Table 2.2.1.
Formulate function \(\mathcal{F}(A,B,C) = (D, E, F)\) through Boolean equations, i.e., find Boolean equations which encode the provided textual descriptions.
Design a combinational circuit in Digital which implements the function \(\mathcal{F}\). Label your inputs (A, B and C) and your outputs (D, E, F). Verify your circuit by comparing its Digital-generated truth table with yours.
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., every Boolean function can be expressed by only using NAND gates or by only using NOR gates. We have already proved that {NAND} is universal, lets do the same for {NOR}!
Tasks
Proof the universality of {NOR} using Boolean equations.
Design three circuits in Digital which exclusively use two-input NOR gates to implement the logical operations AND, OR and NOT.
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. If the two inputs are equal, the comparator’s output is 1. If not, it is 0.
Tasks
Implement an equality comparator for the two 4-bit inputs \(A_{[3:0]}\) and \(B_{[3:0]}\) in Digital.
Showcase your design by running a simulation with the following inputs:
\(A_{[3:0]} = 1011_2\) and \(B_{[3:0]} = 1001_2\), and
\(A_{[3:0]} = 1101_2\) and \(B_{[3:0]} = 1101_2\).
2.5. Timing Analysis
This exercise studies three alternative circuits which implement the XOR (exclusive or) function with two inputs. The schematics of the circuits are given 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. The question is if we should favor any of the three circuits and why? Possible criteria might be assembly costs, the resulting power consumption or occupied area in our final piece of hardware. In this exercise we’ll define the best suited circuit as the one with the shortest propagation delay. Further, we’ll derive the contamination delays of the circuits just for the fun of it 😲. The gates’ delays are given in Table 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
Derive the contamination delay \(t_\text{cd}\) for each of the three circuits in Fig. 2.5.1.
Derive the propagation delay \(t_\text{pd}\) for each of the three circuits in Fig. 2.5.1.