[Link]

sg/~cs2100/

Lecture #19

Sequential Logic

[Link]
 Lecture #2: Overview of C Programming 1-2

Questions?
IMPORTANT: DO NOT SCAN THE QR CODE IN THE
VIDEO RECORDINGS. THEY NO LONGER WORK

Ask at
[Link]

OR

Scan and ask your questions here!

(May be obscured in some slides)
Aaron Tan, NUS Lecture #19: Sequential Logic 3

6.3 Flip-flop Excitation Tables (1/2)

§ Analysis: Starting from a circuit diagram, derive
the state table or state diagram.
§ Design: Starting from a set of specifications (in
the form of state equations, state table, or state
diagram), derive the logic circuit.
§ Characteristic tables are used in analysis.
§ Excitation tables are used in design.
Aaron Tan, NUS Lecture #19: Sequential Logic 4

6.3 Flip-flop Excitation Tables (1/2)

§ Excitation tables: given the required transition from
present state to next state, determine the flip-flop input(s).
+ +
Q Q J K Q Q S R
0 0 0 X 0 0 0 X
0 1 1 X 0 1 1 0
1 0 X 1 1 0 0 1
1 1 X 0 1 1 X 0
JK Flip-flop SR Flip-flop
+ +
Q Q D Q Q T
0 0 0 0 0 0
0 1 1 0 1 1
1 0 0 1 0 1
1 1 1 1 1 0
D Flip-flop T Flip-flop
Aaron Tan, NUS Lecture #19: Sequential Logic 5

6.4 Sequential Circuits: Design

§ Design procedure:
§ Start with circuit specifications – description of circuit
behaviour, usually a state diagram or state table.
§ Derive the state table.
§ Perform state reduction if necessary.
§ Perform state assignment.
§ Determine number of flip-flops and label them.
§ Choose the type of flip-flop to be used.
§ Derive circuit excitation and output tables from the state
table.
§ Derive circuit output functions and flip-flop input functions.
§ Draw the logic diagram.
Aaron Tan, NUS Lecture #19: Sequential Logic 6

6.4 Design: Example #1 (1/5)

§ Given the following state diagram, design the sequential
circuit using JK flip-flops.

0 Questions:
00 How many flip-flops are needed?
1 How many input variable are
1
there?
1
01 11
0 Answers:
0 Two flip-flops.
1
10 Let’s call them A and B.
One input variable.
0
Let’s call it x.
Aaron Tan, NUS Lecture #19: Sequential Logic 7

6.4 Design: Example #1 (2/5)

§ Circuit state/excitation table, using JK flip-flops.
0
Present Next State
00 State x=0 x=1
1 1 AB A+B+ A+B+
1
00 00 01
01 11 01 10 01
0 10 10 11
0 1 11 11 00
10 Present Next
state Input state Flip-flop inputs
0
+ A B x A+ B+ JA KA JB KB
Q Q J K
0 0 0 0 0 0 X 0 X
0 0 0 X 0 0 1 0 1 0 X 1 X
0 1 1 X 0 1 0 1 0 1 X X 1
1 0 X 1 0 1 1 0 1 0 X X 0
1 0 0 1 0 X 0 0 X
1 1 X 0 1 0 1 1 1 X 0 1 X
JK Flip-flop’s 1 1 0 1 1 X 0 X 0
excitation table. 1 1 1 0 0 X 1 X 1
Aaron Tan, NUS Lecture #19: Sequential Logic 8

6.4 Design: Example #1 (3/5)

§ Block diagram.

A' A B' B
Q' Q Q' Q

K J K J
CP
KA JA KB JB

A' Combinational
A External
B circuit output(s)
B' (none)
x
External
What are to input(s)
go in here?
Aaron Tan, NUS Lecture #19: Sequential Logic 9

6.4 Design: Example #1 (4/5)

§ From state table, get flip-flop input functions.
Present Next B
state Input state Flip-flop inputs Bx
A 00 01 11 10
A B x A+ B+ JA KA JB KB 0 0 0 0 1
0 0 0 0 0 0 X 0 X
0 0 1 0 1 0 X 1 X
A 1 X X X X
0 1 0 1 0 1 X X 1 x
0 1 1 0 1 0 X X 0
1 0 0 1 0 X 0 0 X JA = B∙x'
1 0 1 1 1 X 0 1 X
1 1 0 1 1 X 0 X 0 Bx B
1 1 1 0 0 X 1 X 1 A 00 01 11 10
0 X X X X
Bx B Bx B
A 00 01 11 10 A 00 01 11 10 A 1 0 0 1 0
0 0 1 X X 0 X X 0 1 x
A 1 0 1 X X A 1 X X 1 0 KA = B∙x
x x
JB = x KB = (A Å x)'
Aaron Tan, NUS Lecture #19: Sequential Logic 10

