[SOLVED] CS cache Multiplication, Division, and Finite State Machines

Multiplication, Division, and Finite State Machines
1

Multiplication(3.3)
Division(3.4)
FiniteStateMachines(B.10)
Agenda
COMP273 McGill 2

Binary Multiplication and Division
Working in base b, multiplication of a number Nb by b is equivalent to shifting the radix point one place to the right
Example in base 10
143.2*10=1432 and 143.2/10=14.32
Can we do the same thing for binary?
Can do long division and multiplication? What happens with signed numbers?

Multiplications
4

P=AxB
A: Multiplicand B: multiplier
P: product
Revisit Integer Multiplication
Multiplicand is multiplied by each bit of the multiplier
Each intermediate result is added up to get the final product.
COMP273 McGill 5

Unsigned Binary Multiplication Multiplicand: 64 bits shift (left) register
Multiplier: 32bit shift (right) register to read the LSB on each add
Product: 64bit register
Adder circuit: 64bit ALU
Counter: keep track of how many times we shift
COMP273 McGill 7

4bit Example Multiplicand: 1000 Multiplier: 1001 Repetition: 4
Refined Multiplication Circuit
COMP273 McGill
10
32 bits
write
Carry
High 32 bits initialized with zero
64bit result
Multiplicand
32bit ALU
Product
Shift right 32 bits
Control Test
32bits
32 bits
Low 32 bits initialized with multiplier
LSB

COMP273 McGill
11
operands were different
Signed Multiplication
Convert the multiplier and the multiplicand to positive numbers and remember the original signs
Multiplypositivenumbers
The sign of the product is negative if the signs of the
There are faster ways to do multiplication, but outside of scope of this course

Division
12

4bit Example Dividend: 0111 Divisor: 0010 Repetition: 5
10 0111 10
COMP273 McGill
14
Step 1
Step 2
Step 3
Step 4
Step 5
0010 00000111 0010 0000
0010 00000111 00010 000
0010 00000111 00 0010 00
0010 00000111 000 00100
0010 00000011
00000010
0
00
000
0001
00011
Division for Positive Numbers
Normal Way
11
– 11
10
1
Your computer is not that smart, it needs to do it step-by-step
11
1

COMP273 McGill
15
Division for Positive Numbers
Initialize Divisor in high word, 0 in low word
Initialize Quotient with 0
64 bits
Initialize Remainder with b
Divisor
Zero
Quotient
32 bits
32 bits 64 bits
Shift right
32bits
Shift left
64bit ALU 64 bits
control
Remainder
64bit
write
operation
Sign / most Significant Bit

COMP273 McGill
16
Division for Positive Numbers
4bit Example Dividend: 0111 Divisor: 0010 Repetition: 5
Initialize Divisor in high word, 0 in low word
Initialize Quotient with 0
64 bits
Initialize Remainder with b
Divisor
Zero
Quotient
32 bits
32 bits 64 bits
Shift right
32bits
Shift left
64bit ALU 64 bits
control
Remainder
64bit
write
operation
Sign / most Significant Bit

COMP273 McGill
17
64 bits
Division for Positive Numbers
4bit Example Dividend: 0111 Divisor: 0010 Repetition: 5
Initialize Divisor in high word, 0 in low word
Divisor
Zero
Quotient
32 bits
32 bits 64 bits
Shift right
32bits
Shift left
64 bit ALU
Init with Dividend Ends with Remainder
Sign / most Significant Bit
64 bits
control
operation
write
Can read sign bit from ALU instead

Finite State Machines
19

COMP273 McGill
20
Finite State Machines
Amusing illustration to introduce FSMs, but not a real or complete example

COMP273 McGill
21
Transitions triggered by actions
Finite State Machines
Finitesetofstatesencodedinasetofbits
Combinatorialfunctionchoosesthenextstateasafunctionofthe current state and the inputs

COMP273 McGill
22
Finite State Machines
TwoTypesofFSM
Moore Machine: Output is dependent only on current state
Mealy Machine: Output is dependent on both inputs and current state We will focus only on Moore machines

COMP273 McGill
23
TrafficlightsExample
Only Red and Green lights North South / East West
Finite State Machines
Sensors to detect cars waiting
Car waiting at either North or South (NSCar) Car waiting at either East or West (EWCar)

COMP273 McGill
24
Twostates
NS light is green (with EW is light red) EW light is green (with NS is light red)
Finite State Machines
Transitions
When car waiting in one direction, change light for that car When cars sensed in both directions, light changes

State
NSCar EWCar
Next State
NSGreen NSGreen NSGreen NSGreen EWGreen EWGreen EWGreen EWGreen
0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1
NSGreen EWGreen NSGreen EWGreen EWGreen EWGreen NSGreen NSGreen
Outputs
Inputs
Finite State Machines
Derive truth table for state transition and outputs COMP273 McGill
25
State
NSLight EWLight
NSGreen EWGreen
1 0 0 1

State
NSCar EWCar
Next State
NSGreen NSGreen NSGreen NSGreen EWGreen EWGreen EWGreen EWGreen
0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1
NSGreen EWGreen NSGreen EWGreen EWGreen EWGreen NSGreen NSGreen
Outputs
Inputs
Finite State Machines
Derive the Boolean functions for state transitions and outputs COMP273 McGill
26
State NSLight
EWLight
NSGreen 1 EWGreen 0
0 1

State
NSCar EWCar
Next State
NSG0reen NSG0reen NSG0reen NSG0reen EWG1reen EWG1reen EWG1reen EWG1reen
0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1
NSG0reen EWG1reen NSG0reen EWG1reen EWG1reen EWG1reen NSG0reen NSG0reen
Outputs
Inputs
Finite State Machines
Internally, all states are represented in binary COMP273 McGill
27
State
NSLight
EWLight
010 101

COMP273 McGill
28

Put functions in sum of products canonical form and implement with a PLA
FSM Recipe
FSM=StateRegister+CombinationalLogic Create the circuits from Boolean functions
ImplementfunctionasaROM(inputand states form address, outputs and next state are contents)

COMP273 McGill
30
Other Examples Odd parity checker
Reset
FiniteStringPatternRecognizer
ComplexCounterwithDecisionMaking
0
Odd [1]
E.g., count in Gray code, or count in binary based on mode control DigitalCombinationLock
Lock which only opens when correct binary combination is entered
Control processor execution (Chapter 4)
Control cache (Chapter 5)
1
1
0 [0]
Even

COMP273 McGill
31
Puppeteer pulling strings
Puppet
Control
Control Signal Outputs
Datapath
FSM generating sequences of control signals instructs datapath what to do next
State
Registers
Busses
Combinational Functional Units (e.g., ALU)
The Big Picture Computer Hardware = Datapath + Control
Inputs

Review and more information
Multiplication(Section3.3)
Division (Section 3.4)
FiniteStateMachines(SectionB.10)
COMP273 McGill 32