ARITHMETIC in CAO
Number
representations and their operations
•
Three major representations:
Sign and magnitude
One’s complement
Two’s complement
•
Assumptions:
4bit 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,
SignedInteger Representations
Addition and Subtraction
If
carryin to the high order bit =
carryout
then ignore carry
if
carryin differs from
carryout
then overflow
Overflow
Conditions
Overflow when carryin to the
highorder bit does not equal carry out
2’sComplement Add and Subtract Operations
Figure : 2'scomplement 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 nbit
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 ANDOR
circuit for
ci+1
•
All sums can be obtained 1 gate delay after the carries are computed.
•
This is called Carry
Lookahead
adder.
4bit
carrylookahead
adder
Bcell
for a single stage
Carryout
from a 4bit block can be given as:
Rewrite
this as:
Subscript
I denotes the blocked carry lookahead
and identifies the block.
Cascade
4 4bit
adders, c16 can be expressed as:
Blocked CarryLookahead
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: 2bit by 2bit array
multiplier
• Combinatorial
array multipliers are:
Extremely inefficient.
Have
a high gate count for multiplying numbers of practical size such as 32bit or
64bit 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’scomplement signed
operands, (13)´(+11
•For a negative multiplier, a
straightforward solution is to form the 2’scomplement 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
BitPair
Recoding of Multipliers :
•Bitpair
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:
Nonrestoring 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:
Floatingpoint 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 Floatingpoint 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 (23bit mantissa, 8bit
exponent in excess127 representation)
•
Double precision:
 64 bits (52bit mantissa, 11bit
exponent in excess1023 representation)
Guard
Bits And
Rounding :
• While
adding two floating point numbers with 24bit 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 24bit mantissa.
Truncation/rounding
•Chopping:
•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
No comments