6.4 Design: Example #1 (5/5)

§ Flip-flop input functions:
JA = B∙x' JB = x
KA = B∙x KB = (A Å x)'

§ Logic diagram:
A
B

Q' Q Q' Q

K J K J
CP

x
Aaron Tan, NUS Lecture #19: Sequential Logic 11

6.4 Design: Example #2 (1/3)

§ Using D flip-flops, design the circuit based on the state
table below. (Exercise: Design it using JK flip-flops.)

Present Next
state Input state Output
A B x A+ B+ y
0 0 0 0 0 0
0 0 1 0 1 1
0 1 0 1 0 0
0 1 1 0 1 0
1 0 0 1 0 0
1 0 1 1 1 1
1 1 0 1 1 0
1 1 1 0 0 0
Aaron Tan, NUS Lecture #19: Sequential Logic 12

6.4 Design: Example #2 (2/3)

§ Determine expressions for flip-flop inputs and the circuit
output y.
Bx B
Present Next A 00 01 11 10
state Input state Output 0 0 0 0 1
A B x A+ B+ y DA = A∙B' + B∙x'
A 1 1 1 0 1
0 0 0 0 0 0
0 0 1 0 1 1 x
0 1 0 1 0 0 Bx B
0 1 1 0 1 0 A 00 01 11 10
1 0 0 1 0 0 0
1 0 1 1 1 1 0 1 1 0 DB = A'∙x + B'∙x
1 1 0 1 1 0 A 1 0 1 0 1 + A∙B∙x'
1 1 1 0 0 0
x
Bx B
DA(A,B,x) = S m(2,4,5,6) A 00 01 11 10
DB(A,B,x) = S m(1,3,5,6) 0 0 1 0 0
y = B'∙x
y(A,B,x) = S m(1,5) A 1 0 1 0 0

x
Aaron Tan, NUS Lecture #19: Sequential Logic 13

6.4 Design: Example #2 (3/3)

§ From derived expressions, draw logic diagram:
DA = A∙B' + B∙x'
DB = A'∙x + B'∙x + A.B∙x'
y = B'∙x

D Q A

x
Q' A'

D Q B

Q' B'
CP

y
Aaron Tan, NUS Lecture #19: Sequential Logic 14

6.4 Design: Example #3 (1/4)

§ Design involving unused states.

Are there other

Given these Derive these unused states?
Unused state 000:
0 0 0 0 X X X X X X X X X X
0 0 0 1 X X X X X X X X X X
Aaron Tan, NUS Lecture #19: Sequential Logic 15

6.4 Design: Example #3 (2/4)

§ From state table, obtain expressions for flip-flop inputs.

Cx C Cx C
AB 00 01 11 10 AB 00 01 11 10
00 X X 0 0 00 X X X X
01 0 1 1 0 01 X 0 0 X
B B
11 X X X X 11 X X X X
A A
10 X X X 0 10 0 0 0 1
SA = B∙x RA = C∙x'
x x

Cx C Cx C
AB 00 01 11 10 AB 00 01 11 10
00 X X 1 0 00 X X 0 X
01 X 0 0 0 01 0 1 1 1
B B
11 X X X X 11 X X X X
A A
10 0 0 0 0 10 X X X X

SB = A'∙B'∙x x x RB = B∙C + B∙x

Aaron Tan, NUS Lecture #19: Sequential Logic 16

6.4 Design: Example #3 (3/4)

§ From state table, obtain expressions for flip-flop inputs
(cont’d).
Cx C Cx C
AB 00 01 11 10 AB 00 01 11 10
00 X X 0 X 00 X X 1 0
01 1 0 0 X 01 0 X 1 0
B B
11 X X X X 11 X X X X
A A
SC = x' 10 1 0 0 X 10 0 X 1 0 RC = x
x x

Cx C
AB 00 01 11 10
00 X X 0 0
01 0 0 0 0
B
11 X X X X
A
10 0 1 1 0
y = A∙x
x
Aaron Tan, NUS Lecture #19: Sequential Logic 17

6.4 Design: Example #3 (4/4)

§ From derived expressions, draw the logic diagram:
SA = B∙x SB = A'∙B'∙x SC = x' y = A∙x
RA = C∙x' RB = B∙C + B∙x RC = x
y
x S Q A

R Q' A'

S Q B

R Q' B'

S Q C

R Q'
CP
Aaron Tan, NUS Lecture #19: Sequential Logic 18

