CS计算机代考程序代写 mips Digital Logic: Boolean Algebra and Gates (contd..)

Digital Logic: Boolean Algebra and Gates (contd..)

HW: Please go through Participation activities on Zybooks before doing Challenge activities!

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

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)

Sum of Products
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
■ XOR Gate
ABY 00 01 10 11
the results of step 2)

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
■

Product of Sums
■ XOR Gate
ABY 000 011 101 110

Examples of SoP and PoS
ABCZ 0001 0011
0101 0111 1001
ABCD 0000 0010
0101 0110 1000 1011 1100 1110
1011 1100 1110

Logical Completeness
ANY truth table AND, OR, and NOT!
1. AND combinations that yield a “1” in the truth table.
Can implement
ABCD 0000 0010
0101 0110 1000 1011 1100 1110
2. OR the results
of the AND gates.
3. Is not necessarily a minimal solution.

De Morgan’s Laws
Two laws:
◆ A’+B’=(AB)’ ◆ A’ B’ = (A+B)’

De Morgan’s Laws
(A + B)’ = A’B’ conversely (AB)’ = A’ + B’
AB 00 01 10 11
“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 00 01 10 11
“Break the line, change the sign”
AB AB A B A+B
11 10 01 00

Even Simpler Logical Completeness
■ Can implement ANY truth table NAND only!
◆ Make NOT out of NAND?
◆ Make OR out of NAND? ◆ MakeA
ND out of NAND?

Two-Way Multiplexer

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

Four-Way Multiplexer
■ n-bit selector and 2n inputs, one output
◆ output equals one of the inputs, depending on
selector
■ “Four-to-one mux”

Multiple Bit Multiplexers (and Buses)

Two-to-Four Decoder
■ n inputs, 2n outputs
◆ exactly one output is 1 for each possible input pattern
■ Uses:
◆ Convert memory or register address to a control line
◆ Convert an opcode to one of n control lines
◆ We will get to this in the MIPS material

Time for some…
■ We currently use decimal system in daily life
(deci=10 digits,0-9)
■ We know..
1+0=1 1+1=2;1+2=3;1+3=4… 1+8=9;
■ What is 1+9=??

Binary Addition and Half-Adder
■ 0+0=0
■ 0+1=1
■ 1+0=1
■ 1+1=…
■ A half-adder can add 2 bits and produces a sum and carry signal
◆ Sum=AxorB ◆ Carry = AB

One-Bit Full Adder
A B Cin Cout S
000 001 010
011 100 101 110 111

Four-Bit Full Adder
Ripple-carry adder

Masking
■ Want to look only at certain bits of a binary word
■ Use a mask to remove the uninteresting bits
■ Example:
◆ Two values: 01001101 and 01001001
◆ If we want to see bit 3 from right, we AND it with 00000100 to get
★ 00000100 and 00000000, respectively.

Building functions from logic gates
■ Combinational Logic Circuit
◆ Output depends only on the current inputs
◆ Stateless (memoryless)
■ Sequential Logic Circuit
◆ Output depends on the sequence of inputs
(past and present)
◆ Stores information (state) from past inputs

Sequential Circuits and Memory

Combinational vs. Sequential
■ Combinational circuit
◆ Always gives the same output for a given set of
■ Sequential circuit
◆ Remembers previous input
◆ Output depends on state and input
inputs
◆ Example: Adder always generates sum and carry, regardless of previous inputs
CSE 12 Fall 2020
31

Sequential Circuits
■ Store information
■ Output depends on stored information (state) plus
input
◆ So a given input might produce different outputs, depending on the stored information
■ Example: ticket counter
◆ Advances when you push the button ◆ Output depends on previous state
CSE 12 Fall 2020
32

State Machine
The basic type of sequential circuit
◆ Combines combinational logic with storage
◆ “Remembers” state, and changes output (and state) based on inputs and current state
State Machine
Inputs Outputs
Combinational Logic Circuit
Storage Elements
CSE 12 Fall 2020
33

Example of State Machine: Traffic Light
CSE 12 Fall 2020
35

State Machine: Overview
CSE 12 Fall 2020
36

State Machine: Traffic Light
Red State
CSE 12 Fall 2020
Green State
Yellow State
Transition Logic:
If Xs change
else remain
Transition Logic:
If Ys change
else remain
Transition Logic:
If Zs change
else remain
37

State Machine: Traffic Light
Red State
● StartoffindefaultstateRed
CSE 12 Fall 2020
Green State
Yellow State
Transition Logic:
If Xs change
else remain
Transition Logic:
If Ys change
else remain
Transition Logic:
If Zs change
else remain
38

State Machine: Traffic Light
Red State
● AfteraspecifiedtimeXsswitchto next state
CSE 12 Fall 2020
Green State
Yellow State
Transition Logic:
If Xs change
else remain
Transition Logic:
If Ys change
else remain
Transition Logic:
If Zs change
else remain
39

State Machine: Traffic Light
Red State
● AfteraspecifiedtimeYsswitchto next state
CSE 12 Fall 2020
Green State
Yellow State
Transition Logic:
If Xs change
else remain
Transition Logic:
If Ys change
else remain
Transition Logic:
If Zs change
else remain
40

State Machine: Traffic Light
Red State
● AfteraspecifiedtimeZsswitchto next state which is Red.
CSE 12 Fall 2020
Green State
Yellow State
Transition Logic:
If Xs change
else remain
Transition Logic:
If Ys change
else remain
Transition Logic:
If Zs change
else remain
41

