chapter 3 comp. arithmetc and digital logics - Copy.ppt

analyses arithmetic and digital logic in computer circut

1. COMPUTER ARITHMETIC

2. Introduction
•The two principal concerns for computer arithmetic are the
way in which numbers are represented (the binary format)
and the algorithms used for the basic arithmetic operations
(add, subtract, multiply, divide).
•These two considerations apply both to integer and
floating-point arithmetic and are the functions of arithmetic
logic unit (ALU) of the processor.

3. Arithmetic and Logic Unit (ALU)
•The ALU is that part of the computer that actually performs
arithmetic and logical operations on data.
•All of the other elements of the computer system such as
control unit, registers, memory and I/O are there mainly to
bring data into the ALU for it to process and then to take
the results back out.
•The figure shows how the ALU is interconnected with the
rest of the processor.

4. Arithmetic and Logic Unit (ALU)
•Data are presented to the ALU in registers and the results of
an operation are stored in registers. These registers are
temporary storage locations within the processor that are
connected by signal paths to the ALU.
•The ALU may also set flags as the result of an operation. For
example, an overflow flag is set to 1 if the result of a
computation exceeds the length of the register into which it is
to be stored.
•The control unit provides signals that control the operation of
the ALU and the movement of the data into and out of the
ALU.

5. Integer Representation

6. •Sign-Magnitude Representation
Negative integers can be represented using sign-magnitude
representation where the most significant (leftmost) bit in
the word is the sign bit.
If the sign bit is 0, the number is positive; if the sign bit is 1,
the number is negative.
Remaining bits represent the magnitude of the integer.
For example: +18 = 00010010
-18 = 10010010
Integer Representation

7. One drawback of this representation is that addition and
subtraction require a consideration of both the signs of the
numbers and their relative magnitudes to carry out the
required operation.
Another drawback is that there are two representations of 0:
+0 = 00000000
-0 = 10000000
Because of these drawbacks, sign-magnitude representation
is rarely used in implementing the integer portion of the
ALU.
Integer Representation

8. •Twos Complement Representation
It is the most commonly used scheme for integer representation. The
most significant bit is the sign bit and remaining bits represent the
magnitude.
Positive numbers are same as sign-magnitude. For example:
+18 = 00010010
0 is only represented with all zeros.
0 = 00000000
Negative numbers are found by taking the complement of each bit and
adding 1 to the complemented value. Example is shown for -7:
Start with +7= 00000111
Complement= 11111000
Add 1 = +00000001
-7= 11111001
Integer Representation

9. •Example 1: What is the twos complement representation of -55
using 8-bits?
Start with +55 = 00110111
Complement = 11001000
Add 1 =+00000001
-55 = 11001001
•Example 2: What is the twos complement representation of -21
using 8-bits?
Start with +21 = 00010101
Complement = 11101010
Add 1 =+00000001
-21 = 11101011
Integer Representation

10. •Converting between Different Bit Lengths
Suppose that an n-bit integer is needed to be stored in m-
bits, where m>n.
In sign-magnitude representation, sign bit is shifted to the
leftmost position and new added bits are set to 0’s. For
example an 8-bit value needed to be stored in 16-bit:
+18 = 00010010 → 0000000000010010
-18 = 10010010 → 1000000000010010
In twos complement representation, sign bit is also shifted to
the leftmost position and the new added bits are set to the
value of sign bit. This is called sign extension. Example (8
bit → 16 bit):
+18 = 00010010 → 0000000000010010
-18 = 11101110 → 1111111111101110
Integer Representation

11. •Addition
On any addition, the result may be larger than can be held
in the word size being used. This condition is called
overflow.
When overflow occurs, the ALU must signal this fact so
that no attempt is made to use the result.
To detect overflow, the following rule is observed: if two
numbers are added, and they are both positive or both
negative, then overflow occurs if and only if the result has
the opposite sign.
Integer Arithmetic

12. Figure shows examples of binary integer addition.
Note that in (b) and (d), there is a carry bit beyond the end of the
word (indicated by shading), which is ignored.
On the other hand, (e) and (f) show examples of overflow.
Integer Arithmetic

