Chapter 5 Notes

1. 5.2, 5.3 - Karnaugh Maps - Means of simplifying Boolean algebraic expression generally used in digital design for 2 to 5 inputs.
 
Design Method - Generally applicable for class problems.

Example

1. Describe switching function - Given the following table:

a b | z 
0 0 | 1
0 1 | 0
1 0 | 1     z = a'b' + ab'
1 1 | 0

2. Simplify function - Use Karnaugh mappings and/or algebraic methods.
1. Transfer switching function truth table to two-dimensional table as below.
2. Sum of Products - Based on a'b' + ab' = b'(a + a')  = b'
1. Circle largest remaining multiple of 2 rectangle of adjacent 1's or don't cares.
2. Do not circle groups completely within other circled groups.
3. Write product term for each group, removing any sum term with variable that occurs in both uncomplemented and complemented form (e.g. a+a').
4. Sum reduced product terms.
5. If uncircled 1's remain, go to 1.

z   b     \0 | 1  a 0|1 | 0|   1|1 | 0|

z   b     \0 | 1      a 0|1 | 0|   1|1 | 0|

z = b'

1. Product of Sums - Based on (a' + b')(a + b') = a'a + a'b' + ab' + b' = 0 + b'(a + a') + b' = b' + b' = b'
1. Circle largest remaining multiple of 2 rectangle of adjacent 0's or don't cares.
2. Do not circle groups completely within other circled groups.
3. Write sum term for each group, removing any product term with variable that occurs in both uncomplemented and complemented form (e.g. a*a').
4. Form product of reduced sum terms, writing complement of each variable.

If uncircled 0's remain, go to 1.

z   b     \0 | 1  a 0|1 | 0|   1|1 | 0|

z   b     \0 | 1  a 0|1 | 0|   1|1 | 0|

z = b'

Example with DON'T CARES
1. Describe switching function - Recall the 7-segment display is used to display the digits from 0-9 on calculators and many other displays. The 7-segment display appears as:
                 a                             a
          f  |   g   | b                       g  | b
          e |   d   | c                 e |  d
 
where each segment is ON or OFF dependent upon the digit to be displayed. For example, to display the digit 0 would require segments a, b, c, d, e, and f to be ON with segment g OFF. To display the digit 2 would require segments a, b, g, e, and d to be ON and f and c segments OFF as in the above. The definition can be given in the following truth table or switching function d(x₃,x₂,x₁,x₀) with one-set(0,2,3,5,6,8,9):

       x3x2x1x0 | d(x3,x2,x1,x0)
    0  0000    |      1        
    1  0001    |      0         
    2  0010    |      1
    3  0011    |      1         
    4  0100    |      0        
    5  0101    |      1         
    6  0110    |      1         
    7  0111    |      0         
    8  1000    |      1        
    9  1001    |      1         
    10 1010    |      don't care
    11 1011    |      don't care        
    12 1100    |      don't care        
    13 1101    |      don't care         
    14 1110    |      don't care
    15 1111    |      don't care

1. Simplify function - Use Karnaugh mappings and/or algebraic methods.
1. Transfer switching function truth table to two-dimensional table as below.
2. Sum of Products
1. Circle largest remaining multiple of 2 rectangle of adjacent 1's or don't cares.
2. Do not circle groups completely within other circled groups.
3. Write product term for each group, removing any variable that occurs in both uncomplemented and complemented form.
4. Sum reduced product term.
5. If uncircled 1's remain, go to 1.

 
Unsimplified Sum of Products expression
d(x₃,x₂,x₁,x₀)=x₃'x₂'x₁'x₀'+x₃'x₂'x₁x₀'+x₃'x₂'x₁x₀+x₃x₂'x₁x₀'+x₃'x₂x₁x₀'+x₃x₂'x₁'x₀'+x₃'x₂x₁'x₀
 

x1x0         x3x2 \  00    01    11    10            00 |  1  |  0  |  1  |  1 |           01 |  0  |  1  |  0  |  1 |      Product term  x3           11 |  d  |  d  |  d  |  d |               10 |  1  |  1  |  d  |  d |                 x1x0         x3x2 \  00    01    11    10            00 |  1  |  0  |  1  |  1 |           01 |  0  |  1  |  0  |  1 |           11 |  d  |  d  |  d  |  d |      Product term x1x0'           10 |  1  |  1  |  d  |  d |                 x1x0         x3x2 \  00    01    11    10            00 |  1  |  0  |  1  |  1 |           01 |  0  |  1  |  0  |  1 |           11 |  d  |  d  |  d  |  d |      Product term x2'x1           10 |  1  |  1  |  d  |  d |                 x1x0         x3x2 \  00    01    11    10            00 |  1  |  0  |  1  |  1 |           01 |  0  |  1  |  0  |  1 |           11 |  d  |  d  |  d  |  d |      Product term x2'x0'           10 |  1  |  1  |  d  |  d |                 x1x0         x3x2 \  00    01    11    10            00 |  1  |  0  |  1  |  1 |           01 |  0  |  1  |  0  |  1 |           11 |  d  |  d  |  d  |  d |      Product term x2x1'x0           10 |  1  |  1  |  d  |  d | Simplified Sum of Products expression  d(x3,x2,x1,x0)=x3+x2x1'x0+x2'x1+x1x0'+x2'x0'

1. Product of Sums
1. Circle largest remaining multiple of 2 rectangle of adjacent 0's or don't cares.
2. Do not circle groups completely within other circled groups.
3. Write sum term for each group, removing any variable that occurs in both uncomplemented and complemented form.
4. Form product of reduced sum terms, writing complement of each variable.
5. If uncircled 0's remain, go to 1.
Unsimplified Product of Sums
d(x₃,x₂,x₁,x₀)=(x₃+x₂'+x₁+x₀)(x₃+x₂+x₁+x₀')(x₃+x₂'+x₁'+x₀')

x1x0         x3x2 \  00    01    11    10            00 |  1  |  0  |  1  |  1 |           01 |  0  |  1  |  0  |  1 |           11 |  d  |  d  |  d  |  d |    Sum term x2'+x1+x0           10 |  1  |  1  |  d  |  d |                 x1x0         x3x2 \  00    01    11    10            00 |  1  |  0  |  1  |  1 |           01 |  0  |  1  |  0  |  1 |           11 |  d  |  d  |  d  |  d |    Sum term x2'+x1'+x0'           10 |  1  |  1  |  d  |  d |                 x1x0         x3x2 \  00    01    11    10            00 |  1  |  0  |  1  |  1 |           01 |  0  |  1  |  0  |  1 |           11 |  d  |  d  |  d  |  d |    Sum term x3+x2+x1+x0'           10 |  1  |  1  |  d  |  d | Simplified Product of Sums d(x3,x2,x1,x0)=(x2'+x1+x0)(x3+x2+x1+x0')(x2'+x1'+x0')

2. 5.3.4 Quine-McCluskey Tabular Method
• Karnaugh maps are generally manageable for no more than 6 input variables, Quine-McCluskey method  is expandable to larger number of inputs and is relatively easy to program.
• Consists of two steps:
1. Determine prime implicants for function.
2. Select set of prime implicants that covers the function and is minimal.
• Prime implicants - Satisfy the identity xy+xy' = x.
1. Construct table corresponding to minterms (one-set) where 1 is uncomplemented and 0 complemented variable. Don't cares can be chosen to be in one-set.
• First column list minterms, for d(x₃,x₂,x₁,x₀) with one-set(0,2,3,5,6,8,9):

Minterm 2 is x₃'x₂'x₁x₀' represented by 0010.
Minterm 3 is x₃'x₂'x₁x₀ represented by 0011.
• Second column lists implicants with n-1 variables (since an implicant by definition satisfies the identity xy+xy' = x. It is only necessary to examine adjacent groups only (e.g. 0010 and 0011 is adjacent, 0010 and 0111 is not), those that differ only by a variable that is complemented in one minterm and uncomplemented in the other minterm.

For minterm 2 and minterm 3 of:
    x₃'x₂'x₁x₀' + x₃'x₂'x₁x₀ = x₃'x₂'x₁x₀'
                OR
    0010 and 0011 is 001_
The third column list implicants with n-2 variables. To form a pair, implicants from column n-1 must have a _ in the same position and complemented in one minterm and uncomplemented in the other minterm. The minterms pairings have been added as labels to the implicants, for example 0000 and 0010 produce 00_0 implicant which is labeled 0+2.

___________________________________________________
Minterms  | 3-variable    | 2-variable | 1-variable
0  0000 N |  00_0   0+2   |            |           
2  0010 N |  001_   2+3 N |            |
          |  0_10   2+6   |            |                     
3  0011 N |               |            |           
5  0101   |               |            |           
6  0110 N |               |            |           
8  1000 N |  100_   8+9 N |            |           
9  1001 N |               |            |

Mark elements of pairs with an N to indicate they are not prime implicants.
2. Obtain minimum number of prime implicants that covers the one set by constructing a prime-implicant table. The rows correspond to the prime implicants from Table 1 and the columns to elements of the one set. Mark with an 'x' the entries corresponding to one set elements covered by the implicant not marked with an N. The columns with only one 'x' contain an essential prime implicant, and are listed in the final reduced SOP expression.

___________________________________
     | 0 2 3 5 6 8 9 |             
0101 |       x       | * x3'x2x1'x0  
00_0 | x x           | * x3'x2'x0'   
001_ |   x x         | * x3'x2'x1       
0_10 |   x     x     | * x3'x1x0'

d(x3,x2,x1,x0) = 0101 + 00_0 + 001_ + 0_10 = x3'x2x1'x0 + x3'x2'x0' + x3'x2'x1 + x3'x1x0'

3. 5.4 Design of Multiple Output Two Level Gate Networks
• Apply the single output procedure from above (SOP or POS for one output function) to each output independent of other, multiple outputs for the network. For example, for two output functions: g(a,bc) and h(a,b,c); each can be simplified independent of the other. It is often the case that a simpler result can be obtained by solving for several functions simultaneously. However, the methods used in this course are limited to minimization for one function at a time.
4. 5.5 Two Level NAND-NAND and NOR-NOR Networks
• Derive AND-OR and convert to NAND-NAND or derive OR-AND and convert to NOR-NOR network.
• AND-OR to NAND-NAND

1. Add circles to AND output and OR input (recall that a circle is a NOT, so NOT on AND output and NOT on OR input cancel).


2. ANDs are now NANDs. NOTed input ORs are NANDs.


• OR-AND to NOR-NOR

1. Add circles to OR output and AND input (recall that a circle is a NOT, so NOT on OR output and NOT on AND input cancel).


2. ORs are now NORs. NOTed input ANDs are NORs.


5. 5.6 Limitations of Two Level Networks - See text page135.
6. 5.7 Programmable Modules: PLAs and PALs
• PLAs - Programmable Logic Arrays provide NOT-AND-OR or NOT-OR-AND implementation of some maximum number of switching functions. Usually provide an enable for tri-state outputs. The essentials of an unprogrammed PLA appear in the following:


Any NOT-AND-OR switching function of two inputs can be constructed by blowing connections. The following implements the switching function z = xy' + x'y (the XOR operation).