Transcript Class_11_Binary_Multiplier

EKT 221 : DIGITAL 2
Lecture : 1 hrs
ASM : Binary Multiplier
Example Multiplicand
Partial Products are:
101 x 1
Multiplier
Note that the partial
product summation for n
digits,
base 2 numbers requires
adding up to n digits
(with carries) in a
column.
101 x 1
101 x 0
Note also n x m digit
multiply generates up
to an m + n digit result
(same as
decimal).
ASM : Binary Multiplier Example
A
Multiplier (Q)
0 0 0 0 1 1
0
0
Multiplicand (B)
1 0 1
000
+101
101
Multiplier (Q)
A
0 1 0 1 0 1
1 x 101 = 1 0 1
010
+101
111
1 x 101 = 1 0 1
A Multiplier (Q)
0 1 1 1 1 0
Multiplicand (B)
1 0 1
Multiplicand (B)
1 0 1
0 x 101 = 0 0 0
0
0 0 1 1 1 1
Product
1. MUL LSB with Multiplicand
OR check if LSB = 1, if 1 then
do addition
2. ADDITION (A + B)
3. SHIFT Right
1. MUL LSB with Multiplicand
OR check if LSB = 1, if 1 then
do addition
2. ADDITION (A+B)
3. SHIFT Right
1. MUL LSB with Multiplicand
OR check if LSB = 1, if 0 then
do not do Addition
2. SHIFT Right
ASM : Binary Multiplier Example
A
Multiplier (Q)
0 0 0 0 1 1
Multiplicand (B)
1 0 1
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Figure 8-6, Morris Mano, pg 371
Multiplicand is loaded into Reg. B
Multiplier is loaded into Reg. Q
Reg. A is initially zero
Parallel Adder is used to add Reg. A
and Reg B
C FF’s stores Cout of P.A
C is Reset to 0 upon shift right
Counter P is provided to count the
cycle
If P=0 then read result in Reg. A and
Reg. Q. and processing stops.
CU stays in initial state until G=1
In the initial state, Reg. A and FF C is
reset to 0.
After Shifting Right, Reg. A will send
the content to P.A for next cycle.
The LSB of Q is discarded.
CU will check for signal Z and Q0.
CU will decide to add/shift or shift
based on this 2 signals.
The control signal from the CU to the
datapath activate the required
microoperations
Multiplier ASM Chart

Three main states are employed:



IDLE - state in which:
 the outputs of the prior multiply is held until Q is loaded with
the new multiplicand
 input G is used as the condition for starting the
multiplication, and
 C, A, and P are initialized
MUL0 - state in which:
 conditional addition is performed based on the value of Q0.
MUL1 - state in which:
 right shift is performed to capture the partial product and
position the next bit of the multiplier in Q0
 the terminal count of 0 for down counter P is used to sense
completion or continuation of the multiply.
Multiplier ASM Chart
Figure 8.7 : Morris Mano, pg 373
Analysis of ASM Chart




ASM = IDLE and G=0, no action occurs
Multiplication ONLY occurs when G=1.
Moving to state MUL0, C & A are cleared to 0 and P
is loaded with (n-1).
In state MUL0, a decision is made based on Q0:




Q0 = 1, B add to A, result transferred to A and Carry to C
Q0 = 0, A & C unchanged.
Note : Both condition will go to next state MUL1
A Shift Right is performed on the combined content
of C, A and Q.
Analysis of ASM Chart….cont




The shift transfer can be simplified to:
C 0, C || A || Q sr C || A || Q
|| is called concatenation, meaning it is a composite
register or register made up of other registers.
Counter P is decremented in state MUL1. This
illustrates a very IMPORTANT timing difference
between a standard flowchart and an ASM chart.
The decision on Z, which represent P=0, follows the
register transfer statement that updates P in the
ASM chart.
Hardware selection

Identifying h/w is also important:




Reg. A = Shift Reg with parallel load, with CLR
enable to reset the reg. to “0”.
Reg. Q = Shift Reg
C FF’s = accept input from Cout, with CLR enable
to reset the FF to “0”.
Reg. B and Q = Parallel load Reg, used to load
multiplier and multiplicand at the initial stage.
Alternate ASM Chart





Figure 8.8 (a) & (b), Morris Mano, pg 375.
Analyze the circuit.
It reduces the state to just 2. (IDLE and
MUL1 only)
It utilizes the vector decision box.
(READ YOURSELF and Understand)
QUIZ
Reg A : 1110
Reg B : 1010
A3
T0
T1
T2
T3
T4
A2
A1
A0
B3
B2
B1
B0
SUM
(A+B)
+ Cin
1 1 1 0 1 0 1 0 0
Cout
Cin
0
0
Thank you