13. •Subtraction
To subtract one number (subtrahend) from another
(minuend), take the twos complement (negation) of the
subtrahend and add it to the minuend.
Thus, subtraction is achieved using addition.
a - b = a + (-b)
Integer Arithmetic

14. Figure shows examples of binary integer subtraction.
Note that in (b) and (c), carry bit is ignored.
On the other hand, (e) and (f) show examples of overflow.
Integer Arithmetic

15. Figure suggests the data paths and hardware elements needed
to accomplish addition and subtraction.
Integer Arithmetic

16. The central element is a binary adder, which is presented two
numbers for addition and produces a sum and an overflow
indication. The binary adder treats the two numbers as
unsigned integers.
For addition, the two numbers are presented to the adder from
two registers, designated in this case as A and B registers. The
result may be stored in one of these registers or in a third. The
overflow indication is stored in a 1-bit overflow flag.
For subtraction, the subtrahend (B register) is passed through a
complementor so that its twos complement is presented to the
adder. Control signals are needed to control whether or not the
complementor is used, depending on whether the operation is
addition or subtraction.
Integer Arithmetic

17. •Multiplication
Multiplication is a complex process when it is compared to
addition or subtraction.
A wide variety of algorithms have been used in various
computers.
Integer Arithmetic

18. Figure shows the multiplication of unsigned binary integers as
might be carried out using paper and pencil.
The multiplication of two n-bit binary integers results in a
product of up to 2n-bits in length.
Integer Arithmetic

19. Integer Arithmetic
Figure shows a possible implementation of multiplication
where multiplier and multiplicand are loaded into two registers
(Q and M). A third register, shown as A, is also needed and is
initially set to 0.
There is also a 1-bit C register, initialized to 0, which holds a
potential carry bit resulting from addition.

20. Control logic reads the bits of the multiplier one at a time.
If it is 1, then the multiplicand is added to the A register and the
result is stored in register A. Then all of the bits of the C, A,
and Q registers are shifted one bit to the right.
If it is 0, then no addition is performed, just the shift.
This process is repeated for each bit of the original multiplier.
The resulting 2n-bit product is contained in the A and Q
registers.
Integer Arithmetic

21. The flowchart of
unsigned binary
multiplication is
shown in the figure.
Integer Arithmetic

22. An example for multiplication of unsigned binary integers is
shown in the figure. Note that on the second cycle, when the
multiplier bit is 0, there is no add operation.
Integer Arithmetic

23. In the last example, we multiplied 11 (1011) by 13 (1101) to
get 143 (10001111). If we interpret these as twos complement
numbers, we have -5 (1011) times -3 (1101) equals -113
(10001111).
This example demonstrates that straightforward multiplication
will not work if either multiplicand or multiplier are negative.
One possible solution is to convert both multiplier and
multiplicand to positive numbers, perform the multiplication
and take twos complement of result if and only if the signs of
original numbers are different.
Implementers have preferred to use techniques that do not
require this final transformation step. One of most common of
these is Booth’s algorithm.
Integer Arithmetic

24. Booth’s algorithm for
twos complement
multiplication is shown
in the figure.
Integer Arithmetic

25. The multiplier and multiplicand are placed in the Q and M registers,
respectively. There is also a 1-bit register placed logically to the right of
the least significant bit of the Q register.
The results of the multiplication will appear in the A and Q registers.
As before, control logic scans the bits of the multiplier one at a time. Now,
as each bit is examined, the bit to its right is also examined.
If the two bits are the same, then all of the bits of the A, Q, and registers
are shifted to the right 1 bit.
If the two bits differ, then the multiplicand is added to or subtracted from
the A register, depending on whether the two bits are.
Following the addition or subtraction, the right shift occurs with keeping
the rightmost bit same as the shifted bit, which is known as arithmetic
shift. This is required to preserve the sign of the number in A and Q.
Integer Arithmetic

