Abstraction & Digital Logic: From Transistors to Gates
CSE12 Winter 2021
1
0 0 0
2
CSE12 Winter 2021
3
CSE12 Winter 2021
5
Boolean Algebra
Imagine a variable x.
x can have only 1 out of 2 values: 0(low) or 1(high)
With such a binary value on x, what type of possible math operations can we come up with?
This is the basis of Boolean algebra.
Boolean algebra is easily implemented by hardware.
Two constants in Boolean Algebra: 1,0; Three fundamental operators: AND (&), OR(+), NOT
CSE12 Winter 2021
6
Axioms of Boolean Algebra
0·0=0 1+1=1 1·1=1 0+0=0 0·1=1·0=0 1+0=0+1=1 ifx=0thenx’=1 ifx=1thenx’=0
Let’s have a closer look at what exactly those transistors were computing in the previous slides!
CSE12 Winter 2021
7
Single-Variable Theorems
x·0=0 x+ 1 = 1 x·1=x x+ 0 = x x·x=x x+ x = x x · x’ = 0 x + x’ = 1 (x’)’ = x
CSE12 Winter 2021
8
Properties of Boolean Algebra
Commutative x · y = y · x x + y = y + x
Associative
x · (y · z) = (x · y) · z x + (y + z) = (x + y) + z
Distributive
x · (y + z ) = x · y + x · z x + y · z = (x + y) · (x + z)
CSE12 Winter 2021
9
Properties of Boolean Algebra
Absorption
x + x · y = x x · (x + y) = x
x
Combining
x · y + x · y’ = x (x + y) · (x + y’) = x
Y(gulp!)
CSE12 Winter 2021
10
Properties of Boolean Algebra
De Morgan’s Laws (x · y)’ = x’ + y’ (x + y)’ = x’y’
Other
x + x’·y = x + y x · (x’ + y) = x · y
CSE12 Winter 2021
11
Basic Logic Gates
CSE12 Winter 2021
XOR
12
XOR gate
CSE12 Winter 2021
13
XOR
Output is
a(XOR)b=a’b+ab’ (for 2 operands)
In general, we say output is
1 if odd number of inputs are 1 0 if even number of inputs are 1
Output is
a(XOR)b=a’b+ab’ (for 2 operands)
In general, we say output is
1 if odd number of inputs are 1 0 if even number of inputs are 1
XOR gate as a “programmable “inverter (NOT gate)
Thus, we can “program” Z to either be inverse of B, or simply be equal to B, depending on the value of A
Above is an alternative symbol for XOR gate as a programmable inverter. But in general, we will stick to the normal XOR gate symbol
CSE12 Winter 2021 14
Sum of Products (SOP)
How do you get from a truth table to a logic expression?
Sum of products is standard way of synthesizing simple circuits
Procedure:
1. Findtherowswiththe‘1’output
2. Writetheproduct-formexpressionfortheinputs
in that row (0=inverted, 1=normal)
3. Combinetheproductsinstep2intoasum(OR
the results of step 2) CSE12 Winter 2021
15
Sum of Products
XOR Gate
ABY 00 01 10 11
CSE12 Winter 2021
1. Findtherowswiththe‘1’ output
2. Writetheproduct-form expression for the inputs in that row (0=inverted, 1=normal)
3. Combinetheproductsin step 2 into a sum (OR the results of step 2)
16
Product of Sums
Procedure:
1. Findtherowswiththe‘0’output
2. Writethesum-formexpressionfortheinputsin
that row (0=normal, 1=inverted)
3. Combinethesumsinstep2intoaproduct
(AND the results of step 2)
Note: we treat 0 and 1 reverse than for SoP
CSE12 Winter 2021
17
Product of Sums
XOR Gate
ABY 000 011 101 110
CSE12 Winter 2021
18
Examples of SoP and PoS
ABCD 0000 0010
0101 0110 1000 1011 1100 1110
CSE12 Winter 2021
ABCZ 0001 0011
0101 0111 1001 1011
1100 1110
19
Logical Completeness
Can implement
ABCD 0000 0010
0101 0110 1000 1011 1100 1110
CSE12 Winter 2021
ANY truth table AND, OR, and NOT!
1. AND combinations that yield a “1” in the truth table.
2. OR the results
of the AND gates.
20
De Morgan’s Laws
Two laws:
A’ + B’ = (AB)’ A’ B’ = (A+B)’
In general for n binary inputs:
A1’ + A2’ + A3’ + ….+ AN = (A1A2A3…AN)’ A1’ A2’A3’…AN’ = (A1+A2+A3+…+AN)’
CSE12 Winter 2021
21
De Morgan’s Laws
(A + B)’ = A’B’ conversely (AB)’ = A’ + B’
CSE12 Winter 2021
22
A B 0 0 0 1 1 0
1 1
“Break the line, change the sign”
A+B A+B A B A·B
11
10
01
00
De Morgan’s Laws
(A + B)’ = A’B’ conversely (AB)’ = A’ + B’
A B 0 0
0 1
1 0
1 1
“Break the line, change the sign”
AB AB A B A+B
11 10 01 00
CSE12 Winter 2021
23
Even Simpler Logical Completeness
Can implement ANY truth table NAND only! Make NOT out of NAND?
Make OR out of NAND? Make AND out of NAND?
CSE12 Winter 2021
24
Two-Way Multiplexer
CSE12 Winter 2021
25
Two-Way Multiplexer
2-way multiplexer: the output is equal to one of the two inputs, based on a selector
SABY 000 001 010 011 100 101 110 111
CSE12 Winter 2021
26
Four-Way Multiplexer
n-bit selector and 2n inputs, one output
output equals one of the inputs, depending on
selector
“Four-to-one mux”
CSE12 Winter 2021
27