Topic 4_principle - Standard & Canonical

Topic 4: Principle of Combinational Circuit (Standard & Canonical Forms)

E LE 3223 D IG IT A L SY ST E M S

Standard & C anonicalForm

1

Combinational Circuits „

DEFINITION: ‰

„

Logic circuits without feedback from output to input, constructed from a functionality complete gate set are said to be combinational .

Logic circuits that contain no memory (ability to store information) are combinational. ‰

Those that contain memory, including flip-flops are said to be sequential

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

2

Mathematical definition Let X be the set of all input variables and Y set of all output variables. {xo , x1 , x 2 ,.., x n } ⇒ The combinational function F operates on input variables set X to produce output variable set Y „

x0 Inputs

. . xn

„

Combinational Logic Functions

F

y0

. .

Outputs

yn

Output variables are not fed back to the input.

ELE 3223 DIGITAL SYSTEMS

Y = F (X )

Standard & Canonical Form

3

Analysis of Combinational Logic „

Examples of combinational circuits : ‰ decoders, encoders, multiplexers, adders, subtractors, multipliers, comparators, etc.

„

Need to consider the implementation of combinational systems with combinational logic circuits.

„

Combinational logic deals with the method of “combining” basic gates into circuits that carry out a desired application.

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

4

General Logic Design Sequence „ „ „ „ „ „ „

Problem Statement Truth-Table Construction Switching Equations Written Equations Simplified Logic Diagram Drawn Decide on Logic Family for Implementation Logic Circuit Built

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

5

Derivation of Switching Equation „

Logic can be described in several ways ‰

Truth Table

‰

Logic Diagram

‰

Boolean Equation

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

6

Standard Form „

Standard Form can be derived from truth table. It can be formed either: ‰

‰

ELE 3223 DIGITAL SYSTEMS

Sum of products (SOP) – based on logic 1 or Products of Sum (POS) – based on logic 0

Standard & Canonical Form

7

Combinational Logic „

Each input variable group that produces a logical 1 in a truth table output column can form a term in an Boolean Expression. ‰ ‰

Each term is formed by ANDing input variables Each AND term is then ORed with other AND terms to complete output Boolean Equation

K = a b c + a bc + ab c + abc

NOTE : „ Each AND term (also called a product term) identified one input condition where the output is a logical 1. ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

8

Definitions „

Literal ‰

A Boolean variable or its complement.

e.g. „

⇒ X and X are both literals

X

Product Term ‰

A product term is a literal or the logical product (AND) of multiple literals. e.g. Let X , Y , Z be binary variables ⇒ a product term could be

X , XY , XYZ ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

9

„

Sum Term ‰

A sum term is a literal or the logical OR of multiple literals. e.g. Let X , Y , Z be binary variables ⇒ a sum term could be X , X + Y , X + Y + Z

„

Sum of Products ‰

„

SOP is the logical OR of multiple product terms. Each product term is the AND of binary literals. e.g. X + XY + YZ + XYZ is a SOP expression

Products of Sums ‰

POS is the logical AND of multiple OR terms. Each sum term is the OR of binary literals. e.g. (X + XY )(YZ + XY + Z )(Y + Z ) is a POS expression

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

10

Minterms and Maxterms „

Minterm ‰ ‰

„

A minterm is a special case product (AND) term. A minterm is a product term that contains all the input variables (each literal no more than once) that make up a Boolean expression.

Maxterm ‰ ‰

A maxterm is a special case (OR) term. A maxterm is a sum term that contains all the input variables (each literal no more than once) that make up a Boolean expression.

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

11

Minterm Shorthand a 0 0 0

b 0 0 1

c 0 1 0

F 0 1 1

0

1 1

1

1

0 0

0

1

0 1

1

1

1 0

1

1

1 1

0

a •b •c a •b •c a •b•c a •b•c a •b •c a •b •c a •b•c a •b•c

= m0 = m1 = m2 = m3 = m4 = m5 = m6 = m7

A minterm has one literal for each input variable, either in its normal or complemented form. Note: Binary ordering

A canonical sum-of-products form of an expression consists only of minterms OR’d together

F = (a • b • c ) + ( a • b • c ) + (a • b • c ) + (a • b • c ) + (a • b • c ) m1 + m2 + m3 + m5 + m6 F= F = ∑ m (1,2,3,5,6) ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

12

Minterms of Different Sizes Two variables: a 0 0 1 1

b 0 1 0 1

minterm a’b’ = m0 a’b = m1 a b’ = m2 a b = m3

Three variables: a 0 0 0 0 1 1 1 1

