CS3350B Computer Organization Chapter 2: Synchronous Circuits
Part 1: Gates, Switches, and Boolean Algebra
Alex Brandt
Department of Computer Science University of Western Ontario, Canada
Monday February 1, 2021
Alex Brandt
Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 1 / 28
Outline
1 Introduction
2 Logic Gates
3 Boolean Algebra
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 2 / 28
Layers of Abstraction
After looking at high-level CPU and Memory we will now go down to the lowest level (that we care about).
Circuit Design vs Digital (Logic) Design
ë Design of individual circuits vs Using circuits to implement some logic.
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 3 / 28
Circuit Design
Why do we care?
Appreciate the limitations of hardware.
Understand why some things are fast and some things are slow. Need circuit design to understand logic design.
Need logic design to understand CPU Datapath.
If you are ever working with: Assembly, ISAs,
Embedded Systems and circuits, Specialized computer/logic systems,
you will need circuit and logic design.
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 4 / 28
Digital Circuits
Everything is digital: represented by discrete, individual values. ë No gray areas or ambiguity.
Must convert an analog – continuously variable – signal to digital.
For us, the analog signal is electricity (voltage). ë “High” voltage ⇒ 1
ë “Low” voltage ⇒ 0
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 5 / 28
Physicality of Circuits
In the end, everything is a switch. “Input” ⇒ A
“Output” ⇒ Z
If A is 0/false then switch is open.
Alex Brandt
If A is 1/true then switch is closed. This circuit implements:
A≡Z
Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 6 / 28
Transistors: Electrically Controlled Switches
MOS-FET: Metal-Oxide-Semiconductor Field-Effect Transistor
Has a source (S), a drain (D), and a gate (G).
Applying voltage to G allows current to flow between S and D.
In reality, transistors, logic gates, SRAM, use CMOS (Complimentary-MOS). But we don’t care about transistors really…
Flipping a transistor is much faster than moving a physical switch.
ë Speed of switching a transistor directly related to speed of a CPU
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 7 / 28
Outline
1 Introduction
2 Logic Gates
3 Boolean Algebra
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 8 / 28
Logic as Circuits
Propositional Logic: A set of propositions (truth values) combined by some logical connectives.
Truth values ≡ Binary digital signal Logical connectives ≡ Logic gates
Logic Gate: A circuit implementing some logical expression/function. The basics: AND (∧), OR (∨), NOT (¬).
Arity of a function/gate is the number of inputs.
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 9 / 28
Gates as Switches
Both A and B must be true/1 to get the circuit to complete.
Either A or B can be true/1 to get the circuit to complete.
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 10 / 28
Logic Gates In Detail: AND
A B
C
Truth Table for AND
A B A∧B≡C 000 010
A∧B≡C 10 0
A⋅B≡C
111
Alex Brandt
Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 11 / 28
Logic Gates In Detail: OR
A B
C
Truth Table for OR
A B A∨B≡C 000 011
A∨B≡C 10 1
A+B≡C
111
Alex Brandt
Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 12 / 28
Logic Gates In Detail: NOT
AC
Truth Table for NOT
A ¬A≡C 01
¬A≡C10 A≡C
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 13 / 28
More Interesting Logic Gates: NAND
A B
C
Truth Table for NAND
ABA⋅B≡C 001
¬(A∧B)≡C 01 1 101
A⋅B≡C 𝐴⋃︀𝐵
110
Alex Brandt
Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 14 / 28
More Interesting Logic Gates: NOR
A B
C
Truth Table for NOR
ABA+B≡C 001 010 100 110
¬(A ∨ B) ≡ C A+B≡C
Alex Brandt
Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 15 / 28
More Interesting Logic Gates: XOR (Exclusive OR)
A B
C
Truth Table for XOR
A B A⊕B≡C 000 011 101 110
A⊕B≡C
Alex Brandt
Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 16 / 28
Outline
1 Introduction
2 Logic Gates
3 Boolean Algebra
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 17 / 28
The Algebra of Logic Gates
Due to the equivalence of truth values and binary digital signals, Boolean Algebra is heavily used discussing circuitry.
Associativity:
(𝐴+𝐵)+𝐶 ≡𝐴+(𝐵+𝐶) (𝐴⋅𝐵)⋅𝐶 ≡𝐴⋅(𝐵⋅𝐶)
Commutativity:
Identity:
𝐴+0≡𝐴 𝐴⋅1≡𝐴
Annihilation:
𝐴+𝐵≡𝐵+𝐴 𝐴+1≡1 𝐴⋅𝐵≡𝐵⋅𝐴 𝐴⋅0≡0
Distributivity:
𝐴 + (𝐵 ⋅ 𝐶) ≡ (𝐴 + 𝐵) ⋅ (𝐴 + 𝐶) 𝐴 ⋅ (𝐵 + 𝐶) ≡ (𝐴 ⋅ 𝐵) + (𝐴 ⋅ 𝐶)
Idempotence:
𝐴 + 𝐴 ≡ 𝐴 𝐴 ⋅ 𝐴 ≡ 𝐴
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra
Monday February 1, 2021
18 / 28
Boolean Algebra: More Interesting Laws
Absorption:
𝐴 ⋅ (𝐴 + 𝐵) ≡ 𝐴 𝐴 + (𝐴 ⋅ 𝐵) ≡ 𝐴
Double Negation
𝐴≡𝐴 Complementation:
𝐴+𝐴≡1 𝐴⋅𝐴≡0
De Morgan’s Laws:
𝐴+𝐵≡𝐴⋅𝐵 𝐴⋅𝐵≡𝐴+𝐵
Look familiar?
ë Definitions of NOR and NAND.
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 19 / 28
Proving De Morgan’s Laws
Proof by Exhaustion:
ë The easiest way to prove something is to write out each expression’s truth table.
𝐴+𝐵≡𝐴⋅𝐵
ABA+B𝐴+𝐵 AB𝐴𝐵𝐴⋅𝐵 0001 00111 0110 01100 1010 10010 1110 11000
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 20 / 28
Simplifying Expressions with Boolean Algebra (1/2)
𝑥𝑦𝑧 + 𝑥𝑦𝑧
𝑥𝑦𝑧 + 𝑥𝑦𝑧 ≡ 𝑥𝑦(𝑧 + 𝑧) ≡ 𝑥𝑦(1)
≡ 𝑥𝑦
Factor 𝑥𝑦 Complementation of 𝑧 Identity with 𝑥𝑦
𝑥 𝑦 𝑧 𝑥𝑦𝑧 𝑥𝑦𝑧 𝑥𝑦𝑧+𝑥𝑦𝑧 000101 001011 010000
‘011000 100000 101000 110000 111000
Note: 𝐴𝐵 ⇒ 𝐴 ⋅ 𝐵; otherwise use parentheses (𝐴 ⋅ 𝐵) ⇒ 𝐴 ⋃︀ 𝐵.
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 21 / 28
Simplifying Expressions with Boolean Algebra (2/2)
Sometimes a truth table is too challenging… ë For 𝑣 variables a truth table has 2𝑣 rows.
(𝑥 + 𝑧) (𝑎𝑏𝑐𝑑 + 𝑥𝑧) ⇒ 6 variables, 64 rows Instead we can simplify using the laws of Boolean algebra:
(𝑥 + 𝑧) (𝑎𝑏𝑐𝑑 + 𝑥𝑧) ≡ 𝑥𝑧 (𝑎𝑏𝑐𝑑 + 𝑥𝑧) ≡ 𝑥𝑧 (𝑎𝑏𝑐𝑑 + 𝑥𝑧)
≡ 𝑥𝑧
De Morgan’s Law Double negation of 𝑥 and 𝑧 Absorption
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 22 / 28
Simplifying Expressions for Simplified Circuits
𝑦 = ((𝑎𝑏) + 𝑎) + 𝑐
𝑦 ≡ (𝑎𝑏 + 𝑎) + 𝑐 ≡ 𝑎 (𝑏 + 1) + 𝑐 ≡ 𝑎 (1) + 𝑐
≡ 𝑎 + 𝑐
⇓
Factor 𝑎 Annihilaltion Identity
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra
Monday February 1, 2021
23 / 28
Canonical Forms
Different standard or canonical forms.
Conjunctive Normal Form (CNF) ⇒ AND of ORs
ë “Product-of-sums”
Disjunctive Normal Form (DNF) ⇒ ORs of ANDs
ë “Sum-of-products”
CNF (𝑎+𝑏)⋅(𝑎+𝑏)⋅(𝑎+𝑏)
DNF 𝑎𝑏+𝑎𝑏+𝑎𝑏
Every variable should appear in every sub-expression. ë Products for DNF, Sums for CNF.
ë Some authors call this “Full DNF” or “Full CNF”.
Every boolean expression can be converted to a canonical form. DNF more useful and practical ⇒ truth tables.
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 24 / 28
Truth Tables and Disjunctive Normal Forms
We can get a DNF expression directly from a truth table.
𝑎, 𝑏, 𝑐 are inputs, 𝑓 is output.
Create one product term for every entry in the table with 𝑓 ≡ 1. Put 𝑥 in product if 𝑥 is false in that row.
Put 𝑥 in product if 𝑥 is true in that row.
OR all products together.
𝑎𝑏𝑐𝑓
0001 0010 0101 0110 1001 1010 1100 1111
⇒ 𝑎𝑏𝑐+𝑎𝑏𝑐+𝑎𝑏𝑐+𝑎𝑏𝑐
Alex Brandt
Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 25 / 28
Functional Completeness
Functional Completeness – A set of functions (operators) which can adequately describe every operation and outcome in an algebra.
For Boolean algebra the classical set of operators: {+,⋅,¬} is functionally complete but not minimal.
Thanks to De Morgan’s Law we only need one of AND or OR.
The sets {+,¬} and {⋅,¬} are both functionally complete and minimal.
ë minimal – removing any one of the operators would make the set functionally incomplete.
NAND alone is functionally complete; so is NOR alone.
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 26 / 28
NAND is Functionally Complete
NAND alone is functionally complete. NAND ≡ ⋃︀
To prove functional completeness simply show that the operators of the set can mimic the functionality oftheset{+,⋅,¬}.
¬𝑋≡𝑋|𝑋
𝑋⋅𝑌 ≡𝑋|𝑌 ≡(𝑋|𝑌) | (𝑋|𝑌)
𝑋+𝑌 ≡𝑋+𝑌 ≡𝑋⋅𝑌 ≡(𝑋⋃︀𝑋)⋃︀(𝑌⋃︀𝑌)
𝑋𝑋𝑋⋅𝑋𝑋⋅𝑋 0101 1010
𝐴 ≡ 𝑋|𝑌 𝐴|𝐴 1 0 1 0
X Y
0 0
0 1 1010 11 0 1
X Y 𝑋 𝑌 𝑋⋃︀𝑌 00110 01101 10011 11001
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 27 / 28
Summary
Boolean algebra can simplify circuits.
Remove variables that the output does not depend on. Simplifies expression, removing needless gates.
Space and time complexity improved!
Truth tables, canonical forms, functional completeness. Help generating truth tables:
http://turner.faculty.swau.edu/mathematics/
materialslibrary/truth/
Alex Brandt Chapter 2: Synchronous Circuits, Part 1: Gates & Boolean Algebra Monday February 1, 2021 28 / 28