Transcript Logic circuits and Boolean Algebra

Review: Our Friend the Logic Puzzle
•
Frank will go to the party if
Ed goes AND Dan does NOT.
•
Dan will go if Bob does NOT go OR if Carole goes.
•
Ed will go to the party if Alice AND Bob go.
• Let’s start with the Truth Table instead
Logic Puzzle Circuit via Truth Table
A
B
C
AND
F
A
B
C
F
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
0
Universal Method: Circuits from Any
Truth Table (another example)
First, make circuits
for each row in the
Truth Table that has
a 1 in the output.
A
B
C
X
0
0
0
1
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
Another Example (contd)
A
B
C
AND
A
B
C
AND
A
B
C
X
0
0
0
1
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
Another Example (contd)
A
B
C
AND
Finally, combine them
with an OR gate.
OR
A
B
C
AND
X
• The only way X=1 is
if at least ONE of the
AND gates outputs a 1.
• But each AND gate
corresponds to a row
in the Truth Table
with a 1 in the output!
Truth Table with Multiple Outputs
X Y
A
B
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
Truth Table with Multiple Outputs
•
Same as 2 Truth Tables:
X Y
A
B
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
So we can convert into 2 circuits
X
0
0
1
1
Y
0
1
0
1
A
0
0
0
1
X
0
0
1
1
Y
0
1
0
1
B
0
1
1
0
Build Circuits using Universal Mtehod
X
Y
X
Y
AND
OR
AND
X Y
A
0
0
0
0
1
0
1
0
0
1
1
1
B
X Y
B
0
0
0
0
1
1
1
0
1
1
1
0
X
Y
AND
A
Build Circuits using Universal Mtehod
X
Y
X
Y
X
Y
AND
AND
AND
OR
B
A
Cleaning up the Drawing
AND
X
Y
AND
AND
OR
B
A
Universality
•
Same idea works no matter how many input/output variables.
•
So for ANY Truth Table we can write down, we can make a
circuit for it using only 3 Logic Gates: AND, OR, NOT
•
This gives us a very powerful tool !
•
Our first technical use of abstraction: “Make a circuit for that
Truth Table” is something we can abstract and understand.
Additional Issues
Some issues to think about on your own
•
We know that AND,OR, and NOT together are
“universal” – we can make a circuit for any Truth Table
using just these gates ! What else is universal?
•
Surprising answer: There is a single gate
called “NAND” which is universal all by itself!
NAND Gate
X
NAND
Y
X
Y
AND
Logically, AND followed by NOT
If the AND’s output were a 0,
the NAND’s will be a 1
And vice versa
Z
Z
X Y
Z
0
0
1
0
1
1
1
0
1
1
1
0
NOT Gate from NAND Gate
X
NAND
Z
X
Z
NOT
Y
X Y
Z
0
0
1
0
1
1
1
0
1
1
1
0
X
Z
0
1
1
0
Is there a fixed value of Y for which NAND table reduces to NOT?
NOT Gate from NAND Gate
X
NAND
Z
Fix Y at 1
Y
X Y
Z
0
0
1
0
1
1
1
0
1
1
1
0
Truth Table
X
NAND
Z
1
X Y
Z
0
1
1
1
1
0
Truth Table
Are We Done?
Limitations of the Universal Method
•
For how large a circuit can we realistically expect to use the
Universal Method?
•
What do we do for larger circuits?
•
How do we simplify them?
•
Recall two circuits that both solved our logic puzzle, one
simpler than the other
Numeracy
•
How large do circuits get?
•
How large do truth tables get?
Numeracy (contd)
X
Y
0
1
1
0
1-input Truth Table
2 rows
Numeracy (contd)
X
Y
0
1
1
0
1-input Truth Table
2 rows
X Y
Z
0
0
0
0
1
1
1
0
1
1
1
1
2-input Truth Table
4 rows
Numeracy (contd)
A
B
C
F
3-input
Truth
Table:
0
0
0
0
0
0
1
1
0
1
0
1
8 rows
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
0
Numeracy (contd)
Inputs
Rows in truth table
1
2
2
4
3
8
4
??
5
??
Arbitrary N
??
Numeracy (contd)
•
Each input can be 0 or 1 : 2 possibilities.
•
So if there are 4 inputs, that is a total of
2 * 2 * 2 * 2 = 16 possible input values.
Numeracy (contd)
Inputs
Rows in truth table
1
2
2
4
3
8
4
16
5
??
Arbitrary N
??
Numeracy (contd)
Inputs
Rows in truth table
1
2
2
4
3
8
4
16
5
32
Arbitrary N
??
Numeracy (contd)
•
Each input can be 0 or 1 : 2 possibilities.
•
In general, if there are n inputs, there will be
2 * 2 * 2 * 2 * 2 * … * 2 (n times),
or 2n possible input values.
Numeracy (contd)
Inputs
Rows in truth table
1
2
2
4
3
8
4
16
5
32
Arbitrary N
2N
Powers of 2
•
2n comes up a lot in Computer Science.
•
Numbers to memorize:
•
21 = 2,
•
2 = 16,
2 = 32,
2 = 64,
•
27 = 128,
28 = 256,
29 = 512,
•
210 = 1024
4
22 = 4,
5
23 = 8,
6
Keep Memorizing …
210 = 1,024
220 = 1,048,576
30
2 = 1,073,741,824
240 = 1,099,511,627,776
50
2 = 1,125,899,906,842,624
260 = 1,152,921,504,606,846,976
Let’s Make it Easier
•
Some rough numbers:
210 = 1,024  1,000
(103)
220 = 1,048,576  1,000,000 (106)
[ = (103)2]
230  1,000,000,000
(109)
[ = (103)3]
240  1,000,000,000,000
(1012)
[ = (103)4]
250 
(1015)
260 
(1018 )
Powers of 2 (contd)
•
Some rough numbers:
210  1,000 (103 )
kilo
220  1,000,000 (106 )
mega
RAM
230  109
giga
disk
240  1012
tera
BIG disk
250  1015
peta
260  1018
exa
knowledge
Sidebar on Exabytes
• It's taken the entire history of humanity through 1999 to
accumulate 12 exabytes of information. By June 2002, the
second dozen exabytes were created
• 1 exabytes = 50,000 times the library of congress
• Floppy disks to make 1 exabyte would stack 24 million miles
high.
Powers of 2 (contd)
•
16 inputs means Truth Table
has 216 = 210 * 26 = 1,024 * 64
 64,000 rows
