Study Guides
(238,073)

Canada
(114,907)

University of Toronto St. George
(7,975)

Computer Science
(179)

CSC258H1
(7)

Steve Engels
(5)

# CH 2 - Circuits

Unlock Document

University of Toronto St. George

Computer Science

CSC258H1

Steve Engels

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