b 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1

ELE 3223 DIGITAL SYSTEMS

minterm a’b’c’ = m0 a’b’c = m1 a’b c’ = m2 a’b c = m3 a b’c’ = m4 a b’c = m5 a b c’ = m6 a b c = m7

Four variables: a 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

b 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

Standard & Canonical Form

c 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

d 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

minterm a’b’c’d’ = m0 a’b’c’d = m1 a’b’c d’ = m2 a’b’c d = m3 a’b c’d’ = m4 a’b c’d = m5 a’b c d’ = m6 a’b c d = m7 a b’c’d’ = m8 a b’c’d = m9 a b’c d’ = m10 a b’c d = m11 a b c’d’ = m12 a b c’d = m13 a b c d’ = m14 a b c d = m15 13

Canonical Sum of Products „

A canonical SOP is a complete set of minterms that defines when an output variable is a logical 1.

„

Each minterm corresponds to the row in the truth table when the output function is 1.

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

14

Canonical Product of Sums „

A canonical POS is a complete set of maxterms that defines when an output variable is a logical 0.

„

Each maxterm corresponds to the row in the truth table when the output function is 0.

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

15

Canonical Forms „

Canonical defined as “conforming to a general rule”. ‰

„

The rule for switching logic in that each term used in a switching equation must contain all of the variables.

Two formats generally exist for expressing switching equations in a canonical form. ‰ ‰

Sum of minterms Product of maxterms

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

16

Canonical Forms „

Canonical forms are not simplified ‰

„

Use Boolean Theorems to simplify the expressions ‰ ‰

„

Normally the opposite of simplification, containing redundancies.

to eliminate redundancy lower cost of the final logic circuit

Design may require converting to logic realised in one form to another form ‰ ‰

ELE 3223 DIGITAL SYSTEMS

TTL NAND gates to ECL NOR gate Thus can be better to convert to canonical form before simplification carried out Standard & Canonical Form

17

The Connection: Truth Tables to Functions

c 0 1 0

F 0 1 1

Condition that a is 0, b is 0, c is 1.

a 0 0 0

b 0 0 1

0

1 1

a •b •c a •b•c 1 a •b•c

1

0 0

0

1

0 1

1

1

1 0

a •b •c 1 a •b•c

1

1 1

0

Function F is true if any of these and-terms are true!

OR

F = (a • b • c ) + (a • b • c ) + (a • b • c ) + (a • b • c ) + (a • b • c ) Sum-of-Products form ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

18

Minterm Shorthand a 0 0 0

b 0 0 1

c 0 1 0

F 0 1 1

0

1 1

1

1

0 0

0

1

0 1

1

1

1 0

1

1

1 1

0

a •b •c a •b •c a •b•c a •b•c a •b •c a •b •c a •b•c a •b•c

= m0 = m1 = m2 = m3 = m4 = m5 = m6 = m7

A minterm has one literal for each input variable, either in its normal or complemented form. Note: Binary ordering

A canonical sum-of-products form of an expression consists only of minterms OR’d together

F = (a • b • c ) + ( a • b • c ) + (a • b • c ) + (a • b • c ) + (a • b • c ) m1 + m2 + m3 + m5 + m6 F= F = ∑ m (1,2,3,5,6) ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

19

Minterms of Different Sizes Four variables:

Two variables: a 0 0 1 1

b 0 1 0 1

minterm a’b’ = m0 a’b = m1 a b’ = m2 a b = m3

Three variables: a 0 0 0 0 1 1 1 1 ELE 3223 DIGITAL SYSTEMS

b 0 0 1 1 0 0 1 1

c 0 1 0 1 0 1 0 1

minterm a’b’c’ = m0 a’b’c = m1 a’b c’ = m2 a’b c = m3 a b’c’ = m4 a b’c = m5 a b c’ = m6 a b c = m7

a 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Standard & Canonical Form

b 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

c 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

d 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

minterm a’b’c’d’ = m0 a’b’c’d = m1 a’b’c d’ = m2 a’b’c d = m3 a’b c’d’ = m4 a’b c’d = m5 a’b c d’ = m6 a’b c d = m7 a b’c’d’ = m8 a b’c’d = m9 a b’c d’ = m10 a b’c d = m11 a b c’d’ = m12 a b c’d = m13 a b c d’ = m14 a b c d = m15 20

Sum-of-Products Minimization F in canonical sum-of-products form (minterm form):

F = (a • b • c ) + (a • b • c ) + (a • b • c ) + (a • b • c ) + (a • b • c ) Use algebraic manipulation to make a simpler sum-of-products form Duplicate term - OK