•
Circuit could have more than 64,000 gates
Limitations of Universal Method
•
What about 100 inputs?
•
Is it reasonable to use Universal Method on Truth Table
with 100 inputs?
Limitations of Universal Method
•
What about 100 inputs:
•
Is it reasonable to use Universal Method on Truth Table
with 100 inputs?
•
2100  1030
•
Each AND/OR/NOT gate uses at least 1 transistor.
•
This is way beyond current technology, in fact . . .
Limitations of Universal Method
•
State-of-the-art transistors are about 0.1 micrometer (mm)
on a side:
•
Lined end-to-end, you could fit
10,000,000 transistors in 1 m. ( 3 f.)
•
In a 1 m. by 1 m. square, you could fit
100,000,000,000,000 transistors
•
That’s still 999,999,999,999,999,
900,000,000,000,000
too few for 100 input Truth Table !
How Sad Should We Be?
Not Very
•
Just use many Truth Tables, each having fewer inputs.
•
Can make an entire computer using only 16-input Truth
Tables and the Universal Method!
•
On the other hand, must realize that in some cases, we need
more efficient special purpose circuits than the Universal
Method. (We won’t cover these.)
Our First Abstract Tool
Universal Method: Circuits for ANY Truth Table
0’s
&
1’s
Universal
Method
Computers
We are here
So What?
•
We can build logic circuits for 0’s
and 1’s now
•
But why should we?
•
Answer: Because we can
represent so many things
with 0’s and 1’s.
The Meaning of 0 and 1
•
In Logic, we thought of 0 and 1
as meaning True and False.
•
Now, we remove these connotations.
•
Definition: a bit (binary digit) is just a single variable that
can take value either 0 or 1.
Representing Information
•
Information in the world comes in many
forms – letters, numbers, pictures, sounds…
•
How can we represent these things
with 0’s and 1’s?
•
Let’s start with numbers
Representing Numbers
•
Before computers, in many devices, numbers were typically
represented continuously
•
e.g. Analog Clocks:
•
But discrete integers are very important:
•
How many computers do you own?
Binary Numbers
•
How do we count normally?
•
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, … 19, 20, 21 …
100, … 999,
1000, …
98, 99,
•
Suppose we only had two numerals: 0 and 1.
•
Then how would we count?
0, 1,
10, 11,
100, 101, 110, 111,
1000, 1001, 1010 …
1111,
Binary Numbers (contd)
0
0
1
1
2
10
3
11
4
100
5
101
6
110
7
111
8
1000
What are binary numbers?
• Base 2 rather than base 10
• Decimal numbers
– We write (1234)10 to represent a decimal number that
has 4 units, 3 tens, 2 hundreds and 1 thousand.
– (1234)10 = 1 x103 + 2 x102 + 3 x101 + 4 x100
What are binary numbers?
• Base 2 rather than base 10
• Decimal numbers
– We write (1234)10 to represent a decimal number that
has 4 units, 3 tens, 2 hundreds and 1 thousand.
– (1234)10 = 1 x103 + 2 x102 + 3 x101 + 4 x100
• Binary numbers
– We write (1001)2 to represent a binary number that has
1 unit, 0 2’s, 0 4’s and 1 8.
– (1001)2 = 1 x23 + 0 x22 + 0 x21 + 1 x20
Conversion
•
If (10)10 is called 10, what do we call (10)2 ?
•
Can we convert between binary and decimal?
(123)10 = 2*61 + 1
= 22*30 + 21 *1 + (20 * )1
= 23*15 + 0* 22 + 21 *1 + (20 * )1
= 26 + 25 + 24 + 23 + 21 + 2 0
……. = (1111011)2
(101101) 2 = 25 + 23 + 22 + 20 = 32 + 8 + 4 + 1 = 45
From Decimal to Binary: Method 1
101710 / 2
= 508
+ R1
1
508 / 2
= 254
+ R0
0
254 / 2
= 127
+ R0
0
127 / 2
= 63
+ R1
1
63 / 2
= 31
+ R1
1
31 / 2
= 15
+ R1
1
15 / 2
=7
+ R1
1
7/2
=3
+ R1
1
3/2
=1
+ R1
1
1/2
=0
+ R1
1
11111110012 = 101710
From Decimal to Binary: Method 1
101710
- 512 (29)
1
505
- 256 (28)
1
249
- 128 (27)
1
121
- 64 (26)
1
57
- 32 (25)
1
25
- 16 (24)
1
9
- 8 (23)
1
1
[(22)]
0
1
[(21)]
0
1
- 1 (20)
1
11111110012 = 101710
Binary Numbers (contd)
•
Addition :
1 0 1
+
1 1 1
_________________
Binary Numbers (contd)
•
Addition – Our “basic” addition table is really easy now:
0+0=0
0+1=1
1+0=1
1 + 1 = 10
Binary Numbers (contd)
•
Addition – just like usual:
1 0 1
+
1 1 1
_______________
0+0=
0
0+1=
1
1+0=
1
1 + 1 = 10
Binary Numbers (contd)
•
Addition – just like usual:
+
1
0+0=
0
1 0 1
0+1=
1
1 1 1
1+0=
1
_______________
0
1 + 1 = 10
Binary Numbers (contd)
•
Addition – just like usual:
+
1 1
0+0=
0
1 0 1
0+1=
1
1 1 1
1+0=
1
_______________
0 0
1 + 1 = 10
Binary Numbers (contd)
•
Addition – just like usual:
+
1 1
0+0=
0
1 0 1
0+1=
1
1 1 1
1+0=
1
_______________
1
1 0 0
1 + 1 = 10
Binary Numbers (contd)
•
If (10)10 is called 10, what do we call (10)2 ?
•
Can we convert between binary and decimal?
(123)10 = 2*61 + 1
= 22*30 + 21 *1 + (20 * )1
3
2
1
0
= 2 *15 + 0* 2 + 2 *1 + (2 * )1
= 26+ 25 + 24 + 23 + 21 + 20
……. = (1111011)2
(101101) 2 = 25 + 23 + 22 + 20 = 32 + 8 + 4 + 1 = 45
Binary Numbers (contd)
•
•
Can also do:
•
Subtraction, Multiplication, etc
•
Negative Numbers
•
Fractions
Great, but where do Logic Circuits fit in?
Binary Numbers (contd)
•
And you thought we were done with truth tables
•
For Addition on small numbers, can make a truth table:
X Y
Z
0
0
0
0
1
1
1
0
1
1
1
10
Problem:
Output can
be 2 bits
sometimes
Binary Numbers (contd)
•
Addition Truth Table with Multiple Outputs:
X Y
A
B
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0
Binary Numbers (contd)
•
Same as 2 Truth Tables:
X Y
A
X Y
B
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
Binary Numbers (contd)
•
•
Same as 2 Truth Tables:
X Y
A
X Y
B
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
1
1
1
1
1
0
Now we can convert into 2 circuits!
Binary Numbers (contd)
X
Y
X
Y
AND
OR
AND
X Y
A
0
0
0
0
1
0
1
0
0
1
1
1
B
X Y
B
0
0
0
0
1
1
1
0
1
1
1
0
X
Y
AND
A
Binary Numbers (contd)
X
Y
X
Y
AND
OR
AND
B
X Y
B
0
0
0
0
1
1
1
0
1
1
1
0
This is often called the eXclusive OR (XOR) circuit
We say that B is the exclusive OR of X and Y.
We write B = X
Y.
A Logic Puzzle
•
Bob will go to the party if
Ed goes OR Dan goes.
•
Dan will go if Xena does NOT go AND
Yanni goes.
•
Ed will go if Xena goes AND
Yanni does NOT go.
•
This is addition without the carry
•
Bob goes if the XOR of Xena and Yanni go.
A Simple Breakthrough
•
We can represent information by bits.
(So we interpret bits to mean things like numbers.)
•
Then we re-interpret those bits as Logical True/False values
•
Finally we use Universal Method to construct circuits for
operations on information (like Addition)
Intermission
• Questions??
• How are we going to build a circuit for addition?
Addition
X1 X2
Y1 Y2
=========
C Z1 Z2
C is the carry bit
X1
X2
Y1
Y2
Z1
Z2
C
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
1
0
0
0
0
1
1
1
1
0
0
1
0
0
0
1
0
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
1
0
0
1
1
0
0
0
1
0
0
1
0
0
1
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
1
1
1
1
0
0
1
1
0
1
1
0
1
0
0
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
Addition
X1 X2
Y1 Y2
=========
C Z1 Z2
C is the carry bit
Could have 3 circuits
16 inputs each
2 w/ 8 ANDs, 1 OR
1 w 6 ANDs, 1 OR
25 gates
X1
X2
Y1
Y2
Z1
Z2
C
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
1
0
0
0
0
1
1
1
1
0
0
1
0
0
0
1
0
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
1
1
1
0
0
1
1
0
0
0
1
0
0
1
0
0
1
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
1
1
1
1
0
0
1
1
0
1
1
0
1
0
0
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
Addition
X1 X2
Y1 Y2
=========
C Z1 Z2
Rewrite as
X2
X1
Y2
Y1
====
C2
C2 Z2
========
C Z1
Addition
X2
X1
Y2
Y1
====
C2
C2 Z2
====
C Z1
X1
Y1
C2
C
Z1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
1
2 circuits
3 circuits
total of 4 gates
total of 10 gates
Addition
X2
Z2
Y2
Circuit
For
Z2 and carry
C2
X1
Y1
Z1
Circuit
For
Z1 and carry
Carry
Adding Binary Numbers of Any Length
We can use 2 building blocks to add numbers of any length.
Actually we need only 1 building block
ith bit of X
ith bit of Y
ith bit of Z
carry bit out
carry bit
Abstraction in action -- This is a piece of a carry-ripple adder
Adding Binary Numbers of Any Length
• Write the numbers as
– X4 X3 X2 X1 X0
– Y4 Y3 Y2 Y1 Y0
• Represent the sum as
– C Z4 Z3 Z2 Z1 Z0
Adding Binary Numbers of Any Length
• Write the numbers as
– X4 X3 X2 X1 X0
– Y4 Y3 Y2 Y1 Y0
• Represent the sum as
– C Z4 Z3 Z2 Z1 Z0
• Start with X0, Y0, 0 in, Z0 and C0 out
• Then X1,Y1,C0 in and Z1 and C1 out.
• And so on
Adding Binary Numbers of Any Length
At the ith stage
ith bit of X
ith bit of Y
Universal
ith bit of Z
Circuit
carry bit out
carry bit
Abstraction in action -- This is a piece of a carry-ripple adder
Adding Binary Numbers of Any Length
At each stage, take 2 addends and a bit telling whether there is a
carry and produce a sum bit and a bit telling if there is a carry.
We can build a black box to do this
addend
addend
carry bit in
Sum bit
carry bit out
Carry-Ripple Adder
X0 Universal
Circuit
Y0
0
Fixed at 0
Z0
C0
X1 Universal
Circuit
Y1
Z1
X2 Universal
Circuit
Y2
C1
X2 X1 X0
Y2 Y1 Y0
============
C2 Z2 Z1 Z0
Z2
C2
What’s inside the box?
Xi Universal
Circuit
Yi
Cin
Zi
Cout
What’s inside the box?
Xi Universal
Circuit
Yi
Cin
Zi
Cout
Abstraction in Action: Use Truth Tables and the Universal Method
Carry ripple adders
• Useful for some applications
• Too slow for other
– Delay while waiting for the carry to ripple
• One solution – add larger blocks
– Details in the homework assignment
Arithmetic Logical Unit (ALU)
• This is the part of the CPU that does arithmetic,
logical and comparison operations
• We’ve built a piece of the ALU
• With abstraction, we could build the other parts
– Multiplication/subtraction/division
– Comparison
• Then we would write a language to let the user
talk to the ALU (programming)
Pause
• Questions??
• How to build the other parts of the ALU?
– Use abstraction
• Back to representing information
Representing information
• How do we represent characters?
– How many characters might we want to represent?
– What characters might we want to represent?
Representing information
• How do we represent characters?
– How many characters might we want to represent?
– What characters might we want to represent?
•
•
•
•
•
•
A-Z
A-Z and a-z
All the keys on my keyboard
Maybe a power of 2?
Maybe an even power of 2?
Maybe an even bigger power of 2?
26
52
104
128
256
65536
Representing characters
• ASCII is the American Standard Code for Information
Interchange. It is a 7-bit code.
• Many 8-bit codes contain ASCII as their lower half
• The ASCII standard was published by the United States
of America Standards Institute (USASI) in 1968.
Unicode
• Universal Character Set (UCS) contains all characters of all other
character set standards. It also guarantees round-trip compatibility, i.e.,
conversion tables can be built such that no information is lost when
a string is converted from any other encoding to UCS and back.
• UCS contains the characters required to represent almost all known
languages. This includes apart from the many languages which use
extensions of the Latin script also the following scripts and
languages: Greek, Cyrillic, Hebrew, Arabic, Armenian, Gregorian, Japanese,
Chinese, Hiragana, Katakana, Korean, Hangul, Devangari, Bengali, Gurmukhi,
Gujarati, Oriya, Tamil, Telugu, Kannada, Malayam, Thai, Lao, Bopomofo, and a
number of others. Work is going on to include further scripts like Tibetian, Khmer,
Runic, Ethiopian, Hieroglyphics, various Indo-European languages, and many others.
• It’s intended to use 31 bits (32768 possible characters)
What do we do in practice
• Problems
– Bits represent too little – too many are needed
– Decimal numbers don’t translate well into bits
• So,
– Group into blocks of 4 and 8 bits
• 8 bits = 256 characters, holds ASCII
• 8 bits make 1 byte – things are organized into bytes
• 4 bits make 1 nibble
Shorthand: Hexadecimal
0
0 0 0 0
8
1 0 0 0
1
0 0 0 1
9
1 0 0 1
2
0 0 1 0
A
1 0 1 0
3
0 0 1 1
B
1 0 1 1
4
0 1 0 0
C
1 1 0 0
5
0 1 0 1
D
1 1 0 1
6
0 1 1 0
E
1 1 1 0
7
0 1 1 1
F
1 1 1 1
Hexadecimal
• We can add numbers
– 1+1=2, 2+2=4, 4+4=8, 4+8=C, 2+8=A, …
• We can combine 2 hexadecimal numbers to make a byte.
• It’s easier to read than 0’s and 1’s
• In ASCII
– hex 41 through 5A represent A to Z
– Hex 61 through 7A represent a to z
Summary
•
•
•
•
Reviewed gates and the Universal Method
Showed that the universal method can lead to very big circuits
Fixed the problem
Demonstrated the fix
– Carry-ripple adder
• Represented characters
– Hexadecimal
– Bytes, nibbles
Next Time: Memory
Now that we can represent it, how do we store it??