D Flip-Flops
Memory device
Can be positive triggered or negative triggered (by a clock usually abbreviated by clk) Different types e.g. RS, JK
■
■ ■
Inputs/Outputs:
◆ D: input signal
◆ clk: Clock signal
◆ en:if0Qholdsitsvalue,if1,Q
becomes D at clk edge.
◆ rst: if 1 then Q becomes 0
◆ Q: output signal
CSE 12 Fall 2020
42

D flip-flop(positive-edge) timing diagram
■ Q becomes D at positive clk edge (0 -> 1). ◆ Stores value until next positive clk edge.
■ clk oscillates between 0 and 1 ◆ frequency=1/period
CSE 12 Fall 2020
43

D flip-flop(positive-edge) timing diagram
■ Q becomes D at positive clk edge.
◆ Stores value until next positive clk edge.
■ clk oscillates between 0 and 1 ◆ frequency=1/period
CSE 12 Fall 2020
45

Setup and Hold Time
■
■
Setup time: Time before clock edge where signal has to be stable
Hold time: Time after clock edge where signal has to be stable
CSE 12 Fall 2020
49

Latch
■ ■
Output is equal to Input when clk is high. Stores last value when clk is low.
CSE 12 Fall 2020
50

Latch
■ ■
Output is equal to Input when clk is high. Stores last value when clk is low.
CSE 12 Fall 2020
51

Latch
■ ■
Output is equal to Input when clk is high. Stores last value when clk is low.
CSE 12 Fall 2020
52

Latch
■ ■
Output is equal to Input when clk is high. Stores last value when clk is low.
CSE 12 Fall 2020
53

Latch
■ ■
Output is equal to Input when clk is high. Stores last value when clk is low.
CSE 12 Fall 2020
54

Latch
■ ■
Output is equal to Input when clk is high. Stores last value when clk is low.
CSE 12 Fall 2020
55

One way to make a Flip-Flop: Two Latches
■
■
One latch(master) is connected to clk’ and the other(slave) to clk (positive triggered).
When clk transitions to high, slave captures last value of master which is now stored since it’s clk is low.
CSE 12 Fall 2020
56

One way to make a Flip-Flop: Two Latches
■
When clk transitions to high, slave captures last value of master which is now stored since it’s clk is low.
When clk transitions to low Master is open again but slave is closed, retaining value
■
CSE 12 Fall 2020
59

Reset-Set (RS) Latch – or SR
■ Two inputs: Set and Reset
■ Setto0oneofthetwoinputsatatimetostore
a value, S sets, R clears
■ The transition to 00 generates an undefined output
CSE 12 Fall 2020
61

R-S Latch
CSE 12 Fall 2020
62

R-S Latch Nor Gates
CSE 12 Fall 2020
63

Four SR Latch States: S’ 0, R’ 0
0
0
CSE 12 Fall 2020
1
1
64

Four SR Latch States: S’ 0, R’ 1
0
1
1
CSE 12 Fall 2020
1
0
65

Four SR Latch States: S’ 1, R’ 0
1
1
0
CSE 12 Fall 2020
0
1
66

Four SR Latch States: S’ 1, R’ 1 Memory
1
1
Q = 1, Q’ = 0
CSE 12 Fall 2020
1
0
67

Four SR Latch States: S’ 1, R’ 1 Memory
1
0 1
1
Q = 1, Q’ = 0
CSE 12 Fall 2020
1
0
68

Four SR Latch States: S’ 1, R’ 1 Memory
1
1
Q = 0, Q’ = 1
CSE 12 Fall 2020
0
1
69

Four SR Latch States: S’ 1, R’ 1 Memory
1
1 0
1
Q = 0, Q’ = 1
CSE 12 Fall 2020
0
1
70

D Latch
S’
R’
E/clk D R’ 0 0 1
S’ Q Q’ Comment 1 Q Q’ Keepstate
CSE 12 Fall 2020
71

D Latch
S’
R’
E/clk D R’ 0 0 1 0 1 1
S’ Q Q’ Comment 1 Q Q’ Keepstate 1 Q Q’ Keepstate
CSE 12 Fall 2020
72

D Latch
1
0
R’
1 S’
E/clk D R’ 0 0
0 1
S’ Q Q’
1 Q Q’
1 Q Q’ 11D=Q
1
0
Comment Keep state Keep state
CSE 12 Fall 2020
0
73
1 1 0

D Latch
0
1
R’
0 S’
E/clk D R’ 0 0
0 1
S’ Q Q’
1 Q Q’
1 Q Q’ 11D=Q 00D=Q
1 1
0 1
Comment Keep state Keep state
CSE 12 Fall 2020
0 1
74
1 1 0 1

Other types of memory…
SRAM DRAM
(on-chip usually) (off-chip usually)
NAND FLASH
(on or off-chip, non-volatile)
CSE 12 Fall 2020
76

Memory
Now that we know how to store bits,
we can build a memory – a logical k × m array of stored bits.
• • •
Address Space:
number of locations (usually a power of 2)
Addressability:
number of bits per location (e.g., byte-addressable)
k = 2n locations
m bits
CSE 12 Fall 2020
77

22 x 3 Memory
word WE
word select
input bits
addres
s e
write enabl
address decode
CSE 12 Fall 2020
r
output bits
78

Let’s Build a Computer
CSE 12 Fall 2020
79

Example of State Machine: Traffic Light
CSE 12 Fall 2020
80

State Machine: Overview
CSE 12 Fall 2020
81

Basic Computer
Execute
Control
Memory: Could be Flip Flops, SRAM/DRAM, Flash etc
Execute: Combinational Logic (Adder, Shifter, Rotation etc)
Control: Finite State Machine (combination of sequential and combinational logic circuits)
CSE 12 Fall 2020
Memory
87

Data Path
Combinational Logic
Storage
State Machine
CSE 12 Fall 2020
88

Related Posts