Computer Organization and Architecture

UNIT II
SYLLABUS:
Arithmetic and logic unit: Look ahead carries adders. Multiplication: Signed operand multiplication,
Booths algorithm and array multiplier. Division and logic operations. Floating point arithmetic
operation, Arithmetic & logic unit design. IEEE Standard for Floating Point Numbers.

Carry Look-Ahead Adder

The••adder produce carry propagation delay while performing other arithmetic operations like
multiplication and divisions as it uses several additions or subtraction steps. This is a major
problem for the adder and hence improving the speed of addition will improve the speed of all
other arithmetic operations. Hence reducing the carry propagation delay of adders is of great
importance. There are different logic design approaches that have been employed to overcome the
carry propagation problem. One widely used approach is to employ a carry look-ahead which
solves this problem by calculating the carry signals in advance, based on the input signals. This type
of adder circuit is called a carry look-ahead adder.
Here a carry signal will be generated in two cases:
1. Input bits A and B are 1
2. When one of the two bits is 1 and the carry-in is 1.
In ripple carry adders, for each adder block, the two bits that are to be added are available
instantly. However, each adder block waits for the carry to arrive from its previous block. So, it is
not possible to generate the sum and carry of any block until the input carry is known. The
block waits for the block to produce its carry. So there will be a considerable time delay
which is carry propagation delay.
Consider the above 4-bit ripple carry adder. The sum is produced by the corresponding full
adder as soon as the input signals are applied to it. But the carry input is not available on its
final steady-state value until carry is available at its steady-state value. Similarly depends
on and on . Therefore, though the carry must propagate to all the stages in order that
output and carry settle their final steady-state value.
The propagation time is equal to the propagation delay of each adder block, multiplied by the
number of adder blocks in the circuit. For example, if each full adder stage has a propagation delay
of 20 nanoseconds, then will reach its final correct value after 60 (20 × 3) nanoseconds. The
situation gets worse, if we extend the number of stages for adding more number of bits.
Carry Look-ahead Adder :
A carry look-ahead adder reduces the propagation delay by introducing more complex hardware. In
this design, the ripple carry design is suitably transformed such that the carry logic over fixed
groups of bits of the adder is reduced to two-level logic. Let us discuss the design in detail.
Consider the full adder circuit shown above with corresponding truth table. We define two
variables as ‘carry generate’ and ‘carry propagate’ then,

The sum output and carry output can be expressed in terms of carry generate and carry
propagate as
where produces the carry when both , are 1 regardless of the input carry. is associated with the
propagation of carry from to .
The carry output Boolean function of each stage in a 4 stage carry look-ahead adder can be
expressed as

From the above Boolean equations we can observe that does not have to wait for and
to propagate but actually is propagated at the same time as and . Since the Boolean
expression for each carry output is the sum of products so these can be implemented with one
level of AND gates followed by an OR gate.

The implementation of three Boolean functions for each carry output ( , and ) for a
carry look-ahead carry generator shown in below figure.
Time Complexity Analysis :
We could think of a carry look-ahead adder as made up of two “parts”

1. The part that computes the carry for each bit.

2. The part that adds the input bits and the carry for each bit position.
The complexity arises from the part that generates the carry, not the circuit that adds the bits.
Now, for the generation of the carry bit, we need to perform a AND between (n+1) inputs. The
complexity of the adder comes down to how we perform this AND operation. If we have AND
gates, each with a fan-in (number of inputs accepted) of k, then we can find the AND of all the bits
in time. This is represented in asymptotic notation as .
Advantages and Disadvantages of Carry Look-Ahead Adder :
Advantages –

• The propagation delay is reduced.

• It provides the fastest addition logic.
Disadvantages –

• The Carry Look-ahead adder circuit gets complicated as the number of variables increase.
• The circuit is costlier as it involves more number of hardware.
Booth's Multiplication Algorithm
The booth algorithm is a multiplication algorithm that allows us to multiply the two signed binary
integers in 2's complement, respectively. It is also used to speed up the performance of the
multiplication process. It is very efficient too. It works on the string bits 0's in the multiplier that
requires no additional bit only shift the right-most string bits and a string of 1's in a multiplier bit
weight 2k to weight 2m that can be considered as 2k+ 1 - 2m.

Following is the pictorial representation of the Booth's Algorithm:

