Transcript combinational logic

Computer Organization
By
Dr. M. Khamis
Mrs. Dua’a Al Sinari
Parity Checking
Parity checking is used to check the correctness or
erroneous of data.
 Circuit used to raise 1 on its output when its input data
contain even number of 1’s is called even parity circuit,
otherwise it called odd parity circuit.
 Parity checking is used with memory to ensure the read
data is exactly as written one or otherwise it interrupts
the main processor. Also, it is used within the modem to
ensure the correct arrival of the received data.

Parity Checking with the Main Memory
Parity RAM
Data RAM
Parity cct
To interrut processor
Parity cct
How is parity circuits detect the error?
Original
Correct
defected
Data
circuit
circuit
Odd
odd
even
Even
odd
even
The table depicts the expected output of the parity
checking during reading data.
 Note that the output will be always1 when memory is
defected, otherwise, it will be 0.

Design parity checking for 3-inputs



For sake of simplicity 3-inputs are
considered. The truth table will be
as shown. The output (F) of the
even parity circuit is 1 when the
number of the 1’s in the inputs are
even.
F= xyz’ + xy’z + x’yz + x’y’z’
(Draw the corresponding circuit for
the above logic expression to get
the odd parity circuit for 3-inputs)
x
y
z
F
1
1
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
0
0
0
1
How to add binary numbers

Consider adding two 1-bit binary numbers x and y




0+0 = 0
0+1 = 1
1+0 = 1
1+1 = 10
x
y
Carry
Sum
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
0

Carry is x AND y

Sum is x XOR y

The circuit to compute this is called a half-adder
The half-adder


x
y
Sum = x XOR y
Carry = x AND y
x
y
Sum
Carry
Sum
Carry
Using half adders

We can then use a half-adder to compute the sum of
two Boolean numbers
1 0 0
1 1 0 0
+1 1 1 0
?
0 1 0
How to fix this

We need to create an adder that can take a carry bit as an
additional input
Inputs: x, y, carry in
 Outputs: sum, carry out


x
y
c
carry
sum
1
1
1
1
1
1
1
0
1
0
1
0
1
1
0
What about the carry out?
1
0
0
0
1
It’s 1 if either (or both):
 x+y = 10
 x+y = 01 and carry in = 1
0
1
1
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
0
0
This is called a full adder
Will add x and y with a half-adder
 Will add the sum of that to the
carry in



The full adder

The “HA” boxes are half-adders
c
X
Y
x
y
X
Y
HA
HA
S
s
C
S
C
c
The full adder

The full circuitry of the full adder
c
s
x
y
c
Adding bigger binary numbers

Just chain full adders together
x0
y0
x1
y1
x2
y2
x3
y3
X
Y
HA
s0
S
C
C
FA
s1
S
X
Y
C
C
FA
s2
S
X
Y
C
C
FA
S
X
Y
C
s3
c
Adding bigger binary numbers


A half adder has 4 logic gates
A full adder has two half adders plus a OR gate



To add n bit binary numbers, you need 1 HA and n-1 FAs
To add 32 bit binary numbers, you need 1 HA and 31 FAs


Total of 9 logic gates
Total of 4+9*31 = 283 logic gates
To add 64 bit binary numbers, you need 1 HA and 63 FAs

Total of 4+9*63 = 571 logic gates
More about logic gates
To implement a logic gate in hardware, you use a
transistor
 A transistor is a semiconductor device commonly used
to amplify or switch electronic signals.
 Transistors are all enclosed in an “IC”, or integrated
circuit
 The current Intel Pentium IV processors have 55 million
transistors!

Summary: Digital Logic Basics

Hardware consists of a few simple building blocks

These are called logic gates
AND, OR, NOT, …
 NAND, NOR, XOR, …
 Logic gates are built using transistors
 NOT gate can be implemented by a single
transistor
 AND gate requires 3 transistors
 Transistors are the fundamental devices
 Pentium consists of 3 million transistors
 Compaq Alpha consists of 9 million transistors
 Now we can build chips with more than 100
million transistors

Basic Concepts

Simple gates
AND
 OR
 NOT


Functionality can be
expressed by a truth table


A truth table lists output
for each possible input
combination
Precedence
NOT > AND > OR
 F=AB+AB
= (A (B)) + ((A) B)

Basic Concepts (cont.)

Additional useful gates
NAND
 NOR
 XOR





NAND = AND + NOT
NOR = OR + NOT
XOR implements exclusiveOR function
NAND and NOR gates
require only 2 transistors

AND and OR need 3
transistors!
Basic Concepts (cont.)


Basic building block:
 Transistor
Three connection points
Base
 Emitter
 Collector


Transistor can operate

Linear mode


Used in amplifiers
Switching mode

Used to implement
digital circuits
Basic Concepts (cont.)

Number of functions
With N logical variables, we can define
22N functions
 Some of them are useful



AND, NAND, NOR, XOR, …
Some are not useful:
Output is always 1
 Output is always 0


