A more complicated ASM




Current state Next state Condition

AB AB

0 00 1 01 Y

2 10

3 11 X

1 01 0 00

2 10 W

2 10 0 00 T

3 11 0 00 Z

2 10 ZX

3 11



In state 0 the B flip-flop -> Y + X -> X + Y

the A flip-flop -> + X -> X +



In state 1 the B flip-flop -> F

the A flip-flop -> W


In state 2 the B flip-flop -> F

the A flip-flop -> F



In state 3 the B flip-flop ->

the A flip-flop -> ZX + -> X +


A Multiplication Circuit



Phase 1:


Analyse the problem in terms of its inputs


Generate an architecture



Phase 2:


Design a controller (ASM)




Think in terms of normal long multiplication - but in binary not decimal



0111 multiplicand

x 1010 multiplier

----

0000

0111 partial products

0000

0111

-------

01000110 product


This way is not satisfactory:


We have to remember all the partial products before we can sum them to get the final product -> we would need lots of registers


Instead we can keep a running total in a single register.


If the multiplicand and multiplier are each n bits wide, the running total needs to be 2n bits wide.





  1. Start the running total with the multiplier in the low order bits.


  1. Increment a loop counter.


  1. Check the state of the lowest bit.


  1. If it is a 1 add the multiplicand to the high order bits of the total.


  1. Shift the running total 1 bit to the right.


  1. Repeat from 2 until the loop counter gets to n.


The multiplier has now disappeared from the total.


The total itself has the first terms in the addition shifted down to the low order end


ie


Counter Low Add Shift

Bit

1 00001010 -> 0 -> -> 00000101


2 00000101 -> 1 -> 00000101 -> 00111010

01110000

01110101


3 00111010 -> 0 -> -> 00011101


4 00011101 -> 1 -> 00011101 -> 01000110

01110000

10001101


01000110 -> answer








Current state Next state Condition

AB AB

0 00 0 00

1 01 START

1 01 2 10 LOBIT

3 11

2 10 3 11 -

3 11 0 00 EQZ

1 01





159.233 Lecture 9 -