ELEC1303 - Lecture 6

|← Back to Home

ELEC1303 - Lecture 5
Karnaugh Maps - Slides

Issues with Algebraic Manipulation

• Difficult to simplify Boolean expressions
  • There is no clear steps in the manipulation process
  • Does not always guarantee a minimal expression
• Our goal is to minimize the number of literals
  • Literal count is a good measure of cost of logic implementation
  • Proportional to # of transistors in the circuit implementation

The Uniting Theorem

• Key tool to simplification: $A(B^{\prime }+B)=A$

➢ On-set contains all input combinations when the function is 1
➢ Off-set contains all input combinations when the function is 0
➢ Dc-set contains all input combinations for which the function is X

• Essence of simplification of two-level logic:
  • Find two element subsets of the ON-set where only one variable changes its value
  • This single varying variable can be eliminated
  • Single product term can be used to represent both elements

Karnaugh Maps (K-Maps)

• The K-map is a reorganised graphical representation of a truth table
• The K-map can provide a minimal 2-level SOP or POS implementation
  • Used to minimize Boolean equations with 2-4 variables

Its key idea is to place the minterms that differ in only one variable adjacent to one another, so that one can “visualize” opportunities to apply the uniting theorem $A(B^{\prime }+B)=A$ and eliminate one variable

2-Variable K-Map

• In a 2-variable K-map, one square represents a minterm with 2 variables

• Each minterm is adjacent to another minterm that differs in only one variable

Example of using the K-map:

• Simplify: $f=m_0+m_2+m_3=x^{\prime }{y}^{\prime }+x{y}^{\prime }+xy$
• Two adjacent squares containing 1’s can be combined
  • $m_0+m_2=x^{\prime }{y}^{\prime }+x{y}^{\prime }=(x^{\prime }+x)y^{\prime }=y^{\prime }$
  • $m_2+m_3=x{y}^{\prime }+xy=x(y^{\prime }+y)=x$
• Therefore, $f$ can be simplified as: $f=x+y^{\prime }$

3-Variable K-Map

• For a 3-input logic circuit, the truth table will have $2^3$ rows represented by 8 squares in the K-map
• Numbering scheme based on Gray–code
  • e.g. 00, 01, 11, 10 (be careful!)
  • Only one bit changes for adjacent squares

• In a 3-variable K-map, one square represents a minterm with 3 variables

4-Variable K-Map

• For a 4-input logic circuit, the truth table will have $2^4$ rows represented by 16 squares in the K-map
  • Otherwise, same as above

• Squares can be considered adjacent if they are on opposite ends to each other
  • e.g. all four corners could be grouped

K-Maps With Don't Cares

• To use a K-map, it is necessary to make an entry in every square
• We can choose the value of “don’t care” states such that they can be used to assist in minimization
  • However, once you set the value of such tile it cannot change to a different value for another group

Definitions for Two-Level Simplification

• Implicant $-$ a product term that corresponds to a grouping of 1’s
  • Can include don’t cares but must include at least one “1”
• Prime Implicant $-$ implicant that cannot be completely contained in any other implicant
  i.e. the largest possible implicant for a group of 1’s
• Essential Prime Implicant $-$ a prime implicant which is the only one that covers a group of 1’s
  • “Don’t cares” used in prime implicants but do not make implicant essential
  • You must use this implicant to cover all 1’s

Product-of-Sums Minimisation

• Apply same techniques as earlier, but group 0s in your K-maps
• Replace all maxterms in grouping by a single expression
  • Expression formed by OR of the complement of the variables which do not change throughout grouping
• Thus, all those variables changing in the grouping are eliminated

Both forms of minimisation are viable and should be attempted as one technique may produce more simplified results than the other

---

ELEC1303 - Lecture 7