ECE 331 - Digital System Design

ECE 331 - Digital System Design

ECE 331 Digital System Design Standard Forms for Boolean Expressions (Lecture #4) Standard Forms for Boolean Expressions Sum-of-Products (SOP) Derived from the Truth table for a function by considering those rows for which F = 1.

The logical sum (OR) of product (AND) terms. Realized using an AND-OR circuit. Product-of-Sums (POS) Derived from the Truth table for a function by considering those rows for which F = 0.

The logical product (AND) of sum (OR) terms. Realized using an OR-AND circuit. ECE 301 - Digital Electronics 2 In Mathematical Terms Disjunctive Normal Form (DNF)

Literals within each term are ANDed Terms are Ored Analogous to Sum-of-Products (SOP) Conjunctive Normal Form (CNF) Literals within each term are Ored

Terms are ANDed Analogous to Product-of-Sums (POS) ECE 301 - Digital Electronics 3 Sum-of-Products (SOP) ECE 301 - Digital Electronics 4 Minterms

A minterm, for a function of n variables, is a product term in which each of the n variables appears once. Each variable in the minterm may appear in its complemented or uncomplemented form. For a given row in the Truth table, the corresponding minterm is formed by For all n variables in the function F.

Including variable xi, if xi = 1 Including the complement of xi, if xi = 0 ECE 301 - Digital Electronics 5 Minterms ECE 301 - Digital Electronics 6 Sum-of-Products

Any function F can be represented by a sum of minterms, where each minterm is ANDed with the corresponding value of the output for F. F = (mi . fi) Denotes the logical sum operation where mi is a minterm

and fi is the corresponding functional output Only the minterms for which fi = 1 appear in the expression for function F. F = (mi) = m(i) ECE 301 - Digital Electronics shorthand notation 7

Sum-of-Products The Canonical Sum-of-Products for function F is the Sum-of-Products expression in which each product term is a minterm. The expression is unique However, it is not necessarily the lowest-cost

Synthesis process Determine the Canonical Sum-of-Products Use Boolean Algebra (and K-maps) to find an optimal, functionally equivalent, expression. ECE 301 - Digital Electronics 8 Sum-of-Products AND sum

Y' + X'YZ' + XY X.Y AND OR product term Product Term = Logical ANDing of literals Sum = Logical ORing of product terms ECE 301 - Digital Electronics 9

Sum-of-Products Use the Distributive Laws to multiply out a Boolean expression. Results in the Sum-of-Products (SOP) form. F = (A + B).(C + D).(E) F = (A.C + A.D + B.C + B.D).(E) F = A.C.E + A.D.E + B.C.E + B.D.E not in SOP form Product terms are of single variables

H = A.B.(C + D) + ABE ECE 301 - Digital Electronics 10 Product-of-Sums (POS) ECE 301 - Digital Electronics 11 Maxterms

A Maxterm, for a function of n variables, is a sum term in which each of the n variables appears once. Each variable in the Maxterm may appear in its complemented or uncomplemented form. For a given row in the Truth table, the corresponding Maxterm is formed by Including the variable xi, if xi = 0 Including the complement of xi, if xi = 1 ECE 301 - Digital Electronics

12 Maxterms ECE 301 - Digital Electronics 13 Product-of-Sums Any function F can be represented by a product of Maxterms, where each Maxterm is ANDed with the complement of the corresponding value of the output for F.

F = (Mi . f 'i) Denotes the logical product operation where Mi is a Maxterm and f 'i is the complement of the corresponding functional output

Only the Maxterms for which fi = 0 appear in the expression for function F. F = (Mi) = M(i) ECE 301 - Digital Electronics shorthand notation 14 Product-of-Sums The Canonical Product-of-Sums for function F is the Product-of-Sums expression in which

each sum term is a Maxterm. The expression is unique However, it is not necessarily the lowest-cost Synthesis process Determine the Canonical Product-of-Sums Use Boolean Algebra (and K-maps) to find an

optimal, functionally equivalent, expression. ECE 301 - Digital Electronics 15 Product-of-Sums OR product term X.(Y' + Z).(X' + Y + Z) X' + Y + Z AND sum term

OR Sum Term = Logical ORing of variables Product = Logical ANDing of sum terms ECE 301 - Digital Electronics 16 Product-of-Sums Use the Distributive Laws to factor a Boolean expression. Results in the Product-of-Sums (POS) form. F = V.W.Y + V.W.Z + V.X.Y + V.X.Z F = (V).(W.Y + W.Z + X.Y + X.Z)

F = (V).(W + X).(Y + Z) not in POS form Sum terms are of single variables H = (A+B).(C+D+E) + CE ECE 301 - Digital Electronics 17 SOP and POS

Any function F may be implemented as either a Sumof-Products (SOP) expression or a Product-of-Sums (POS) expression. Both forms of the function F can be realized using logic gates that implement the basic logic operations. However, the two logic circuits realized for the function F do not necessarily have the same cost. Objective: minimize the cost of the designed circuit Compare the cost of the SOP realization with that of the POS realization ECE 301 - Digital Electronics

18 Converting between SOP and POS The sum-of-products (SOP) form of a Boolean expression can be converted to its corresponding product-of-sums (POS) form by factoring the Boolean expression. The product-of-sums (POS) form of a Boolean expression can be converted to its corresponding sum-of-products (SOP) form by multiplying out the Boolean expression. ECE 301 - Digital Electronics

19 Dual The dual of a Boolean expression is formed by changing AND to OR, OR to AND, 0 to 1, and 1 to 0. Alternately, it can be determined by complementing the entire Boolean expression, and then complementing each of the literals. The SOP and POS are duals of one another.

ECE 301 - Digital Electronics 20 Logic Circuit Implementations ECE 301 - Digital Electronics 21 Student Exercise: Draw the AND-OR circuits for the following Sum-of-Products (SOP) expressions: 1. F1 = A'B + AC' + B'C 2. F2 = ABD + BCD' + AB'C' + B'CD ECE 301 - Digital Electronics

22 Student Exercise: Draw the OR-AND circuits for the following Product-of-Sums (POS) expressions: 1. F1 = (A+B').(A'+C).(B+C') 2. F2 = (A+B+D).(B'+C+D').(A'+B+C).(B+C'+D) ECE 301 - Digital Electronics 23 Summary of Logic Functions ECE 301 - Digital Electronics

24 ECE 301 - Digital Electronics 25 Representing Logic Levels (using voltages) ECE 301 - Digital Electronics 26 Signal Levels and Logic Levels ECE 301 - Digital Electronics

27 Signal Levels and Logic Levels ECE 301 - Digital Electronics 28 Signal Levels in Logic Gates ECE 301 - Digital Electronics 29

Recently Viewed Presentations

  • Coca-Colas History  Invented in May of 1886 by

    Coca-Colas History Invented in May of 1886 by

    Coca-Cola's History. Invented in May of 1886 by Dr. John Styth Pemberton. First glass sold for 5 cents at Jacob's Pharmacy in Atlanta. May 29, 1886- first newspaper advertisement pronounced it "Delicious and Refreshing"
  • Whats normal? Breathing - Whats normal? Compared to

    Whats normal? Breathing - Whats normal? Compared to

    Exercise pets - cats should get 15-20 minutes per day. Dog's exercise is dependent upon breed. Different dog breeds have different common ailments. Consult your vet. Keep nails trimmed; if doing this yourself, first consult your vet. Brush and groom...
  • LINGUISTICS 200: Introduction to Linguistic Thought

    LINGUISTICS 200: Introduction to Linguistic Thought

    Today Parts of vocal tract used in producing vowels Articulatory description of vowels IPA symbols for English vowels Speech Synthesis: brief intro
  • 8th Annual Michigan Traffic Safety Summit Guidance for

    8th Annual Michigan Traffic Safety Summit Guidance for

    Fail to obey flashing signal (yellow or red) Fail to obey signal generally. Violate RR grade crossing device/regulations. Fail to obey stop sign. Fail to obey yield sign. Fail to obey traffic control device generally. Turn in violation of traffic...
  • Information for Parents on Key Stage 2 SATs

    Information for Parents on Key Stage 2 SATs

    In this Year 6 class… Children have: Spelling booklets - Look, Say, Cover, Write, Check - 5 out of 7 days - bring in on Monday; Reading Records - Green (for reviews); -
  • AGU Poster - Federation of Earth Science Information Partners

    AGU Poster - Federation of Earth Science Information Partners

    ESIP Poster: (ID) JPSS Introduction The Joint Polar Satellite System (JPSS) is the NOAA's next-generation operational Earth observation Program that acquires and distributes global environmental data from multiple polar-orbiting satellites
  • Teaching american history project

    Teaching american history project

    Come up with some activities for students to engage in around these words (or in some cases, find a proper synonym). Be prepared to share some of you amazing vocabulary ideas. ... Find one quote from Washington's Farewell Address to...
  • Getting Your International Students to Berkeley

    Getting Your International Students to Berkeley

    Promoting International Student Success Campus Wide Advising Strategies Berkeley International Office Outcomes Enhance awareness of trends in Berkeley's international student population Showcase units and services that support international students Promote an inclusive environment for advising international students Today's Agenda Snapshot...