Karnaugh Map (K-map)
·
A Karnaugh map (or K-map) is a method used
to minimize Boolean expressions without having to use Boolean algebra theorems
and equation manipulations.
· K-map is a grid-like representation of a
truth table, but the mode of presentation gives more insight.
· Has zero and one entries at different
positions. Each position in a grid corresponds to a truth table
entry.
Example
of truth table
A
|
B
|
C
|
F
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
1
|
1
|
The Karnaugh map
uses the following rules for the simplification of expressions by grouping
together adjacent cells containing ones
·
Groups
may not include any cell containing a zero
·
Groups may be
horizontal or vertical, but not diagonal
· Groups
must contain 1, 2, 4, 8, or in general 2n cells.
That is
if n = 1, a group will contain two 1's since 21 = 2.
If n = 2,
a group will contain four 1's since 22 = 4.
·
Each
group should be as large as possible
·
Each cell
containing a one must be in at least one group
·
Groups
may overlap
·
Groups
may wrap around the table. The leftmost cell in a row may be grouped with the
rightmost cell and the top cell in a column may be grouped with the bottom cell
·
There
should be as few groups as possible, as long as this does not contradict any of
the previous rules
Summary:
1.
No zeros allowed.
2.
No diagonals.
3.
Only power of 2 number
of cells in each group.
4.
Groups should be as
large as possible.
5.
Everyone must be in at
least one group.
6.
Overlapping allowed.
7.
Wrap around allowed.
8.
Fewest number of groups
possible.
Universal Gates
A logic circuit of any complexity can be realized by using
only the three basic gates (NOT, AND, and OR Gates). There are two universal
gates, the NAND Gate and the NOR gate. Each of those can also realize logic
circuit single-handedly. The NAND and NOR gates are therefore called universal
gates.
NAND Gate
A NAND gate (Its name is an abbreviation of NOT AND, or its
extended name ‘Negated AND gate’) is a digital logic gate with two or more inputs
and one output with behaviour that is the opposite of an AND gate. The output
of a NAND gate is true when one or more, but not all, of its inputs are false.
If all of a NAND gate's inputs are true, then the output of the NAND gate is
false.
The truth table and the graphic symbol of NAND gate is shown
in the below figure.
A
|
B
|
Output
|
0
|
0
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
NOR Gate
A NOR gate (Its name is an abbreviation of NOT OR, or its
extended name ‘Negated OR gate’) is a digital logic gate with two or more
inputs and one output with behaviour that is the opposite of an OR gate. The
output of a NOR gate is true all of its inputs are false. If one or more of a
NOR gate's inputs are true, then the output of the NOR gate is false.
The truth table and the graphic symbol of NOR gate is shown
in the below figure.
A
|
B
|
Output
|
0
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
1
|
1
|
0
|
No comments:
Post a Comment