Transcript Document

Data Manipulation
CSCI130
Instructor: Dr. Imad Rahal
Layered Architecture
LAYER
Order
Application SW: Excel & Access
2
High-order P.L.: Visual Basic
1
Low-order P.L.: Assembly
3
System SW: O.S.
3
Machine Language
4
Data Representation
5
HW: Circuit Design
6
0
clock
16-3000 MHz (~3.0 GHz)
Overview of Computer Hardware

“necessary” components of a computer


components needed for convenience



CPU, Main memory
computer won’t be very practical to use otherwise
Secondary/Auxiliary storage, I/O devices
Main memory


Connects to the motherboard
Divided into two major parts
Overview of Computer Hardware

RAM --- Random Access Memory




ROM --- Read Only Memory




memory registers which store data before/after CPU processing
Available for users and programs so store data in and read data from
Volatile --- does not persist when no electric power is supplied to its
circuits
Permanent
Holds programs that are vital for the operation of the computer
As the name indicates, can be read but never altered
CPU




Central Processing Unit
Single silicon chip with circuits attached to it
Known as microprocessor
Sits on a circuit board known as the motherboard
Data Manipulation

Computing an answer to an equation:



5*3 + 62 – 7
Assume our computer can’t directly multiply, subtract, or
raise to power
Multiplication task:







1:
2:
3:
4:
5:
6:
7:
Get 1st number, Number_1
Get 2nd number, Number_2
Answer = 0
Add Number_1 to Answer
Subtract 1 from Number_2
if Number_2>0, go to step 4
Stop
Data Manipulation

All tasks done by a general-purpose computer can be
accomplished through the following set of
operations

Input/output


Store data




Not mentioned in book but important
numbers (positive, negative or fractions), text, pictures, etc …
Compare data (numbers, pictures, sounds, letters)
Add
Move data from one storage (memory) location to another

Editing a text document
Data Manipulation

Adding and comparing bit patterns is sufficient to achieve an “operational”
machines




Hard-wired vs. programmed
This is done by circuits for adding and comparing bit patterns in registers
Circuits are made up of logical gates
Gates and Truth Tables


Gates needed are NOT, AND, and OR
NOT Gate:


Single input and single output
Reverses input




1  0 and 0  1
If there is a strong electric current

 shut it off
If there is no/weak electric current

 turns it on
Like a power switch
NOT Truth Table
A
NOT A (A’)
1
0
0
1
Data Manipulation

AND Gate



Accepts two inputs (or
more) and yields one output
Output is 0 when any input
is 0
Requires power coming
from both lines in order to
give out power
AND Truth Table
A
B
A AND B
(AB)
0
0
0
0
1
0
1
0
0
1
1
1
Data Manipulation

OR Gate



Accepts two inputs and
yields one output
Output is 1 when any input
is 1
Requires power coming
from at least one of the
input lines in order to give
out power
OR Truth Table
A
B
A OR B
A+B
0
0
0
0
1
1
1
0
1
1
1
1
Data Manipulation

These three simple gates are combined to create
circuits that perform more complicated operations


Circuits, in turn, might then be used (thru programs) to
perform even more complicated tasks
Gate combinations can be expressed in three ways

(1) Through Expressions



A AND B  AB
A OR B  A+B
NOT A  A’

A’B’ + AB
NOT

AND
OR
(2) Through Circuit diagrams
 Enough rows to hold all input
Given an expression
combinations
 Draw a gate after its inputs have been drawn
1
 1 letter  2 rows
 Try A’B’ + AB
2
 2 letters  2 rows
(3) Through Truth Tables
3
 3 letters 2 rows
 Each of the representations can be derived from
n
the other
 n letters 2 rows
 Derive truth table given expression




One column for each letter
Make 1 additional column for every sub-expression
(order: parentheses, NOTs, ANDs, ORs)
A
B
A’
B’
A’B’
AB
A’B’+AB
0
0
1
1
1
0
1
0
1
1
0
0
0
0
1
0
0
1
0
0
0
1
1
0
0
0
1
1
Practice

Try A + (A.B’+B.C)’

How many gates?

Design circuit


Parenthesis, NOT, AND, and then OR
Find truth table

How many rows?
Data Manipulation

given a circuit diagram  expression  truth
table

Mark every output wire by its label
Sum of Products Method


Given a truth table, how to find expression?
Sum-of-product method

For each row with a 1 in the final column


AND letters with a 1 in their column and negation of the
letters with a 0 in their column
Connect the resulting AND groups with ORs
A
B
?
0
0
1

0
1
1

1
0
0

1
1
1

A’B’
A’B
Ignore
AB
 A’B’+A’B+AB
 Complicated and UGLY  !!! (requires
space, and is costly and slow)
Simplification

Why simplify?


UGLY 
Circuits supposed to be as simple as possible

Save on speed (operation execution---fewest gates as
possible because every gates slows the operation a bit)


Save space (on motherboard)


(in general) more gates  more time
Notebooks!
Save money (not as critical)
Simplification of Expressions

Laws of Boolean Algebra

Commutative Law



A+B = B+A, A.B=B.A
E.g. addition and multiplication

A.(B+C) = A.B + A.C,
E.g. multiplication over addition
A+(B.C) = (A+B).(A+C)
Idempotency Law

A+A = A, A.A=A
Double Negation



Distributive Law



DeMorgan’s Law



(A’)’ = A
E.g. -(-5) = +5
(A+B)’ = A’.B’,
(A.B)’ = A’+B’
Identities



A.0 = 0, A+0=A
A.1 = A, A+1=1
A.A’ = 0, A+A’ = 1
Simplification of Expressions

To simplify (reduce the number of gates)

(1) look at two or more terms sharing one or more letters



use distributive Law
AB + AC = A(B+C)
A’B’+A’B+AB






A’(B’+B) + AB
A’(1) + AB
A’ + AB
(A’+A)(A’+B)
(1)(A’+B)
A’+B
// distributive law (#1)
// identities
// identities
// distributive law (#2)
// identities
// identities
Simplification of Expressions






A.B’+A’.B’+A’.B
B’. (A + A’) + Distributive
A’.B law Distributive
Identities
B’ + A’.B
Distributive
Law
(B’ + A’).(B’ + B)Idempotency
B’ + A’
DeMorgans
Idempotency Law
(B.A)’
Distributive Law
Simplification of Expressions

AB’+B+B’+AB
AB’+1 + AB

1

Identities
Identities
Simplification of Expressions
Distributive law
Idempotency Law
Idempotency Law
Distributive Law
Circuit for Equivalence


We need to compare the data
contents of two registers
Data is in binary



compare them bit by bit
Start right to left
Take two inputs



If both 0s or 1s, output 1
Otherwise, output a zero
A’B’+AB

(Sum of products method)



Ask yourself: when am I getting a 1?
 (A+B)’ +AB (simpler)
Draw circuit
A
B
A=B
0
0
1
0
1
0
1
0
0
1
1
1
Circuit for Equivalence
Circuit
for
Addition