Use commutativity to reorder to group similar terms

F = (a • b • c) + (a • b • c) + (a • b • c ) + (a • b • c) + (a • b • c ) + (a • b • c )

F = ( a + a )(b • c ) + (c + c )( a • b) + ( a + a )(b • c ) Use x’+x = 1 identity

F = (b • c ) + ( a • b ) + (b • c )

Use distributivity to factor out common terms

We will find a better method (K-maps) later… ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

21

Example of Canonical Conversion Y = f (a, b, c ) = ab + ac + bc

SOP

Identify the missing variables in each AND term for ab ⇒

c

ab → ab (c + c ) = ab c + ab c

for

ac

⇒ b

ac → ac (b + b ) = abc + ab c

for

bc

⇒ a

bc → bc (a + a ) = abc + a bc

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

22

Example of Canonical Conversion ⇒ Canonical SOP form: Y = ab c + ab c + abc + ab c + abc + a bc

Two terms the same ⇒ expression is

A+ A = A

, thus final

Y = ab c + abc + ab c + abc + a bc

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

23

Example of Canonical Conversion G = f (w, x, y , z ) = w x + yz

SOP

Identify the missing variables in each term for wx ⇒ y & z w x → w x( y + y )( z + z ) w xyz + w xyz + w xyz + w xyz

for

⇒ x&w r r yz → yz ( x + x )(w + w ) yz

yz xw + yz x w + yz xw + yz x w G = w xyz + w xyz + w xyz + w xyz + yz xw + yz x w + yz xw + yz x w ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

24

Example of Canonical Conversion POS

T = f (a, b, c ) = (a + b )(b + c)

Identify the missing variables in each OR term for (a + b ) ⇒ c a + b → a + b + (cc ) = (a + b + c)(a + b + c )

for

(b + c)

⇒ a

(b + c + aa ) → ( a + b + c)( a + b + c)

T = (a + b + c)(a + b + c )(a + b + c)(a + b + c) ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

25

Example of Canonical Conversion ⇒ Canonical POS form: T = (a +b + c)(a +b + c)(a +b + c)(a +b + c)

Two terms the same ⇒ expression is

A. A = A

, thus final

T = (a +b + c)(a +b + c)(a +b + c)

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

26

Generation of Switching Equations from Truth-Table „

What happens when we have a large number of minterms or maxterms ?

P = ab c + ab c + abc + abc + a bc „

Switching equations can be written more conveniently by using minterm or maxterm numerical designation. ‰

where decimal equivalent value for the term can be written directly.

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

27

Generation of Switching Equations P = ab c + ab c + abc + abc + a bc „

If decoded each of the minterms based on binary weighting of each variable and produce a list of decimal minterms, the result would be

P = ∑ (5,4,6,7,3) ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

28

Product-of-Sums from a Truth Table A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1

C 0 1 0 1 0 1 0 1

F 0 0 0 1 1 1 1 1

F 1 1 1 0 0 0 0 0

Find an expression for F’ (the complement)

F = ABC + ABC + ABC F = ABC + ABC + ABC

Complement both sides…

F = ABC • ABC • ABC F = ( A + B + C) • ( A + B + C ) • ( A + B + C) ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

Use DeMorgan’s Law to re-express as product-of sums 29

Maxterms A 0 0 0 0 1 1 1 1

B 0 0 1 1 0 0 1 1 „

C 0 1 0 1 0 1 0 1

F 0 0 0 1 1 1 1 1

F 1 1 1 0 0 0 0 0

F = ( A + B + C) • ( A + B + C ) • ( A + B + C)

Maxterms

To find a Product-of-Sums form for a truth table ‰

‰

Make one maxterm for each row in which the function is zero For each maxterm, each variable appears once „ „

ELE 3223 DIGITAL SYSTEMS

In its complemented form if it is one in the row In its regular form if it is zero in the row Standard & Canonical Form

30

Maxterm Shorthand Product of Sums A

B

C

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

Maxterms A + B + C = M0 A + B + C = M1 A + B + C = M2 A + B + C = M3 A + B + C = M4 A + B + C = M5 A + B + C = M6 A + B + C = M7

F in canonical maxterm form:

F = ( A + B + C) • ( A + B + C ) • ( A + B + C) F = M 0 • M1 • M 2 F = ∏ M(0, 1, 2) ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

31

Generation of Switching Equations „

A canonical POS is representation by

P = π (5,4,6,7,3)

ELE 3223 DIGITAL SYSTEMS

Standard & Canonical Form

32