7. Memory (1/4)
§ Memory stores programs and data.
§ Definitions:
§ 1 byte = 8 bits
§ 1 word: in multiple of bytes, a unit of transfer between main
memory and registers, usually size of register.
§ 1 KB (kilo-bytes) = 210 bytes; 1 MB (mega-bytes) = 220 bytes;
1 GB (giga-bytes) = 230 bytes; 1 TB (tera-bytes) = 240 bytes.

§ Desirable properties: fast access, large capacity,

economical cost, non-volatile.
§ However, most memory devices do not possess all these
properties.
Aaron Tan, NUS Lecture #19: Sequential Logic 19

7. Memory (2/4)
Memory hierarchy
Fast, expensive
(small numbers),
volatile
registers

main memory

disk storage
Slow, cheap
(large numbers),
magnetic tapes
non-volatile
Aaron Tan, NUS Lecture #19: Sequential Logic 20

7. Memory (3/4)
Data transfer
Address Memory
Up to 2k
addressable 0
Processor 1
locations. 2
k-bit address bus 3
MAR 4
5
n-bit data bus
MDR
:

Control lines
(R/W, etc.)
Aaron Tan, NUS Lecture #19: Sequential Logic 21

7. Memory (4/4)
§ A memory unit stores binary information in groups of bits
called words.
§ The data consists of n lines (for n-bit words). Data input
lines provide the information to be stored (written) into
the memory, while data output lines carry the information
out (read) from the memory.
§ The address consists of k lines which specify which word
(among the 2k words available) to be selected for reading
or writing.
§ The control lines Read and Write (usually combined into
a single control line Read/Write) specifies the direction of
transfer of the data.
Aaron Tan, NUS Lecture #19: Sequential Logic 22

7.1 Memory Unit

§ Block diagram of a memory unit:
n data
input lines
n

k
k address lines Memory unit
2k words
n bits per word
Read/Write

n data
output lines
Aaron Tan, NUS Lecture #19: Sequential Logic 23

7.2 Read/Write Operations

§ Write operation:
§ Transfers the address of the desired word to the address lines.
§ Transfers the data bits (the word) to be stored in memory to the
data input lines.
§ Activates the Write control line (set Read/Write to 0).

§ Read operation:
§ Transfers the address of the desired word to the address lines.
§ Activates the Read control line (set Read/Write to 1).

Memory Enable Read/Write Memory Operation

0 X None
1 0 Write to selected word
1 1 Read from selected word
Aaron Tan, NUS Lecture #19: Sequential Logic 24

7.3 Memory Cell

§ Two types of RAM
§ Static RAMs use flip-flops as the memory cells.
§ Dynamic RAMs use capacitor charges to represent data. Though
simpler in circuitry, they have to be constantly refreshed.
§ A single memory cell of the static RAM has the following
logic and block diagrams:
Select

Select
R

Input S Q Output Input BC Output

Read/Write
Read/Write
Logic diagram Block diagram
Aaron Tan, NUS Lecture #19: Sequential Logic 25

7.4 Memory Arrays (1/4)

§ Logic construction
of a 4´3 RAM (with
decoder and OR
gates):
Aaron Tan, NUS Lecture #19: Sequential Logic 26

7.4 Memory Arrays (2/4)

§ An array of RAM chips: memory chips are
combined to form larger memory.
§ A 1K ´ 8-bit RAM chip:

RAM 1K x 8

Input data 8 DATA (8) (8)

8
Output data
Address 10 ADRS (10)
Chip select CS
Read/write RW

Block diagram of a 1K x 8 RAM chip

Aaron Tan, NUS Lecture #19: Sequential Logic 27

7.4 Memory Arrays (3/4)

Address
Input data
Lines Lines 8 lines
11 10 0–9 0–1023
DATA (8) (8)
ADRS (10)
2x4
CS
decoder RW
1K x 8

S0 0 1024 – 2047
1 DATA (8) (8)
S1 2 ADRS (10)
3 CS
RW
1K x 8

2048 – 3071
Read/write DATA (8) (8)
ADRS (10)
CS
RW
1K x 8

§ 4K ´ 8 RAM. 3072 – 4095

DATA (8) (8)
ADRS (10)
CS
RW
1K x 8 Output
data
Aaron Tan, NUS Lecture #19: Sequential Logic 28

7.4 Memory Arrays (4/4) Read/write control line not

included in this diagram.
21-bit
addresses 19-bit internal chip address
A0
A1

A 19
A 20

2-bit
decoder

512K x 8
512k X 8
memory chip memory chip D 31-24 D 23-16 D 15-8 D 7-0

§ 2M ´ 32 memory module
19-bit 8-bit data
address input/output

§ Using 512K ´ 8 memory chips.

Chip select
Aaron Tan, NUS Lecture #19: Sequential Logic 29

End of File