Computer Organization

20IMCAT203
Module III

1
 Syllabus
Module Title: Arithmetic and Logic Unit
Number Representation – Addition of Positive Numbers – Addition and Subtraction of
Signed Numbers – Design of Fast Adders – Carry Look Ahead Addition – Multiplication
of Positive Numbers – Signed Operand Multiplication (Booth’s Algorithm)

(Hamachar, Vranesic & Zaky, ”Computer Organization”, 5th Edition, McGrawHill, 2011 –
Chapter 2 and Chapter 6)

2
 Introduction
• Computers are built using logic circuits that operate on information represented by two
valued electrical signals.

• The two values are 0 and 1.

• Define the amount of information represented by such a signal as a bit of information.

• Bit stands for binary digit.

• The most natural way to represent a number in a computer system is by a string of bits,
called a binary number.

• A text character can also be represented by a string of bits called a character code.

3
 Number Representation
• A digital system can understand positional number system only where there are a few
symbols called digits and these symbols represent different values depending on the
position they occupy in the number.

• A value of each digit in a number can be determined using

• The digit

• The position of the digit in the number

• The base of the number system (where base is defined as the total number of
digits available in the number system).

4
 Decimal Number System
• The number system that we use in our day-to-day life is the decimal number
system.
• Decimal number system has base 10 as it uses 10 digits from 0 to 9.
• In decimal number system, the successive positions to the left of the decimal point
represents units, tens, hundreds, thousands and so on.
• Each position represents a specific power of the base (10).
• For example, the decimal number 1234 consists of the digit 4 in the units position, 3
in the tens position, 2 in the hundreds position, and 1 in the thousands position,
and its value can be written as:

5
Number System

6
 Binary Number System

• Characteristics
• Uses two digits, 0 and 1.
• Also called base 2 number system
• Each position in a binary number represents a 0 power of the base (2). Example:
20
• Last position in a binary number represents an x power of the base (2). Example:
2x where x represents the last position - 1.
• Example
• Binary Number: 101012
• Calculating Decimal Equivalent −

7
 Octal Number System
• Characteristics
• Uses eight digits, 0,1,2,3,4,5,6,7.
• Also called base 8 number system
• Each position in an octal number represents a 0 power of the base (8). Example:
80
• Last position in an octal number represents an x power of the base (8). Example:
8x where x represents the last position - 1.
• Example
• Octal Number − 125708
• Calculating Decimal Equivalent

8
 Hexadecimal Number System

• Characteristics

• Uses 10 digits and 6 letters, 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

• Letters represents numbers starting from 10. A = 10, B = 11, C = 12, D = 13, E = 14, F =
15.
• Also called base 16 number system.

• Each position in a hexadecimal number represents a 0 power of the base (16).

Example 160.
• Last position in a hexadecimal number represents an x power of the base (16).
Example 16x where x represents the last position - 1.
9
 Hexadecimal Number System
• Example −
• Hexadecimal Number: 19FDE16
• Calculating Decimal Equivalent −

10
11
 Number Representation
• Consider an n-bit vector
• B = bn-1…….b1b0 //// 00111010 n=8, n-1=7
• Where bi = 0 or 1 for 0 <= i <= n-1.
• This vector can be represented unsigned integer values V in the range 0 to 2n-1,
where
• V(B)= bn-1 x 2n-1 + … + b1 x 21 + b0 x 20

• We need to represent both positive and negative numbers.

• Three systems are used for representing such numbers:
• Sign–and–magnitude
• 1’s-complement
• 2’s-complement

12
 Number Representation
• The simplest way of representing a signed number is the sign magnitude(SM)
method.
Sign and magnitude
− The sign-magnitude binary format is the simplest conceptual format. In this method
of representing signed numbers, the most significant digit (MSD) takes an extra
meaning.
• If the MSD is a 0, we can evaluate the number just as we would any normal
unsigned integer. And also we shall treat the number as a positive one.
• If the MSD is a 1, this indicates that the number is negative.
• The other bits indicate the magnitude (absolute value) of the number. Some of
signed decimal numbers and their equivalent in SM notation follows assuming a
word size of 4 bits.

13
Number Representation

14
 Number Representation
• Sign–and–magnitude
• Negative values are represented by changing the most significant bit from 0 to
1.
• +3 = 0011 and -3 = 1011

• 1’s-complement
• Negative values are obtained by complementing each bit of the corresponding
positive number.
• +3 = 0011 and -3 = 1100

• 2’s-complement
• By adding 1 to the 1’s complement of that number.
• +3 = 0011 and -3 = 1101

15
 Number Representation
• In all three systems, the leftmost bit is 0 for positive numbers and 1 for negative
numbers.

