(5.2)

chapter (5.2) will be added about few hours later

Combination Circuit Design, Design Procedure, Code Converter Example (5.1)

Combination Circuit Design

• Design of a combinational circuit is the development of a circuit from a description

of its function.

– “design an excess-123 encoder”

– “provide a circuit that will multiplex one of three 8-bit input buses onto an 8-bit output bus.”

Design Procedure

1. Determine the required number of inputs and outputs and assign variables to them.

2. Derive the truth table that defines the required relationship between inputs and outputs.

3. Obtain and simplify the Boolean function.

4. Draw the logic diagram.

5. Verify the correctness of the design.

Code Converter Example

• Design a circuit that converts a binary-coded decimal  (BCD) codeword to its corresponding excess-3 codeword.
• If the input is a number n expressed in BCD, the output should be the number n+3 expressed in binary.
• We need 4 input variables (a,b,c,d) and 4 output functions w(a,b,c,d),x(a,b,c,d),y(a,b,c,d),z(a,b,c,d)).

By convention, a and w are the most significant bits of the input and output, respectively.

• The truth table relating the input and output variables is shown at right.
• Note that the outputs for inputs 1010 through 1111 are don't cares.

The K-maps for w( ), x( ), y( ), and z( ) can be constructed with don't cares.The simplified Boolean functions derived from the K-maps are:

– z = d’

– y = cd + c’d’

– x = b’c + b’d + bc’d’

– w = a+bc+bd

Combinational Circuits (5)

• A combinational circuit consists of logic gates whose outputs at any time are determined by the inputs using logic operations.
• For n input variables, there are 2ⁿ possible binary input combinations.
• For each binary combination of the input variables, there is one possible binary value

on each output.

•  Hence, a combinational circuit can be described by

1. a truth table that lists the output values for each combination of the input variables, or

2. m Boolean functions, one for each output  variable.

Combinational Circuit Analysis

• Analysis of a combinational circuit is the determination of the Boolean function that

the circuit implements.

• The analysis starts with a given logic circuit diagram and ends with a set of Boolean

functions or (equivalently) a truth table.

 Example:

Multilevel NAND Circuits (4.3)

1. Convert all AND gates to NAND gates with AND-NOT graphic symbols.

2. Convert all OR gates to NAND gates with NOT-OR graphic symbols.

3. Check all the bubbles in the diagram.  For every bubble that is not counteracted by

another bubble along the same line, insert a NOT gate or complement the input literal

from its original appearance.

Example

• Use NAND gates and NOT gates to implement Z = E’F(AB+C’+D’)+GH

Problem. Implement the circuit with the truth table

Two-Level NAND Gate Implementation Example (4.2)

• _f(X,Y,Z) = Sm(0,6)

1. Express f in SOP form: f = X’Y’Z’ +XYZ’

2. Obtain the AND-OR implementation for f.

3. Add bubbles and inverters to transform AND-OR to NAND-NAND gates.

• Two-level implementation with NANDs

Two-Level NOR Gate

Implementation Example

• f(X,Y,Z) = ПM(0,6)   
• 1. Express f’ in SOP form:

1. f’ = Sm(1,2,3,4,5,7)= X’Y’Z + X’YZ’ + X’YZ + XY’Z’ + XY’Z + XYZ

2. f’ = XY’ + X’Y + Z

