Transcript Boolean Operations

CS231: Computer Architecture I
Laxmikant Kale
Fall 2002
Review
•
There are 10 kinds of people in the
world
– Those who understand binary
and those who don’t
0000
0
0001
1
2
3
4
5
257
6
68
7
8
120
9
45
10
27
11
32
12
13
14
15
Introduction to CS231
16
1
Binary addition example worked out
•
•
Some terms are given here
Exercise: what are these numbers equivalent to in decimal?
The initial carry
in is implicitly 0
1
+
1
1
1
1
1
most significant
bit (MSB)
1
0
1
0
0
1
1
0
1
0
1
(Carries)
(Augend)
(Addend)
(Sum)
least significant
bit (LSB)
Introduction to CS231
2
Basic Gates
•
There are three basic kinds of logic gates
Operation:
AND
of two inputs
OR of two
inputs
NOT
(complement)
on one input
Logic gate:
•Two Questions:
•How can we implement such switches?
•What can we build with Gates? And How?
Introduction to CS231
3
Doing addition with gates
•
Lets do simple stuff first:
– Can we add two numbers each with just 1 bit?
• Bit: binary digit
– 0+0 = 0, 0+1 = 1 , 1+0 = 1, and 1+1 = ???
• 2. But 2 is not a symbol.
• 10 (just as 5 + 5 is 10 in decimal)
• Result is 0 with 1 carried over to the next bit..
– Whats 1 and 0? High and low voltage respectively.
Half adder
Result
Carry
Introduction to CS231
4
Half adder: result
Result
Output is 1 iff
exactly one of the 2
inputs is 1
This circuit is so common,
that it has a name an
symbol as a gate by
itself: Exclusive OR
Exclusive OR
Introduction to CS231
5
Adding two bits
•
•
•
A half adder is used to add two bits.
The result consists of two bits: a sum (the right bit) and a carry out
(the left bit)
Here is the circuit and its block symbol
0
0
1
1
+0
+1
+0
+1
=0
=1
=1
= 10
Introduction to CS231
6
Adding three bits
•
But what we really need to do is add three bits: the augend and addend,
and the carry in from the right.
1
+
1
1
1
1
1
X
Y
Cin
Cout
S
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
0
1
0
0
1
1
0
1
0
0
0
0
0
1
1
1
1
0
1
1
0
1
0
1
+0
+0
+1
+1
+0
+0
+1
+1
+0
+0
+0
+1
+0
+1
+0
+1
Introduction to CS231
= 00
= 01
= 01
= 10
= 01
= 10
= 10
= 11
7
Full adder circuit
•
•
Why are these things called half adders and full adders?
You can build a full adder by putting together two half adders.
Introduction to CS231
8
A 4-bit adder
•
•
•
Four full adders together can make a 4-bit adder
There are nine total inputs to the 4-bit adder:
– two 4-bit numbers, A3 A2 A1 A0 and B3 B2 B1 B0
– an initial carry in, CI
The five outputs are:
– a 4-bit sum, S3 S2 S1 S0
– a carry out, CO
Introduction to CS231
9
An example of 4-bit addition
•
Let’s put our initial example into this circuit: A=1011, B=1110
1
1
1
0
1
1
1
•
•
•
•
•
•
1
1
1
0
0
1
0
0
0
1
Step 1: Fill in all the inputs, including CI=0
Step 2: The circuit produces C1 and S0 (1 + 0 + 0 = 01)
Step 3: Use C1 to find C2 and S1 (1 + 1 + 0 = 10)
Step 4: Use C2 to compute C3 and S2 (0 + 1 + 1 = 10)
Step 5: Use C3 to compute CO and S3 (1 + 1 + 1 = 11)
The final answer is 11001
Introduction to CS231
10
Now that we can add, how about some memory?
•
•
•
•
We want to save results computed before, and recall them in a later
calculation, for example
Gates help us build memory
How can a circuit “remember” anything on its own?
– After all, the values on the wires are always changing, as outputs
are generated in response to inputs.
The basic idea is feedback: we make a “loop” in the circuit, so the
circuit outputs are inputs as well
When S and R are 0, Q
is “stable”: whatever it
was, it stays in that
state. Ergo : memory.
When S is 1 and R is 0, Q becomes 1
Set and Reset inputs…
When R is 1 and S is 0, Q becomes 0
Introduction to CS231
11
So, we have built a calculator
•
•
•
•
It is not a computer yet…
– We have to type each step into a calculator
– We’d like to “program” standard steps
• E.g. Add 57 numbers sitting in memory in specific places
– Also, support other operations (subtract..)
Two new ideas and components are needed for this:
– Addressable memory
– Stored Program
Addressable memory
– Memory organized in a bunch of locations, such that contents of specified
location can be brought back to the adder when needed.
– Each memory location has an “address” (binary, of course)
Stored Program:
– The instructions for which numbers to operate on, what operation to do
(add/subtract, ..) and where to store the result
– The instructions themselves can be represented in binary and stored in the
memory!
– The processor must have circuits to decode and “interpret” these instructions
Introduction to CS231
12
Components of a basic computer
Data
ALU
(Arithmetic/Logic Unit:
Basic operations
Memory
Program
Control and Decoding
Introduction to CS231
13
Summary
•
•
•
•
•
Controllable Switches are easy to make
These switches can be used to put together “Logic Gates”
Logic Gates can be put together to make half adder, full adders and
multi-bit adders
– So we can see they can be used for other such circtuits as well
Logic Gates can be used to make circtuits that “remember” or store
data
A Computer includes, at its heart :
– An ALU (Arithmetic Logic Unit)
– Instruction Decoding and associated circuits
– Memory
– Stored Program
Introduction to CS231
14
Number systems
•
To get started, we’ll discuss one of the fundamental concepts
underlying digital computer design:
Deep down inside, computers work with just 1s and 0s.
•
•
•
Computers use voltages to represent information. In modern CPUs the
voltage is usually limited to 1.6-1.8V to minimize power consumption.
It’s convenient for us to translate these analog
Volts
voltages into the discrete, or digital, values 1 and 0.
1.8
But how can two lousy digits be useful for anything?
1
– First, we’ll see how to represent numbers with
just 1s and 0s.
– Then we’ll introduce special operations
0
for computing with 1s and 0s, by treating them as
0
the logical values “true” and “false.”
©2000-2002 Howard Huang
15
Rest of Today’s lecture
•
•
•
Having seen an overview last week,
– We will now start a more thorough study
Number systems
– Review of binary number representation
– How to convert between binary and decimal representations
– Octal and Hex representations
Basic boolean operations
– AND, OR and NOT
– The idea of “Truth Table”
– Boolean functions and expressions
– Truth table for Boolean expressions
Introduction to CS231
16
Decimal review
•
Numbers consist of a bunch of digits, each with a weight:
1
100
•
2
1
.
3
1/10
7
1/100
5
Digits
1/1000 Weights
The weights are all powers of the base, which is 10. We can rewrite the
weights like this:
1
102
•
6
10
6
101
2
100
.
3
10-1
7
10-2
5
10-3
Digits
Weights
To find the decimal value of a number, multiply each digit by its weight
and sum the products.
(1 x 102) + (6 x 101) + (2 x 100) + (3 x 10-1) + (7 x 10-2) + (5 x 10-3) = 162.375
Introduction to CS231
17
Converting binary to decimal
•
•
We can use the same trick to convert binary, or base 2, numbers to
decimal. The only difference is that the weights are powers of 2.
For example, here is 1101.01 in binary:
1
23
•
1
22
0
21
1
20
.
0
2-1
1
2-2
Binary digits, or bits
Weights (in base 10)
The decimal value is:
(1 x 23) + (1 x 22) + (0 x 21) + (1 x 20) + (0 x 2-1) + (1 x 2-2) =
8
+
4
+
0
+
1
+
0
+ 0.25 = 13.25
Powers of 2:
20 = 1
21 = 2
22 = 4
23 = 8
24
25
26
27
=
=
=
=
16
32
64
128
28 = 256
29 = 512
210 = 1024
Introduction to CS231
18
Converting decimal to binary
•
•
•
To convert a decimal integer into binary, keep dividing by 2 until the
quotient is 0. Collect the remainders in reverse order.
To convert a fraction, keep multiplying the fractional part by 2 until it
becomes 0. Collect the integer parts in forward order.
Example: 162.375:
162 / 2
81 / 2
40 / 2
20 / 2
10 / 2
5/2
2/2
1/2
•
= 81
= 40
= 20
= 10
=5
=2
=1
=0
rem 0
rem 1
rem 0
rem 0
rem 0
rem 1
rem 0
rem 1
0.375 x 2 = 0.750
0.750 x 2 = 1.500
0.500 x 2 = 1.000
So, 162.37510 = 10100010.0112
Introduction to CS231
19
Why does this work?
•
•
This works for converting from decimal to any base
Why? Think about converting 162.375 from
decimal to decimal.
162 / 10 = 16
16 / 10 = 1
1 / 10 = 0
•
•
rem 2
rem 6
rem 1
Each division strips off the rightmost digit (the
remainder). The quotient represents the remaining
digits in the number.
Similarly, to convert fractions, each multiplication
strips off the leftmost digit (the integer part).
The fraction represents the remaining digits.
0.375 x 10 = 3.750
0.750 x 10 = 7.500
0.500 x 10 = 5.000
Introduction to CS231
20
Base 16 is useful too
•
The hexadecimal system uses 16 digits:
0123456789ABCDEF
•
•
•
You can convert between base 10 and base
16 using techniques like the ones we just
showed for converting between decimal and
binary.
For our purposes, base 16 is most useful as
a “shorthand” notation for binary numbers.
– Since 16 = 24, one hexadecimal digit is
equivalent to 4 binary digits.
– It’s often easier to work with a number
like B4 instead of 10110100.
Hex is frequently used to specify things
like 32-bit IP addresses and 24-bit colors.
Introduction to CS231
Decimal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Binary
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Hex
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
21
Binary and hexadecimal conversions
•
Converting from hexadecimal to binary is easy: just replace each hex
digit with its equivalent 4-bit binary sequence.
261.3516 =
2
6
1
.
3
516
= 0010 0110 0001 . 0011 01012
•
To convert from binary to hex, make groups of 4 bits, starting from the
binary point. Add 0s to the ends of the number if needed. Then, just
convert each bit group to its corresponding hex digit.
10110100.0010112 = 1011
=
B
0100 . 0010 11002
4
.
2
C16
Hex
Binary
Hex
Binary
Hex
Binary
Hex
Binary
0
0000
4
0100
8
1000
C
1100
1
0001
5
0101
9
1001
D
1101
2
0010
6
0110
A
1010
E
1110
3
0011
7
0111
B
1011
F
1111
Introduction to CS231
22
Number Systems Summary
•
•
•
Computers are binary devices.
– We’re forced to think in terms of base 2.
– Today we learned how to convert numbers between binary, decimal
and hexadecimal.
We’ve already seen some of the recurring themes of architecture:
– We use 0 and 1 as abstractions for analog voltages.
– We showed how to represent numbers using just these two signals.
Next we’ll introduce special operations for binary values and show how
those correspond to circuits.
Introduction to CS231
23
Boolean Operations
•
•
So far, we’ve talked about how arbitrary numbers can be represented
using just the two binary values 1 and 0.
Now we’ll interpret voltages as the logical values “true” and “false”
instead. We’ll show:
– How functions can be defined for expressing computations
– How to build circuits that implement our functions in hardware
©2000-2002 Howard Huang
24
Boolean values
•
•
•
•
Earlier, we used electrical voltages to represent
Volts
two discrete values 1 and 0, from which binary numbers
1.8
can be formed.
True
It’s also possible to think of voltages as representing
two logical values, true and false.
False
For simplicity, we often still write digits instead:
0
– 1 is true
– 0 is false
We will use this interpretation along with special operations to design
functions and hardware for doing arbitrary computations.
Introduction to CS231
25
Functions
•
•
Computers take inputs and produce outputs, just like functions in math!
Mathematical functions can be expressed in two ways:
An expression is
finite but not unique
A function table is
unique but infinite
f(x,y) = 2x + y
=x+x+y
= 2(x + y/2)
= ...
•
x
y
f(x,y)
0
…
2
…
23
…
0
…
2
…
41
…
0
…
6
…
87
…
We can represent logical functions in two analogous ways too:
– A finite, but non-unique Boolean expression.
– A truth table, which will turn out to be unique and finite.
Introduction to CS231
26
Basic Boolean operations
•
There are three basic operations for logical values.
Operation:
AND (product)
of two inputs
Expression:
xy, or xy
Truth table:
OR (sum) of
two inputs
NOT
(complement)
on one input
x+y
x’
x
y
xy
x
y
x+y
x
x’
0
0
0
0
0
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
1
1
1
1
1
1
Introduction to CS231
27
Boolean expressions
•
We can use these basic operations to form more complex expressions:
f(x,y,z) = (x + y’)z + x’
•
•
Some terminology and notation:
– f is the name of the function.
– (x,y,z) are the input variables, each representing 1 or 0. Listing the
inputs is optional, but sometimes helpful.
– A literal is any occurrence of an input variable or its complement.
The function above has four literals: x, y’, z, and x’.
Precedences are important, but not too difficult.
– NOT has the highest precedence, followed by AND, and then OR.
– Fully parenthesized, the function above would be kind of messy:
f(x,y,z) = (((x +(y’))z) + x’)
Introduction to CS231
28
Truth tables
•
•
•
A truth table shows all possible inputs and outputs of a function.
Remember that each input variable represents either 1 or 0.
– Because there are only a finite number of values (1 and 0), truth
tables themselves are finite.
– A function with n variables has 2n possible combinations of inputs.
Inputs are listed in binary order—in this example, from 000 to 111.
f(x,y,z) = (x + y’)z + x’
f(0,0,0)
f(0,0,1)
f(0,1,0)
f(0,1,1)
f(1,0,0)
f(1,0,1)
f(1,1,0)
f(1,1,1)
= (0 + 1)0 + 1
= (0 + 1)1 + 1
= (0 + 0)0 + 1
= (0 + 0)1 + 1
= (1 + 1)0 + 0
= (1 + 1)1 + 0
= (1 + 0)0 + 0
= (1 + 0)1 + 0
=1
=1
=1
=1
=0
=1
=0
=1
Introduction to CS231
x
y
z
f(x,y,z)
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
1
0
1
29
Primitive logic gates
•
Each of our basic operations can be implemented in hardware using a
primitive logic gate.
– Symbols for each of the logic gates are shown below.
– These gates output the product, sum or complement of their inputs.
Operation:
Expression:
AND (product)
of two inputs
OR (sum) of
two inputs
xy, or xy
x+y
NOT
(complement)
on one input
x’
Logic gate:
Introduction to CS231
30
Expressions and circuits
•
•
•
Any Boolean expression can be converted into a circuit by combining
basic gates in a relatively straightforward way.
The diagram below shows the inputs and outputs of each gate.
The precedences are explicit in a circuit. Clearly, we have to make sure
that the hardware does operations in the right order!
(x + y’)z + x’
Introduction to CS231
31
Boolean operations summary
•
•
•
•
•
•
We can interpret high or low voltage as representing true or false.
A variable whose value can be either 1 or 0 is called a Boolean variable.
AND, OR, and NOT are the basic Boolean operations.
We can express Boolean functions with either an expression or a truth
table.
Every Boolean expression can be converted to a circuit.
Next time, we’ll look at how Boolean algebra can help simplify
expressions, which in turn will lead to simpler circuits.
Introduction to CS231
32