16
Addition of Positive Numbers

17
 Addition of Positive Numbers

• The sum of 1 and 1 requires the 2-bit vector 10 to represent the value 2.
• We say that the sum is 0 and carry-out is 1.

• In order to add multiple bit numbers, addition starts from the low-order(right)
end of the bit vectors, propagating carries toward the high-order (left)
end.

18
Addition of Positive Numbers

19
 Addition of Positive Numbers

• Example 1: 10001 + 11101

• Example 2: 10111 + 110001

• Example 3: 101101 + 11001

• Example 4: 1011001 + 111010

• Example 5: 1110 + 1111

• Example 6: 10111 + 110101

• Example 7: 11011 + 1001010

20
Addition and Subtraction of Signed Numbers

21
 Arithmetic Addition
Signed-magnitude Addition
• The addition of two numbers in the signed-magnitude system follows the rules of
ordinary arithmetic.

• If the signs are the same, we add the two magnitudes and give the sum the common
sign.

• If the signs are different, we subtract the smaller magnitude from the larger and give
the result the sign of the larger magnitude.

• For example, (+25) + (-37) = -(37 - 25) = -12 and is done by subtracting the smaller
magnitude 25 from the larger magnitude 37 and using the sign of 37 for the sign of the
result. 22
 Arithmetic Addition

Signed 2's complement addition

• The addition of two numbers in the signed 2's complement addition system follows.
• Add the two numbers, including their sign bits, and discard any carry out of the sign
(leftmost) bit position.

• Numerical examples for addition are shown below.

Eg 1: +6 00000110
+13 00001101
+19 00010011

Eg 2: -6 11111010 (Signed 2's complement of -6)

+13 00001101 +
+7 1]00000111
23
 Arithmetic Addition
