Scribd
Upload
38 views31 pages

Question 5

The document discusses the design of a digital system, focusing on the architecture of a soda dispenser and its control logic using a finite state machine (FSM). It outlines the components of the datapath, control path, and the implementation of arithmetic operations such as multiplication. The design process includes mapping data operations to functional blocks and implementing control signals for the system's operation.

Uploaded by

phmthai2300
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
38 views31 pages

Question 5

The document discusses the design of a digital system, focusing on the architecture of a soda dispenser and its control logic using a finite state machine (FSM). It outlines the components of the datapath, control path, and the implementation of arithmetic operations such as multiplication. The design process includes mapping data operations to functional blocks and implementing control signals for the system's operation.

Uploaded by

phmthai2300
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 31

Lecture 22:

System (RTL) Design

CSE 140: Components and Design


Techniques for Digital Systems

Diba Mirza
Dept. of Computer Science and Engineering
University of California, San Diego 1
Design the datapth (2A)
Inputs: c (bit), a (8 bits), s (8 bits) s a
Outputs: d (bit) // '1' dispenses soda
Local storage: tot (8 bits)
tot_ld ld
c tot
Add tot_clr clr
a
Init Wait 8
tot:=tot+a 8 8
d:='0' c'*(tot<s)
c’*(tot<s)’ 8-bit
tot:=0 tot_lt_s 8-bit
< adder
Disp
Datapath 8
SodaDispenser d:='1'
Step 2A
Q: According to the current design, under which of the following conditions
does the register output ‘tot’ change?
A.Whenever the value of the coin inserted (‘a’) changes
B.Whenever the cost of the soda (‘s’) changes
a
C.When the signal tot_ld becomes high
D.When the signal tot_clr becomes high
2
Source: Vahid
Connect data path to controller(2B)
s a
s a
8 8
tot_ld ld
c tot
tot_clr clr
a
tot_ld 8
d 8 8
tot_clr
tot_lt_s 8-bit 8-bit
Controller Datapath < adder
tot_lt_s 8
Datapath

Step 2B Step 2A

3
Source: Vahid
Design control path FSM
s a
8 8
Inputs: c (bit), a (8 bits), s (8 bits)
Outputs: d (bit) // '1' dispenses soda c
Local storage: tot (8 bits)
tot_ld
c d
tot_clr
Add
Init Wait Controller Datapath
tot:=tot+a tot_lt_s

d:='0' c'*(tot<s) Step 2B


c’*(tot<s)’
tot:=0
Disp
Inputs : c, tot_lt_s (bit)
SodaDispenser d:='1' Outputs : d, tot_ld , tot_clr (bit)
c tot_ld
Step 1 c
Add tot_clr
d
Init Wait
tot_ld=1 tot_lt_s
d=0 c' *
tot_lt_s’
c¢*tot_lt_s
tot_clr=1
Disp

Controller d=1

4 Step 2C
Source: Vahid
Implement controller FSM
Inputs : c, tot_lt_s (bit)
Outputs : d, tot_ld , tot_clr (bit)
c tot_ld
c
Add tot_clr
d
tot_lt_s

tot_clr
tot_ld
Init Wait
tot_ld=1 tot_lt_s
s1 s0 c n1 n0 d
d=0 c¢*
tot_lt_s
c¢*tot_lt_s
0 0 0 0 0 1 0 0 1 tot_clr=1
0 0 0 1 0 1 0 0 1 ¢ Disp
Init

0 0 1 0 0 1 0 0 1
Controller d=1
0 0 1 1 0 1 0 0 1
0 1 0 0 1 1 0 0 0
0 1 0 1 0 1 0 0 0 Step 2C
Wait

0 1 1 0 1 0 0 0 0
0 1 1 1 1 0 0 0 0 Use controller (FSM) design
1 0 0 0 0 1 0 1 0
process from previous lectures to
Add

1 1 0 0 0 0 1 0 0 complete the design


Disp

5
Source: Vahid
Datapath components
• Need component library from which to choose

clr I A B A B I I1 I0
ld reg add cmp shift<L/R> mux2x1
Q S lt eq gt Q s0 Q

clk^ and clr=1: Q=0 S = A+B (unsigned) shiftL1: <<1 s0=0: Q=I0
clk^ and ld=1: Q=I A<B: lt=1 shiftL2: <<2 s0=1: Q=I1
else Q stays same A=B: eq=1 shiftR1: >>1
A>B: gt=1 ...

