Sequential Logic circut design

Computer Organization1 CS1400

Feng Jiang

Boolean algebra

• Reading 2.5 P57-P65 • Axioms and Theorems

• Theorems required P57 P58 T1- T3 • Could derive T6 T7 T8

• De Morgan’s theorems and T9 T10

Boolean algebra

Boolean algebra

Digital Logic Fundamentals

Z = X+Y Z = ——

Z = Z = X + Y— —

NOT all variables Change & to | and | to & NOT the result

De Morgan's theorems

X�Y X�Y

Boolean algebra

Boolean algebra

T8 T3 Duality P59

• Review • Boolean algebra

• Exercise Examples (a)-(e) P61

Day 5

Boolean algebra

• Exercise • P61 • Homework(no submission) • P98-100 2.1 -2.12, 2.14

Boolean algebra

Boolean algebra

Boolean algebra

Less terms is preferred Less variables in one term is preferred “Big not” should be simplified

Boolean algebra De Morgan’s theorems Complement Sum of products <> product of sums

Boolean algebra De Morgan’s theorems

Boolean algebra De Morgan’s theorems

Boolean algebra De Morgan’s theorems Complement Sum of products <> product of sums

• Review • Boolean algebra

• Exercise Examples (a)-(e) P61

Day 5

• Start • K-map

• Review Boolean algebra • (Application of De Morgan’s and Exercise 2 )

• Read • Applications of combinational logic

Day 6

• Review: Axioms and Theorems, solution manual, link, reference

• Karnaugh Map

• Review Boolean algebra (Exercise 2) • (Application of De Morgan’s and Exercise 2 )

• Reading for next class • Applications of combinational logic • Multiplexer ? Adder ? Decoder?

Day 6

• A two-dimensional tool of the truth table • Could be used to simplify Boolean

expressions • Review “truth table” & “minterm” • 2^n lines vs. 2^n cells

Karnaugh Map (K-Map)

KarnaughMaps

Karnaugh Maps

Karnaugh Maps, how to plot

By truth table

By Boolean expression F= A’D+A’BCD+ACD’

Karnaugh Maps, how to plot Examples:

Karnaugh Maps, how to plot Examples:

F= B+A’C F= AB’C +BC

Karnaugh Maps, how to simplify Map the terms Group adjacent cells

*NO diagonal adjacent *torus shaped

Larger group >> less variables in one term

Karnaugh Maps, to simplify Map the terms Group adjacent cells

*NO diagonal adjacent *torus shaped

Larger group >> less variables in one term

Karnaugh Maps, how to simplify Map the terms Group adjacent cells

*NO diagonal adjacent *torus shaped

F=A’B’ + A’BCD+ACD

Karnaugh Maps, how to simplify Map the terms Group adjacent cells

*NO diagonal adjacent *torus shaped

Karnaugh Maps, how to simplify Map the terms Group adjacent cells

*NO diagonal adjacent *torus shaped

Karnaugh Maps, how to simplify Map the terms Group adjacent cells

*NO diagonal adjacent *torus shaped

For a four-variable K-map

Karnaugh Maps, to simplify Map the terms Group adjacent cells

• Start • K-map

• Review Boolean algebra (announce quiz2) • (Application of De Morgan’s and Exercise 2 )

• Read • Applications of combinational logic

Day 6

Boolean algebra Applications of De Morgan’s theorems

Boolean algebra Applications of De Morgan’s theorems

• Product-of-Sum ->Sum-of-Product • (A+B)(A’+C) = AC+A’B+BC =AC+A’B • 2.12 P100

• Sum-of-Product -> Product-of-Sum • 2.14 P100

• F=A’B+AD’ F’=(A’B+AD’)’ F=(F’)’ • F=F’’=(F’)’= ( (A’B+AD’)’ )’

Boolean algebra Applications of De Morgan’s theorems

• Sum-of-Product -> Product-of-Sum • To obtain a product-of-sums expression, it's necessary to

generate the complement of F in a sum-of-products form and then complement it.

Combinational Logic Examples

A+B+C using only NAND gates

f F F F

Combinational Logic Examples

• Multiplexer P34 P84 • Decoder • Adder • Multiplier P64

Multiplexer (MUX) P34 P35

4 to 1 Multiplexer

Multiplexer (MUX)

8 to 1 MUX 1 of 8 multiplexer

8 to 1 MUX and other MUX

BCD to 7–segment control signal

decoder

c0 c1 c2 c3 c4 c5 c6

A B C D

BCD to 7-segment display controller • Understanding the problem • Input is a 4 bit bcd digit (A, B, C, D) • Output is the control signals for the display (7 outputs C0 –

C6) • Block diagram c1c5