Eg3: +6 00000110
-13 11110011 (Signed 2's complement of -13)
–7 11111001 (Signed 2's complement of -7)

Eg4: -6 11111010 (Signed 2's complement of -6)

-13 11110011 (Signed 2's complement of -13)
-19 1] 11101101 (Signed 2's complement of -19)

24
 Addition of two Signed Binary Numbers

• Consider the two signed binary numbers A & B, which are represented in 2’s
complement form.

• We can perform the addition of these two numbers, which is similar to the addition of
two unsigned binary numbers.

• But, if the resultant sum contains carry out from sign bit, then discard it in order to get
the correct value.

• If resultant sum is positive, you can find the magnitude of it directly.

• But, if the resultant sum is negative, then take 2’s complement of it in

order to get the magnitude. 25
 ⇒+7+710 ++4+410 = 01011010112.

Arithmetic Addition

• Let us perform the addition of two decimal numbers +7 and +4 using 2’s complement
method.
• The 2’s complement representations of +7 and +4 with 5 bits each are shown below.
• +710 = 001112
• +410 = 001002
• The addition of these two numbers is:
• +710 ++410 = 001112+001002
⇒+710 ++410 = 010112
• The resultant sum contains 5 bits. So, there is no carry out from sign bit.
• The sign bit ‘0’ indicates that the resultant sum is positive. So, the magnitude of sum is
11 in decimal number system.
• Therefore, addition of two positive numbers will give another positive number.
26
 Addition of two Signed Binary Numbers
Example 2
• Let us perform the addition of two decimal numbers -7 and -4 using 2’s complement
method.
• The 2’s complement representation of -7 and -4 with 5 bits each are shown below.

−710 = 110012

−410 = 111002

• The addition of these two numbers is

−710 + −410 = 110012 + 111002

⇒ −710 + −410 = 1101012

27
 Addition of two Signed Binary Numbers

• The resultant sum contains 6 bits. In this case, carry is obtained from sign bit. So, we can
remove it.

• Resultant sum after removing carry is −710 + −410 = 101012.

• The sign bit ‘1’ indicates that the resultant sum is negative.

• So, by taking 2’s complement of it we will get the magnitude of resultant sum as 11 in
decimal number system.

• Therefore, addition of two negative numbers will give another negative

number.
28
 Subtraction of two Signed Binary Numbers

• Consider the two signed binary numbers A & B, which are represented in 2’s complement
form. We know that 2’s complement of positive number gives a negative number. So,
whenever we have to subtract a number B from number A, then take 2’s complement of B and
add it to A. So, mathematically we can write it as:
A - B = A + 2′s complement of B

• Similarly, if we have to subtract the number A from number B, then take 2’s complement of A
and add it to B. So, mathematically we can write it as:
B - A = B + 2′s complement of A

• So, the subtraction of two signed binary numbers is similar to the addition of two signed binary
numbers. But, we have to take 2’s complement of the number, which is supposed to be
subtracted. This is the advantage of 2’s complement technique. Follow, the same rules of
addition of two signed binary numbers.
29
 Subtraction of two Signed Binary Numbers
• Let us perform the subtraction of two decimal numbers +7 and +4 using 2’s complement method.
• The subtraction of these two numbers is:

+710 − +410 = +710 + −410

The 2’s complement representation of +7 and -4 with 5 bits each are shown below.
+710 = 001112

-410 = 111002

⇒+710 + -410 = 001112 + 111002 = 1000112

Here, the carry obtained from sign bit. So, we can remove it. The resultant sum after removing
carry is
+710 + -410 = 000112
The sign bit ‘0’ indicates that the resultant sum is positive. So, the magnitude of it is 3 in decimal
30
number system. Therefore, subtraction of two decimal numbers +7 and +4 is +3.
Example:
• Let us perform the subtraction of two decimal numbers +4 and +7 using 2’s complement
method.
• The subtraction of these two numbers is

+410 − +710 = +410 + −710

• The 2’s complement representation of +4 and -7 with 5 bits each are shown below.
+410 = 001002
−710 = 110012
⇒+410 + −710 = 001002 + 110012 = 111012

• Here, carry is not obtained from sign bit. The sign bit ‘1’ indicates that the resultant sum is
negative. So, by taking 2’s complement of it we will get the magnitude of resultant sum as 3 in
decimal number system. Therefore, subtraction of two decimal numbers +4 and +7 is -3.
31
 Arithmetic Subtraction
Example 1:
11010–1101

Example 2:
100 – 110000

Example 3:
1010100 – 1010100

Example 4:
-34 – (-45)

32
 Arithmetic Operations
• A basic operation in digital computers is the addition or subtraction of two numbers.
• Arithmetic operations occur at the machine instruction level.
• They are implemented, along with basic logic functions such as AND, OR, NOT, and
EXCLUSIVE-OR [XOR], in the arithmetic and logic unite (ALU] subsystem of the processor.
• Here we need to look on to the logic circuits used to implement arithmetic operations.
• The time needed to perform an addition operation affects the processor’s performance.
• Multiply and divide operations, which require more complex circuitry than either
addition or subtraction operations also affect performance.
• Compared with arithmetic operations, logic operations are simple to implement using
combinational circuitry. They require only independent Boolean operations on individual
bit positions of the operands, whereas carry/borrow lateral signals are required in
arithmetic operations.

33
Addition and Subtraction of Signed Numbers

34
Addition and Subtraction of Signed Numbers

35
Addition Logic for a Single Stage

36
An n-bit ripple-carry adder

37
Cascade of k n-bit adders

38
 Ripple Carry Adder-

• Ripple Carry Adder is a combinational logic circuit.

• It is used for the purpose of adding two n-bit binary numbers.

• It requires n full adders in its circuit for adding two n-bit binary numbers.

• It is also known as n-bit parallel adder.

4-bit Ripple Carry Adder-

• 4-bit ripple carry adder is used for the purpose of adding two 4-bit binary numbers.

39
In Mathematics, any two 4-bit binary numbers A3A2A1A0 and
B3B2B1B0 are added as shown below-

40
Using ripple carry adder, this addition is carried out as shown by the
following logic diagram-

41
• Ripple Carry Adder works in different stages.
• Each full adder takes the carry-in as input and produces carry-out and sum bit as
output.
• The carry-out produced by a full adder serves as carry-in for its adjacent most
significant full adder.
• When carry-in becomes available to the full adder, it activates the full adder.
• After full adder becomes activated, it comes into operation.

Why Ripple Carry Adder is Called So?

• In Ripple Carry Adder, The carry out produced by each full adder serves as carry-in
for its adjacent most significant full adder.
• Each carry bit ripples or waves into the next stage.
• That’s why, it is called as “Ripple Carry Adder”.

42
Disadvantages of Ripple Carry Adder-

• Ripple Carry Adder does not allow to use all the full adders simultaneously.
• Each full adder has to necessarily wait until the carry bit becomes available from its
adjacent full adder.
• This increases the propagation time.
• Due to this reason, ripple carry adder becomes extremely slow.
• This is considered to be the biggest disadvantage of using ripple carry adder.

• To overcome this disadvantage, Carry Look Ahead Adder comes into play.

43
 Design of Fast Adders

• If an n-bit carry adder is used in the addition/subtraction unit, it may have too much delay in
developing its outputs.

• The delay incurred is acceptable can be decided only in the context of the speed of other processor
components and the data transfer times of registers and cache memories.

• The delay through a network of logic gates depends on the integrated circuit electronic technology
used in fabricating the network and on the number of gates in the paths from inputs to outputs.

• The delay through any combinational logic network constructed from gates in a particular network is
determined by adding up the number of logic-gates delays along the longest signal propagation path
through the network.

• In the case of the n-bit ripple carry adder, the longest path is from inputs x 0, y0, and c0 at the LSB

position to outputs cn and sn-1 at the most-significant-bit [MSB] position.

44
 Design of Fast Adders

• Two approaches can be taken to reduce delay in adders.

• The first approach is to use the fastest possible electronic technology in implementing the
ripple-carry logic design or variations of it.
• The second approach is to use an augmented logic gate network structure that is larger
than the n-bit ripple carry adder. [Eg: Carry LookHead Adder]

• A number of design techniques have been used to implement high-speed adders. They
include electronic circuit designs for fast propagation of carry signals as well as variations on
the basic network structure as in Carry LookHead Adder.

45
 Carry Look Ahead Adder

• 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 ith block waits for the i-1th block to produce its carry.

• So there will be a considerable time delay which is called carry propagation delay.

• 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. 46
47
Carry Look Ahead Adder

• Consider the full adder circuit

shown with corresponding
truth table. If we define two
variables as carry generate Gi
and carry propagate Pi then,
• P i = Ai ⊕ B i
• Gi = Ai B i

• The sum output and carry

output can be expressed as
• Si = P i ⊕ C i
• C i +1 = Gi + Pi Ci
48
 Carry Look Ahead Adder
• Where Gi is a carry generate which produces the carry when both Ai, Bi are one
regardless of the input carry.
• Pi is a carry propagate and it is associate with the propagation of carry from Ci to Ci
+1.
• The carry output Boolean function of each stage in a 4 stage carry-Lookahead adder
can be expressed as
• C1 = G0 + P0 Cin
• C2 = G1 + P1 C1
= G1 + P1 G0 + P1 P0 Cin
• C3 = G2 + P2 C2
= G2 + P2 G1+ P2 P1 G0 + P2 P1 P0 Cin
• C4 = G3 + P3 C3
= G3 + P3 G2+ P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 Cin
49
 Carry Look Ahead Adder

• From the above Boolean equations we can observe that C4 does not have to wait
for C3 and C2 to propagate but actually C4 is propagated at the same time as C3 and
C2.

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

• Therefore, a 4 bit parallel adder can be implemented with the carry-Lookahead

scheme to increase the speed of binary addition as shown in below figure.

50
51
Multiplication of Positive Numbers

52
 Multiplication of Positive Numbers

• The usual algorithm for multiplying integers by hand is shown in slide# 52.

• This algorithm applies to unsigned numbers and to positive signed numbers.

• The product of two n-digit numbers can be accommodated in 2n digits. [The

product of the two 4-bit numbers fit into 8 bits].

• Binary multiplication of positive operands can be implemented in a combinational

two-dimensional logic array.

53
Array Multiplication of Positive Binary Operands

54
• In the binary system, multiplication of the multiplicand by one bit of the multiplier is easy.

• If the multiplier bit is 1, the multiplicand is entered in the appropriate position to be

added to the partial product.

• If the multiplier bit is , then is entered.

• Binary multiplication of positive operands can be implemented in a combinational two-

dimensional logic array, as shown in figure b in previous slide.

• The main component in each cell is a full adder FA.

• The AND gate in each cell determines whether a multiplicand bit ‘mj’, is added to the

incoming partial-product bit, based on the value of the multiplier bit ‘qi’.
55
Array Multiplication of Positive Binary Operands

56
 Sequential Multiplier
• Sequential Multiplier is an old method to multiply two binary numbers. But it is also
relevant in many architectures and it is the base of many newly developed
multiplication techniques. The multiplication between a and b is shown below.

57
Sequential Circuit Binary Multiplier

58
Sequential Circuit Binary Multiplier

59
Sequential Multiplier

60
 Array Multiplication of Positive Binary Operands

• Binary multiplication of positive operands can be implemented in a combinational

two-dimensional logic arrays.
• The main component in each cell is a full adder FA.

• The AND gate in each cell determines whether a multiplication bit, m j, is added to

the incoming partial-product bit, based on the value of the multiplier bit, qi.

61
Signed-Operand Multiplication

62
 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 notation.
• It is also used to speed up the performance of the multiplication process.
• The booth algorithm is a multiplication algorithm that allows us to multiply the two
signed binary integers in 2's complement, respectively.

63
 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 notation.
• It is also used to speed up the performance of the multiplication process.

64
65
66
Shift Arithmetic Right