ARITHMETIC in CAO

Number representations and their operations 

•   Three major representations:

          Sign and magnitude

          One’s complement

          Two’s complement

•   Assumptions:

          4-bit machine word

          16 different values can be represented

          Roughly half are positive, half are negative

Sign and Magnitude Representation

 

• High order bit is sign: 0 = positive, 1 = negative

• Three low order bits is the magnitude: 0 (000) thru 7 (111)

• Two representations for 0

One’s Complement Representation

 

•Subtraction implemented by addition & 1's complement

•Still two representations of 0

•Some complexities in addition

Two’s Complement Representation

like 1's comp

except shifted

one position

clockwise

•Only one representation for 0

•One more negative number than positive number

 

Binary, Signed-Integer Representations

 

           Addition and Subtraction

If carry-in to the high order bit =

carry-out then ignore carry

if carry-in differs from

carry-out then overflow

 

Overflow Conditions

Overflow when carry-in to the high-order bit does not equal carry out

 

2’s-Complement  Add and Subtract Operations

 

Figure : 2's-complement Add and Subtract operations.

Fast Adder

• Recall the equations:

 

• Second equation can be written as:

   

• We can write:

   

•Gi is called generate function and Pi is called propagate function

•Gi and Pi are computed only from xi and yi and not ci, thus they can be computed in one gate delay after X and Y are applied to the inputs of an n-bit adder.

•  All carries can be obtained 3 gate delays after X, Y and c0 are applied.

      -One gate delay for Pi and Gi

      -Two gate delays in the AND-OR circuit for ci+1

•  All sums can be obtained 1 gate delay after the carries are  computed.

•  This is called Carry Lookahead adder.

 

4-bit

carry-lookahead

adder

                                                      B-cell for a single stage

Carry-out from a 4-bit block can be given as:

Rewrite this as:

Subscript I denotes the blocked carry lookahead and identifies the block.

Cascade 4 4-bit adders, c16 can be expressed as:

 

Blocked Carry-Lookahead adder

 

After xi, yi and c0 are applied as inputs:

  - Gi and Pi for each stage are available after 1 gate delay.

  - PI is available after 2  and GI after 3 gate delays.

  - All carries are available after 5 gate delays.

  - c16 is available after 5 gate delays.

  - s15 which depends on c12 is available after 8 (5+3)gate delays

    

Array Multiplier :

 

Product is:   p7,p6,..p0

Multiplicand is shifted by displacing it through an array of adders.

Typical multiplication cell

 

 

Figure: 2-bit by 2-bit array multiplier

•  Combinatorial array multipliers are:

Extremely inefficient.

Have a high gate count for multiplying numbers of practical size such as 32-bit or 64-bit numbers.

Perform only one function, namely, unsigned integer product.

•   Improve gate efficiency by using a mixture of combinatorial array techniques and sequential techniques requiring less combinational logic

 

Signed Multiplication 

•Considering 2’s-complement signed operands, (-13)´(+11

 

•For a negative multiplier, a straightforward solution is to form the 2’s-complement of both the multiplier and the multiplicand and proceed as in the case of a positive multiplier.

•This is possible because complementation of both operands does not change the value or the sign of the product.

•A technique that works equally well for both negative and positive multipliers – Booth algorithm.

Booth Algorithm

 

•Consider in a multiplication, the multiplier is positive 0011110, how many appropriately shifted versions of the multiplicand are added in a standard procedure?

•Since 0011110 = 0100000 – 0000010, if we use the expression to the right.

 

•In general, in the Booth scheme, -1 times the shifted multiplicand is selected when moving from 0 to 1, and +1 times the shifted multiplicand is selected when moving from 1 to 0, as the multiplier is scanned from right to left.

 

 

•Best case – a long string of 1’s (skipping over 1s)

•Worst case – 0’s and 1’s are alternating

 

Bit-Pair Recoding of Multipliers :

•Bit-pair recoding halves the maximum number of summands (versions of the multiplicand).

Multiplication requiring only n/2 summands.

 

Manual Division

 

Circuit Arrangement

 

Restoring Division :

Algorithm : 

Step 1 :Shift A and Q left one binary position

Step 2: Subtract M from A, and place the answer back in A

Step 3 :If the sign of A is 1, set q0 to 0 and add M back to A (restore A); otherwise, set q0 to 1

Step 4 :Repeat these steps n times

Example:-

 

Non-restoring Division :

Algorithm :

Step 1: (Repeat n times)

If the sign of A is 0, shift A and Q left one bit position and subtract M from A; otherwise, shift A and Q left and add M to A.

Now, if the sign of A is 0, set q0 to 1; otherwise, set q0 to 0.

Step 2 : If the sign of A is 1, add M to A

 Example:-

 

Floating-point Arithmetic operations

 

Add/Subtract Rule : 

•Choose the number with the smaller exponent.

•Shift its mantissa right until the exponents of both the numbers are equal.

•Add or subtract the mantissas.

•Determine the sign of the result.

•Normalize the result if necessary and truncate/round to the number of mantissa bits.

 

Multiply Rule :

1.Add the exponents.

2.Subtract the bias.

3.Multiply the mantissas and determine the sign of the result.

4.Normalize the result (if necessary).

5.Truncate/round the mantissa of the result.  

Divide Rule : 

1.Subtract the exponents

2.Add the bias.

3.Divide the mantissas and determine the sign of the result.

4.Normalize the result if necessary.

5.Truncate/round the mantissa of the result.

 

IEEE Standard For Floating-point Numbers :

•  IEEE Floating Point notation is the standard representation in use. 

            There are two representations:

             - Single precision.

             - Double precision.

•  Both have an implied base of 2.

•  Single precision:

        - 32 bits (23-bit mantissa, 8-bit exponent in excess-127 representation)

•  Double precision:

       - 64 bits (52-bit mantissa, 11-bit exponent in excess-1023 representation) 

 

 

Guard Bits And Rounding : 

• While adding two floating point numbers with 24-bit mantissas, we shift the mantissa of the number with the smaller exponent to the right until the two exponents are equalized.

•  This implies that mantissa bits may be lost during the right shift .

• To prevent this, floating point operations are implemented by keeping guard bits, that is, extra bits. 

•  The arithmetic on the mantissas is performed with these extra bits of precision.

•After an arithmetic operation, the guarded mantissas are:

     - Normalized (if necessary)

     - Converted back by a process called truncation/rounding to

         a 24-bit mantissa.

Truncation/rounding

•Chopping:

       - The guard bits (excess bits of precision) are dropped.

•Von Neumann rounding:

–If the guard bits are all 0, they are dropped.

–However, if any bit of the guard bit is a 1, then the LSB of the retained bit is set to 1.

 

•Rounding:

–If there is a 1 in the MSB of the guard bit then a 1 is added to the LSB of the retained bits.

– If there is a 0 in the MSB bit then the guards bits are simply removed