c2c4 c6

c0

c3

CS 150 - Fall 2000 - Combinational Examples - 44

A B C D C0 C1 C2 C3 C4 C5 C6 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 – – – – – – – – 1 1 – – – – – – – – –

Formalize the problem

• Truth table • implementation

c1c5

c2c4 c6

c0

c3

2 to 4 Decoder

Adder

Exercise

• Combinational Logic • Sequential Logic (start at Day 9)

Sequential Logic

Every digital system is likely to have combinational circuits, most systems encountered in practice also include storage elements, which require that the system be described in term of sequential logic.

Sequential Logic 50

What We Need: • When inputs change... • Wait until combinational logic has finished and result it stable... • Then sample the output value and save... • Feed the saved output back to the input of the combinational logic

• Make sure the saved output can’t change

• Key idea: we sample the result at the right time, i.e. when it is ready • Only then do we update the stored value

• How do we know when to sample?

• How do we know when the inputs changed?

• How do we know how long to wait?

• A sequential circuit is one whose outputs depend not only on its current inputs, but also on the past sequence of inputs. • In other words, sequential circuits must be able to

“remember” (i.e., store) the past history of the inputs in order to produce the present output. • The information about the previous inputs history is

called the state of the system. • A circuit that uses n binary state variables to store its

past history can take up to 2n different states. • Since n is always finite, sequential circuits are also

called finite state machines (FSM).

Sequential Logic

Sequential Logic 52

"remember"

"load" "data" "stored value"

"0"

"1"

"stored value"

Simplest circuits with feedback • Two inverters form a static memory cell

• will hold value as long as it has power applied

“Latch”

How to get a new value into the memory cell? • selectively break feedback path • load new value into cell

“Latch”

Let’s Use This Latch

• What happens?

X1 X2 • • • Xn

Combinational circuit

Z1 Z2 • • •

Sequential Logic 54

What We Need: • A circuit that can sample a value • A signal that says when to sample

• Edge-triggered D flip-flop (register) • Samples on positive edge of clock • Holds value until next positive edge • Most common storage element

• Clock • Periodic signal, each rising edge signals D flip-flops to sample • All registers sample at the same time

D Q

Sequential Logic 55

Let’s Use This D flip-flop • Does this work? • What do we need to say about the inputs X1, X2, ...? • This is a synchronous sequential circuit

X1 X2 • • • Xn

Combinational circuit

Z1 Z2 • • •

D QD Q

A basic sequential circuit is a flip-flop Flip-flop has two stable states of complementary output values

flip-flop, latch

“Flip-flop” include latches and flip-flops

Flip-flop: Hold, sample at edge of control signal

Latch: Hold, transfer input whenever enabled

RS (set-reset) flip-flop based on two nor gates

RS flip-flop implemented by cross coupling two NOR gates

RS flip-flop (RS Latch)

RS flip-flop (RS Latch)

SR (set-reset) flip-flop based on two nand gates Textbook mistake

RS flip-flop (RS Latch)

RS flip-flop (RS Latch)

Exercise For a given S and R inputs to SR flip-flop, sketch the output signal Q

Q

t

Exercise

Clocked RS Latch (RS with enable)

C C

The D latch: store it and look it up

E

E

The D latch: store it and look it up D

CLK

Input Q Q

The D Latch: store it and look it up • Output depends on clock

• Clock high: Input passes to output • Clock low: Latch holds its output

• Latches are level sensitive and “transparent”

CLK

D

Qlatch

D

CLK

Input Q Q

EDGE-TRIGGERED FLIP FLOPS Characteristics

- State transition occurs at the rising edge or falling edge of the clock pulse

Latches

Edge-triggered Flip Flops (positive)

respond to the input only at this time

respond to the input only during these periods

Edge triggered flip-flop changes only when the clock C changes

Edge triggered flip-flop

The D flip-flop • Input sampled at clock edge • Rising edge: Input passes to output • Otherwise: Flip-flop holds its output

• Flip-flops can be rising-edge triggered or falling-edge triggered

CLK

D

Qff

D

CLK

Input Q Q

D Q Q

CLK

Input Output Output

CLK

D

Qlatch

The D flip-flop

Qlatch

The D flip-flop

CLK

D

Qff

Latch vs. flip-flop

Latch vs. flip-flop

Latch -> Flip Flop

The master-slave D flip-flop

Latch -> Flip Flop

The master-slave D flip-flop

Latch and Flip Flop

The master-slave D flip-flop

Falling edge triggered Rising edge triggered

Latch and Flip Flop

The master-slave D flip-flop

