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