Booth Example 00 just shift 11 just shift 01 add shift (ending of 1's) 10 subtract shift (beginning of 1's) (n = 5) -12 * 5 multipicand multiplier -12 =(10100) 5=(00101) 00000 00101 0 1 0 //since 1 0 subtract and shift //(shift 11bits and shift off very last) sub 01100 //sub.(-12)= +12. result 01100 00101 0 shift 00110 00010 1 //since 0 1 add and shift (1st shift) add 10100 00010 1//adding -12 result 11010 00010 1 shift 11101 00001 0 //since 1 0 subtract //arithmetic shift so..padding 1 sub 01100 result 01001 00001 0 shift 00100 10000 1 add and shift (3rd shift) add 10100 r esult 11000 10000 1 shift 11100 01000 0 shift (4th shift) shift 11110 00100 0 shift (5th shift) shift 5th time so end. //5 bits.. 5 shift //stop 11110 00100 0 //END..discard Dicision bit. 11110 00100 // Negative 60. (-12) * 5 = -60 (n = 4) 7 * 7 mulitipicand multiplier 7 = (0111) 7 =(0111) 0000 0111 0 subtract and shift sub 1001 result 1001 0111 0 shift(1st) 1100 1011 1 shift shift(2nd) 1110 0101 1 shift shift(3rd) 1111 0010 1 add and shift add 0111 0010 1 result 0110 0010 1 shift(4th) 0011 0001 0 subtract and shift (Did 4th shift; so END). 7*7 = 49 #### Do for (-9) * 15 = -45.. What will be the minimum bit length (n)? #### ##Division### IDEA 1101--Q 0101 / 01000011 - 101 11011 - 101 111 - 000 111 - 101 10 --R Shift / Add & Subtract A = B * R + Q c , B, R, Q : Registers B R Q //A XXXX XXXXXXXX for 67/5 c R Q 01000011 //67 1-sh 1000011 //look blank at the end.. sub 1011 //-5 res 1 0011011 // c = 1, put c back .. put 1back 00110111 //look 1 at the end 2-sh 0110111 //look blank at the end sub 1011 //-5 res 1 0001111 // c = 1, put c back put 1 back 00011111 3-sh 00111110 sub 1011 //-5 res 0 11101110 // c = 0, put c back.(0) put 0 back 11101110 4-sh 11011100 // since last c =0; add 0101 // 5 add res 1 00101100 // put c back put 1 back 00101101 // R = 2 Q = 13. 0010 1101 R Q ###IDEA R+D: Restoring(1) and Shifting(2) and Subtracting(3) R+D :(1) Restoring 2R+2D :(2) Shifting 2R+2D-D :(3) Subtracting. 2R+D : Result ...Equal to Shifting and Adding... // NonRestoring Algorithm ### ### Restoring NonRestoring Dividend Divisor Q Dividend Divisor Q 01000011 00000101 00000000 01000011 00000101 00000000 Alignment (shift Divisor and set the number of cycles) ################################################################ 01000011 01010000 00000000 01000011 01010000 00000000 cycle = 5 (number of shift plus 1) ################################################################ c=5 c= 5 subtract 01010000 subtract R D Q R D Q 01000011 01010000 01000011 01010000 (sub) 10110000(-0101000) 10110000(-01010000) res: 0 11110011 res: 0 11110011 put 0 into Q put 0 into Q R D Q R D Q 111110011 01010000 0 111110011 01010000 0 since since negative negative add back(restore) (non restoring) and shift D shift D sub at the next cycle(always) add at the next cycle(when pos.sub; neg.add;) dec. counter. dec. counter. 11110011 + 01010000 01000011 (R)//restoring 111110011 (R) //non restoroing shift D shift D 00101000 00101000 #################################################################### c=4 R D Q R D Q 01000011 00101000 0 11110011 00101000 0 (sub) 11011000(-00101000) add 00101000 res: 1 00011011 res: 1 00011011 put 1 into Q put 1 into Q R D Q R D Q 00011011 00101000 01 00011011 00101000 01 since since positive positive just shift D shift D sub. at the next cycle sub. at the next cycle dec. counter. dec. counter. 00011011 00010100 00011011 00010100 ##################################################################### c = 3 R D Q R D Q 00011011 00010100 01 00011011 00010100 01 (sub) 11101100(-00010100) (sub) 11101100(-00010100) res: 1 00000111 res: 1 00000111 put 1 into Q put 1 into Q R D Q R D Q 00000111 00010100 011 00000111 00010100 011 since since positive positive just shift D shift D sub. at the next cycle sub. at the next cycle dec. counter dec. counter 00000111 00001010 00000111 00001010 ######################################################################## c = 2 R D Q R D Q 00000111 00001010 011 00000111 00001010 011 (sub) 11110110(-00001010) (sub) 11110110(-00001010) res:0 11111101 res: 11111101 put 0 into Q put 0 into Q 0110 0110 since since negative negative add back(restore) (non restoring) and shift D shift D sub at the next cycle(always) add at the next cycle dec. counter. dec. counter. 11111101 + 00001010 00000111 (R)//restoring 111111101 (R) //non restoroing shift D shift D 00000101 00000101 ######################################################################### c = 1 R D Q R D Q 00000111 00000101 0110 11111101 00000101 0110 (sub) 11111011(-00000101) (add) 00000101(+00000101) res 1 00000010 res:0 00000010 put 1 into Q put 1 into Q 01101 01101 since since positive positive and shift D shift D sub at the next cycle(always) sub at the next cycle dec. counter. dec. counter. ########################################################################## c = 0 R Q R Q 00000010 01101 00000010 01101 IMPORTANT: IF IT WAS NEGATIVE at c = 1 cycle, RESTORE R for both algorithm. O/W, STOP. at the above example, it was positive so no restoring for both algorithm. ############################################################################ HW DO DIVISION for Dividend =8 and Divisor = 3. R D Q 00001000 00000011 Alignment. 00001000 00001100 ,, so c = 3.. do ........... ........... #############################################################################