- With 1’s complement - x -> 2^m-x-1*
- With 2’s complement - x-> 2^m-x*
Must be remembered - Multiplication of two m bits results with 2m bits at max.
- Assume the multiplication component is “parallel array multiplier” and the adder component is sequential(גלי)*
- Compute delay time.*
- All multipliers can be computed in parallel - O(6m-3)
- First adder can start the computation once it gets some bits from the 1st multiplier
- When it gets the last bit from the first multiplier - he need to add the last digit of the LSB and then add the n LSB bits coming from the multipliers.
- Because the adder is sequential, it would take O(6m-3) + 2(m+1)
- The second adder works in parallel with the first adder. The delay occurs with the last bit O(2)
- The third is of the same idea as the first adder, just that we wait for the n+1 bit - thus we need to add n bits in total - additional 2m.
In total: 6m-3+2m+2+2+2m = 10m+1.
Same question but using CLA, why does the time it take for the first adder is 1+4logk(2n) and not less even though n-1 LSB bits are pre-calculated?
- Have a look at the image attached.*
- For the top Ci to be computed we need both the left base and the right base to be computed. Normally the bases are computed in parallel and take the same time. When n bits are given first, the right base is computed, but it does not speed up the computation because we need the left base to be computed also before the rest of the computation is done.*
Same question but using sequential multiplier.
- With sequential multiplier the resulting bits come at once, at the end. That is, the adder cannot work in parallel with the multiplier.*
- Therefore we have, 2m^2+m(multipliers) + 2m*2(first adder) + 2(second adder) + 2m(third adder)*
Explain why run-time is O((1+2m)m)
- Partial product generator works as “מחבר גלי”. That is, it ends after 2m operations.*
- The digit adder works in parallel with the partial product. When the partial product’s last bit is shifted to the m+1 digit adder(after 2m time),* to finish its computation, the digit adder needs only
Important one. Sit and solve.
Important! using CLA you can’t get faster than setting k=m. This way we use all the information available in parallel. So basically - Min(1+4logk(m)) = 1+4logm(m) = 1+4*1 = 5.
Answer
- Minimum time - the last carry does not depend on the previous one - it can simply be found using the Full adder in O(2).*
- Maximum time - the last carry does depend on the previous one, and so the previous depends on the previous-previous and so on. This way it takes 1+4logk(n).*
Why in CLA computing G and P takes O(1) even though P requires XOR operation?
The final equation is Ci+1= Gi+Pi*Ci
We can remove the condition of x=y=1 from P, because anyway it makes G=1.
So we need to compute: Gi = AND(x,y) and Pi = OR(x,y).
How many components is need for the addition of two 2^m numbers?
- FA - 2^m
- Simple PG - 2^m
- Recursive PG - CLA - 2^m-1
- In total - 3*2^m-1
- X is positive. How can we transform it into -X in 1’s/2’s complement method?*
- Example: X = 0111 = 7*
- What is the advange/disadvantage of 1’s complemt?*
Write a very important equation of 2’s complement?
given that x is of m bits
1’s complement:
- -X = 2^m - X - 1.
- X=0111 -> -X = 2^4-7-1 = 8 = 1000.
2’s complement:
- -X = 2^m - X.
- X = 0111 -> -X = 2^4-7 = 9 = 1001.
Advantage: we can substract two numbers easily, we can turn it into addition by negating the substractor.
Disadvantage: 0 has double representation.
- (320132) - base 4. -> (11 10 00 01 11 10) - base 2 -> (111 000 011 110) = (7036) - base 8*
- (7036) - base 8 * 8 = (70360)-base 8 = (0111 0000 1111 0000) = (70F0)-base 16*
Explain Tri-state and how can we implement 2-1 MUX using triset and not gate.
Recall and memorize
Recall How register is implemented