6
Source: Vahid
5.4
More RTL Design
• Additional datapath components
(signed)
W_d
A B A B A clr W_a
sub mul abs inc upcnt W_e
clk^ and W_e=1:
S P Q Q RF[W_a]= W_d
RF R_e=1:
R_a
R_e R_d = RF[R_a]
S = A-B P = A*B Q = |A| clk^ and clr=1: Q=0 R_d
(signed) (unsigned) (unsigned) clk^ and inc=1: Q=Q+1
else Q stays same

7
Source: Vahid
Step 2A: Datapath—Simple Examples
X Y Z X X Y Z X Y Z

k k=0: Preg = Y + Z
Preg = X + Y + Z Preg = Preg + X Preg=X+Y; regQ=Y+Z
k=1: Preg = X + Y
Preg Preg Preg regQ Preg

P P P Q P
(a) (b) (c) (d)
X Y Z X X Y Z X Y Z

DP DP
A B
add1 A B A B A B
S add1 A B A B add1 add2
S add1 add2 S S
X+Y S S

A B 0 clr I I1 I0
add2 1 ld Preg 0 clr I 0 clr I mux2x1
S Q 1 ld Preg 1 ld regQ k s0 Q
X+Y+Z Q Q a

0 clr I 0 clr I
1 ld Preg P P Q 1 ld Preg
Q Q
DP DP

P P

8
Source: Vahid
Design Process
• Describe system in programs
• Data subsystem
– List data operations
– Map operations to functional blocks
– Add interconnect for data transport
– Input control signals and output conditions
• Control Subsystem
– Derive the sequence according to the hardware program
– Create the sequential machine
– Input conditions and output control signals

9
Example: Multiplication
Input X, Y
Arithmetic
Output Z
Z=X × Y Variable M, i
• M=0 • M=0
• For i=n-1 to 0
• For i=n-1 to 0
– If Yn-1=1, M=M+X
– If Yi=1, M=M+X* 2i
– Shift Y left by one bit
• Z=M – If i != 0, shift M left by one
bit
• Z=M

10
Source: CK Cheng
Implementation: Example
Multiply(X, Y, Z, start, done)
{ Input X[15:0], Y[15:0] type bit-vector,
start type boolean;
Local-Object A[15:0], B[15:0] ,M[31:0], i[4:0] type bit-vector;
Output Z[31:0] type bit-vector,
done type boolean;
S0: If start’ goto S0 || done ç1;
S1: A ç X || B ç Y || iç0 || Mç0 || done ç0;
S2: If B15 = 0 goto S4 || içi+1;
S3: M ç M+A;
S4: if i>= 16, goto S6
S5: MçShift(M,L,1) || BçShift(B,L,1) || goto S2;
S6: Z:çM || doneç 1|| goto S0;
}

11
Source: CK Cheng
Step 0: Syntax
S1: A ç X || B ç Y || iç0 || Mç0 || done ç 0;
S2: If B15 = 0 goto S4 || içi+1;
S3: M ç M+A;
S5: MçShift(M,L,1) || BçShift(B,L,1) || goto S2;
S6: Z:çM || doneç 1|| goto S0;

12
Source: CK Cheng
Step 1: Identify Input and Output of data and control subsystems

Multiply(X, Y, Z, start, done) Z=XY


{ Input: X[15:0], Y[15:0] type bit-vector,
start type boolean;
Local-Object : A[15:0], B[15:0] ,M[31:0],
16
i[4:0] type bit-vector; X Data 32
Output Z[31:0] type bit-vector, 16 Z
done type boolean; Y Subsystem
S0: If start’ goto S0 || done ç1;
S1: A ç X || B ç Y || iç0 || Mç0 || done ç0; ? ?
S2: If B15 = 0 goto S4 || içi+1;
S3: M ç M+A;
S4: if i>= 16, goto S6
start Control
S5: MçShift(M,L,1) || BçShift(B,L,1) || goto S2; Subsystem done
S6: Z:çM || doneç 1|| goto S0;
}

13
Source: CK Cheng
Step 2a: Identify Data Subsystem Operations
Multiply(X, Y, Z, start, done)
{ Input: X[15:0], Y[15:0] type bit-vector, Z=XY
start type boolean;
Local-Object : A[15:0], B[15:0] ,M[31:0], 16 32
i[4:0] type bit-vector; X Data
Output Z[31:0] type bit-vector, 16 Z
done type boolean; Y Subsystem
S0: If start’ goto S0 || done ç1;
S1: A ç X || B ç Y || iç0 || Mç0 || done ç 0; ? ?
S2: If B15 = 0 goto S4 || içi+1;
S3: M ç M+A;
Control
S4: if i>= 16, goto S6 start
S5: MçShift(M,L,1) || BçShift(B,L,1) || goto S2; Subsystem done
S6: Z:ç M || doneç 1|| goto S0;
}

