Study Guides (238,073)
CSC258H1 (7)

# CH 2 - Circuits

3 Pages
154 Views

School
University of Toronto St. George
Department
Computer Science
Course
CSC258H1
Professor
Steve Engels
Semester
Winter

Description
CIRCUIT CREATION o Ex. m 2 output (Y1) only goes high in the third line of truth table A B C D m m Y Y  Making logic with gates 2 8 1 2 o Logic gates like the following allow us to create an output value, 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 based on two inputs 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 0 o What do we do in the case of more complex circuits, with several 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 inputs and more than one output? 1 0 0 0 0 1 0 1  Circuit example 1 0 0 1 0 0 0 0 o The circuit on the right has 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 tree inputs (A, B and C) 1 1 0 0 0 0 0 0 and two outputs (X and Y) 1 1 0 1 0 0 0 0 o What logic is needed to set 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 X high when all three o When OR two minterms (m +m ),2res8lt is output (Y2) that goes inputs are high? rd th o What logic is needed to set high in both minterm cases (3 and 9 row) o Two canonical forms of boolean expressions: Y high when the number of high inputs is odd?  Sum-of-Minterms (SOM)  Combinational Circuits o Small problmes can be solved easily  Since each minterm corresponds to a single high output in the truth table, the combined high outputs are a union of these minterms  Also known as: Sum-of-Products  Ex. Y = m 2 + m 6 + m 7 + m 10 A B C D m 2 m 6 m 7 m 10 Y 0 0 0 0 0 0 0 0 0 o Larger problems require a more systematic approach  Ex. Given three inputs A, B, and C, make output Y high in the 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 case where all of the inputs are low, or when A and B are low 0 0 1 1 0 0 0 0 0 and C is high, or when A and C are low but B is high, or when A 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 is low and B and C are high. 0 1 1 0 0 1 0 0 1  Creating logic 0 1 1 1 0 0 1 0 1 o Basic steps 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0  1. Create truth tables 1 0 1 0 0 0 0 1 1  2. Express as boolean expression 1 0 1 1 0 0 0 0 0  3. Convert to gates 1 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 o The key to an efficient design?  Spending extra time on Step 2 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0  Creating Boolean expressions o Terms to know:  Product-of-Maxterms (POM) ( )  Since each maxterm only produces a single low output  Minterm = an AND + expression with every input present in true or complemented form, i.e. each row of a truth table in the truth talbe, the combined low outputs are an  Set of values & the associated output intersection of these maxterm expressions  Also known as: Product-of-Sums  Maxterm = an OR ∙ expression with every input present in true or complemented form  Ex. Y = M 3 * M 5 * M 7 * M 10 * M 14 A B C D M M M M M Y  Ex. For 4 given inputs A, B, C and D 3 5 7 10 14 0 0 0 0 1 1 1 1 1 1  Valid minterms: 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 A ∙ B ∙ C ∙ D A ∙ B ∙ C ∙ D A ∙ B ∙ C ∙ D  Valid maxterms: 0 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 1 1 A + B + C + D A + B + C + D A + B + C + D 0 1 0 1 1 0 1 1 1 0  Nether min nor maxterms: 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 A ∙ B + C ∙ D A ∙ B ∙ D A + B 1 0 0 0 1 1 1 1 1 1 o A note about notation: 1 0 0 1 1 1 1 1 1 1  AND expressions are denoted by the muliplcation symbol 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1  Ex. A ∙ B ∙ C A ∗ B ∗ C A ∧ B ∧ C 1 1 0 0 1 1 1 1 1 1  OR expressions are denoted by the addition symbol 1 1 0 1 1 1 1 1 1 1  Ex. A + B + C A ∨ B ∨ C 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1  NOT is denoted by multiple symbols ′ o Sum-of-Minterms is a way of expressing which inputs cause the  Ex. ¬A A A output to go high.  XOR occurs rarely in circuit expressions  Assumes that the truth table columns list the input according  Ex. A⨁B to some logical or natural order o Given n inputs, there are 2 minterms and maxterms possible o Minterm and Maxterm expressions are used for efficiency reasons  Minterms are labled as m frox m (A*B*0) to m (A*B*C)7  More compact that display entire truth table  Maxterms are labled as M fromxM (A+B+0) to M (A+B+C) 7  Sum-of-minterms are useful in cases with very few input  X indicates the entry in the truth table combinations that produce very high output  Using Minterms and Maxterms  Sum-of-maxterms are useful when expressing truth tables that o A single minterm indicates a set of inputs that will make the output have very few low output cases go high  Coverting SOM to gates  Reducing Boolean expressions o Once you have a Sum-of-Minterms expression, it is easy to convert A B C Y this to the equivalent combination of gates 0 0 0 0 o Ex. 0
More Less

Related notes for CSC258H1

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.