Latch vs. flip-flop

Positive-edge triggered flip-flop changes only on the rising edge of the clock C

Edge triggered flip-flop

EDGE-TRIGGERED FLIP FLOPS P118 Figure 3.25

Ways of clocking flip-flops Ways of clocking flip-flops: 1, Whenever clock is asserted. level-sensitive flip-flop (latch) 2, whenever clock is changing state. Edge-sensitive flip-flop 3,Capture data on one edge of clock and transfer it to the output of the following edge (master-slave flip-flop)

Exercise The input D to a positive-edge triggered flip-flop is shown Find the output signal Q

Q

t

Exercise

Two processors communicating via dual-ported RAM

Two processors communicating via dual-ported RAM

Review: Day 12

Registers: using D flip-flop

D3:0 4 4

CLK

Q3:0

clock

data in may changestable

data out (Q) stable stablestable

Registers • Sample data using clock • Hold data between clock cycles • Computation (and delay) occurs between registers

clock

data in D Q D Q data out

Shift Registers (SIPO)

Shift registers

Shift Registers

Clock pulse needed to store input data? Clock pulse needed to read output data?

PISO example

Preset and clear control signal

The normal data inputs to a flip flop (D, S and R, or J and K) are referred to as synchronous inputs because they have effect on the outputs (Q and not-Q) only in step, or in sync, with the clock signal transitions. These extra inputs that I now bring to your attention are called asynchronous because they can set or reset the flip-flop regardless of the status of the clock signal. Typically, they’re called preset and clear.

Preset and clear control signal The normal data inputs to a flip flop (D, S and R, or J and K) are referred to as synchronous inputs because they have effect on the outputs (Q and not-Q) only in step, or in sync, with the clock signal transitions. These extra inputs that I now bring to your attention are called asynchronous because they can set or reset the flip-flop regardless of the status of the clock signal. Typically, they’re called preset and clear.

Shift registers

Other flip-flops

• JK flip-flops P120 mistake

Other flip-flops

• JK flip-flops P120 read

CLK

Negative Edge triggered JK flip-flop

Summary of flip-flops

Exam 1 coverage

Slide 1-3 Topics: Number system (book4.1 4.2 4.3) Fundamental gates (book 2.2) Boolean algebra (book 2.5) All axioms and theorems (T1-T3) in 2.5.1 Optional: (Karnaugh maps (2.5.4 how to plot, how to simplify)) Multiplexer (book 2.6.1) Adder (Slide 3, book 2.6) BCD decoder (slide 3, book 2.6) RS latch (book 3.1) D latch (book 3.2) D flip-flop (master-slave book 3.3.3 3.3.4) Shift register (book 3.6.1) Counter (synchronous and asynchronous)

Counter

Asynchronous binary up-counter

Counter

Asynchronous binary up-counter

Asynchronous binary down-counter ? (a) Output Q2’Q1’Q0’ (b) Use the Q0’, Q1’ and Q2’ as clocks

Counter

Synchronous binary up-counter

Counter

Synchronous binary down-counter

Counter

An electronic machine which has 1. external inputs 2. externally visible outputs 3. internal state

Output and next state depend on inputs current state

Finite State Machine State machine offers the designer a formal way of specifying, designing, testing and analyzing the sequential circuits.

Finite State Machine State machine offers the designer a formal way of specifying, designing, testing and analyzing the sequential circuits.

The Mealy state machine

The Moore state machine

Finite State Machine State machine offers the designer a formal way of specifying, designing, testing and analyzing the sequential circuits.

State Diagram of RS Latch, D flip-flop

Finite State Machine

Finite State Machine

Finite State Machine Now we need to code the symbols

W=0 W=1

0 1

Finite State Machine

Finite State Machine

Finite State Machine

H

Applications

• Cross walk light

Logicly

• 1, Free one-month trial • 2, https://logic.ly/purchase/ • VGXRM-DKBXB-W2BRR-JKPKD-VXV9F

Sequential Circuit

Setup Time and Hold Time

Applications- Full Adder

Exam 1 coverage

Slide 1-3 Topics: Number system (book4.1 4.2 4.3) Fundamental gates (book 2.2) Boolean algebra (book 2.5) All axioms and theorems (T1-T3) in 2.5.1 Optional: (Karnaugh maps (2.5.4 how to plot, how to simplify)) Multiplexer (book 2.6.1) Adder (Slide 3, book 2.6) BCD decoder (slide 3, book 2.6) RS latch (book 3.1) D latch (book 3.2) D flip-flop (master-slave book 3.3.3 3.3.4) Shift register (book 3.6.1) Counter (synchronous and asynchronous)