Difference between revisions of "Karnaugh Maps"
(→Introduction) 
m (Marc moved page Karnaugh Map to Karnaugh Maps) 

(30 intermediate revisions by one other user not shown)  
Line 3:  Line 3:  
Combinational logic refers to networks whose output is strictly dependent on the inputs. The analysis of such networks requires first the writing of the Boolean algebraic equation representative of the network, and then the complete characterization of the output as a result of all the possible combinations of the inputs.  Combinational logic refers to networks whose output is strictly dependent on the inputs. The analysis of such networks requires first the writing of the Boolean algebraic equation representative of the network, and then the complete characterization of the output as a result of all the possible combinations of the inputs.  
Minimization involves reducing the Boolean algebraic expression to some minimal form. <br />  Minimization involves reducing the Boolean algebraic expression to some minimal form. <br />  
−  Any minimization tool in Boolean is based on the algebraic theorems. Algebraic reduction of Boolean functions is not easy and requires considerable experience, judgement and luck. It becomes more apparent as the complexity of the function increases. As a result extensive effort has been devoted toward developing techniques, aids or tools, that will allow the logic designer to minimize a function. The Venn diagram, Veitch diagram, Karnaugh map, QuineMcCluskey method, and other techniques have all been developed with but one objectiveto allow the designed to arrive at a minimal expression as rapidly as possible with the least amount of effort.  +  Any minimization tool in Boolean is based on the algebraic theorems. Algebraic reduction of Boolean functions is not easy and requires considerable experience, judgement and luck. It becomes more apparent as the complexity of the function increases. 
+  
+  For example the two input variable expression as $ A \overline{B} + \overline{A} \overline{B}$ is obviously dependent only on $ \overline{B} $. But it is not so obvious that the following three input expression $ A \overline{B} + \overline{B} C + \overline{A} C $ is represented by $ A \overline{B} + \overline{A} C $ . <br />  
+  
+  As a result extensive effort has been devoted toward developing techniques, aids or tools, that will allow the logic designer to minimize a function. The Venn diagram, Veitch diagram, Karnaugh map, QuineMcCluskey method, and other techniques have all been developed with but one objectiveto allow the designed to arrive at a minimal expression as rapidly as possible with the least amount of effort.  
<br />  <br />  
−  +  
+  Among these methods the '''Karnaugh Maps''' (made by G. Karnaugh in 1953) will be presented bellow.  
+  
+  The Karnaugh map is an orderly arrangement of squares with assignments such that the difference between any two adjacent squares is a onevariable change. The map must contain a square or cell for each unique combination of input variables. A map for two variables A and B must have four cells, because there are 2<sup>2</sup> different combinations of two input variables. A map for three variables A, B and C must contain 2<sup>3</sup> or eight cells, and a map on n variables must contain 2<sup>n</sup> cells. An assignment of 1 for uncomplemented variable and 0 for a complemented variable is made. For instance, a term $ A \overline{B} C $ is equivalent to the binary notations 101. The table bellow shows the ways to define each cell of two, three and four variables functions. <br/>  
+  The alphabetical input variables are identified at the upper lefthand corner of the box. For example, for three input variable function, the diagonal lines indicates that the variables A and B are represented by the binary notations across the top of the matrix (which is a Gray Code with the unique property of only a single bit change when going from one state to the next) and are contained in the vertical column below each assignment. The variable C is designed down the side of the matrix and is represented by horizontal rows within the matrix. Each cell represents a unique combination of the variables.  
+  
The '''Karnaugh map''' technique is thought to be the most valuable tool available for dealing with Boolean functions. It provides instant recognition of the basic patterns, can be used to obtain all possible combinations and minimal terms, and is easily applied to all varieties of complex problems. Minimization with the map is accomplished through recognition of basic patterns.<br />  The '''Karnaugh map''' technique is thought to be the most valuable tool available for dealing with Boolean functions. It provides instant recognition of the basic patterns, can be used to obtain all possible combinations and minimal terms, and is easily applied to all varieties of complex problems. Minimization with the map is accomplished through recognition of basic patterns.<br />  
The appearance of 1’s in adjacent cells immediately identifies the presence of a redundant variable. <br />  The appearance of 1’s in adjacent cells immediately identifies the presence of a redundant variable. <br />  
−  The following  +  The following table illustrates some examples of minimizing with two, three, four and fivevariable map.<sup>[1]</sup> 
<br />  <br />  
−  +  This table illustrates the grouping of one, two, four, eight and sixteen cells, depending on the number of inputs. For example, in a fourvariable map, the grouping of two cells eliminates one variable, the grouping of four cells eliminates two variables, and the grouping of eight cells eliminates three variables. The rule is the same for different number of input variables. <br/>  
+  Any given grouping of 1’s in the Karnaugh map is identified by a product form. <br/>  
+  Minimization involves the gathering of the various groups in the most efficient manner. The mapping of a sum of product terms is accomplished by inserting a 1 in each cell of a map containing a particular product term. <br/>  
+  The advantage of the map is that it gives a clear and complete picture of the function. It can immediately be determined if the reduction is unique or if there exist other minimal expressions.<br />  
+  
+  
+  = Karnaugh Map examples =  
{ class="wikitable"  { class="wikitable"  
+    
+    
+  [[File:T21.jpg152px]]  
+    
+  [[File:T22.jpg152px]]  
+    
+  [[File:T23.jpg152px]]  
+    
+  [[File:T24.jpg152px]]  
+    
    
    
Line 64:  Line 89:  
[[File:T413.jpg256px]]  [[File:T413.jpg256px]]  
    
−  
}  }  
+  { class="wikitable"  
+    
+  width="525pt"[[File:T71.jpg469px]] width="525pt" [[File:T72.jpg469px]]  
+    
+  width="525pt"[[File:T73.jpg469px]] width="525pt" [[File:T75.jpg469px]]  
+  }  
+  
''' RULES SUMMARY'''<br />  ''' RULES SUMMARY'''<br />  
Line 92:  Line 123:  
    