2. Take the complement of f’ to get f in the POS form: f = (f’)' = (X'+Y)(X+Y')Z'

3. Obtain the OR-AND implementation for f.

4. Add bubbles and inverters to transform OR-AND implementation to NOR-NOR implementation.

• Two-level implementation with NORs

AND-OR (SOP) Emulation with NANDs (4.1)

Gates (4)

Product of Sums Simplification (3.5)

·         Use sum-of-products simplification on the zeros of the function in the K-map to get f’.

·         Recall that the complement of a boolean function can be obtained by (1) taking the

dual and (2) complementing each literal. (aka generalized DeMorgan’s rule).

·         Complement f’ using DeMorgan’s Theorem to get f.

Example

·         Find a simplified product-of-sums expression for f(a,b,c,d) = M(0,1,7,15).

·         (f(a,b,c,d))’ =a’b’c’ + bcd

·         f_dual (a,b,c,d) = (a’+b’+c’)(b+c+d)

·         f(a,b,c,d) = (a+b+c)(b’+c’+d’)

Minimization with don’t cares (3.4)

•  Treat don't cares as if they are 1s to generate PIs.
• Delete PI's that cover only don't care minterms.
• Treat the covering of remaining don't care minterms as optional in the selection process (i.e. they may be, but need not be, covered).

Use of Don't Care Conditions (3.3)

There may be a combination of input values which:

·         will never occur

·         if they do occur, the output is of no concern.

·         The function value for such combinations is  called a don't care.

·         They are denoted with a d (or x, or –). Each d may be arbitrarily assigned the value 0 or

1 in an implementation.

Systematic Procedure for Simplifying Boolean Functions (3.2)

1. Generate all PIs of the function.

2. Include all essential PIs.

3. For remaining minterms not included in the essential PIs, select a set of other PIs (which have already been generated earlier) to cover them, with minimal overlap in the set.

4. The resulting simplified function is the logical OR of the product terms selected above.

Example

·         f(a,b,c,d) = m(0,1,2,3,4,5,7,14,15).

·          Five grouped terms, not all needed.

·         3 shaded cells covered by only one term

·         3 EPIs, since each shaded cell is covered by a different term.

·         F(a,b,c,d) = a’c’ + a’d + a’b’ + abc  (EPIs are indicated in bold)

PI  a’d must be added to EPIs (because it covers remaining 1 and is larger than other PI (bcd), which covers the same 1)

Essential Prime Implicant (3.1)

·         An essential prime implicant of a function is a prime implicant that contains at least one minterm not contained in any  other prime implicant.

·         To find essential prime implicants, we first generate all prime implicants of a function, and then select those prime implicants that contain at least one 1 that is not covered by any other prime implicant.

·         For the previous example, the PIs are d’, bc, and ab’c’; all of these are essential.

Example

·         Consider f2(a,b,c,d), whose K-map is shown at right.

·         The only essential PI is bd’.

Implicants and Prime Implicants (3)

·         An Implicant of a function is a product term of the function.

·         A product term is called an implicant, because whenever it takes the value 1, the function also takes the value 1, hence the term implies the function’s value.

·         A Prime Implicant of a function is an implicant of the function not contained (entirely!) in any “larger” implicant.

Example

·         Consider function f(a,b,c,d) whose K-map is shown below.  

·         c’d’ is not a prime implicant because c’d’ is contained in d’.

·         bcd is not a prime implicant because bcd is contained in bc.

·         d’, bc, and ab’c’ are prime implicants.

Four-variable Map Simplification (2.3)

• One square represents a minterm of 4 literals.
• A rectangle of 2 adjacent squares represents a product term of 3 literals.
• A rectangle of 4 squares represents a product term of 2 literals.
• A rectangle of 8 squares represents a product term of 1 literal.
• A rectangle of 16 squares produces a function that is equal to logic 1.

Example

·         Simplify the following Boolean function

g(A,B,C,D) = m(0,1,2,4,5,7,8,9,10,12,13).

First put the function g( ) into the map, and then group as many 1s as possible

·         g(A,B,C,D) = c’+b’d’+a’bd

Simplification 2.2

·         Enter minterms of the Boolean function into the map, then group terms

Here the term a’c is in the a=0 row  and in the 01 and 11columns (with a common 1 in the C position, note that the variable b is absent in this term and we have to present both values 0 and 1 for the variable b). The term bc’ is in the column 10 ( the variable a is absent and, therefore, is presented by 2 values 0 and 1in the rows a=0 and a=1) , the minterm abc is in the row a=1 and the column 11.

·         Top cells are  adjacent to bottom cells. Left-edge cells are adjacent to right edge  cells.

·         Note variable ordering.

Recipe for minimization as SOP, Three-Variable Map (2.1)

Recipe for minimization as SOP

• Enter 1s in the K-map for each product term in the function
• Group adjacent K-map cells containing 1s to obtain a product with fewer variables.
• Handle “boundary wrap” for K-maps of 3 or more variables.
• Realize that answer may not be unique

•Note variable ordering: (x,y,z), x is row, yz specify column.

•Each cell adjacent to four other cells (left/right edge wrap)

The types of structures that are either minterms or are generated by repeated application of the

minimization theorem on a three variable map are shown at right. Groups of 1, 2, 4, 8 are possible. An implicant of a function is a product term that can be used in a sum of products expression for that function, that is, the function is 1 whenever the implicant is 1 (and maybe other times, as well). From the point of view of the map, an implicant is a rectangle of 1, 2, 4, 8, . . . (any power of 2) 1’s. That rectangle may not include any 0’s.

Consider the function, F, of the following maps. The second map shows the first four groups of 2; the third map shows the other group of 2 and the group of 4.

Karnaugh Maps (2)

Another way to represent a logic function: a graphical representation. _ One map cell corresponds to a row in the  truth table.  One map cell corresponds to a minterm in the boolean expression; areas of map correspond to minterms, maxterm, product terms, etc

•Note ordering of variables, for f(x1,x2), x1 is the row, x2 is the column.

•Cell 0 represents x1’x2’; a 1 in that cell means that minterm is present in the function. (etc.)

 Any two adjacent cells in the map differ by only one variable, which is primed in one cell and unprimed in the other.

• Example:  f(x1,x2) = x1’x2’+ x1’x2 + x1x2’ = m0 + m1 + m2= x1’ + x2’

• Grouping (ORing) of 1s allows simplification
• What (simpler) function is represented by each dashed rectangle?

– x1’ = m0 + m1

– x2’ = m0 + m2

Note m0 covered twice

Exercise 1. (1.13)

• Prove with the aid of the laws of boolean algebra that f1(a,b,c)=f2(a,b,c), where f1(a,b,c)=a’bc+ab’c+ab’c’+a’bc’++abc’+abc and f2(a,bc)=a+b ;
• The following 2 problems refer to the table :

 (1)  Write F₁(x,y,z) as a sum of minterms.

 (2)  Write F₂(x,y,z) as a product of maxterms.       

(3) Convert the sum-of-products (SOP) from standard to canonical form:

      f1(a,b,c)=ab+c ;

      f2(a,b,c)=a+b’c+a’bc ;

(4) Convert the product-of sums (POS) from standard to canonical form:

      f3(a,b,c)=a(b+c’);

Shorthand, Conversion Between Canonical Forms, Standard Forms, Conversion of sum-of-productsfrom standard to canonical form, Conversion of product-of-sums from standard to canonical form (1.12)

Shorthand:  S and P

• f1(a,b,c) = Sm(1,2,4,6), where S indicates that this is a sum-of-products form, and m(1,2,4,6) indicates that the minterms to be included are m1, m2, m4, and m6.
• f1(a,b,c) = PM(0,3,5,7), where indicates that this is a product-of-sums form, and M(0,3,5,7) indicates that the maxterms to be included are M0, M3, M5, and M7.

Conversion Between Canonical Forms

• Replace S with P (or vice versa) and replace those js that appeared in the original form with those that do not.
• Example: f1(a,b,c) = a’b’c + a’bc’ + ab’c’ + abc’ = m1 + m2 + m4 + m6= S (1,2,4,6)=

        = P (0,3,5,7)= (a+b+c)•(a+b’+c’)•(a’+b+c’)•(a’+b’+c’)

Standard Forms

• Standard forms are like canonical forms except that not all variables need appear in the individual product (SOP) or sum (POS) terms.
• Example:f1(a,b,c) = a’b’c + bc’ + ac’ is a standard sum-of-products form
• f1(a,b,c) = (a+b+c)•(b’+c’)•(a’+c’) is a standard product-of-sums form.

Conversion of sum-of-productsfrom standard to canonical form

• Expand non-canonical terms by inserting  equivalent of 1 in each missing variable:

(x + x’) = 1

• Remove duplicate minterms
• f1(a,b,c) = a’b’c + bc’ + ac’= a’b’c + (a+a’)bc’ + a(b+b’)c’= a’b’c + abc’ + a’bc’ + abc’ + ab’c’= ab’c + abc’ + a’bc + ab’c’

Conversion of product-of-sums, from standard to canonical form

• Expand noncanonical terms by adding 0 in terms of missing variables: xx’ = 0
• Remove duplicate maxterms
• f1(a,b,c) = (a+b+c)•(b’+c’)•(a’+c’)= (a+b+c)•(aa’+b’+c’)•(a’+bb’+c’)

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

Maxterm and Minterm, Canonical Forms (1.11)

• Minterm: For n variables, the minterm is a product (•, AND) term that contains each variable exactly once, in complemented or uncomplemented form.
• In minterm mj, a variable is complemented if its value in the binary equivalent of j is 0.
•  Maxterm: For n variables, the maxterm is a sum (+, OR) term which contains each variable exactly once, in complemented or uncomplemented form.
• In maxterm Mj, a variable is complemented if its value in the binary equivalent of j is 1.
• Truth Table notation for minterms, maxterms

 Minterms and Maxterms are easy to denote using a truth table.

 Example (3 variables):

Canonical Forms

• Any Boolean function f( ) can be expressed as a  unique sum of minterms (except for commutativity).
• The minterms included are those m_j such that f( ) = 1 in row j of the truth table for f( ).
• Any Boolean function f( ) can be expressed as a unique product of maxterms (except for  commutativity).
• The maxterms included are those Mj such that  f( ) = 0 in row j of the truth table for f().

Example:  Truth table for f1(a,b,c):

• The canonical sum-of-products form for f1 is f1(a,b,c) = a’b’c + a’bc’ + ab’c’ + abc’
• The canonical product-of-sums form for f1 is f1(a,b,c)= (a+b+c)•(a+b’+c’)•(a’+b+c’)•(a’+b’+c’).

Canonical and Standard Forms (1.10)

• We are preparing to consider formal techniques for the simplification of Boolean functions.

Simplified functions in turn lead to “less expensive” logic circuits

Complement of a Function (1.9)

•  The complement of a function is obtained by interchanging AND and OR operations and complementing each variable and constant.
• Or change 1s to 0s and 0s to 1s in the truth table column containing F’s value.
• One should not confuse the complement of a function with the dual of a function.

Example:   Find G(x,y,z), the complement of  F(x,y,z) = x’yz’ + x’y’z

                                                                                                                                                     G = F’ = (x’yz’ + x’y’z)’= (x’yz’)’•(x’y’z)’= (x+y’+z)•(x+y+z’)

                           Find  H(x,y,z), the dual of F(x,y,z) = x’yz’ + x’y’z

                                                                                                                                                                                                                                                                                        H  = (x’+y+z’) (x’+y’+ z)

Algebraic Manipulation (1.8)

Algebraic Manipulation

• Boolean algebra is a useful tool for simplifying digital circuits.
• Why do it? Simpler is cheaper and smaller.
• Example: Simplify F= x’yz + x’yz’ + xz.

        F = x’yz + x’yz’ + xz   = x’y(z+z’) + xz = x’y•1 + xz = x’y + xz

•  Example: Prove x’y’z’ + x’yz’ + xyz’ = x’z’ + yz’

• Equal term has been added: if any term (equal to an already existing term) is being added, total value of the expression is not changed

  Proof:    x’y’z’+ x’yz’+ xyz’= x’y’z’ + x’yz’ + x’yz’ + xyz’= x’z’(y’+y) + yz’(x’+x)= x’z’•1 + yz’•1= x’z’ + yz’

                 QED

Commutativity, Distributive laws, Associativity, DeMorgan's laws, Absorption (Covering), Consensus, Clutching (1.7)

Commutativity

Commutativity: " x, y ÎÂ,

– x+y = y+x

– x•y = y•x

Distributive laws

Distributivity: " x, y, z ÎÂ

» x•(y+z) = x•y + x•z

» x + (y•z) = (x+y)•(x+z)

Provable via perfect induction

Associativity

·         (x+y) + z = x + (y+z)

·         (x•y)•z = x•(y•z)

DeMorgan's laws

·         THESE ARE IMPORTANT

·         (x+y)’ = x’•y’

·         (x•y)’ = x’+y’

Absorption (Covering)

·         x + x•y = x

·         x•(x+y) = x

·         Proof: x + x•y  = x•1 + x•y = x•(1+y) = x•(y + 1)= x•1 = x

QED  (second part true by duality)

Consensus

·         xy + x’z + yz = xy + x’z

·         (x+y)•(x’+z)•(y+z) = (x+y)•(x’+z)

·         Proof: xy + x’z + yz  = xy + x’z + (x+x’)yz = xy + x’z + xyz + x’yz= (xy + xyz) + (x’z + x’zy)  = xy + x’z                                 

      QED.

Clutching

• xy+xy’=x
• (x+y)(x+y’)=x

Involution (1.6)

·         (x’)’ = x

·         Proof: perfect induction again

 (0’)’ = (1)’ = 0

QED

Null elements (1.5)

•  x+1 = 1
• x•0 = 0
• Prove by perfect induction: consider all values of x and verify equality.

– 0+1 = 1, 1+1 = 1

– 0•0 = 0, 1•0 = 0 (complement)