Transcript Chapter 4 Part I

CHAPTER 4: PART I
ARITHMETIC FOR
COMPUTERS
1
The MIPS ALU
• We’ll be working with the MIPS instruction set architecture
– similar to other architectures developed since the 1980's
– used by NEC, Nintendo, Silicon Graphics, Sony
• Below is the Interface Representation of an ALU
operation
a
32
ALU
result
32
b
32
2
Numbers
• Bits are just bits (no inherent meaning)
– conventions define relationship between bits and
numbers
• Binary numbers (base 2)
0000 0001 0010 0011 0100 0101 0110 1000 1001...
For an n-bit representation: The decimals
represented: 0...2n-1
• Of course it gets more complicated:
Numbers are finite (possibility of overflow)
How can fractions and real numbers be represented?
How can negative numbers be represented?
• We will consider the representation of negative numbers.
3
Possible Representations
One’s Compliment Two’s Compliment
signed
signed
Unsigned
Sign Magnitude
000 = 0
000 = +0
000 = +0
000 = +0
001 = 1
001 = +1
001 = +1
001 = +1
010 = 2
010 = +2
010 = +2
010 = +2
011 = 3
011 = +3
011 = +3
011 = +3
100 = 4
100 = -0
100 = -3
100 = -4
101 = 5
101 = -1
101 = -2
101 = -3
110 = 6
110 = -2
110 = -1
110 = -2
111 = 7
111 = -3
111 = -0
111 = -1
Works on positives
only
Addition Complicated
Zero not unique
Zero unique
•Issues: balance, number of zeros, ease of operations
•Two’s compliment best to represent signed integers.
4
Converting between positive decimal and binary
•
•
Convert decimal 49 to 8-bit binary:
49/2 = 24 r 1
24/2 = 12 r 0
12/2 = 6 r 0
6/2 = 3 r 0
3/2 = 1 r 1
1/2 = 0 r 1
Now read the remainders from bottom to top: the binary equivalent is 110001.
In 8 bit form, it is: 0011 0001. In 16 bit form it is: 0000 0000 0011 0001
It is very easy to convert from a binary number to a decimal number. Just like
the decimal system, we multiply each digit by its weighted position, and add
each of the weighted values together. For example, the binary value 0100 1010
represents:
0100 1010  0  27  1 26  0  25  0  24  1 23  0  22  1 21  0  20
 64  8  2  74