14
Source: CK Cheng
Step 2b: Map Data Operations to functional modules in data library

Multiply(X, Y, Z, start, done)


{ Input: X[15:0], Y[15:0] type bit-vector, operation
start type boolean;
A ß X A ß Load (X)
Local-Object : A[15:0], B[15:0] ,M[31:0],
i[4:0] type bit-vector;
B ßY B ß Load (Y)
Output Z[31:0] type bit-vector, Mß0 Mß Clear(M)
done type boolean; iß0 iß Clear(i)
S0: If start’ goto S0 || doneç1; ißi+ 1 i ß INC(i)
S1: A ç X || B ç Y || iç0 || Mç0 || done ç 0; MßM+A Mß Add(M,A)
S2: If B15 = 0 goto S4 || içi+1; MßShift(M,L,1) M ß SHL(M)
S3: M ç M+A; BßShift(B,L,1) B ß SHL(B)
S4: if i>= 16, goto S6
Z:ßM Wires
S5: MçShift(M,L,1) || BçShift(B,L,1) || goto S2;
S6: Z:ç M || doneç 1|| goto S0;
}

15
Source: CK Cheng
Step 2c: Implement the data subsystem
D

Registers: If C then R ç D C LD

R
operation
A ß Load (X)
B ß Load (Y)
B ß SHL(B)
Mß Clear(M)
Mß Add(M,A)
M ß SHL(M)
iß Clear(i)
i ß INC(i)

16
Source: CK Cheng
Function Modules: Registers to store data (A, B, M)

Register A Register M
operation
A ß Load (X) X D R D R
A M
B ß Load (Y) 16 LD 16 LD CLR
B ß SHL(B)
C0
C1 C2
Mß Clear(M)
Mß Add(M,A)
M ß SHL(M) Register B
iß Clear(i) 16
i ß INC(i) Y D R
LD B B[15]

C3
17
Source: CK Cheng
Function Modules: Adder, Shifter (updates to M)

A Selector
Register A Register M
Adder
operation B S 0
A ß Load (X) X D R D R
A M
B ß Load (Y) 16 LD 16 LD CLR
1
B ß SHL(B)
C0 <<
Mß Clear(M)
SHL
C4 C1 C2
Mß Add(M,A)
M ß SHL(M) Register B
iß Clear(i) 16
i ß INC(i) Y D R
LD B B[15]

C3
18
Source: CK Cheng
Function Modules: Adder, Shifter (updates to B)
operation
A ß Load (X)
B ß Load (Y)
B ß SHL(B) A
Register A Selector Register M
Mß Clear(M) Adder
Mß Add(M,A) B S 0
X D R D R
M ß SHL(M) A M
16 LD 16 LD CLR
iß Clear(i) 1
i ß INC(i)
C0 <<
SHL
C4 C1 C2

16 Selector Register B
Y
0
D R B B[15]
<<
1 LD
SHL
C5 C3
19

Source: CK Cheng
Function Modules: Counter (updates to i)
operation
A ß Load (X)
B ß Load (Y)
B ß SHL(B) A
Register A Selector Register M
Mß Clear(M) Adder
Mß Add(M,A) B S 0
X D R D R
M ß SHL(M) A M
16 LD 16 LD CLR
iß Clear(i) 1
i ß INC(i)
C0 <<
SHL
C4 C1 C2

16 Selector Register B
Y
0
D R B B[15] Counter i
<< D R
1 LD
SHL
CLR Inc i[4]
C5 C3
C6 C7 20

Source: CK Cheng
Step 2d: Map Control Signals to Operations

operation
A ß Load (X) C0=1
B ß Load (Y) C5=0 and C3 =1
A
B ß SHL(B) C5=1 and C3 =1 Register A Selector Register M
Mß Clear(M) C2 =1
Adder
B S 0
Mß Add(M,A) C4=0 and C1=1X D R D R
M ß SHL(M) C4=1 and C1=1 16 A M
LD 16 LD CLR
iß Clear(i) C6=1 1
i ß INC(i) C7=1 C0 <<
SHL
C4 C1 C2

16 Selector Register B
Y
0
D R B B[15] Counter i
<< D R
1 LD
SHL
CLR Inc i[4]
C5 C3
C6 C7 21

Source: CK Cheng
16 32
X Data
16 Z
Y Subsystem
B[15], i[4] C0:7

Control
start
Subsystem done

