1> Karnaugh Map: Express the following function in a ...

1> Karnaugh Map: Express the following function in a minimal sum ofproducts form.

f(a,b,c,d) = sum m(1,2,4,5,8,14) + sum d(6,10,13).

Solution:

First we have to fill in the K-map:

00

01

11

10

0

1

0

1

1

1

0

-

0

-

0

1

1

0

0

-

Then we have to pick the 1 terms, forming the prime implicants. Note that don't cares can be treated to be 0 or 1.

f(a,b,c,d) = cd' + a'c'd + a'bc' + ab'd'

2> Karnaugh Map: Express the following function in a minimal product of sums form.

f(a,b,c,d) = sum m(1,2,4,5,8,14) + sum d(6,10,13).

Solution:

First we have to fill in the K-map:

00

01

11

10

0

1

0

1

1

1

0

-

0

-

0

1

1

0

0

-

Then we have to pick the 0 terms, forming the prime implicates. Note that don treated to be 0 or 1.

f(a,b,c,d) = (c' + d')(a' + d')(a' + b' + c)(a + b + c + d)

3> Karnaugh Map: Implement the following function with a minimal two level NOR network.

f(a,b,c,d) = sum m(0,4,5,9,11,14,15) + sum d(2,8).

Solution:

First we have to fill in the K-map:

00

01

11

10

1

0

0

-

1

1

0

0

0

0

1

1

-

1

1

0

Then we have to pick the 0 terms, forming the prime implicates. Note that don treated to be 0 or 1. The reason why we want to come up with the product of sums form is that we are asked to implement the function using two level NOR network.

f(a,b,c,d) = (a + c')(a + b + d')(a' + b' + c)(a' + b + d)

Now let's say y1 = a + c' y2 = a + b + d' y3 = a' + b' + c y4 = a' + b + d Then f(a,b,c,d) = y1.y2.y3.y4 Taking the complement of both sides of the equation, we get:

f ' = y1' + y2' + y3' + y4' So,

f = ( f ` )' = ( y1' + y2' + y3' + y4' ) ` = NOR(y1',y2',y3',y4'). Since

y1' = (a + c')' = NOR(a,c') y2' = (a + b + d')' = NOR(a,b,d') y3' = (a' + b' + c)' = NOR(a',b',c) y4' = (a' + b + d)' = NOR(a',b,d), we finally have:

f = NOR(NOR(a,c'), NOR(a,b,d'), NOR(a',b',c), NOR(a',b,d))

4> Quine-McClusky Method: Find the minimum sum of products expression of the following function using Quine-McClusky method. Show your process of deriving the prime implicants and include the implicant chart.

F(a,b,c,d,e) = sum m(0,1,2,9,15,19,23,25,30) + sum d(4,5,28,31)

Solution:

Step 1 ? Finding Prime Implicants: The first step is to list all elements of the on-set and don't-care set in terms of their minterm indices, represented as binary number. The elements are grouped according to the number of 1's in the binary representation. This is accomplished through the implication table as follows:

Column I 00000

00001 00010 00100

00101 01001

10011 11001 11100

Column II 0000000-0 * 00-00

00-01 0-001 * 0010-

-1001 *

10-11 * 111-0 *

Column III 00-0- *

01111 10111 11110

-1111 * 1-111 * 1111- *

11111

From the above table, Prime implicants are 000-0, 0-001, -1001, 10-11, 111-0, -1111, 1-111, 1111-

Step 2 ? Finding The Minimum Cover: The second step of the method is to find the smallest collection of prime implicants that cover the complete on-set of the function. This is accomplished through the prime implicant chart as follows:

000-0 0-001 -1001 10-11 111-0 -1111 1-111 111100-0-

0 1 2 9 15 19 23 25 30

X

X

X

X

X

X

XX

X

X

X

X

XX

From the above chart, the essential prime implicants are 000-0, -1111, 10-11, -1001 and two minterms are still uncovered, represented by the column 1 and 30. To cover these remaining minterms, we can choose prime implicants as 00-0-(or 0-001) and 111-0(or 1111-). Therefore, the final answer is as follows:

F(a,b,c,d,e) = a'b'c'e'+ bc'd'e + ab'de + bcde + a'b'd' + abcd

5> Quine-McClusky Method: Find the minimum sum of products expression of the following function using Quine-McClusky method. Show your process of deriving the prime implicants and include the implicant chart.

F(a,b,c,d) = sum m(0,1,4,5,6,7,9,11,15) + sum d(10,14)

Solution:

Step 1 ? Finding Prime Implicants: The first step is to list all elements of the on-set and don't-care set in terms of their minterm indices, represented as binary number. The elements are grouped according to the number of 1's in the binary representation. This is accomplished through the implication table as follows:

Column I 0000

0001 0100

0101 0110 1001 1010

0111 1011 1110

Column II 0000-00

0-01 01001-0 -001 *

01-1 01110-1 * 1-10

-111 *

Column III 0-0- *

01-- *

1-1- * -11- *

1111

1-11

111-

From the above table, Prime implicants are ?001, 10-1, -111, 0-0-, 01--, 1-1-, -11-

Step 2 ? Finding The Minimum Cover: The second step of the method is to find the smallest collection of prime implicants that cover the complete on-set of the function. This is accomplished through the prime implicant chart as follows:

0 1 4 5 6 7 9 11 15

0-0-

XXXX

01--

XXXX

1-1-

XX

-11-

XX

X

-001

X

X

10-1

XX

-111

X

X

From the above chart, the essential prime implicant is only 0-0- and five minterms are still uncovered, represented by the column 6,7,9,11,15. To cover these remaining minterms, we can choose prime implicants as ?11- and 10-1. Therefore, the final answer is as follows:

F(a,b,c,d,e) = a'c'+ bc + ab'd

6> Given a four input Boolean function

f(a,b,c,d)= sum m(0,1,2,9,13,15)+ sum d (4,5,11).

Implement the function using a minimal network of AND, OR, NOT gates.

Solution:

We have to imlement the function using sum of products and product of sums forms and after that we have to choose the cheaper implementation.

First we have to fill in the K-map:

00

01

11

10

1

1

0

1

-

-

0

0

0

1

1

0

0

1

-

0

First let's implement the sum of products form, picking 1 entries:

f(a,b,c,d) = c'd + a'c' + ad + a'b'd'

For this implementation, we need 4 inverter, 4 AND and 1 OR gates.

Now, let's implement the same function using product of sums form:

f(a,b,c,d) = (a + b')(a' + d)(a + c' + d')

For this implementation, we need 4 inverter, 3 OR and 1 AND gates.

Obviously, the second implementation is cheaper since it uses 8 gates instead of 9.

7> Write the characteristic equations and excitation tables of four types of flip-flops.

Solution:

SR flip-flop

Q (current

state) 0 0 1 1

Q+ (next state)

0 1 0 1

S

R

0

-

1

0

0

1

-

0

The characteristic equation is:

Q+ = S + R'Q

JK flip-flop

Q (current

state) 0 0 1 1

Q+ (next state)

0 1 0 1

S

R

0

-

1

-

-

1

-

0

The characteristic equation is:

Q+ = JQ' + K'Q

D flip-flop

Q

Q+

D

(current (next

state)

state)

0

0

0

0

1

1

1

0

0

1

1

1

The characteristic equation is:

Q+ = D

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download