Department

Computer ScienceCourse Code

CSC258H1Professor

Steve EngelsThis

**preview**shows half of the first page. to view the full**1 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:

Valid maxterms:

Nether min nor maxterms:

o A note about notation:

AND expressions are denoted by the muliplcation symbol

Ex.

OR expressions are denoted by the addition symbol

Ex.

NOT is denoted by multiple symbols

Ex.

XOR occurs rarely in circuit expressions

Ex.

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