ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
1
DIGITAL ELECTRONICS AND
MICROPROCESSORS
ELM3111 Digital Electronics and
Microprocessors
Some of the contents are adopted from
M. Morris Mano, Michael D Ciletti.Digital Design, 4nd edition, Pearson & Prentice Hall, 2007.
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Contents
2-3 Canonical vs Standard Forms of the Boolean Expressions
› Sum of Minterms and product of Maxterms examples
› Canonical vs Standard representations
2-4 Other Commonly used gates
2-5 Special Notes on Gates
3- Gate level Minimization
› Karnaugh Diagrams
2
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
3
2-3 Canonical Vs Standard Forms Of The
Boolean Expressions
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
4
Conversion Between Canonical Forms
Example:
Consider the function F(A, B, C)=Σ (1, 2, 3, 7). Express the
function using product of maxterms.
Solution:
F’(A, B, C)=Σ (0, 4, 5, 6)= m0 + m4 + m5 +m6
Now use De-Morgan’s Law
F(A,B,C)=(F’(A, B, C))’= (m0 + m4 + m5 +m6)’=M0M4M5M6
Where Mj=mj’
5
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Conversion Between Canonical Forms
A
B
C
F
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
m0 (A’B’C’)
M0 (A+B+C)
m4 (AB’C’)
M4 (A’+B+C)
m5 (AB’C)
M5 (A’+B+C’)
m6 (ABC’)
M6 (A’+B’+C)
Mj=mj’
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Conversion Between Canonical Forms
A
B
C
A’B’C
xy
canonical
A’BC’
A’BC
A’BC
F(A,B,C)=Σ (1, 2, 3, 7).
6
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Conversion Between Canonical Forms
A
B
C
A+B+C
A’+B+C
A’+B+C’
A’+B’+C
canonical
F(A,B,C)= ΠM0M4M5M6
7
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Standard Forms
F1=y’+xy+x’yz’
F2=x(y’+z)(x’+y+z’)
8
These are standard form Boolean expressions
- Two level representation
- Sum of products or product of sums with
reduced number of variables in the terms
(not canonical)
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
2-4 Other Commonly Used Gates
9
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Logic functions of N variables
•
•
So far, we have defined 3 gates
Why consider new gates?
• Cheaper hardware, more flexibility.
10
11
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
The NAND Gate
x
y
•
•
•
z
This is a NAND gate.
It is a combination of an AND gate followed by an inverter.
NAND gates have several interesting properties.
NAND(a,a)=(aa)’ = a’ = NOT(a)
(NAND(a,b))’=(ab)’’ = ab = AND(a,b)
NAND(a’,b’)=(a’b’)’ = a+b = OR(a,b)
x
y
z
0
0
1
0
1
1
1
0
1
1
1
0
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
12
The NAND Gate
•
These three properties show that a NAND gate with both of its
inputs driven by the same signal is equivalent to a NOT gate
• A NAND gate whose output is complemented is equivalent to
an AND gate, and a NAND gate with complemented inputs
acts as an OR gate.
• Therefore, we can use a NAND gate to implement all three of
the elementary operators (AND,OR,NOT).
• Therefore, ANY switching function can be constructed using
only NAND gates. Such a gate is said to be primitive or
functionally complete.
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
13
NAND Gates into Other Gates
what are these circuits?
x
x’
NOT Gate
x
y
xy
AND Gate
x
x+y
y
OR Gate
14
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
The NOR Gate
•
•
x
y
z
This is a NOR gate. It is a combination of an OR gate followed by an
inverter.
NOR gates also have several interesting properties
NOR(a,a)=(a+a)’ = a’ = NOT(a)
NOR’(a,b)=(a+b)’’ = a+b = OR(a,b)
NOR(a’,b’)=(a’+b’)’ = ab = AND(a,b)
x
0
0
1
1
y
0
1
0
1
z
1
0
0
0
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
15
The NOR Gate
•
•
•
•
•
Like the NAND gate, the NOR gate is functionally complete.
Any logic function can be implemented using just NOR gates.
Both NAND and NOR gates are very valuable as any design can be
realized using either one.
It is easier to build an IC chip using all NAND or NOR gates than to
combine AND,OR, and NOT gates.
NAND/NOR gates are typically faster at switching and cheaper to
produce.
16
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
The NOR Gate into other Gates
x
x’
x
y
x+y
NOT Gate
OR Gate
x
xy
y
AND Gate
17
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
The XOR Gate (Exclusive-OR)
x
y
z
• XOR gates assert their output
when exactly one of the inputs
is asserted, hence the name.
• The switching algebra symbol
for this operation is , i.e.
1  1 = 0 and 1  0 = 1.
x
0
0
1
1
y
0
1
0
1
z
0
1
1
0
18
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
The XNOR Gate
x
y
z
•
•
This is a XNOR gate.
This functions as an exclusive-NOR gate, or
simply the complement of the XOR gate.
•
The switching algebra symbol for this operation is , i.e.
1  1 = 1 and 1  0 = 0.
0
x
y
z
0
0
1
1
0
1
0
0
1
1
1
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Example
19
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
20
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
2-4 Special Notes On Gates
21
22
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Integrated Circuits- Digital Logic Families
• IC’s in a semiconductor chip is called a chip,
• It contains the electronic components for constructing gates
CMOS NOT gate
TTL NOT gate
Digital Logic Families
TTL transistor–transistor logic;
ECL emitter‐coupled logic;
MOS metal‐oxide semiconductor;
CMOS complementary
metal‐oxide semiconductor.
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
23
Integrated Circuits- Integration Level
• Digital ICs are often categorized according to the complexity of their circuits,
• Small‐scale integration (SSI) devices contain several independent gates in a
single package. The inputs and outputs of the gates are connected directly to the
pins in the package. The number of gates is usually fewer than 10 and is limited
by the number of pins available in the IC.
• Medium‐scale integration (MSI) devices have a complexity of approximately 10 to
1,000 gates in a single package. decoders, adders, and multiplexers registers
and counters.
• Large‐scale integration (LSI) devices contain thousands of gates in a single
package. Processors, memory chips, and programmable logic devices.
• Very large‐scale integration (VLSI) devices now contain millions of gates within a
single package. large memory arrays and complex microcomputer chips.
• Because of their small size and low cost, VLSI devices have revolutionized the
computer system design technology, giving the designer the capability to create
structures that were previously uneconomical to build.
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Integrated Circuits
24
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Integrated Circuits
25
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
3 Gate Level Minimization
26
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Gate Level Minimization Problem
Example: using the canonical form of the function
F(A, B, C)=Σ (0, 4, 5, 6) simplify it
• m0 =(A’B’C’)
• m4 =(AB’C’)
• m5 =(AB’C)
• m6 =(ABC’)
F= A’B’C’+ AB’C’+ AB’C+ AB’C’+ ABC’+ AB’C’
F=
B’C’+
AB’+
AC’
27
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
28
Efficient Gate Level Minimization
• Gate-level minimization is the design task of finding an optimal gate-level
implementation of the Boolean functions describing a digital circuit.
• This task is well understood, but is difficult to execute by manual methods
when the logic has more than a few inputs.
• Fortunately, computer-based logic synthesis tools can minimize a large set of
Boolean equations efficiently and quickly.
• Nevertheless, it is important that a designer understand the underlying
mathematical description and solution of the problem.
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
29
Efficient Gate Level Minimization
• The complexity of the digital logic gates that implement a Boolean function is
directly related to the complexity of the algebraic expression from which the
function is implemented.
• Although the truth table representation of a function is unique, when it is
expressed algebraically it can appear in many different, but equivalent, forms.
Boolean expressions may be simplified by algebraic means minimization is
awkward because it lacks specific rules to predict each succeeding step in
the manipulative process.
THE MAP METHOD
• The map method presented here provides a simple, straightforward
procedure for minimizing Boolean functions.
• This method may be regarded as a pictorial form of a truth table. The map
method is also known as the Karnaugh map or K-map .
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
30
Efficient Gate Level Minimization
• A K-map is a diagram made up of squares, with each square representing one minterm of the function that
is to be minimized.
• Any Boolean function can be expressed as a sum of minterms, it follows that a Boolean function is
recognized graphically in the map from the area enclosed by those squares whose minterms are included
in the function.
•
In fact, the map presents a visual diagram of all possible ways a function may be expressed in standard
form.
• By recognizing various patterns, the user can derive alternative algebraic expressions for the same
function, from which the simplest can be selected.
• The simplified expressions produced by the map are always in one of the two standard
• forms: sum of products or product of sums.
•
It will be assumed that the simplest algebraic expression is an algebraic expression with a minimum
number of terms and with the smallest possible number of literals in each term.
• This expression produces a circuit diagram with a minimum number of gates and the minimum number of
inputs to each gate.
• We will see subsequently that the simplest expression is not unique: It is sometimes possible to find two or
more expressions that satisfy the minimization criteria. In that case, either solution is satisfactory
31
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Karnaugh Map for sum of products
F = Σ(m0,m1) = A’B + A’B’
B
0
1
0
A’B’
A’B
1
AB’
AB
A
If A’B=1 for A=0, B=1 put 1 here
A
B
F
0
0
1
0
1
1
1
0
0
1
1
0
B
0
1
0
1
1
1
0
0
A
32
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Karnaugh Map for sum of products
A
B
C
F
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
BC 00
01
11
10
0
0
1
0
1
1
1
1
1
1
A
F=AB’C’ +AB’C +ABC +ABC’ + A’B’C + A’BC’
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
33
Rules for K-Maps
 We can reduce functions by circling 1’s in the K-map
 Each circle represents minterm reduction
 Following circling, we can deduce minimized and-or form.
Rules to consider
Every cell containing a 1 must be included at least once.
The largest possible “power of 2 rectangle” must be enclosed.
The 1’s must be enclosed in the smallest possible number of rectangles.
34
ELM3111 Digital Electronics and Microprocessors | Dr Muharrem Mercimek
Rules for K-Maps
• A Karnaugh map is a graphical tool for assisting in the general simplification
procedure
A
0
1
B
0
1
0
1
1
0
1
0
0
1
1
1
1
A
F=A’
B
0
F=A’B + A’B’
F=B+A
F=AB+A’B + AB’
BC 00
01
11
10
0
0
1
0
1
1
1
1
1
1
A
F=A+B’C +BC’
F=AB’C’ +AB’C +ABC +ABC’ + A’B’C + A’BC’
Download

Lecture notes 4