Arithmetic Hardware

1-Bit Half Adder

  • Used to add single bit numbers, doesn’t take no Carry-in, but their is a carry out, sum and carry-out

  • Sum = A’B + AB’ = A Xor B

  • Count = AB

Using the half-adder, we can’t use the carryout from the previous one, a limitation, basically can’t add the adders(can’t link them)

1-Bit Full Adder

  • Sum = A Xor B XOR Cin(carryin)

  • Cout = AB + ACin + BCin

  • It can be constructued using two half adders and one OR gate


More explanation on how the sum was gotten.


Standard Gate Logic Design Apporach


Alternative implementation

Ripple-Carry Adder

We cascade 1-bit adders together

Parallel Adder


Example of logic implementation

With overflow, when it is 0, there is no overflow, and when there is 1, there is overflow

The reason why it is a XOR gate is because the only conditions to have overflow is 01 and 10, which match the definition of overflow

Subtraction with Ripple-Carry adder

Disadvantage with Ripple-Carry Adder

Very long delay

    Carry bit may have to propagate from LSB to MSB

    Worst case delay for n-bit adder = 2n gate delays

Carrys from low to high order stages

The key to speeding up addition is determining carry values sooner/quicker


Carry -Lookahead Logic


32-Bit ALI


Computer Arithmetic

(Arithmetic logic unit) = ALU


Integer Multiplication


Combinational Multipier

multiplying each one, and at the end, do the sum of each at the bottom

Problem is it is waaay to many gates, 12 adders, need 88 gates total.


Some obervations:

The # of bits in the product is larger than the number in either the multiplicand or the multiplier(factor a and factor b)

m bits x n bits = m + n bit product


Overflow is a possible issue


Binary rule “choices”

0 => place 0

1=>place a copy


3 versions of unsigned multiplication hardware

    sucessive refinement


Version 1

the multiplicand and produce is 64 bit

If the LSB of multiciand is 1, add that to the product, other then, keep going



Example 1 with this version

11 × 9


0000 1011(11) times 1001(9), initializing currently, with iteration 0 and step 0, and product currently at 0000 0000


iteration 1, steps 1a. 2, 3, wiht the action adding and shift, product is currently the multipcant, and the multiple is shifting the value of everything to the left(0001 0110) while the other one shift to the right(0100)


How the logic/implementation of it works.

96 Steps, around 100 clock cycles.


Observations on Version 1:

Half the bits of the miltiplicand are always 0, so the 64-bit adder is wasted


Version 2



Version 2 Example(11 × 9)


Observations

Product register wastes space, so


Version 3


it places the multiplier in the lower half of the product(essentially using the product as a multiplier)


Example 3(same numbers, just how to implement it)


Multiplying by a Constant

Essentially, it mutlplies short constants with a series of shifts and adds, with it having the same effect as multplying 2² or 2³, stuff like that.


Signed Multiplication


Make moth positive, leave out the sign bit, run for 31 stpes, nad set sign bit negative of signs of inputs differ( + / - = -)


Booth’s Algorithm

Multiply two-s complement signed numbers, uses the same hardware as before, and reduce the number of steps


The multiplcation is handled by algorithm 3 from last time for multiplying(the one where the product is a representation of the multiplyer)


When product is 10, substract multiplcand from the left half of the prpduct and place the result in the left half of the Product register.

When prduct is 01, add multiplcand to the left half of the prpduct and palce the result in the left half of the Pruduct register


Example(-6 X -5)


-6 = 1010 = 0110

-5 = 1011


Another Example:


Solution:


Orginally for speed, since shifts are faster than adding and works proprerly for 2’s complement numbers without the specifal fix for sign