26. Integer Arithmetic
The figure shows an example to multiply 7 (0111) and 3
(0011) using Booth’s algorithm.
00010101 = 21
A Q Q-1 M Comment
0000 0011 0 0111Initial values
1001 0011 0 0111 A=A-M
1100 1001 1 0111 Shift right
1110 0100 1 0111 Shift right
0101 0100 1 0111 A=A+M
0010 1010 0 0111 Shift right
0001 0101 0 0111 Shift right

27. Integer Arithmetic
The figure shows an example to multiply 7 (0111) and -3 (1101) using
Booth’s algorithm.
11101011 = –21
A Q Q-1 M Comment
0000 1101 0 0111Initial values
1001 1101 0 0111 A=A-M
1100 1110 1 0111 Shift right
0011 1110 1 0111 A=A+M
0001 1111 0 0111 Shift right
1010 1111 0 0111 A=A-M
1101 0111 1 0111 Shift right
1110 1011 1 0111 Shift right

28. Integer Arithmetic
The figure shows an example to multiply -7 (1001) and 3 (0011) using
Booth’s algorithm.
11101011 = –21
A Q M Comment
0000 0011 0 1001Initial values
0111 0011 0 1001 A=A-M
0011 1001 1 1001 Shift right
0001 1100 1 1001 Shift right
1010 1100 1 1001 A=A+M
1101 0110 0 1001 Shift right
1110 1011 0 1001 Shift right

29. Integer Arithmetic
The figure shows an example to multiply -7 (1001) and -3 (1101) using
Booth’s algorithm.
00010101 = 21
A Q Q-1 M Comment
0000 1101 0 1001 Initial values
0111 1101 0 1001 A=A-M
0011 1110 1 1001 Shift right
1100 1110 1 1001 A=A+M
1110 0111 0 1001 Shift right
0101 0111 0 1001 A=A-M
0010 1011 1 1001 Shift right
0001 0101 1 1001 Shift right

30. •Division
Division is somewhat more complex than multiplication
but is based on the same general principles.
The basis for the algorithm is the paper-and-pencil
approach, and the operation involves repetitive shifting
and addition or subtraction.
Figure shows an example of the long division of
unsigned binary integers.
Integer Arithmetic

31. Integer Arithmetic
Figure shows a machine
algorithm that
corresponds to the long
division process.

32. Integer Arithmetic

33. Integer Arithmetic
An example for (7)/(3) is shown in the figure.
Quotient
Remainder
A Q M Comment
0000 0111 0011 Initial values
0000 1110 0011 Left Shift
1101 1110 0011 A=A-M
0000 1110 0011 Restore A
0001 1100 0011 Left shift
1110 1100 0011 A=A-M
0001 1100 0011 Restore A
0011 1000 0011 Left shift
0000 1000 0011 A=A-M
0000 1001 0011
0001 0010 0011 Left Shift
1110 0010 0011 A=A-M
0001 0010 0011 Restore A

34. Integer Arithmetic
A division operation can be defined as:
D = Q x V + R
where D is the dividend, Q is the quotient, V is the divisor and R
is the remainder.
The algorithm assumes that the divisor (V) and the dividend
(D) are positive and that V < D.
If V = D, then the quotient (Q) is 1 and the remainder (R) is 0.
If V > D, then the quotient (Q) is 0 and the remainder (R) is D.

35. Integer Arithmetic
This process can, with some difficulty, be extended to negative
numbers.
Consider the following examples of integer division with all
possible combinations of signs of D and V:
D = 7, V = 3 Q = 2, R = 1
D = 7, V = -3 Q = -2, R = 1
D = -7, V = 3 Q = -2, R = -1
D = -7, V =-3 Q = 2, R = -1
Note that the magnitudes of Q and R are unaffected by the
input signs but for example (-7/3) and (7/-3) produces different
remainders.

36. Integer Arithmetic
Actually, the signs of Q and R are easily derivable form the
signs of D and V where:
Sign(R) = Sign(D)
Sign(Q) = Sign(D) x Sign(V)
Hence, one way to do twos complement division is to convert
the operands into unsigned values and at the end, change the
signs by complementation where needed.

37. COMPUTER ARITHMETIC