In the above flowchart, initially, AC and Qn + 1 bits are set to 0, and the SC is a sequence counter that
represents the total bits set n, which is equal to the number of bits in the multiplier. There are BR that
represent the multiplicand bits, and QR represents the multiplier bits. After that, we encountered
two bits of the multiplier as Qn and Qn + 1, where Qn represents the last bit of QR, and Qn + 1 represents
the incremented bit of Qn by 1. Suppose two bits of the multiplier is equal to 10; it means that we
have to subtract the multiplier from the partial product in the accumulator AC and then perform the
arithmetic shift operation (ashr). If the two of the multipliers equal to 01, it means we need to perform
the addition of the multiplicand to the partial product in accumulator AC and then perform the
arithmetic shift operation (ashr), including Qn + 1. The arithmetic shift operation is used in Booth's
algorithm to shift AC and QR bits to the right by one and remains the sign bit in AC unchanged. And
the sequence counter is continuously decremented till the computational loop is repeated, equal to
the number of bits (n).

Working on the Booth Algorithm

1. Set the Multiplicand and Multiplier binary bits as M and Q, respectively.
2. Initially, we set the AC and Qn + 1 registers value to 0.
3. SC represents the number of Multiplier bits (Q), and it is a sequence counter that is continuously
decremented till equal to the number of bits (n) or reached to 0.
4. A Qn represents the last bit of the Q, and the Qn+1 shows the incremented bit of Qn by 1.
5. On each cycle of the booth algorithm, Qn and Qn + 1 bits will be checked on the following parameters
as follows:
i. When two bits Qn and Qn + 1 are 00 or 11, we simply perform the arithmetic shift right operation
(ashr) to the partial product AC. And the bits of Qn and Qn + 1 is incremented by 1 bit.
ii. If the bits of Qn and Qn + 1 is shows to 01, the multiplicand bits (M) will be added to the AC
(Accumulator register). After that, we perform the right shift operation to the AC and QR bits
by 1.
iii. If the bits of Qn and Qn + 1 is shows to 10, the multiplicand bits (M) will be subtracted from the
AC (Accumulator register). After that, we perform the right shift operation to the AC and QR
bits by 1.
6. The operation continuously works till we reached n - 1 bit in the booth algorithm.
7. Results of the Multiplication binary bits will be stored in the AC and QR registers.
There are two methods used in Booth's Algorithm:

1. RSC (Right Shift Circular)

It shifts the right-most bit of the binary number, and then it is added to the beginning of the binary
bits.

2. RSA (Right Shift Arithmetic)

It adds the two binary bits and then shift the result to the right by 1-bit position.
Example: 0100 + 0110 => 1010, after adding the binary number shift each bit by 1 to the right and
put the first bit of resultant to the beginning of the new bit.

Example: Multiply the two numbers 7 and 3 by using the Booth's multiplication algorithm.

Ans. Here we have two numbers, 7 and 3. First of all, we need to convert 7 and 3 into binary numbers
like 7 = (0111) and 3 = (0011). Now set 7 (in binary 0111) as multiplicand (M) and 3 (in binary 0011)
as a multiplier (Q). And SC (Sequence Count) represents the number of bits, and here we have 4 bits,
so set the SC = 4. Also, it shows the number of iteration cycles of the booth's algorithms and then
cycles run SC = SC - 1 time.

Qn Qn + 1 M = (0111) AC Q Qn + 1 SC
M' + 1 = (1001) & Operation

1 0 Initial 0000 0011 0 4

Subtract (M' + 1) 1001

1001

Perform Arithmetic Right Shift operations (ashr) 1100 1001 1 3

1 1 Perform Arithmetic Right Shift operations (ashr) 1110 0100 1 2

0 1 Addition (A + M) 0111

0101 0100

Perform Arithmetic right shift operation 0010 1010 0 1

0 0 Perform Arithmetic right shift operation 0001 0101 0 0

The numerical example of the Booth's Multiplication Algorithm is 7 x 3 = 21 and the binary
representation of 21 is 10101. Here, we get the resultant in binary 00010101. Now we convert it into
decimal, as (000010101)10 = 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.
Example: Multiply the two numbers 23 and -9 by using the Booth's multiplication algorithm.

Here, M = 23 = (010111) and Q = -9 = (110111)

Qn Qn + 1 M=010111 AC Q Qn + 1 SC
M' + 1 = 1 0 1 0 0 1

Initially 000000 110111 0 6

1 0 Subtract M 101001

101001

Perform Arithmetic right shift operation 110100 111011 1 5

1 1 Perform Arithmetic right shift operation 111010 011101 1 4

1 1 Perform Arithmetic right shift operation 111101 001110 1 3

0 1 Addition (A + M) 010111

010100

Perform Arithmetic right shift operation 001010 000111 0 2

1 0 Subtract M 101001

110011

Perform Arithmetic right shift operation 111001 100011 1 1

1 1 Perform Arithmetic right shift operation 111100 110001 1 0

Qn + 1 = 1, it means the output is negative.

Hence, 23 * -9 = 2's complement of 111100110001 => (00001100111)