232 Week 7 Algorithmic State Machines v1 2 PDF

Preview

Summary

Download 232 Week 7 Algorithmic State Machines v1 2 PDF

Description

Week-7

Design at the Register Transfer Level Algorithmic State Machines

Algorithmic State Machine (ASM) q฀ 

q฀ 

Spring'11

Our design methodologies do not scale well to real-world problems. …

232 - Logic Design / Algorithmic State Machines (ASM)

2

Algorithmic State Machine (ASM) q฀ 

q฀ 

q฀ 

Procedure for implementing a problem with a given piece of equipment. Define ”digital algorithmic solutions” for hardware. Resembles a conventional flow chart but interpreted differently: ◦  ASM describes the sequence as well as the timing of events. ◦  Adapted to specify the control sequence and data processing operations.

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

3

q฀  A

Control and Datapath

digital system can be split into two components: q฀ 

Datapath: Manipulates data according to the system requirements. q฀  Control (Unit/Logic): Generates the signals for sequencing the operations in the data processor.

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

4

State Box

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

5

Decision Box

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

6

Conditional Box

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

7

Spring'11

ASM Block

q฀ 

One entrance path

q฀ 

Any number of exit paths

q฀ 

Describes the state of the system during one clock-pulse interval.

q฀ 

The operations within the state and the conditional boxes are all executed with a common clock pulse while the system is in state T1.

232 - Logic Design / Algorithmic State Machines (ASM)

8

ASM chart – State diagram

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

9

Timing

§฀ 

All the following operations occur simultaneously (in parallel): §฀  A ß฀ A+1 §฀  If E == 1 then R ß฀ 0 §฀  Depending on the values of E and F, the state is changed to T2, T3 or T4.

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

10

Design Problem q฀ 

q฀ 

Design a digital system with two flip-flops, E and F, and one 4-bit binary counter, A. The individual flipflops of A are denoted by A4, A3, A2, and A1 (where A4 holding the MSB). A start signal S initiates system operation by clearing the counter A and the flip-flop F. The counter is then incremented by 1 starting from the next clock pulse and continues to increment until the operations stop. Counter bits A3 and A4 determine the sequence of operations: ◦  If A3 == 0, E is cleared to 0 and the count continues. ◦  If A3 == 1, E is set to 1; then if A4 == 0, the count continues, but if A4 == 1, F is set to 1 on the next clock pulse and the system stops counting.

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

11

Control & Datapath Status Signals

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

12

ASM Chart q฀ 

Design a digital system with two flipflops, E and F, and one 4-bit binary counter, A. The individual flip-flops of A are denoted by A4,A3,A2, and A1 (where A4 holding the MSB).

q฀ 

A start signal S initiates system operation by clearing the counter A and the flip-flop F. The counter is then incremented by 1 starting from the next clock pulse and continues to increment until the operations stop. Counter bits A3 and A4 determine the sequence of operations: ◦  If A3 == 0, E is cleared to 0 and the count continues. ◦  If A3 == 1, E is set to 1; then ◦  if A4 == 0, the count continues, ◦  but if A4 == 1, F is set to 1 on the next clock pulse and the system stops counting.

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

13

Sequence of Operations Counter

Flip-flops

A4

A3

A2

A1

E

F

0

0

0

0

1

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

1

0

0

Conditions

State

A3=0, A4=0

T1

L1

L1, L3

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

L2

14

Sequence of Operations Counter

Spring'11

Flip-flops

Conditions

State

A3=0, A4=0

T1

A4

A3

A2

A1

E

F

0

0

0

0

1

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

1

1

0

0

0

1

0

0

0

0

0

1

0

1

1

0

0

1

1

0

1

0

0

1

1

1

1

0

1

0

0

0

1

0

1

0

0

1

0

0

1

0

1

0

0

0

1

0

1

1

0

0

1

1

0

0

0

0

1

1

0

1

1

0

T2

1

1

0

1

1

1

T0

A3=1, A4=0

A3=0, A4=1

232 - Logic Design / Algorithmic State M

The Datapath

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

16

The Datapath

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

17

State Diagram for Control

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

18

State Table Present state symbol

Spring'11

Present state

Inputs

Next state

Outputs

G0

G1

S

A3

A4

G0

G1

T0

T1

T2

T0

0

0

0

X

X

0

0

1

0

0

T0

0

0

1

X

X

0

1

1

0

0

T1

0

1

X

0

X

0

1

0

1

0

T1

0

1

X

1

0

0

1

0

1

0

T1

0

1

X

1

1

1

1

0

1

0

T2

1

1

X

X

X

0

0

0

0

1

232 - Logic Design / Algorithmic State Machines (ASM)

19

State Table Present state symbol

Inputs

Next state

Outputs

G0

G1

S

A3

A4

G0

G1

T0

T1

T2

T0

0

0

0

X

X

0

0

1

0

0

T0

0

0

1

X

X

0

1

1

0

0

T1

0

1

X

0

X

0

1

0

1

0

T1

0

1

X

1

0

0

1

0

1

0

T1

0

1

X

1

1

1

1

0

1

0

T2

1

1

X

X

X

0

0

0

0

1

q฀ 

DG0 = T1 A3 A4 DG1 = T0 S + T1

q฀ 

T0 = G1’

q฀ 

T1 = G0’ G1

q฀ 

T2 = G0

q฀ 

Spring'11

Present state

232 - Logic Design / Algorithmic State Machines (ASM)

20

Control Logic

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

21

Control Logic

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

22

Recall q฀  q฀  q฀ 