38. •With a fixed-point (e.g. twos complement), it is possible to
represent a range of positive and negative integers centered on 0.
•By assuming a radix point, this format allows the representation
of numbers with a fractional component but with some
limitations.
•Very large numbers cannot be represented, nor can very small
fractions.
Floating-Point Representation

39. •Figure indicates the range of numbers that can be represented
in a 32-bit word.
Floating-Point Representation

40. •For decimal numbers, one gets around this limitation by using scientific
notation. Thus, for example:
976,000,000,000,000 = 9.76 × 10
14
0.0000000000000976 = 9.76 × 10
-14
•Sliding the decimal point to a convenient location and using the exponent of
10 to keep track of that decimal point allows a range of very large and very
small numbers to be represented with only a few digits.
Floating-Point Representation

41. Floating-Point Representation

42. Floating-Point Representation

43. Floating-Point Representation

44. Example:
•Write the representation of 8.375 x 2
5
in a 32-bit floating
point format.
Solution: Firstly, the number should be written in binary format.
Integer part:
8 = 1000
Floating point part:
0.375 x 2 = 0.75
0.75 x 2 = 1.5
0.5 x 2 = 1.0
0.375 = 011
So, 8.375 = 1000.011
Floating-Point Representation

45. •Secondly, normalize the value and find the biased exponent.
1000.011 x 2
5
= 1.000011 x 2
8
= 1.000011 x 2
1000
Exponent (8) = 00001000
Bias value (127) = + 01111111
Biased exponent= 10000111
Sign bit = 0
Significand = 00001100000000000000000
Biased Exponent = 10000111
Floating-Point Representation

46. Floating-Point Arithmetic
•In floating-point arithmetic, addition and subtraction are more
complex than multiplication and division because of need for
alignment.
• There are 4 basic phases for addition and subtraction:
1.Check for zeros
2.Align the significands
3.Add or subtract the significands
4.Normalize the result

47. •Digital Logics
47

48. Introduction
•In the latter part of the nineteenth century, George Boole
incensed philosophers and mathematicians alike when he
suggested that logical thought could be represented
through mathematical equations.
•How dare anyone suggest that human thought could be
encapsulated and manipulated like an algebraic formula?
•Computers, as we know them today, are implementations
of Boole’s Laws of Thought.
•John Atanasoff and Claude Shannon were among the first
to see this connection.
48

49. •In the middle of the twentieth century, computers were
commonly known as “thinking machines” and
“electronic brains.”
•Many people were fearful of them.
•Nowadays, we rarely ponder the relationship between
electronic digital computers and human logic. Computers
are accepted as part of our lives.
•Many people, however, are still fearful of them.
49

50. Boolean Algebra
•Boolean algebra is a mathematical system for the
manipulation of variables that can have one of two
values.
•In formal logic, these values are “true” and “false.”
•In digital systems, these values are “on” and “off,”
1 and 0, or “high” and “low.”
•Boolean expressions are created by performing
operations on Boolean variables.
•Common Boolean operators include AND, OR, and
NOT.
50

51. •A Boolean operator can be completely
described using a truth table.
•The truth table for the Boolean operators
AND and OR are shown at the right.
•The AND operator is also known as a
Boolean product. The OR operator is
the Boolean sum.
51

52. •The truth table for the Boolean NOT operator is shown
below.
•The NOT operation is most often designated by an
overbar. It is sometimes indicated by a prime mark ( ‘ ) or
an “elbow” (

).
52

53. •A Boolean function has:
At least one Boolean variable,
At least one Boolean operator, and
At least one input from the set {0,1}.
•It produces an output that is also a member of the
set {0,1}.
53
That is why the binary numbering system is
so convenient in digital systems.

54. •The truth table for the
Boolean function:

is shown at the right.
•To make evaluation of the
Boolean function easier, the
truth table contains extra
(shaded) columns to hold
evaluations of subparts of the
function.
54

55. •As with common arithmetic,
Boolean operations have
rules of precedence.
•The NOT operator has
highest priority, followed by
AND and then OR.
•This is how we chose the
(shaded) function subparts in
table.
55

