IS A MULTIPLICATION ALGORITHM THAT MULTIPLIES TWO SIGNED BINARY NUMBERS IN TWO'S COMPLEMENT NOTATION. ANDREW DONALD...

 

Transcribed Image Text:

IS A MULTIPLICATION ALGORITHM THAT MULTIPLIES TWO SIGNED BINARY NUMBERS IN TWO'S COMPLEMENT NOTATION. ANDREW DONALD BOOTH INVENTED THE ALGORITHM IN 1950 WHILE DOING RESEARCH ON CRYSTALLOGRAPHY AT BIRKBECK COLLEGE IN BLOOMSBURY, LONDON. BOOTH'S ALGORITHM IS OF INTEREST IN THE STUDY OF COMPUTER ARCHITECTURE. PHASE #1 - DESCRIPTION: DEVELOP A PLAN TO DESIGN AND FINALLY IMPLEMENT A SET OF FUNCTIONS USING C++ THAT WOULD IMPLEMENT THE BOOTH MULTIPLIER ALGORITHM. PHASE 1 WILL INCLUDE THE LITERATURE WRITE UP, DESCRIPTION OF THE BOOTH MULTIPLIER AND A COMPLETE DESCRIPTION OF THE FUNCTIONS PLAN: 1. FUNCTIONS TYPE VOID, OR ANY DATA RETURNING FUNCTION 2. TYPE OF DATA PASSED IN TO THE FUNCTIONS (FUNCTION PARAMETERS OR ARGUMENTS) 3. TYPE OF FUNCTION PARAMETERS (VALUE OR REFERENCE). 4. GLOBAL VARIABLES IF NEEDED. 5. BOOTH MULTIPLIER LAYOUT AND ITS INDIVIDUAL PARTS (MULTIPLICAND (Q), MULTIPLIER (M), A AND Q.1 REGISTERS) DETAILS. 6. THE BINARY ARRAY LAYOUT. 7. HAND WORK OUT A FULL EXAMPLE FROM A TO Z. ALGORITHM EXAMPLE: 1. 15 x 9 - 135 = 2. 15 x 9135 3. 15 x 9 = 135 4. 15 x 9 = 135 MULTIPLICAND = -15 MULTIPLIER = 9 1. CONVERT THE NUMBERS TO BINARY MULTIPLICAND = 01111 MULTIPLIER = 01001 2. IF THERE IS A NEGATIVE NUMBER CONVERT TO 2'S COMPLEMENT MULTIPLICAND = 100001 MULTIPLIER = 01001 3. POPULATE THE TABLE 0 0 0 1 0 Od A 0 0 0 0 0 1 0 0 0 700 AOLOHO 1 1 1 1 1 1 1 0 1 HOTP OTTOO 0 0 1 0 0 оо OO OOHHH QOOOOH OOOOO 1 Q-1 0 Σ DESCRIPTION 0 0 0 1 1 1 0 0 HO 1 1 0 0 0 1 1 0 HOOO 1 0 0 1 0 1 0 0 000 00 0 1 00 1 0 1 0 1 0 0 1 0 OOOOO 1 INITIAL STATE 0 0 0 LETT 0 1 A A - M 1 ASR 1 A - A + M 1 ASR 0 000 1 0 0 1 1 0 0 0 1 0 0 1 ASR 0 0 0 1 0 1 1 1 0 OTO 0 0 1 1 1 HOO 1 0 0 0 1 1 1 1 0 0 1 1 OOO 0 нно 1 1 0 1 1 0 OOO 0 1 0 0 1 ASR 0 1 0 0 0 1 0 0 OO 1 A A - M 1 ASR 4. COMPARE THE LAST 2 BIT OF THE TABLE AND BASED ON COMPARISON LAST TWO BITS OPERATION 10 0 0 OR 11 01 A A M ASR A+ A+ M 1 2 3 4 5 5. EVERY STEP MUST TERMINATE WITH ASR (ARITHMETIC SHIFT RIGHT) 6. NUMBER OF STEPS NEEDED TO CALCULATE THE ASNSWER IS THE NUMBER OF BITS IN REGISTERS A OR Q 7. LIMIT YOUR MULTIPLICATION TO NUMBERS LESS THAN 15 8. ANSWER WILL BE IN BOTH REGITERS A AND Q 9. ANSWER WILL BE GIVEN IN 2'S COMPLEMENT FORM IS A MULTIPLICATION ALGORITHM THAT MULTIPLIES TWO SIGNED BINARY NUMBERS IN TWO'S COMPLEMENT NOTATION. ANDREW DONALD BOOTH INVENTED THE ALGORITHM IN 1950 WHILE DOING RESEARCH ON CRYSTALLOGRAPHY AT BIRKBECK COLLEGE IN BLOOMSBURY, LONDON. BOOTH'S ALGORITHM IS OF INTEREST IN THE STUDY OF COMPUTER ARCHITECTURE. PHASE #1 - DESCRIPTION: DEVELOP A PLAN TO DESIGN AND FINALLY IMPLEMENT A SET OF FUNCTIONS USING C++ THAT WOULD IMPLEMENT THE BOOTH MULTIPLIER ALGORITHM. PHASE 1 WILL INCLUDE THE LITERATURE WRITE UP, DESCRIPTION OF THE BOOTH MULTIPLIER AND A COMPLETE DESCRIPTION OF THE FUNCTIONS PLAN: 1. FUNCTIONS TYPE VOID, OR ANY DATA RETURNING FUNCTION 2. TYPE OF DATA PASSED IN TO THE FUNCTIONS (FUNCTION PARAMETERS OR ARGUMENTS) 3. TYPE OF FUNCTION PARAMETERS (VALUE OR REFERENCE). 4. GLOBAL VARIABLES IF NEEDED. 5. BOOTH MULTIPLIER LAYOUT AND ITS INDIVIDUAL PARTS (MULTIPLICAND (Q), MULTIPLIER (M), A AND Q.1 REGISTERS) DETAILS. 6. THE BINARY ARRAY LAYOUT. 7. HAND WORK OUT A FULL EXAMPLE FROM A TO Z. ALGORITHM EXAMPLE: 1. 15 x 9 - 135 = 2. 15 x 9135 3. 15 x 9 = 135 4. 15 x 9 = 135 MULTIPLICAND = -15 MULTIPLIER = 9 1. CONVERT THE NUMBERS TO BINARY MULTIPLICAND = 01111 MULTIPLIER = 01001 2. IF THERE IS A NEGATIVE NUMBER CONVERT TO 2'S COMPLEMENT MULTIPLICAND = 100001 MULTIPLIER = 01001 3. POPULATE THE TABLE 0 0 0 1 0 Od A 0 0 0 0 0 1 0 0 0 700 AOLOHO 1 1 1 1 1 1 1 0 1 HOTP OTTOO 0 0 1 0 0 оо OO OOHHH QOOOOH OOOOO 1 Q-1 0 Σ DESCRIPTION 0 0 0 1 1 1 0 0 HO 1 1 0 0 0 1 1 0 HOOO 1 0 0 1 0 1 0 0 000 00 0 1 00 1 0 1 0 1 0 0 1 0 OOOOO 1 INITIAL STATE 0 0 0 LETT 0 1 A A - M 1 ASR 1 A - A + M 1 ASR 0 000 1 0 0 1 1 0 0 0 1 0 0 1 ASR 0 0 0 1 0 1 1 1 0 OTO 0 0 1 1 1 HOO 1 0 0 0 1 1 1 1 0 0 1 1 OOO 0 нно 1 1 0 1 1 0 OOO 0 1 0 0 1 ASR 0 1 0 0 0 1 0 0 OO 1 A A - M 1 ASR 4. COMPARE THE LAST 2 BIT OF THE TABLE AND BASED ON COMPARISON LAST TWO BITS OPERATION 10 0 0 OR 11 01 A A M ASR A+ A+ M 1 2 3 4 5 5. EVERY STEP MUST TERMINATE WITH ASR (ARITHMETIC SHIFT RIGHT) 6. NUMBER OF STEPS NEEDED TO CALCULATE THE ASNSWER IS THE NUMBER OF BITS IN REGISTERS A OR Q 7. LIMIT YOUR MULTIPLICATION TO NUMBERS LESS THAN 15 8. ANSWER WILL BE IN BOTH REGITERS A AND Q 9. ANSWER WILL BE GIVEN IN 2'S COMPLEMENT FORM

Answer rating: 100% (QA)

Here is a stepbystep plan to design and implement a Booth multiplication algorithm in C 1 Functions ... View the full answer