Arithmatic Algorithms


Binary Multiplication

Multiplicand Register B = 22 = 10110

Multiplier Register Q = 21= 10101

Fig: Binary multiplication Algo Step Qn Operation Carry (E) Acc (A) Multiplier (Q) Count
initialize x x 0 00000 10101 5
1, 1, A=A+B 00000

10110

———–

10110

Shr EAQ 0 01011 01010 4
2 0 Shr EAQ 0 00101 10101 3
3 1 Add 0 00101

10110

——–

11011

Shr EAQ 0 01101 11010 2
4 0 Shr EAQ 0 00110 11101 1
5 1 Add 0 00110

10110

——–

11100

Shr EAQ 0 01110 01110 0
ANSWER 22 x 21 = 462 = 00111001110

Example-2

Multiplicand Register B = 30 = 11110

Multiplier Register Q = 26= 11010

Fig: Binary multiplication Algo Step Qn Operation Carry (E) Acc (A) Multiplier (Q) Count
initialize x x 0 00000 11010 5
1, 0 Shr EAQ 0 00000 01101 4
2 1 Add A, B 0 00000

11110

——–

11110

Shr EAQ 0 01111 00110 3
3 0 Shr EAQ 0 00111 10011 2
4 1 Add 1 00111

11110

——–

00101

10011
Shr EAQ 0 10010 11001 1
5 1 Add 1 10010

11110

———

10000

0 Shr EAQ 0 11000 01100 0
ANSWER 30×26 = 780 = 01100001100

2’sComplement Multiplication Booth’s Algorithm

-12 x -20

Let

multiplicand = -20 ; Reg B(- 20) =101100

2’s Complement B’+1 = (+20) = 010100

Multipler Reg Q = -12 = 10100

-20 x -12 = 240

Fig: Booth’s Algo for 2’s compliment multiplication

Booth’s Algorith Step Qn Qn+1 Operation Acc Q = -12 Qn+1 Count
initialize 0 Initialize Acc, Q, B, Qn+1 000000 10100 0(initial value) 5
1 0 0 Arithmetic shift right (AQQn+1) 000000 01010 0 4
2 0 0 Arithmetic shift right (AQQn+1) 000000 00101 0 3
3 1 0 A-B=A+B’+1 000000

010100

———-

010100

Arithmetic shift right (AQQn+1) 001010 00010 1 2
4 0 1 A+B 001010

101100

———-

110110

Arithmetic shift right (AQQn+1) 111011 00001 0 1
5 1 0 A-B 111011

010100

———-

001111

Arithmetic shift right (AQQn+1) 000111 10000 1 0 stop
ANSWER -20 x -12 = +240 = 00011110000

 

error: Content is protected !!