56. •Digital computers contain circuits that implement
Boolean functions.
•The simpler that we can make a Boolean function, the
smaller the circuit that will result.
•Simpler circuits are cheaper to build, consume less
power, and run faster than complex circuits.
•With this in mind, we always want to reduce our
Boolean functions to their simplest form.
•There are a number of Boolean identities that help us to
do this.
56

57. •Most Boolean identities have an AND (product) form as well
as an OR (sum) form. Here are identities using both forms.
First group is rather intuitive:
57

58. •Second group of Boolean identities: Basic Postulates
58

59. •Last group of Boolean identities are perhaps the most useful
specially in set theory or formal logic
59

60. •We can use Boolean identities to simplify the function:
as follows:
60

61. •Sometimes it is more economical to build a circuit using
the complement of a function (and complementing its
result) than it is to implement the function directly.
•DeMorgan’s law provides an easy way of finding the
complement of a Boolean function.
•Recall DeMorgan’s law states:
61

62. •DeMorgan’s law can be extended to any number of
variables.
•Replace each variable by its complement and change all
ANDs to ORs and all ORs to ANDs.
•Thus, we find the complement of:
is:
62

63. •Through our exercises in simplifying Boolean
expressions, we see that there are numerous ways of
stating the same Boolean expression.
•These “synonymous” forms are logically equivalent.
•Logically equivalent expressions have identical truth
tables.
•In order to eliminate as much confusion as possible,
designers express Boolean functions in standardized or
canonical form.
63

64. •There are two canonical forms for Boolean expressions:
sum-of-products and product-of-sums.
•Recall the Boolean product is the AND operation and the
Boolean sum is the OR operation.
•In the sum-of-products form, ANDed variables are ORed
together.
•For example:
•In the product-of-sums form, ORed variables are ANDed
together:
•For example:
64

65. •It is easy to convert a function to
sum-of-products form using its truth
table.
•Look at the values of the variables
that make the function true (=1).
•Using the truth table, we list the
values of the variables that result in
a true function value.
•Each group of variables is then
ORed together.
65

66. •The sum-of-products form for
the function is:
66
This function is not in simplest
terms. The main aim is only to
rewrite the function in canonical
sum-of-products form.

67. Logic Gates
•We have looked at Boolean functions in abstract terms.
•In this section, we see that Boolean functions are
implemented in digital computer circuits called gates.
•A gate is an electronic device that produces a result based
on two or more input values.
•In reality, gates consist of one to six transistors, but digital
designers think of them as a single unit.
•Integrated circuits contain collections of gates suited to a
particular purpose.
67

68. •The three simplest gates are the AND, OR, and NOT gates.
•They correspond directly to their respective Boolean
operations, as you can see by their truth tables.
68

69. •Another very useful gate is the exclusive OR (XOR) gate.
•The output of the XOR operation is true only when the
values of the inputs differ.
69
Note the special symbol 
for the XOR operation.

70. •NAND and NOR are two very important gates. Their
symbols and truth tables are shown below.
70

71. •NAND and NOR are
known as universal
gates because they are
inexpensive to
manufacture and any
Boolean function can be
constructed using only
NAND or only NOR
gates.
71

72. •Gates can have multiple inputs and more than one
output.
•A second output can be provided for the complement
of the operation.
72

73. Digital Components
•The main thing to remember is that combinations of gates
implement Boolean functions.
•The circuit below implements the Boolean function:
73
simplified Boolean expressions so that
we can create simpler circuits.

74. Combinational Circuits
•We have seen a circuit that implements the Boolean function:
•This circuit is an example of a combinational logic circuit.
•Combinational logic circuits produce a specified output
(almost) at the instant when input values are applied.
74

75. •Combinational logic circuits give us
many useful devices.
•Adder:
One of the simplest is the half adder,
which finds the sum of two bits.
We can gain some insight as to the
construction of a half adder by
looking at its truth table, shown at
the right.
75

76. •As we see, the sum can be found using the XOR
operation and the carry using the AND operation.
76