Spring'11

What’s an ASM? What are the components? What’s the design procedure?

232 - Logic Design / Algorithmic State Machines (ASM)

23

q฀ 

Binary Multiplier

How do we do multiplication by hand? In binary? 1

0

1

1

1

multiplicand

1

0

0

1

1

multiplier

---------------------------------

1

1

0

1

1

1

0

1

1

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

--------------------------------1

Spring'11

1

0

1

1

0

1

0

1

product

232 - Logic Design / Algorithmic State Machines (ASM)

24

High-Level View

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

25

Datapath for Binary Multiplier 1

0

1

1

1

0

0

1

1 1

§฀  Sum only two binary numbers accumulating

1

§฀  Instead of shifting the multiplicand to the

-----------------------

1

0

1

0

1

1

1

0

1

1

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

the partial sums in Register Q. left, shift the product to the right

§฀ 

----------------------1

Spring'11

1

0

1

1

0

1

0

1

232 - Logic Design / Algorithmic State Machines (ASM)

26

§฀ 

ASM for Binary Multiplier

P: the number of bits in the registers

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

27

Initial State Z=0

Register B

10111 ! =1

101 ! P

Spring'11

0 !

00000 !

10011 !

C

Register A

Register Q

232 - Logic Design / Algorithmic State Machines (ASM)

28

Q0 = 1; add B –

first partial product

10111! 00000! +------! 0 10111! Z=0

Register B

10111 ! =1

100 ! P

Spring'11

0 !

10111 !

10011 !

C

Register A

Register Q

232 - Logic Design / Algorithmic State Machines (ASM)

29

Shift Right CAQ Z=0

Register B

10111 ! =1

100 ! P

Spring'11

0 !

01011 !

! 11001

C

Register A

Register Q

232 - Logic Design / Algorithmic State Machines (ASM)

30

Q0 = 1; add B –

second partial product

10111! 01011! +------! 1 00010! Z=0

Register B

10111 ! =1

011 ! P

Spring'11

1 !

00010 !

! 11001

C

Register A

Register Q

232 - Logic Design / Algorithmic State Machines (ASM)

31

Shift right CAQ Z=0

Register B

10111 ! =1

011 ! P

Spring'11

1 !

10001 !

! 01100

C

Register A

Register Q

232 - Logic Design / Algorithmic State Machines (ASM)

32

Q0 = 0; Shift right CAQ Z=0

Register B

10111 ! =0 010 ! P

Spring'11

1 !

01000 !

! 10110

C

Register A

Register Q

232 - Logic Design / Algorithmic State Machines (ASM)

33

Q0 = 0; Shift right CAQ Z=0

Register B

10111 ! =0 001 ! P

Spring'11

! 0

00100 !

! 01011

C

Register A

Register Q

232 - Logic Design / Algorithmic State Machines (ASM)

34

Q0 = 1; Add B 10111! 00100! +------! 0 11011!

–

fifth partial product

Z=0

Register B

10111 ! =1 000 ! P

Spring'11

! 0

11011 !

! 01011

C

Register A

Register Q

232 - Logic Design / Algorithmic State Machines (ASM)

35

Shift right CAQ Z=1

Register B

10111 ! =1

000 ! P

Spring'11

! 0

01101 !

! 10101

C

Register A

Register Q

232 - Logic Design / Algorithmic State Machines (ASM)

36

Trace of the Binary Multiplication Initial conditions : B=10111

C

A

Q

Multiplier in Q

0!

00000!

10011! 101!

Q0 = 1; add B

P

10111!

First partial product

0!

10111!

Shift right CAQ

0!

01011!

Q0=1; add B

100! 11001!

10111!

Second partial product

1!

00010!

Shift right CAQ

0!

10001!

01100!

Q0=0; shift right CAQ

0!

01000!

10110! 010!

Q0=0; shift right CAQ

0!

00100!

01011! 001!

Q0=1; add B

011!

10111!

Fifth partial product

0!

11011!

Shift right CAQ

0!

01101!

000! 10101!

Final product in AQ = 0110110101

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

37

Making the design of the control logic easier

Z=0

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

38

Control Logic

§฀  Signals to be generated: §฀  §฀ 

T0-T3 L (The Load signal for Register A, that allows the loading the sum into register A.

§฀ 

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

39

Control Circuit implemented with D flip-flops + Decoder

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

40

One FF per state §฀  §฀  §฀  §฀ 

T0 = T0 S’ + T3 Z T1 = T0 S T2 = T1 + T3 Z’ T3 = T2

Z=0

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

41

§฀ 

ASM with Four Control Inputs

Operations are left blank.

§฀ 

We are interested in the design of the control part only.

§฀ 

Four control inputs: w, x, y, z

§฀ 

Four states: T0-T3 needs 2 flip-flops.

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

42

Using MUX’es to implement the control logic §฀  Two D flip-flops encode the state.

§฀  The state is decoded into state signals T0-T3 by a decoder.

§฀  The current state multiplexes the next state.

§฀  Challenge: how to set the inputs of the MUX’es?

Spring'11

232 - Logic Design / Algorithmic State Machines (ASM)

43

Multiplexer Inputs Present state

Spring'11

Next State

Input conditions

G1

G2

G1

G2

0

0

0

0

w’

0

0

0

1

w

0

1

1

0

x

0

1

1

1

x’

1

0

0

0

y’

1

0

1

0

yz’

1

0

1

1

yz

1

1

0

1

y’z

1

1

1

0

Y

1

1

1

1

y’z’

Multiplexer inputs MUX1