“Number of functions” definition is useful in proving
completeness property
Basic Concepts (cont.)

Complete sets

A set of gates is complete

If we can implement any logical function using
only the type of gates in the set
You can uses as many gates as you want
 Some example complete sets

{AND, OR, NOT}
complete set
 {AND, NOT}
 {OR, NOT}
 {NAND}
 {NOR}


Not a minimal
Minimal complete set
 A complete set with no redundant elements.
Basic Concepts (cont.)



Universal Gates: A universal gate is a gate which can implement
any Boolean function without need to use any other gate type.
Proving NAND gate is universal
an AND gate is typically
NAND gate is called universal gate
implemented as a NAND
gate followed by an
inverter not the other way
around!!
Basic Concepts (cont.)


Proving NOR gate is universal
NOR gate is called universal gate
an OR gate is typically
implemented as a NOR
gate followed by an
inverter not the other
way around!!
Logic Chips: it is categorized according to the
complexity of their circuit.
Logic Chips (cont.)
 Integration levels
 SSI (small scale integration)
 Introduced in late 1960s
 1-10 gates (previous examples)
 MSI (medium scale integration)
 Introduced in late 1960s
 10-100 gates
 Decoders, adders, multiplexers…
 LSI (large scale integration)
 Introduced in early 1970s
 100-10,000 gates
 Processors, memory chips…
 VLSI (very large scale integration)
 Introduced in late 1970s
 More than 10,000 gates
Logic Functions

Logical functions can be expressed in several
ways:
Truth table
 Logical expressions
 Graphical form


Example:

Majority function
Output is 1 whenever majority of inputs is 1
 We use 3-input majority function

Logic Functions (cont.)
3-input majority function

A
B
C
F
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
1
0
0
1
0
1
1
1
Logical expression form
F=AB+B C+AC
Logical Equivalence

All three circuits implement F = A B function
Logical Equivalence (cont.)

Proving logical equivalence of two circuits
Derive the logical expression for the output of each
circuit
 Show that these two expressions are equivalent


Two ways:

You can use the truth table method



For every combination of inputs, if both expressions yield the
same output, they are equivalent
Good for logical expressions with small number of variables
You can also use algebraic manipulation

Need Boolean identities
Logical Equivalence (cont.)

Derivation of logical expression from a circuit

Trace from the input to output

Write down intermediate logical expressions along the
path
Logical Equivalence (cont.)

Proving logical equivalence: Truth table method
A
0
0
1
1
B
0
1
0
1
F1 = A B
0
0
0
1
F3 = (A + B) (A + B) (A + B)
0
0
0
1
Help in reducing design complexity
 Reduce chip count


We look at some useful combinational circuits
Number Systems and Boolean Algebra
Combinational circuits
 Output depends only on the current inputs
 Combinational circuits provide a higher level of
abstraction

4/6/2016October 12, 2008
INTRODUCTION TO COMBINATIONAL CIRCUITS
30

Multiplexer

Selection input
determines the input
that should be
connected to the
output
4-data input MUX
Number Systems and Boolean Algebra
2n data inputs
 n selection inputs
 a single output

4/6/2016October 12, 2008
MULTIPLEXERS
31
4-data input MUX implementation
4/6/2016October 12, 2008
MULTIPLEXERS (CONT.)
Number Systems and Boolean Algebra
32
MUX implementations
4/6/2016October 12, 2008
MULTIPLEXERS (CONT.)
Number Systems and Boolean Algebra
33
Majority function
Odd-parity function
Efficient implementation: Majority function
4/6/2016October 12, 2008
MULTIPLEXERS (CONT.)
Number Systems and Boolean Algebra
34

Decoder selects one-out-of-N inputs
Number Systems and Boolean Algebra
36
2ˣ4 Decoder
4/6/2016October 12, 2008
DECODERS
Logic function implementation:
A full adder implementation
4/6/2016October 12, 2008
DECODERS (CONT.)
Number Systems and Boolean Algebra
S(A,B,Cin)=∑(1,2,4,7)
Cout(A,B,Cin)=∑(3,5,6,7)
3ˣ 8 Decoder
37
4/6/2016October 12, 2008
COMPARATOR

Used to implement comparison operators (= , > , < ,  , )
(A>B)=A3B3’ + x3A2B2’ + x3x2A1B1’ + x3x2x1A0B0’
(A<B)=A3’B3 + x3A2’B2 + x3x2A1’B1 + x3x2x1A0’B0
Number Systems and Boolean Algebra
Xi=AiBi + Ai’Bi’ for i=0,1,2,3
38
Serial construction of an 8-bit comparator
4/6/2016October 12, 2008
COMPARATOR (CONT.)
Number Systems and Boolean Algebra
40
x>y
CMP
x<y
Number Systems and Boolean Algebra
x>y x=y x<y
y
x
y
x
x=y
4/6/2016October 12, 2008
1-BIT COMPARATOR
41