ZeePedia buy college essays online


Digital Logic Design

<<< Previous Converting between POS and SOP using the K-map Next >>>
 
img
CS302 - Digital Logic & Design
Lesson No. 11
KARNAUGH MAP & BOOLEAN EXPRESSION SIMPLIFICATION
Mapping a Standard POS Expression
For a Standard POS expression, a 0 is placed in the cell corresponding to the product
term (maxterm) present in the expression. The cells are not filled with 0s have 1s. The
Standard
POS
expression
having
a
Domain
of
three
variables
(A + B + C).(A + B + C).(A + B + C).(A + B + C) uses a 3-Variable Karnaugh Map. The sum
terms or the Maxterms are 1, 2, 5 and 7. The expression can be represented by a K-Map by
placing a 0 at Maxterm locations 1, 2, 5 and 7 and placing 1 at remaining places. Any of the
two K-maps can be used. Figure 11.1.
AB\C
0
1
00
1
0
A\BC  00
01
11
10
01
0
1
0
1
0
1
0
11
1
0
1
1
0
0
1
10
1
0
Figure 11.1
Mapping a Standard POS expression
Karnaugh Map simplification of POS expressions
POS expressions can be easily simplified by use of the K-Map in a manner similar to
the method adopted for simplifying SOP expressions. After the POS expression is mapped on
the K-map, groups of 0s are marked instead of 1s based on the rules for forming groups used
for simplifying SOP.
In the next step minimal sum terms are determined. Each group, including a group
having a single cell, represents a sum term having variables that occur in only one form either
complemented or un-complemented.
A 3-variable K-map yields
·  A sum term of three variables for a group of 1 cell
·  A sum term of two variables for a group of 2 cell
·  A sum term of one variable for a group of 4 cell
·  A group of 8 cells yields a value of 0 for the expression.
A 4-variable K-map yields
·  A sum term of four variables for a group of 1 cell
·  A sum term of three variables for a group of 2 cell
·  A sum term of two variables for a group of 4 cell
·  A sum term of one variable for a group of 8 cell
·  A group of 16 cells yields a value of 0 for the expression.
Example 1 & 2
0
1
AB\C
00
01
11
10
A\BC
00
0
1
0
0
1
1
1
01
1
0
1
1
0
0
0
11
1
1
10
0
1
Figure 11.2
Simplification of POS expression using a 3-variable K-Map
99
img
CS302 - Digital Logic & Design
A POS expression having 3 Maxterms is mapped to a 3-variable column based K-map.
A single group of two cells and a group of one cell are formed.
·  The first group of 0s comprising of cells 0 and 4 forms the sum term (B + C)
The second group comprising of cell 3 forms the sum term (A + B + C)
·
The three term POS expression simplifies to a 2 term POS expression (B + C).(A + B + C) .
A POS expression having 4 Maxterms is mapped to a 3-variable column based K-map.
Two groups of 2 cells each and a third group of single cell are formed.
·  The single cell group comprising of cell 0 forms the sum term (A + B + C)
The second group of 0s comprising of cells 5 and 7 forms the sum term (A + C)
·
·  The third group of 0s comprising of cells 6 and 7 forms the sum term (A + B)
The  four  term  POS  expression  simplifies  to  a  3  term  POS
expression
(A + B + C).(A + C).(A + B) .
Example 3 & 4
0
1
AB\C
00
01
11
10
A\BC
0
0
00
0
0
0
1
1
1
1
01
1
1
1
1
0
1
1
11
0
1
10
Figure 11.3
Simplification of POS expression using a 3-variable K-Map
A POS expression having 3 Maxterms is mapped to a 3-variable column based K-map.
Two groups of two cells are formed.
·  The first group of 0s comprising of cells 0 and 1 forms the sum term (A + B)
·  The second group of 0s comprising of cells 0 and 4 forms the sum term (B + C)
The three term POS expression simplifies to a 2 terms POS expression (A + B).(B + C)
A POS expression having 3 Maxterms is mapped to a 3-variable column based K-map.
One group of 2 cells and another group of single cell are formed.
·  The first group of 0s comprising of cell 0 and 1 forms the sum term (A + B)
The second group comprising of cell 6 forms the sum term (A + B + C)
·
The three term POS expression simplifies to a 2 term POS expression (A + B).(A + B + C)
Example 5
AB\CD
00
01
11
10
0
0
00
1
1
01
0
0
1
1
1
11
1
1
1
10
1
1
1
0
100
img
CS302 - Digital Logic & Design
Figure 11.4
Simplification of POS expression using a 4-variable K-Map
A POS expression having 5 Maxterms is mapped to a 4-variable column based K-map.
Three groups of two cells are formed.
The first group of 0s comprising of cells 4 and 5 forms the sum term (A + B + C)
·
The second group of 0s comprising of cells 0 and 4 forms the sum term (A + C + D)
·
·  The third group of 0s comprising of cells 2 and 10 forms the sum term (B + C + D)
The  five  term  POS  expression  has  reduced  to  a  3  term  POS  expression
(A + B + C).(A + C + D).(B + C + D)
Example 6
11
10
AB\CD
00
01
00
0
0
1
0
01
0
0
1
1
11
1
0
1
1
0
10
1
0
1
Figure 11.5
Simplification of POS expression using a 4-variable K-Map
A POS expression having 8 Maxterms is mapped to a 4-variable column based K-map.
Two groups of 4 cells and one group of two cells are formed.
·  The first group of 0s comprising of cells 0, 1, 4 and 5 forms the sum term (A + C)
The second group of 0s comprising of cells 1, 5, 9 and 13 forms the sum term (C + D)
·
·  The third group of 0s comprising of cells 2 and 10 forms the sum term (B + C + D)
The
eight
term
POS
expression
has
reduced
to
a
3
term
POS
expression (A + C).(C + D).(B + C + D) .
Example 7
01
AB\CD
00
11
10
00
1
0
1
1
0
01
0
0
1
11
1
0
1
1
10
1
0
1
1
Figure 11.6
Simplification of POS expression using a 4-variable K-Map
A POS expression having 6 Maxterms is mapped to a 4-variable column based K-map.
Three groups of 2 cells and one group of a single cell are formed.
·  The first group of 0s comprising of cells 4 and 5 forms the sum term (A + B + C)
The second group of 0s comprising of cells 5 and 7 forms the sum term (A + B + D)
·
The third group of 0s comprising of cells 1 and 9 forms the sum term (B + C + D)
·
101
img
CS302 - Digital Logic & Design
·  The fourth group comprising of cell 14 forms the sum term (A + B + C + D)
The
six
term
POS
expression
has
reduced
to
a
4
term
POS
expression (A + B + C).(A + B + D).(B + C + D).(A + B + C + D)
Converting between POS and SOP using the K-map
Converting between the two forms of standard expressions is very simple. If the 1s
mapped on the K-map are grouped together they form the product terms of the SOP
expression. Similarly, if the 0s mapped on the K-map are grouped together they form the sum
terms of the POS expression
Consider the POS expression (A + B + C).(A + B + D).(B + C + D).(A + B + C + D)
01
AB\CD
00
11
10
00
01
10
AB\CD
11
00
1
0
1
1
00
1
0
1
1
01
0
0
0
1
01
0
0
0
1
11
1
0
1
1
11
1
1
1
0
1
1
1
10
1
0
1
1
10
0
Figure 11.7
Converting between SOP and POS using K-map
An equivalent SOP expression can be obtained by grouping the 1s together.
BD + BC + ABC + ABD + ACD
Five-Variable Karnaugh Map
A K-map for 5 variables can be constructed by using two 4-variable K-maps. Figure
11.8. The cells 0 to 15 lie in the 4-variable map A=0 and cells 16 to 31 lie in the 4-variable map
A=1.
The two, 4-variable maps are considered to be lying on top of each other. Thus a two
dimensional map is formed. Rules for grouping of 0s and 1s remain unchanged. In a 2-
dimensional map, the groups of adjacent 0s or 1s can also span both the maps. In a 5-variable
Karnaugh map groups of 2, 4, 8, 16 and 32 can be formed.
BC\DE
00
01
11
10
BC\DE
00
01
11
10
00
0
1
3
2
00
16
17
19
18
01
4
5
7
6
01
20
21
23
22
11
12
13
15
14
11
28
29
31
30
10
8
9
11
10
10
24
25
27
26
Figure 11.8
5-variable Karnaugh Map using A=0 and A=1 maps
Mapping, Grouping and Simplification using 5-variable Karnaugh maps is identical to
those of 3 and 4 variable Karnaugh maps.
102
img
CS302 - Digital Logic & Design
Simplification of 5-Variable Karnaugh Map
BC\DE
00
01
11
10
BC\DE
00
01
11
10
00
0
1
0
1
00
1
1
0
0
01
0
1
0
0
01
1
1
0
0
11
0
0
0
1
11
0
0
0
1
10
0
0
1
1
10
0
1
1
1
Figure 11.9
5-variable Karnaugh Map Simplification
The 5-variable Karnaugh map is mapped with Minterms in plane A=0 and A=1
respectively. Consider the groups that are formed.
·
Starting with A=0 map. The cells 1 and 5 form a group of two cells. These two cells along
with cells 17 and 21 in map A=1 from a group of 4 cells. This group of 4 cells represents
the term BDE
·
The cell 2 in map A=0. Cell 2 does not form a group with any adjacent cells. Therefore it is
a group of single cell having the product term ABCDE
·
The cells 10 and 11 in map A=0. These two cells form a group of four with adjacent cells
26 and 27 in map A=1. Therefore the group of 4 cells represents the product term BCD
·
Tthe cells 11 and 14 in map A=0 and cells 26 and 30 in map A=1represent a group of 4
cells representing the product term BDE
Now considering the map A=1.
·  The 4 cells 16, 17, 20 and 21 represent the product term ABD
·  The cell 25 along with cell 27 in map A=1 represent the product term ABCE
Functions having multiple outputs
In the discussions on Boolean expressions and Function Tables that represent
Boolean functions it has been assumed that Logic Circuits have multiple inputs and single
output. Practical Logic circuits however, have multiple inputs and multiple outputs. Circuits
having a single output or multiple outputs are treated in the same manner.
Circuits having multiple outputs are represented by multiple function tables one for
each output or a single function table having multiple output columns. The example of a BCD
to 7-Segment Decoder circuit which has 4 inputs and 7 outputs is considered to explain
functions having multiple outputs.
7-Segment Display
The 7-segment display digit is shown. Figure 11.10. 7-Segment Display is used to
display the decimal numbers 0 to 9. A 7-segment display digit has 7 segments a, b, c, d, e, f
and g that are turned on/off by a digital circuit depending upon the number that is to be
displayed.
103
img
CS302 - Digital Logic & Design
Digit
Segments
0
a, b, c, d, e, f
1
b, c
2
a, b, d, e, g
3
a, b, c, d, g
4
b, c, f, g
5
a, c , d, f, g
6
a, c, d, e, f, g
7
a, b, c
8
a, b, c, d, e, f, g
9
a, b, c, d, f, g
Figure 11.10 7-Segment Display
Different set of segments have to be turned on to display different digits. For example,
to display the digit 3, segments a, b, c, d and g have to be turned on. To display the digit 7,
segments a, b and c have to be turned on. The table indicates the segments that are turned on
for each digit.
The circuit that turns on the appropriate segments to display a digit is known as a BCD
to 7-Sement Decoder. The input to the BCD to 7-Segment decoder circuit is a 4-bit BCD
number between 0 and 9. The seven output lines of the decoder connect to the 7 segments.
Figure 11.11.
7-segment
output
4-bit
a
Logic
BCD
f
b
Circuit
g
input
e
c
d
Figure 11.11 BCD to 7-Segment Decoder
To implement the decoder circuit having 4 inputs and 7 outputs, function tables have to
be drawn which represent the output status of each output line for all combinations of inputs.
For example, the segment a is turned on when the 4-bit input is 0, 2, 3, 5, 6, 7, 8 and 9.
Similarly, the segment b is turned on for 0, 2, 3, 4, 7, 8 and 9 combinations of inputs. Thus
seven expressions, one for each segment has to be be determined before the decoder circuit
can be implemented.
Seven function tables are required to represent the input/output combinations for each
segment. The seven function tables for segments a, b, c, d, e, f and g are shown. Figure
11.12a-g. To determine the seven expressions for each of the seven outputs, seven 4-variable
Karnaugh maps are used. The Karnaugh maps and the simplified expressions are shown.
Figure 11.13a-g. An alternate way of representing the seven Function tables is to have a
single function table with the four columns representing the 4-bit input BCD number and seven
104
img
CS302 - Digital Logic & Design
output columns each representing one of the seven segments a, b, c, d, e, f and g
respectively.
Since the 4-bit input to the decoder circuit can have 16 possible input combinations,
therefore each of the seven Function tables have sixteen input combinations. However, the
last 6 input combinations are don't care as these combinations never occur because the input
to the circuit is a 4-bit BCD number. The don't care states help in simplifying the Boolean
expressions for the seven segments.
Input
Output
Input
Output
A
B
C
D
Seg. a
A
B
C
D
Seg. a
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
0
x
0
0
1
1
1
1
0
1
1
x
0
1
0
0
0
1
1
0
0
x
0
1
0
1
1
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
1
1
1
1
1
x
Figure 11.12a
Function Table for Segment a
Input
Output
Input
Output
A
B
C
D
Seg. b
A
B
C
D
Seg. b
0
0
0
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
0
0
1
0
1
1
0
1
0
x
0
0
1
1
1
1
0
1
1
x
0
1
0
0
1
1
1
0
0
x
0
1
0
1
0
1
1
0
1
x
0
1
1
0
0
1
1
1
0
x
0
1
1
1
1
1
1
1
1
x
Figure 11.12b
Function Table for Segment b
Input
Output
Input
Output
A
B
C
D
Seg. c
A
B
C
D
Seg. c
0
0
0
0
1
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
0
0
1
0
0
1
0
1
0
X
0
0
1
1
1
1
0
1
1
X
0
1
0
0
1
1
1
0
0
X
0
1
0
1
1
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
1
1
1
1
1
x
105
img
CS302 - Digital Logic & Design
Figure 11.12c
Function Table for Segment c
Input
Output
Input
Output
A
B
C
D
d
A
B
C
D
d
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
0
x
0
0
1
1
1
1
0
1
1
x
0
1
0
0
0
1
1
0
0
x
0
1
0
1
1
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
0
1
1
1
1
x
Figure 11.12d
Function Table for Segment d
Input
Output
Input
Output
A
B
C
D
Seg. e
A
B
C
D
Seg. e
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
1
0
x
0
0
1
1
0
1
0
1
1
x
0
1
0
0
0
1
1
0
0
x
0
1
0
1
0
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
0
1
1
1
1
x
Figure 11.12e
Function Table for Segment e
Input
Output
Input
Output
A
B
C
D
Seg. f
A
B
C
D
Seg. f
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
0
1
0
1
0
x
0
0
1
1
0
1
0
1
1
x
0
1
0
0
1
1
1
0
0
x
0
1
0
1
1
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
0
1
1
1
1
x
Figure 11.12f
Function Table for Segment f
106
img
CS302 - Digital Logic & Design
Input
Output
Input
Output
A
B
C
D
Seg. g
A
B
C
D
Seg. g
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
0
1
1
0
1
0
x
0
0
1
1
1
1
0
1
1
x
0
1
0
0
1
1
1
0
0
x
0
1
0
1
1
1
1
0
1
x
0
1
1
0
1
1
1
1
0
x
0
1
1
1
0
1
1
1
1
x
Figure 11.12g
Function Table for Segment g
00
11
11
10
AB\CD
01
10
AB\CD
00
01
00
1
0
1
1
1
1
00
1
1
0
01
1
0
1
0
01
1
1
1
11
x
x
x
x
11
x
x
x
X
10
1
x
1
1
x
x
10
1
x
a = A + C + BD + BD
b = B + CD + CD
AB\CD
01
10
00
11
10
AB\CD
00
01
11
00
00
0
1
1
1
1
1
0
1
01
0
1
0
1
01
1
1
1
1
11
x
x
x
x
11
x
x
x
x
1
x
x
10
1
1
x
x
10
1
c = C+D+B
d = A + BD + BC + CD + BCD
00
10
AB\CD
01
11
AB\CD
00
01
11
10
00
1
0
0
1
00
1
0
0
0
01
0
0
0
1
01
1
1
0
1
x
x
11
x
x
11
x
x
x
x
10
1
0
x
x
10
1
1
x
x
e = BD + CD
f = B + CD + BC + BD
11
10
AB\CD
00
01
00
0
0
1
1
1
01
1
0
1
x
11
x
x
x
10
1
1
x
x
g = A + BC + CD + BC
107
img
CS302 - Digital Logic & Design
Figure 11.13a-g
Karnaugh Maps and Simplified Boolean Expressions for Display Segments
a to g
108
Table of Contents:
  1. AN OVERVIEW & NUMBER SYSTEMS
  2. Binary to Decimal to Binary conversion, Binary Arithmetic, 1’s & 2’s complement
  3. Range of Numbers and Overflow, Floating-Point, Hexadecimal Numbers
  4. Octal Numbers, Octal to Binary Decimal to Octal Conversion
  5. LOGIC GATES: AND Gate, OR Gate, NOT Gate, NAND Gate
  6. AND OR NAND XOR XNOR Gate Implementation and Applications
  7. DC Supply Voltage, TTL Logic Levels, Noise Margin, Power Dissipation
  8. Boolean Addition, Multiplication, Commutative Law, Associative Law, Distributive Law, Demorgan’s Theorems
  9. Simplification of Boolean Expression, Standard POS form, Minterms and Maxterms
  10. KARNAUGH MAP, Mapping a non-standard SOP Expression
  11. Converting between POS and SOP using the K-map
  12. COMPARATOR: Quine-McCluskey Simplification Method
  13. ODD-PRIME NUMBER DETECTOR, Combinational Circuit Implementation
  14. IMPLEMENTATION OF AN ODD-PARITY GENERATOR CIRCUIT
  15. BCD ADDER: 2-digit BCD Adder, A 4-bit Adder Subtracter Unit
  16. 16-BIT ALU, MSI 4-bit Comparator, Decoders
  17. BCD to 7-Segment Decoder, Decimal-to-BCD Encoder
  18. 2-INPUT 4-BIT MULTIPLEXER, 8, 16-Input Multiplexer, Logic Function Generator
  19. Applications of Demultiplexer, PROM, PLA, PAL, GAL
  20. OLMC Combinational Mode, Tri-State Buffers, The GAL16V8, Introduction to ABEL
  21. OLMC for GAL16V8, Tri-state Buffer and OLMC output pin
  22. Implementation of Quad MUX, Latches and Flip-Flops
  23. APPLICATION OF S-R LATCH, Edge-Triggered D Flip-Flop, J-K Flip-flop
  24. Data Storage using D-flip-flop, Synchronizing Asynchronous inputs using D flip-flop
  25. Dual Positive-Edge triggered D flip-flop, J-K flip-flop, Master-Slave Flip-Flops
  26. THE 555 TIMER: Race Conditions, Asynchronous, Ripple Counters
  27. Down Counter with truncated sequence, 4-bit Synchronous Decade Counter
  28. Mod-n Synchronous Counter, Cascading Counters, Up-Down Counter
  29. Integrated Circuit Up Down Decade Counter Design and Applications
  30. DIGITAL CLOCK: Clocked Synchronous State Machines
  31. NEXT-STATE TABLE: Flip-flop Transition Table, Karnaugh Maps
  32. D FLIP-FLOP BASED IMPLEMENTATION
  33. Moore Machine State Diagram, Mealy Machine State Diagram, Karnaugh Maps
  34. SHIFT REGISTERS: Serial In/Shift Left,Right/Serial Out Operation
  35. APPLICATIONS OF SHIFT REGISTERS: Serial-to-Parallel Converter
  36. Elevator Control System: Elevator State Diagram, State Table, Input and Output Signals, Input Latches
  37. Traffic Signal Control System: Switching of Traffic Lights, Inputs and Outputs, State Machine
  38. Traffic Signal Control System: EQUATION DEFINITION
  39. Memory Organization, Capacity, Density, Signals and Basic Operations, Read, Write, Address, data Signals
  40. Memory Read, Write Cycle, Synchronous Burst SRAM, Dynamic RAM
  41. Burst, Distributed Refresh, Types of DRAMs, ROM Read-Only Memory, Mask ROM
  42. First In-First Out (FIFO) Memory
  43. LAST IN-FIRST OUT (LIFO) MEMORY
  44. THE LOGIC BLOCK: Analogue to Digital Conversion, Logic Element, Look-Up Table
  45. SUCCESSIVE –APPROXIMATION ANALOGUE TO DIGITAL CONVERTER