Recent Post


Number representations and their operations 

   Three major representations:

          Sign and magnitude

          One’s complement

          Two’s complement


          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

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.

                                                      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 :


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


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

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.



       - 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.


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

No comments