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.

Start the running total with the multiplier in the

**low**order bits.

Increment a loop counter.

Check the state of the lowest bit.

If it is a 1 add the multiplicand to the

**high**order bits of the total.

Shift the running total 1 bit to the right.

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 -