Memory Allocation III CSE 351 Autumn 2016
Digital Logic – Combinational
CMPT 295
L25: Combinational Logic
Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification
2
CMPT 295
L25: Combinational Logic
Roadmap
3
car *c = malloc(sizeof(car));
c->miles = 100;
c->gals = 17;
float mpg = get_mpg(c);
free(c);
Car c = new Car();
c.setMiles(100);
c.setGals(17);
float mpg =
c.getMPG();
Java:
C:
Assembly language:
Machine code:
0111010000011000
100011010000010000000010
1000100111000010
110000011111101000011111
Computer system:
OS:
Memory & data
Arrays & structs
Integers & floats
RISC V assembly
Procedures & stacks
Executables
Memory & caches
Processor Pipeline
Performance
Parallelism
CMPT 295
L25: Combinational Logic
3
Why is this important?
Why study hardware design?
Background for other more in-depth classes
Only course in CMPT that deals with hardware
We need some digital systems knowledge to build our own processor
4
CMPT 295
L25: Combinational Logic
Why is this important?
We need some digital systems knowledge to build our own processor
Why build our own processor?
Because we believe computer scientists should have an answer to the question “How does a computer work?”
So you can understand how code is actually executed on a computer
5
CMPT 295
L25: Combinational Logic
Why is this important?
So you can understand how code is actually executed on a computer
Why do we care about how code executes?
Reliability
Performance
Security
6
CMPT 295
L25: Combinational Logic
Hardware Design
Why study hardware design and processors and computers
if you only care about high-level software?
Example of the power of layered abstractions
Transistors -> Combinational Logic
Combinational Logic -> Sequential Logic
Sequential Logic -> Processors
Processors -> Machine Language
Machine Language -> Assembly
Assembly -> High-level Programming Languages
High-level Programming Languages -> Word,Minecraft,Twitter
At each step we can “abstract away” the lower steps and (mostly) forget they exist
7
CMPT 295
L25: Combinational Logic
Synchronous Digital Systems (SDS)
Synchronous:
All operations coordinated by a central clock
“Heartbeat” of the system! (processor frequency)
Digital:
Represent all values with two discrete values
Electrical signals are treated as 1’s and 0’s
1 and 0 are complements of each other
High/Low voltage for True/False, 1/0
Hardware of a processor, such as a RISC-V processor, is an example of a Synchronous Digital System
8
CMPT 295
L25: Combinational Logic
9
CMPT 295
L25: Combinational Logic
9
Historical Trend
10
Trend:
Hardware gets more powerful every year.
(Really due to hard work of thousands of engineers)
Therefore:
Software gets more resources and faster compute!
(And has to keep up with ever-changing hardware)
CMPT 295
L25: Combinational Logic
10
Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification
11
CMPT 295
L25: Combinational Logic
Type of Circuits
Digital Systems consist of two basic types of circuits:
Combinational Logic (CL)
Output is a function of the inputs only, not the history of its execution
e.g. circuits to add A, B (ALUs)
Sequential Logic (SL)
Circuits that “remember” or store information
a.k.a. “State Elements”
e.g. memory and registers (Registers)
12
CMPT 295
L25: Combinational Logic
Logic Gates (1/2)
Special names and symbols:
NOT
AND
OR
a b c
0 0 0
0 1 0
1 0 0
1 1 1
a b c
0 0 0
0 1 1
1 0 1
1 1 1
a c
0 1
1 0
Circle means NOT!
13
CMPT 295
L25: Combinational Logic
Logic Gates (2/2)
Inverted versions are easier to implement in CMOS
NAND
NOR
XOR
a b c
0 0 1
0 1 0
1 0 0
1 1 0
a b c
0 0 0
0 1 1
1 0 1
1 1 0
a b c
0 0 1
0 1 1
1 0 1
1 1 0
14
CMPT 295
L25: Combinational Logic
15
A
B
C
D
Combining Multiple Logic Gates
(NOT(A AND B)) AND (A OR (NOT B AND C))
CMPT 295
L25: Combinational Logic
15
Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification
16
CMPT 295
L25: Combinational Logic
Representations of
Combinational Logic
Text Description
Circuit Diagram
Transistors and wires
Logic Gates
Truth Table
Boolean Expression
All are equivalent
17
CMPT 295
L25: Combinational Logic
Truth Tables
Table that relates the inputs to a combinational logic circuit to its output
Output only depends on current inputs
Use abstraction of 0/1 instead of high/low V
Shows output for every possible combination of inputs
How big?
0 or 1 for each of N inputs, so 2N rows
18
CMPT 295
L25: Combinational Logic
General Form
F
Y
A
B
C
If N inputs, how many distinct functions F do we have?
Function maps each row to 0 or 1, so possible functions
19
A B C
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
Y
F(0,0,0)
F(0,0,1)
F(0,1,0)
F(0,1,1)
F(1,0,0)
F(1,0,1)
F(1,1,0)
F(1,1,1)
0
1
0
0
0
1
1
0
2N
CMPT 295
L25: Combinational Logic
Circle the output, use variables/animations, talk about the output as a bit combination (integer?)
Maybe 3 inputs?
Multiple Outputs
For 3 outputs, just three indep. functions:
X(A,B,C,D), Y(A,B,C,D), and Z(A,B,C,D)
Can show functions in separate columns without
adding any rows!
F
Y
A
B
C
D
X
Z
20
CMPT 295
L25: Combinational Logic
Question: Convert the following statements into
a Truth Table for: (x XOR y) OR (NOT z)
X Y Z (A) (B) (C) (D)
0 0 0 1 1 1 1
0 0 1 0 0 0 0
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 1 1 1
1 0 1 1 1 0 1
1 1 0 1 1 1 0
1 1 1 1 0 1 1
21
CMPT 295
L25: Combinational Logic
21
Question: Convert the following statements into
a Truth Table for: (x XOR y) OR (NOT z)
X Y Z (A) (B) (C) (D)
0 0 0 1 1 1 1
0 0 1 0 0 0 0
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 1 1 1
1 0 1 1 1 0 1
1 1 0 1 1 1 0
1 1 1 1 0 1 1
22
CMPT 295
L25: Combinational Logic
22
More Complicated Truth Tables
3-Input Majority
a b c y
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
2-bit Adder
A B C
a1 a0 b1 b0 c2 c1 c0
.
.
.
+
c1
a1
a0
b1
b0
c2
c0
How many
rows?
23
CMPT 295
L25: Combinational Logic
Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification
24
CMPT 295
L25: Combinational Logic
My Hand Hurts…
Truth tables are huge
Write out EVERY combination of inputs and outputs (thorough, but inefficient)
Finding a particular combination of inputs involves scanning a large portion of the table
There must be a shorter way to represent combinational logic
Boolean Algebra to the rescue!
25
CMPT 295
L25: Combinational Logic
Boolean Algebra
Represent inputs and outputs as variables
Each variable can only take on the value 0 or 1
Overbar or ¬ is NOT: “logical complement”
e.g. if A is 0, A is 1. If A is 1, then ¬A is 0
Plus (+) is 2-input OR: “logical sum”
Product (·) is 2-input AND: “logical product”
All other gates and logical expressions can be built from combinations of these
¬AB + A¬B == (NOT(A AND B)) OR (A AND NOT B)
For slides, will use ¬A
26
CMPT 295
L25: Combinational Logic
Laws of Boolean Algebra
These laws allow us to perform simplification:
27
CMPT 295
L25: Combinational Logic
Demorgan’s law example
27
We can show that these
are equivalent!
Truth Table to Boolean Expression
Read off of table
For 1, write variable name
For 0, write complement of variable
Sum of Products (SoP)
Take rows with 1’s in output column,
sum products of inputs
c=
Product of Sums (PoS)
Take rows with 0’s in output column, product the sum of the complements of the inputs
c =
a b c
0 0 0
0 1 1
1 0 1
1 1 0
28
¬a
b
+
a
¬b
(a + b) · (¬a + ¬b)
CMPT 295
L25: Combinational Logic
Choice between the two generally comes down to whether the output function has more 0’s or 1’s. Choosing the conversion (SoP/PoS) with less items will result in a shorter expression!
(This example happens to be balanced: 2 0’s and 2 1’s)
28
Faster Hardware?
Recall: Everything we are dealing with is just an abstraction of transistors and wires
Inputs propagating to the outputs are voltage signals passing through transistor networks
There is always some delay before a CL’s output updates to reflect the inputs
Simpler Boolean expressions ↔ smaller transistor networks ↔ smaller circuit delays ↔ faster hardware
29
CMPT 295
L25: Combinational Logic
Agenda
Muxes
Sequential Logic Timing
Maximum Clock Frequency
Finite State Machines
Functional Units
Summary
Bonus Slides
Logisim Intro
30
CMPT 295
L25: Combinational Logic
Should be at no later than 10
Data Multiplexor
Multiplexor (“MUX”) is a selector
Place one of multiple inputs onto output (N-to-1)
Shown below is an n-bit 2-to-1 MUX
Input S selects between two inputs of n bits each
31
This input is passed to output if selector bits match shown value
Represents that this wire has n bits
CMPT 295
L25: Combinational Logic
Implementing a 1-bit 2-to-1 MUX
Schematic:
Truth Table:
Boolean Algebra:
Circuit Diagram:
32
s a b c
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
CMPT 295
L25: Combinational Logic
1-bit 4-to-1 MUX (1/2)
Schematic:
Truth Table: How many rows?
Boolean Expression:
e = ¬s1¬s0a + ¬s1s0b + s1¬s0c + s1s0d
33
26
CMPT 295
L25: Combinational Logic
1-bit 4-to-1 MUX (2/2)
Can we leverage what we’ve previously built?
Alternative hierarchical approach:
34
CMPT 295
L25: Combinational Logic
Bonus slides (not testable)
35
CMPT 295
L25: Combinational Logic
Agenda
Combinational Logic
Combinational Logic Gates
Truth Tables
Boolean Algebra
Circuit Simplification
36
CMPT 295
L25: Combinational Logic
Manipulating Boolean Algebra
SoP and PoS expressions can still be long
We wanted to have shorter representation than a truth table!
Boolean algebra follows a set of rules that allow for simplification
Goal will be to arrive at the simplest equivalent expression
Allows us to build simpler (and faster) hardware
37
CMPT 295
L25: Combinational Logic
Boolean Algebraic
Simplification Example
38
CMPT 295
L25: Combinational Logic
Do on black board
From distribution: a(b +1) + c
Froms laws of 0s and 1s: b+1 = b
= ab + c
Truth Table
a b c y
0 0 0 0
0 0 1 1
0 0 1 1
38
Circuit Simplification
(Transistors and/or Gates)
1)
2)
3)
4)
39
CMPT 295
L25: Combinational Logic
Representations of
Combinational Logic
Text Description
Circuit Diagram
Transistors and wires
Logic Gates
Truth Table
Boolean Expression
All are equivalent
40
CMPT 295
L25: Combinational Logic
Try all input
combinations
SoP or PoS
Propagate signals
through gates
Try all input combinations
Converting Combinational Logic
Truth
Table
Boolean
Expression
Circuit
Diagram
This is difficult to do efficiently!
Wire inputs to proper gates
(easiest to use AND, OR, and NOT)
41
CMPT 295
L25: Combinational Logic
Circuit Simplification Example (1/4)
Simplify the following circuit:
Options:
Test all combinations of the inputs and build the Truth Table, then use SoP or PoS
Write out expressions for signals based on gates
Will show this method here
A
B
C
D
42
CMPT 295
L25: Combinational Logic
Circuit Simplification Example (2/4)
Simplify the following circuit:
Start from left, propagate signals to the right
A
B
C
D
A
C
¬B
B
A
AB
¬BC
¬(AB)
A+¬BC
43
Arrive at D = ¬(AB)(A + ¬BC)
CMPT 295
L25: Combinational Logic
Circuit Simplification Example (3/4)
Simplify Expression:
D = ¬(AB)(A + ¬BC)
= (¬A + ¬B)(A + ¬BC) DeMorgan’s
= ¬AA + ¬A¬BC + ¬BA + ¬B¬BC Distribution
= 0 + ¬A¬BC + ¬BA + ¬B¬BC Complementarity
= ¬A¬BC + ¬BA + ¬BC Idempotent Law
= (¬A + 1)¬BC + ¬BA Distribution
= ¬BC + ¬BA Law of 1’s
= ¬B(A + C) Distribution
Which of these
is “simpler”?
44
CMPT 295
L25: Combinational Logic
Circuit Simplification Example (4/4)
Draw out final circuit:
D = ¬BC + ¬BA = ¬B(A + C)
Simplified Circuit:
Reduction from 6 gates to 3!
How many gates
do we need for each?
5
3
A
B
C
D
45
CMPT 295
L25: Combinational Logic
Also only has to go through 2 “stages” worth of gates as opposed to 4 previously.
Longest path here is B → NOT → AND → D. Before one of the longest paths was B → NOT → AND → OR → AND → D.
45