77. •A half adder can be changed
into a full adder by including
gates for processing the carry
bit.
•The truth table for a full
adder is shown at the right.
77

78. •How can we change the half
adder shown below to make it
a full adder?
78

79. •Here’s a completed full adder.
79

80. •Just as we combined half adders to make a full adder, full
adders can connected in series.
•The carry bit “ripples” from one adder to the next; hence, this
configuration is called a ripple-carry adder.
80
Today’s systems employ more efficient adders.

81. •Decoders:
Decoders are another important type of combinational circuit.
Among other things, they are useful in selecting a memory
location according a binary value placed on the address lines
of a memory bus.
Address decoders with n inputs can select any of 2
n
locations.
81
This is a block diagram for a decoder.

82. •This is what a 2-to-4 decoder looks like on the inside.
82
If x = 0 and y = 1,
which output line
is enabled?

83. •Multiplexer:
A multiplexer does just the
opposite of a decoder.
It selects a single output from
several inputs.
The particular input chosen for
output is determined by the value
of the multiplexer’s control lines.
To be able to select among n
inputs, log
2n control lines are
needed.
83
This is a block
diagram for a
multiplexer.

84. •This is what a 4-to-1 multiplexer looks like on the inside.
84
If S
0 = 1 and S
1 = 0,
which input is
transferred to the
output?

85. •Combinational logic circuits are perfect for situations when
we require the immediate application of a Boolean function to
a set of inputs.
•There are other times, however, when we need a circuit to
change its value with consideration to its current state as well
as its inputs.
These circuits have to “remember” their current state.
•Sequential logic circuits provide this functionality for us.
85

86. Sequential Circuits
•As the name implies, sequential logic circuits require a
means by which events can be sequenced.
•State changes are controlled by clocks.
•A “clock” is a special circuit that sends electrical pulses
through a circuit.
•Clocks produce electrical waveforms such as the one
shown below.
86

87. •State changes occur in sequential circuits only when the
clock ticks.
•Circuits can change state on the rising edge, falling edge, or
when the clock pulse reaches its highest voltage.
87

88. •Circuits that change state on the rising edge, or falling
edge of the clock pulse are called edge-triggered.
•Level-triggered circuits change state when the clock
voltage reaches its highest or lowest level.
88

89. •To retain their state values, sequential circuits rely on
feedback.
•Feedback in digital circuits occurs when an output is looped
back to the input.
•A simple example of this concept is shown below.
•If Q is 0 it will always be 0, if it is 1, it will always be 1.
Why?
89

90. •You can see how feedback works by examining the most
basic sequential logic components, the SR flip-flop.
The “SR” stands for set/reset.
•The internals of an SR flip-flop are shown below, along
with its block diagram.
90

91. •The behavior of an SR flip-flop is described by a
characteristic table.
•Q(t) means the value of the output at time t.
Q(t+1) is the value of Q after the next clock pulse.
91

92. •The SR flip-flop actually has
three inputs: S, R, and its
current output, Q.
•Thus, we can construct a
truth table for this circuit, as
shown at the right.
•Notice the two undefined
values. When both S and R
are 1, the SR flip-flop is
unstable.
92

93. •If we can be sure that the inputs to an SR flip-flop will
never both be 1, we will never have an unstable circuit.
This may not always be the case.
•The SR flip-flop can be modified to provide a stable
state when both inputs are 1.
93
• This modified flip-flop is
called a JK flip-flop, shown at
the right.
- The “JK” is in honor of
Jack Kilby.

94. •At the right, we see
how an SR flip-flop can
be modified to create a
JK flip-flop.
•The characteristic table
indicates that the flip-
flop is stable for all
inputs.
94

95. •Another modification of the SR flip-flop is the D flip-flop,
shown below with its characteristic table.
•You will notice that the output of the flip-flop remains the
same during subsequent clock pulses. The output changes
only when the value of D changes.
95

96. •The D flip-flop is the fundamental circuit of
computer memory.
•D flip-flops are usually illustrated using the block
diagram shown below.
•The characteristic table for the D flip-flop is shown
at the right.
96