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

Bit

1 00001010 -> 0 -> -> 00000101

2 00000101 -> 1 -> 00000101 -> 00111010

01110000

01110101

3 00111010 -> 0 -> -> 00011101

4 00011101 -> 1 -> 00011101 -> 01000110

01110000

10001101

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 -