ELEC1303 - Lecture 4

|← Back to Home

ELEC1303 - Lecture 3
Canonical Forms - Slides

Canonical Forms

• A canonical form provides a standardized way to translate a truth table into a unique Boolean expression
• There are two canonical forms:
  • Sum of Products (SOP) / Sum of Minterms (SOM)
  • Product of Sum (POS), / Product of Maxterms (POM)
• They can be determined directly from truth table
  • However, canonical form $\ne$ minimal form
  • Canonical forms include a larger number of literals

Minterms and Maxterms

• Minterm (or product term)
  • A minterm is an AND of all variables in either true or complemented form
    • Variables are in complemented form when they are set to ‘0’
  • The function will equal 1 when any of the minterms are true

Example with 2 variables:

$A$	$B$	Minterm	Expression
0	0	$m_0$	$A^{\prime }{B}^{\prime }$
0	1	$m_1$	$A^{\prime }B$
1	0	$m_2$	$A{B}^{\prime }$
1	1	$m_3$	$AB$
If you want a function to be 1 for inputs (1, 0) and (1, 1), then:
$F(A,B)=m_2+m_3=A{B}^{\prime }+AB$

• Maxterm (or sum term)
  • A maxterm is an OR of all variables in either true or complemented form
    • Variables are in true form when they are set to ‘0’
  • The function will equal 0 when any of the maxterms are false

Example with 2 variables:

$A$	$B$	Maxterm	Expression
0	0	$M_0$	$A+B$
0	1	$M_1$	$A+B^{\prime }$
1	0	$M_2$	$A^{\prime }+B$
1	1	$M_3$	$A^{\prime }+B^{\prime }$
If you want a function to be 0 for inputs (0, 1) and (1, 0), then:
$F(A,B)=M_1+M_2=(A+B^{\prime })\cdot (A^{\prime }+B)$

Conversion Between Canonical Forms

To convert a Boolean function $f$ from one canonical form to another, interchange the symbols $\sum$ and $\prod$ and list those indices missing from the original form

Example:

• SOP: $f=m_0+m_2+m_3+m_5+m_7=\sum m(0,2,3,5,7)$
• POS: $f=M_1\cdot M_4\cdot M_6=\prod M(1,4,6)$

Compliment of a Boolean Function

• The complement of a SOP is a POS with the same indices
• This compliment of a POS is a SOP with the same indices
  $f=\sum m(0,2,3,5,7)\to f^{\prime }=\prod m(0,2,3,5,7)$

Incompletely Specified Functions

• In some logic circuits, certain input conditions are impossible
• In these cases, the output value is defined as a “don’t care”
  • This reduces the cost of the logic circuit
• We mark a “don’t care” entry as an ‘X’ in a function table

When using canonical representation of function, you must represent two of three sets: on-set (‘1’s), off-set (‘0’s) or dc-set (‘X’). If you represent two sets, by process of elimination, you will know the third set. So far, we have only been representing the on-set.

• There are lots of examples of canonical representations in the slides

Implementations of Two-Level Logic

• We can implement directly any canonical form with two levels of gates

Multi-Level Logic

• Factoring out the canonical form to find the minimised form will reduce the number of gates, but we will still be left with two levels
• We can also sometimes reduce the number of overall gates by increasing the number of logic levels
  • Adding levels may reduce gates but increase delay

Advantages

• Circuits may be smaller
• Gates have a smaller number of inputs
• Circuits may be faster

Disadvantages

• More difficult to design
• Tools for optimization are not as good as for two-level
• Analysis is more complex

---

ELEC1303 - Lecture 5