22
Source: CK Cheng
Design the Control Subsystem
Multiply(X, Y, Z, start, done)
{
S0: If start’ goto S0 || doneß1;
S1: Aß X || B ßY || iß0 || Mß0 || done ß0;
S2: If B15 = 0 goto S4 || ißi+1;
S3: M ßM+A; operation
S4: if i>= 16, goto S6 A ß Load (X) C0=1
S5: MßShift(M,L,1) || BßShift(B,L,1) || goto S2; B ß Load (Y) C5=0 and C3 =1
S6: Z:ßM || doneß1|| goto S0 B ß SHL(B) C5=1 and C3 =1
} Mß Clear(M) C2 =1
Mß Add(M,A) C4=0 and C1=1
Multiply(X, Y, Z, start, done) M ß SHL(M) C4=1 and C1=1
{ iß Clear(i) C6=1
S0: If start’ goto S0 || doneß1; i ß INC(i) C7=1
S1: C0=1 || C5=0 and C3 =1 || C6=1|| C2 =1 || done ß0;
S2: If B15 = 0 goto S4 || C7=1;
S3: C4=0 and C1=1;
S4: if i[4], goto S6
S5: C4=1 and C1=1|| C5=1 and C3 =1 || goto S2;
S6: Z:ßM || doneß1|| goto S0 23
} Source: CK Cheng
Control Subsystem
S6
S0
start’
Multiply(X, Y, Z, start, done) start
{
S0: If start’ goto S0 || doneß1; S1 S5
S1: C0=1 || C5=0 and C3 =1 || C6=1|| C2 =1 || done ß0;
S2: If B15 = 0 goto S4 || C7=1;
S3: C4=0 and C1=1;
S2 i[4]
S4: if i[4], goto S6 i[4]’
S5: C4=1 and C1=1|| C5=1 and C3 =1 || goto S2;
S6: Z:ßM || doneß1|| goto S0 B[15] B[15]’
}
S3 S4

24
Source: CK Cheng
One-Hot State
Machine

S6
S0
start’
start
S1 S5

S2 i[4]’ i[4]

B[15] B[15]’
S3 S4

25
Source: CK Cheng
One-Hot State
Machine start’
S0

start

S6
S0
start’
start S1
S1 S5 S6

S2 S2
i[4]’ i[4]
B[15] B[15]’ B15’ B15
i[4]
S3 S4 S5
S4
S3

i[4]’

26
Source: CK Cheng
Control Subsystem: One-Hot State
Machine Design
Input: State Diagram
1.Use a flip flop to replace each state.
2.Set the flip flop which corresponds to the initial
state and reset the rest flip flops.
3.Use an OR gate to collect all inward edges.
4.Use a Demux to distribute the outward edges.

27
Source: CK Cheng
Data Subsystem

A
Register A Selector Register M
Adder
B S 0
X D R D R
A M
16 LD 16 LD CLR
1
C0 <<
SHL
C4 C1 C2

16 Selector Register B
Y
0
D R B B[15] Counter i
<< D R
1 LD
SHL
CLR Inc i[4]
C5 C3
C6 C7 28

Source: CK Cheng
Multiply(X, Y, Z, start, done)
{
S0: If start’ goto S0 || doneß1;
S1: C0=1 || C5=0 and C3 =1 || C6=1|| C2 =1 || done ß0;
S2: If B15 = 0 goto S4 || C7=1;
S3: C4=0 and C1=1;
S4: if i[4], goto S6
S5: C4=1 and C1=1|| C5=1 and C3 =1 || goto S2;
S6: Z:ßM || doneß1|| goto S0
}
C0 C1 C2 C3 C4 C5 C6 C7 done
(mux) (mux)
S0 0 0 0 0 X X 0 0 1
S1 1 0 1 0 X 0 1 0 0
S2 0 0 0 1 X X 0 1 0
S3 0 1 0 0 0 X 0 0 0
S4 0 0 0 0 X X 0 0 0
S5 0 1 0 1 1 1 0 0 0
S6 0 0 0 0 X X 0 0 1
29
Source: CK Cheng
C0 C1 C2 C3 C4 C5 C6 C7 done
(mux) (mux)
S0 0 0 0 0 X X 0 0 1
S1 1 0 1 0 X 0 1 0 0
S2 0 0 0 1 X X 0 1 0
S3 0 1 0 0 0 X 0 0 0
S4 0 0 0 0 X X 0 0 0
S5 0 1 0 1 1 1 0 0 0
S6 0 0 0 0 X X 0 0 1
30
Source: CK Cheng
One-Hot State
Machine start’
S0

S6 start
S0
start’
start
S1 S5 S1
S6

S2 i[4]
i[4]’ S2
B[15] B[15]’
B15’ B15

S3 S4 i[4]
S5
S4
S3

i[4]’

31
Source: CK Cheng

You might also like