Department

Computer ScienceCourse Code

CSC258H1Professor

Steve EngelsThis

**preview**shows half of the first page. to view the full**3 pages of the document.**CIRCUIT CREATION

Making logic with gates

o Logic gates like the following allow us to create an output value,

based on two inputs

o What do we do in the case of more complex circuits, with several

inputs and more than one output?

Circuit example

o The circuit on the right has

tree inputs (A, B and C)

and two outputs (X and Y)

o What logic is needed to set

X high when all three

inputs are high?

o What logic is needed to set

Y high when the number of high inputs is odd?

Combinational Circuits

o Small problmes can be solved easily

o Larger problems require a more systematic approach

Ex. Given three inputs A, B, and C, make output Y high in the

case where all of the inputs are low, or when A and B are low

and C is high, or when A and C are low but B is high, or when A

is low and B and C are high.

Creating logic

o Basic steps

1. Create truth tables

2. Express as boolean expression

3. Convert to gates

o The key to an efficient design?

Spending extra time on Step 2

Creating Boolean expressions

o Terms to know:

Minterm = an AND (+) expression with every input present in

true or complemented form, i.e. each row of a truth table

Set of values & the associated output

Maxterm = an OR (∙) expression with every input present in

true or complemented form

Ex. For 4 given inputs A, B, C and D

Valid minterms:

A ∙ B ∙ C ∙ D A ∙ B ∙ C ∙ D A ∙ B ∙ C ∙ D

Valid maxterms:

A + B + C + D A + B + C + D A + B + C + D

Nether min nor maxterms:

A ∙ B + C ∙ D A ∙ B ∙ D A + B

o A note about notation:

AND expressions are denoted by the muliplcation symbol

Ex. A ∙ B ∙ C A ∗ B ∗ C A ∧ B ∧ C

OR expressions are denoted by the addition symbol

Ex. A + B + C A ∨ B ∨ C

NOT is denoted by multiple symbols

Ex. ¬A A′ A

XOR occurs rarely in circuit expressions

Ex. A⨁B

o Given n inputs, there are 2n minterms and maxterms possible

Minterms are labled as mx from m0 (A*B*C) to m7 (A*B*C)

Maxterms are labled as Mx from M0 (A+B+C) to M7 (A+B+C)

X indicates the entry in the truth table

Using Minterms and Maxterms

o A single minterm indicates a set of inputs that will make the output

go high

o Ex. m2 output (Y1) only goes high in the third line of truth table

A

B

C

D

m2

m8

Y1

Y2

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

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

0

1

1

0

0

0

0

0

0

1

1

1

0

0

0

0

1

0

0

0

0

1

0

1

1

0

0

1

0

0

0

0

1

0

1

0

0

0

0

0

1

0

1

1

0

0

0

0

1

1

0

0

0

0

0

0

1

1

0

1

0

0

0

0

1

1

1

0

0

0

0

0

1

1

1

1

0

0

0

0

o When OR two minterms (m2+m8), result is output (Y2) that goes

high in both minterm cases (3rd and 9th row)

o Two canonical forms of boolean expressions:

Sum-of-Minterms (SOM)

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 = m2 + m6 + m7 + m10

A

B

C

D

m2

m6

m7

m10

Y

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

1

0

1

0

0

0

1

0

0

1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

1

1

0

0

1

0

0

1

0

1

1

1

0

0

1

0

1

1

0

0

0

0

0

0

0

0

1

0

0

1

0

0

0

0

0

1

0

1

0

0

0

0

1

1

1

0

1

1

0

0

0

0

0

1

1

0

0

0

0

0

0

0

1

1

0

1

0

0

0

0

0

1

1

1

0

0

0

0

0

0

1

1

1

1

0

0

0

0

0

Product-of-Maxterms (POM)

Since each maxterm only produces a single low output

in the truth talbe, the combined low outputs are an

intersection of these maxterm expressions

Also known as: Product-of-Sums

Ex. Y = M3 * M5 * M7 * M10 * M14

A

B

C

D

M3

M5

M7

M10

M14

Y

0

0

0

0

1

1

1

1

1

1

0

0

0

1

1

1

1

1

1

1

0

0

1

0

1

1

1

1

1

1

0

0

1

1

0

1

1

1

1

0

0

1

0

0

1

1

1

1

1

1

0

1

0

1

1

0

1

1

1

0

0

1

1

0

1

1

1

1

1

1

0

1

1

1

1

1

0

1

1

0

1

0

0

0

1

1

1

1

1

1

1

0

0

1

1

1

1

1

1

1

1

0

1

0

1

1

1

0

1

0

1

0

1

1

1

1

1

1

1

1

1

1

0

0

1

1

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

1

1

0

1

1

1

1

0

0

1

1

1

1

1

1

1

1

1

1

o Sum-of-Minterms is a way of expressing which inputs cause the

output to go high.

Assumes that the truth table columns list the input according

to some logical or natural order

o Minterm and Maxterm expressions are used for efficiency reasons

More compact that display entire truth table

Sum-of-minterms are useful in cases with very few input

combinations that produce very high output

Sum-of-maxterms are useful when expressing truth tables that

have very few low output cases

###### You're Reading a Preview

Unlock to view full version