5
Converting between negative decimal and binary
•
•
Convert decimal -50 to 8-bit binary.
– Convert 50 to binary:
Now read the remainders from bottom upwards 50 = 110010
– Extend to 8 bits: 0011 0010
– Invert bits:
1100 1100
Get 2’s compliment
– Add 1: -50 =
1100 1101
Answer is 1100 1101
Convert 1101 1011 to decimal.
– Invert bits:
0010 0100
– Add 1:
0010 0101
– Convert to decimal: 20  22  25  1  4  32  37 Final answer = -37.
6
Two’s Complement Number System
•
Take 8 bit binary:
0 = 0000 0000
1 = 0000 0001 -1 = 1111 1111
2 = 0000 0010 -2 = 1111 1110
3 = 0000 0011 -3 = 1111 1101
? = 0111 1111
? = 1000 0000
•
Largest positive = 28/2 – 1
•
Smallest negative = - 28/2
7
MIPS
• 32 bit signed numbers:
0000
0000
0000
...
0111
0111
1000
1000
1000
...
1111
1111
1111
0000 0000 0000 0000 0000 0000 0000two = 0ten
0000 0000 0000 0000 0000 0000 0001two = + 1ten
0000 0000 0000 0000 0000 0000 0010two = + 2ten
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1111
1111
0000
0000
0000
1110two
1111two
0000two
0001two
0010two
=
=
=
=
=
+
+
–
–
–
2,147,483,646ten
2,147,483,647ten
2,147,483,648ten
2,147,483,647ten
2,147,483,646ten
1111 1111 1111 1111 1111 1111 1101two = – 3ten
1111 1111 1111 1111 1111 1111 1110two = – 2ten
1111 1111 1111 1111 1111 1111 1111two = – 1ten
8
Addition & Subtraction (4 bit word)
•
Using the regular algorithm for binary addition, add (5+12), (-5+12), (-12+-5),
and (12+-12) in Two's Complement system. Then convert back to decimal
numbers.
5+12
-5+12
-12+-5
12+-12
00000101 11111011 11110100 00001100
00001100 00001100 11111011 11110100
00010001 00000111 11101111 00000000
17
7
- 17
0
9
Examples
• Convert 37, -56, 2, -5 into 8 bit 2’s compliment:
• Convert the 8-bit signed binary to decimal:
(a) 0010 0110
(b) 1001 1011
(c) 0110 1111
• Carryout the addition by first converting into 8 bits 2’s
compliment numbers:
(a) 89+23
(b) 49-23
(c) 5+56
10
Detecting Overflow
• No overflow when adding a positive and a negative number
• No overflow when signs are the same for subtraction
• Overflow occurs when the value affects the sign:
– overflow when adding two positives yields a negative
– or, adding two negatives gives a positive
– or, subtract a negative from a positive and get a negative
– or, subtract a positive from a negative and get a positive
• Consider the operations A + B, and A – B
– Can overflow occur if B is 0 ?
– Can overflow occur if A is 0 ?
• Detection of overflow in signed bit addition: Carry in into
most significant bit ≠ carry out.
11
Boolean Algebra and logic gates
• Transistors inside a modern computer are digital with two values 1,
0 (high and low voltage: asserted or de-asserted).
• Boolean variable: Takes only two values - true (1), false (0).
• proposition : In formal logic, a proposition (statement) is a
declarative sentence that is true or false.
• Boolean operators: Used to construct propositions out of other
propositions.
• Gates: Hardware implementing basic Boolean operators. The basic
gates are NOT (negation), AND (conjunction), OR (disjunction).
• Boolean algebra: Deals with Boolean (logical) variables and logic
operations operating on those variables. A Boolean function can be
expressed algebraically with:
– Binary variables;
– Logic operations symbols;
– Parentheses;
12
– Equal sign.
Boolean Algebra and logic gates
• Truth tables: All possible values of input determine various values
of outputs. These values can be represented using a truth table.
• Logic diagram: Composed of graphic symbols for logic gates.
Represents Boolean functions. To represent a function with n binary
variables, we need a list of 2n combinations.
• Logic blocks are physical components:
– Combinational: Without memory. The output depends only on
the current input.
– Sequential: Have memory (state). The output and state depend
on the input and state.
13
Truth tables of operators and Logical Gates
Gates: AND, OR, NAND, NOR, XOR.
a
0
0
1
1
b
0
1
0
1
AND
0
0
0
1
a AND b = ab
OR
0
1
1
1
NAND
1
1
1
0
NOR
1
0
0
0
a OR b = a+b
a NOR b = a+b
a NAND b = ab
a XOR b = a
b
14
Truth table for expressions
Ex : Draw truth tab
les for :
y  ab  ac ;
y  (a  b)  b
15
Proving identities using truth tables
16
Basic Identities of Boolean Algebra
1
x0  x
x1  x
Indentity
2
3
x 1  1
xx  x
x0  0
xx  x
Domination
Idemponent
4
5
x  x 1
x y  yx
x  x 1
xy  yx
Inverse
Commutative
6
7
x  ( y  z)  ( x  y)  z
x( y  z )  xy  xz
x( yz )  ( xy ) z
x  yz  ( x  y )( x  z )
Associativity
Distributive
8
xx
9
( x  y)  x y
xy  x  y
DeMorgan
10
x  xy  x
x( x  y )  x
Absorption
Complementary
17
Proving Boolean identities using algebra
• Boolean identities can be used to simplify
expressions and prove identities.
P rovetheBooleanindentit ies using algebra
ab  a b  b  1
( x  y )(x  z )  x  yz
a (b  a )  b  b
ab  a  b c  b
18
Sum of Products
• Given any Boolean expression,
one can draw a truth table.
• Given any truth table with inputs
and outputs, can one get a
Boolean expression of each output
in terms of the inputs
corresponding to the truth table?
• Example: What is the formula of
output A in terms of inputs x, y,
and z?
• First answer: Sum of Products
Formula
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
A
1
0
1
1
0
0
0
1
19
Sum of Products
• Consider inputs: x, y,
z; outputs F, G
• The sum of products
formulae for outputs F
and G are:
F  x yz  x yz  x yz  xyz  xyz
G  x yz  x yz  xyz  xyz
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
F
0
1
0
0
1
1
1
1
G
1
0
0
0
1
0
1
1
20
Programmable Logical Arrays, PLAs
A PLA is a customizable AND matrix followed by a customizable
OR matrix. It directly implements a sum of products formula.
Inputs
AND gates
Product terms
OR gates
Outputs
21
Karnaugh-maps (K-maps)
• K-maps are used to simplify sum of products logical formulas
(with 2, 3, or 4 inputs) using the truth table.
• K-map approach is to minimize the number of product terms
• Programs exists to simplify more complicated formulas
• A K-map for 2 inputs: x, y
• Why the need for simplified formulas? Smaller and thus
cheaper logical components.
22
Example
x
0
0
1
1
y
0
1
0
1
A
1
1
0
0
A  x y  xy (Sum of Products)
A  x (K-map simplification)
23
K-maps for 3-4 inputs
24
Examples: 3 input K-maps
x y
z
F G H J
0 0
0
0
1
0
0
0 0
1
1
0
0
0
0 1
0
0
0
0
0
0 1
1
0
0
0
0
1 0
0
1
1
1
0
1 0
1
1
0
0
1
1 1
0
1
1
1
0
1 1
1
1
1
0
1
25
Examples: 3 input K-maps
• The outputs simplify
to:
F  yz  x
G  yz  yx
H  xz
J  xz
26
Examples: 4 input K-maps
K  ac  acd
L  bd  acd  bc  abcd
27
Combining Gates
Circuits for output functions:
Output = x + yz, Output = x + yz and Output = (x +y)(x + z)
y
z
x
y
z
x
Output = x + yz
Output = x + yz
x
y
x
z
Output = (x +y)(x + z)
28
Multiple Inputs
• We can construct a multiple-input gate consisting of many
AND gates (or one with many OR gates). Due to the
Associatively law, the order with which the gates are
operated is not important.
• The output of a multiple-input AND gate is 1 only if all the
inputs are.
• The output of a multiple-input OR gate is 1 if any of the
inputs is 1.
• We can also place multiple inputs to other gates such as the
NAND, NOR or XOR gates.
• The multiple gates XOR gates indicates 1 of the number of
1’s of odd and 0 if the number of 1’s is even. This feature can
be used in error detection devices.
29
Multiple Inputs
30
Design of a computer component.
• Technology => Performance
Complex Cell
CMOS Logic Gate
Transistor
Wires
31
Basic Technology: CMOS
• CMOS: Complementary Metal Oxide Semiconductor
– NMOS (N-Type Metal Oxide Semiconductor) transistors
– PMOS (P-Type Metal Oxide Semiconductor) transistors
• NMOS Transistor
– Apply a HIGH (Vdd) to its gate turns the transistor into a
“conductor”
– Apply a LOW (GND) to its gate shuts off the conduction path
• PMOS Transistor
– Apply a HIGH (Vdd) to its gate shuts off the conduction path
– Apply a LOW (GND) to its gate turns the transistor into a
“conductor”
32
Basic Components: CMOS Inverter
NOT Symbol (Inverter)
In
Out
.
• Inverter Operation
Vdd
PMOS
In
Out
NMOS
Vdd
Vdd
Out
Open
Out
Open
Discharge
33
Basic Components: CMOS Logic Gates
NOR Gate
NAND Gate
A
A
Out
B Out
0
0
1
1
B
0
1
0
1
1
1
1
0
A
A
Out
B
Vdd
0
0
1
1
B Out
0
1
0
1
1
0
0
0
Vdd
A
Out
B
B
Out
A
34
Boolean Function Example
• Problem: Consider a logic function with three inputs: A,
B, and C.
Output D is true if at least one input is true
Output E is true if exactly two inputs are true
Output F is true only if all three inputs are true
• Show the truth table for these three functions.
• Show the Boolean equations for these three functions.
• Show an implementation consisting of inverters, AND, and
OR gates.
35
Boolean Function Example
•
•
•
•
•
Inputs: A, B. C; Outputs: D, E, F
D is true if at least one input is true.
E is true if exactly two inputs are true.
F is true if all the inputs are true.
The truth table will contain 23 = 8 entries
A
0
0
0
0
1
1
1
1
Inputs
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
D
0
1
1
1
1
1
1
1
Outputs
E
0
0
0
1
0
1
1
0
F
0
0
0
0
0
0
0
1
36
Boolean Function Example: PLA
Inputs
A
B
C
Outputs
D
Inputs
E
A
F
B
AND plane
C
Abbreviated PLA
Outputs
D
OR plane
E
F
37
Boolean Function Example
• The Boolean Functions corresponding to the outputs above
are:
• The equation for D:
D=A+B+C
• The equation for F:
F = ABC
• The equation for E:
E  ABC  ABC  ABC  ( AB  AC  BC)( ABC)
38
The Multiplexor
• Selects one of the inputs to be the output, based on a
control input
S
A
0
B
1
C
note: we call this a 2-input mux
even though it has 3 inputs!
Or a 1-select multiplexor.
• If (S = = 0) C = A else C = B
39
Implementing a 2-input multiplexor
c  s  a  s b
If s  0 : then c  1 a  0  b  a
If s  1: then c  0  a  1 b  b
40
The 1 bit Logical Unit for AND and OR
Operation
a
0
Result
b
1
41
The Multiplexor with 2 selects
• if (S == 00)
Out = A
else if (S == 01) Out = B
else if (S == 10) Out = C
else if (S == 11) Out = D
2
S
A
B
C
0
1
2
D
3
Out
42
Designing a Full Adder
• Binary addition is done with carries from right to left
(0)
0
0
(0) 0
...
...
...
(0)
0
0
(0) 0
(1)
0
0
(0) 1
(1)
1
1
(1) 1
(0)
1
1
(1) 0
(Carries)
1
0
(0) 1
• Input and output specification for a 1-bit adder
a
0
0
0
0
1
1
1
1
Inputs
b
0
0
1
1
0
0
1
1
CarryIn
0
1
0
1
0
1
0
1
Output
CarryOut
0
0
0
1
0
1
1
1
Sum
0
1
1
0
1
0
0
1
43
Designing a Full Adder
• From the sum of products
formula, the Sum is:
Sum  abCarryin  abCarryin  abCarryin  abCarryin
CarryOut  b CarryIn  a CarryIn  a b
• The sum of products formula
for CarryOut can be
simplified to give:
• One can design a Full Addera
circuit with
Inputs = a, b, CarryIn
Outputs = Sum, CarryOut b
• We will abstract this Full
Adder circuit as 
CarryIn
+
CarryOut
Sum
44