CS计算机代考程序代写 CS 2204: Digital Circuits

CS 2204: Digital Circuits

Lecture 6

Minimization using k-maps
Consider the truth table:

1
1
0
1

Can we speed this up?

K = “Karnaugh”

k-map
First re-arrange your truth table as 2-d “map”

1
1
0
1

1

1 1

0

k-map

1

1 1

0

More examples

1 1

0 0

1 0

0 1

0 0

0 1

3-variable k-maps

Combination rules

1

11

1

1

1

11

1

4-variable k-map

Cubes of size 2, 4, and 8
are possible. Any cube can
be expressed as the product
of the variables that are
common across all the
minterms in the cube

Example 1

1

11

1

1 1

Example 2

1

1

1 1 1

1 1

1 1 1

Example 3

1

1 1 1

1 1

1 1

Example 4

1

1 1 1

1 1

1

1

1

1

From sop to pos
We can also write f in “product-of-sum”
form as follows

Each entry of a
truth-table is also
associated with a
“max-term.” E.g.

A Boolean function f can
be written as the
“product” of maxterms
over rows for which f=0

Example pos form

Example pos form

Implementation using and/or gates

Implementation using NAND and NOR GATES
On real silicon chips we can only implement NAND (NOT-AND)
and NOR (NOT-OR) gates, along with NOT gates. We would
implement AND gates using NAND followed by NOT. Likewise, we
would implement OR gates using NOR followed by NOT.

Transitioning between gates

FRom and-or to NAND-NOR Boolean logic netlists

Another example (with POS form)

Not gates can be designing using Nands or Nors

exercise
Implement using ONLY NOR gates