−   [[File:CIR6_A.jpg420px]]  [[File:T6n.jpg  +  width="425pt"<center> [[File:C2IN1.jpg380px]]</center> width="288pt" [[File:T2IN1.jpg160px]] width="380pt" <center>[[File:C2OUT1.jpg190px]]</center> 
+  }  
+  == Sample problem 2 ==  
+  ''' Karnaugh Map to minimize a digital circuit '''  
+  { class="wikitable"  
+    
+  ! Initial circuit !! Karnaugh Map !! AND/OR circuit  
+    
+  
+   [[File:CIR6_A.jpg420px]]  [[File:T6n.jpg290px]]  [[File:c6b.jpg380px]]  
+  }  
+  
+  == Sample problem 3 ==  
+  ''' Karnaugh Map to minimize a digital circuit '''  
+  { class="wikitable"  
+    
+  ! Initial circuit !! Karnaugh Map !! AND/OR circuit  
+    
+  
+   [[File:C4IN1.jpg460px]]  [[File:T4IN1N.jpg286px]] width="346pt" <center> [[File:C4OUT1.jpg230px]]</center>  
+  }  
+  
+  == Sample problem 4 ==  
+  ''' Simplify the following Boolean three variable equation using Karnaugh map. '''  
+  { class="wikitable"  
+    
+  ! Initial function !! Karnaugh Map !! Minimal function  
+    
+  
+   $ f = \overline{A} \overline{B} \overline{C} + A B \overline{C} +A \overline{B} + \overline{A} \overline{C} $  [[File:TEX4.jpg286px]]  $ f = \overline{C} + A \overline{B} $  
+  }  
+  
+  == Sample problem 5 ==  
+  ''' Simplify the following Boolean four variable equation using Karnaugh map. '''  
+  { class="wikitable"  
+    
+  ! Initial function !! Karnaugh Map !! Minimal function  
+    
+  
+   $ f = A \overline{B} \overline{D} + A B \overline{C} \overline{D} + A B C + B \overline{C} D + \overline{A} B C D $  [[File:TEX5.jpg286px]]  $ f = B D + A \overline{D} $  
}  }  
1. William E. Wickes, Logic Design with Integrated Circuits, John Willey & Sons, Inc, New YorkLondonSydney  1. William E. Wickes, Logic Design with Integrated Circuits, John Willey & Sons, Inc, New YorkLondonSydney 
Latest revision as of 08:31, 2 September 2020
Contents
Introduction
Logic design implies the analysis, synthesis, minimization, and implementation of binary functions.
Combinational logic refers to networks whose output is strictly dependent on the inputs. The analysis of such networks requires first the writing of the Boolean algebraic equation representative of the network, and then the complete characterization of the output as a result of all the possible combinations of the inputs.
Minimization involves reducing the Boolean algebraic expression to some minimal form.
Any minimization tool in Boolean is based on the algebraic theorems. Algebraic reduction of Boolean functions is not easy and requires considerable experience, judgement and luck. It becomes more apparent as the complexity of the function increases.
For example the two input variable expression as $ A \overline{B} + \overline{A} \overline{B}$ is obviously dependent only on $ \overline{B} $. But it is not so obvious that the following three input expression $ A \overline{B} + \overline{B} C + \overline{A} C $ is represented by $ A \overline{B} + \overline{A} C $ .
As a result extensive effort has been devoted toward developing techniques, aids or tools, that will allow the logic designer to minimize a function. The Venn diagram, Veitch diagram, Karnaugh map, QuineMcCluskey method, and other techniques have all been developed with but one objectiveto allow the designed to arrive at a minimal expression as rapidly as possible with the least amount of effort.
Among these methods the Karnaugh Maps (made by G. Karnaugh in 1953) will be presented bellow.
The Karnaugh map is an orderly arrangement of squares with assignments such that the difference between any two adjacent squares is a onevariable change. The map must contain a square or cell for each unique combination of input variables. A map for two variables A and B must have four cells, because there are 2^{2} different combinations of two input variables. A map for three variables A, B and C must contain 2^{3} or eight cells, and a map on n variables must contain 2^{n} cells. An assignment of 1 for uncomplemented variable and 0 for a complemented variable is made. For instance, a term $ A \overline{B} C $ is equivalent to the binary notations 101. The table bellow shows the ways to define each cell of two, three and four variables functions.
The alphabetical input variables are identified at the upper lefthand corner of the box. For example, for three input variable function, the diagonal lines indicates that the variables A and B are represented by the binary notations across the top of the matrix (which is a Gray Code with the unique property of only a single bit change when going from one state to the next) and are contained in the vertical column below each assignment. The variable C is designed down the side of the matrix and is represented by horizontal rows within the matrix. Each cell represents a unique combination of the variables.
The Karnaugh map technique is thought to be the most valuable tool available for dealing with Boolean functions. It provides instant recognition of the basic patterns, can be used to obtain all possible combinations and minimal terms, and is easily applied to all varieties of complex problems. Minimization with the map is accomplished through recognition of basic patterns.
The appearance of 1’s in adjacent cells immediately identifies the presence of a redundant variable.
The following table illustrates some examples of minimizing with two, three, four and fivevariable map.^{[1]}
This table illustrates the grouping of one, two, four, eight and sixteen cells, depending on the number of inputs. For example, in a fourvariable map, the grouping of two cells eliminates one variable, the grouping of four cells eliminates two variables, and the grouping of eight cells eliminates three variables. The rule is the same for different number of input variables.
Any given grouping of 1’s in the Karnaugh map is identified by a product form.
Minimization involves the gathering of the various groups in the most efficient manner. The mapping of a sum of product terms is accomplished by inserting a 1 in each cell of a map containing a particular product term.
The advantage of the map is that it gives a clear and complete picture of the function. It can immediately be determined if the reduction is unique or if there exist other minimal expressions.
Karnaugh Map examples
RULES SUMMARY
No zeros allowed.
No diagonals.
Only power of 2 number of cells in each group.
Groups should be as large as possible.
Every one must be in at least one group.
Overlapping allowed.
Wrap around allowed.
Fewest number of groups possible.
Sample problems
Sample problem 1
Karnaugh Map to minimize a digital circuit
Initial circuit  Karnaugh Map  AND/OR circuit 


Sample problem 2
Karnaugh Map to minimize a digital circuit
Initial circuit  Karnaugh Map  AND/OR circuit 

Sample problem 3
Karnaugh Map to minimize a digital circuit
Initial circuit  Karnaugh Map  AND/OR circuit 


Sample problem 4
Simplify the following Boolean three variable equation using Karnaugh map.
Initial function  Karnaugh Map  Minimal function 

$ f = \overline{A} \overline{B} \overline{C} + A B \overline{C} +A \overline{B} + \overline{A} \overline{C} $  $ f = \overline{C} + A \overline{B} $ 
Sample problem 5
Simplify the following Boolean four variable equation using Karnaugh map.
Initial function  Karnaugh Map  Minimal function 

$ f = A \overline{B} \overline{D} + A B \overline{C} \overline{D} + A B C + B \overline{C} D + \overline{A} B C D $  $ f = B D + A \overline{D} $ 
1. William E. Wickes, Logic Design with Integrated Circuits, John Willey & Sons, Inc, New YorkLondonSydney