Transcript Document

Computer logic
• Data and programs in digital computers are
represented and processed by electronic circuit
networks called digital logic circuits or logic
circuits, for short.
• Logic circuits are the heart of computer
hardware.
• Logic circuits operate on two logical values,
usually called bit 0 and bit 1, and the operations
are based on the principles of Boolean Algebra.
Computer logic
• Logical circuits are made from two basic devices
– Logic gate
– Flip-flop
• Flip-flops provide memory for storing data while
logic gates provide operations on, or functions
of, the values stored in these memory devices.
• Logic gate is a combinational circuit that
performs an elementary logic operation.
Logic function and truth table
• The values of input x1 and x2 and the
corresponding value y of each basic logic
gate is represented in it truth table.
• The truth table lists all possible switch
setting (input values) along with value of
the result (output value) for each setting.
Logic Function and Truth Table
• In general logic terms, this truth table represents the
function values y of two variables x1 and x2 values as
y = f(x1, x2)
and may be extended to n variable as the logic function
y = f(x1,x2,...,xn)
• Basic logic gates can be used to construct logic
network (network of logic gates) or logic circuit that
implements more complex logic function (Boolean
function).
Logic Function and Truth Table
• At any moment, the output signal of a gate is a
function of the input signals at that moment.
• The AND gate can have two or more inputs and one
output.
– The output is 1 if and only if all the inputs are 1s.
– Otherwise it is 0.
• The OR gate can have two or more inputs and one
output.
– The output is 1 if any of the inputs is 1.
– Otherwise it is 0.
• Not gate or “inverter” has one input and one output
which is always the opposite of the input.
Logic Function and Truth Table
• Truth table is important way for describing logic
function values.
• Any logic function with n inputs and one output,
the corresponding truth table will have one
column for each input, and one column for the
output.
• The truth table will have one row for every
possible combination of inputs; 2n rows in all.
• The output column in each row simply specifies
the output for that combination of inputs.
Logic Function and Truth Table
• The logic function :
Y = A·B + A·B
• The corresponding truth table :
A
B
A.B
A.B
1
1
0
0
1
0
1
0
0
0
0
1
1
0
0
0
Y= A· B + A· B
1
0
0
1
Logic Function and Truth Table
The corresponding logic circuit
A
B
Y = A·B + A·B
Boolean Function and Boolean
Expression
• There are two important problems of
Boolean functions and Boolean
expressions :
– Given the values of a Boolean function, how
can a Boolean expression that represent this
function be found ?
– Is there a smaller set of operators that can be
used to represent all Boolean functions ?
Boolean Function and Boolean
Expression
• Both of these problems have practical
importance in circuit design.
• Methods of representing of Boolean
functions
– Sum-of-products expansions (minterm
expansions )
– Product-of-sums expansions (maxterm
expansions )
Boolean Function and Boolean
Expression
• Find Boolean expressions that represent the
Boolean functions F(x,y,z) and G(x,y,z) below :
x
0
0
0
0
1
1
1
1
F(x,y,z) = x y z


y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
F(x,y,z) G(x,y,z)
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
G(x,y,z) = x y z + x y z
 
 
exclusive-OR ( x  y )
x
0
0
1
1
y
0
1
0
1
x y
0
1
1
0
• Sum-of-products expansions
f(x, y) = 1
x = 1
x = 0
when
and
and
y = 0
y = 1
x y = x•y + x•y
exclusive-OR ( x  y )
x
0
0
1
1
y
0
1
0
1
x y
0
1
1
0
• Product-of-sums expansions
f(x, y) = 0 when
x = 1
x = 0
and
and
y = 1
y = 0
x y = (x+y) • (x+y)
Boolean Function
• The Boolean functions F and G of n variables
are equal if and only if
F( b1 , b2 , … , bn) = G( b1 , b2 , … , bn )
whenever b1, b2 , … , bn belong to B = { 0 , 1 }
• Two different Boolean expressions that
represent the same Boolean function are called
equivalent Boolean expressions.
Boolean Function
Example
• To show F( x , y, z ) = G( x , y, z )
where
F( x , y, z ) = x + y•z
G( x , y,z ) = ( x + y ) •( x + z )
F( x , y, z ) = x + y•z
G( x , y,z ) = ( x + y ) •( x + z )
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(x,y,z) G(x,y,z)
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
Cj-1
Sj = Aj + Bj
C
Circuit
Aj
Bj
Cj
Input
Am Bm
Cm
C
Circuit
Sm
A2 B2
Cm-1
C2
C
Circuit
S2
Output
A1 B1
C1
C
Circuit
S1
0
Elements of computer hardware
Transistors
Group of transistors
Circuit boards
ICs
Computer
Elements of computer hardware
• Transistors are the smallest computational
elements.
• Boolean functions and memories are
formed by groups of transistors.
• Elementary addition and multiplication is
done by boolean functions and memory
elements called flip-flops.
• Integrated circuits (ICs) contain a large
number of such functions.
Elements of computer hardware
• Printed circuits boards contain severeral
integrated circuits to form a either a full
computer or specific I/O (input/output)
functions.
• Massive storage such as disks and tapes
interfaces the computer through its main
bus.
Functional organization
CPU
Main memory
Bus
Bus translator
I/O interface
I/O interface
Integrated circuits
• The logic gates AND, OR, NOT are the
basic components of digital logic circuits of
computers. However, these three gates
are in principle sufficient to construct a
logic circuit of any kind.
• The number of gates that are combined in
a single integrated circuit (IC) is often used
to distinguish different levels of IC
manufacturing.
Integrated circuits
• Four levels of IC chips are recognized :
– Small-scale integration ( SSI )
• 1 to 9 gates per chip
– Medium-scale integration ( MSI )
• 10 to 99 gates per chip
– Large-scale integration ( LSI )
• 100 to 100,000 gates per chip
– Very large-scale integration ( VLSI )
• over 100,000 gates per chip
Integrated circuits
• An integrated circuit (IC) is a
microelectronic device consisting of many
interconnected transistors and other
components.
• ICs are constructed (‘fabricated’) on a
small rectangle, called a ‘die’, cut from a
silicon (or for special applications,
sapphire) wafer.
Integrated circuits
• ICs can be classified into analog, digital, or
hybrid (both digital and analog on the same
chip).
• Digital ICs can contain anything from one to
millions of logic gates, flip-flops, multiplexers,
etc. in a few square millimeters.
• The small size of ICs allows high speed, low
power dissipation, and reduced manufacturing
cost compare with board-level integration.