14 Multiplication Methods Flashcards
Example of implementation of a multiplier
Binary multiplications?
Circuit realization of Binary multiplication?
The number of AND gates, stage holders and bits required for a multiplication?
Thus, for a 4 x 4 multiplier we will need: 16 AND gates and 3 stages of adders to produce 8 bits.
How can problems occur when multiplying negative numbers?
Process to compute the correct multiplication of negative number using the unsigned multiplier plus additional hardware.
- If a negative number is present, then take its two’s complement to obtain its equivalent magnitude (positive representation).
- Multiply input values with their positive representation.
- Apply the correct sign to the final product
- If the product should be negative, then take the two’s complement in the final result.
- This creates a number that is in two’s complement format
The correct method for multiplying 7 and -7
What is Booth’s algorithm
Booth’s algorithm attempts to reduce the complexity of a multiplication by replacing multiple adders with a shift register and an adder/subtractor.
This algorithm was developed to speed up the multiplication of two signed numbers.
No need to compute the sign of the final product performed by the traditional multiplication procedure
Booths algorithm Definitions?
Let M be the multiplicand.
Let Q be the multiplier.
Consider a 1-bit register Q-1 initialised to 0.
Consider a register A initialised to 0.
Booth algorithm Condictions?
- If Q0 and Q-1 are the same (00 or 11), then perform arithmetic right shift by 1 bit.
- If Q0 and Q-1 are 10, then perform A = A – M and arithmetic right shift.
- If Q0 and Q-1 are 01, then perform A = A + M and arithmetic right shift.
The Wallace Tree diagram?
- As multiplications get larger sequential addition processes becomes inefficient.
- Wallace tree algorithm suggest to add terms (bits) as soon as possible.
- The idea of Wallace tree algorithm is “divide & conquer” (divide partial products).
- Fast addition is possible across all the bit slices.
The stages of the Wallace tree diagram.
Stage 1: partial products
Stage 2: addition of partial products
Stage 3: final addition
Advantages and disadvantages of wallace tree?
This is process is fast because all the adders are done in parallel!
This is a fast multiplication algorithm but it requires large number of logic gates.