CS计算机代考程序代写 Abstraction & Digital Logic: From Transistors to Gates

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