EECS 31/CSE 31/ICS 151 Homework 3 Questions with Solutions

View Questions Only
View Questions with Strategies

Problem 1

Question

(Map representation) Generate the map representations for the following Boolean functions.

1. F = w'x' + xy +wy' +wx
2. F = x1'x0'+x1'y0+y1y0+x1'y1+x0'y1
3. F = w'z' +wz+w'y+yz
4. F = w'x'z'+w'xy+wxz+wx'y+w'yz'

Solution

1. w\xy	00	01	11	10
   0	1	1	1	0
   1	1	0	1	1

2. X0X1\Y0Y1	00	01	11	10
   00	1	1	1	1
   01	0	1	1	0
   11	0	0	1	0
   10	0	1	1	1

3. w\yz	00	01	11	10
   0	1	0	1	1
   1	0	1	1	0

4. wx\yz	00	01	11	10
   00	1	0	0	1
   01	0	0	1	1
   11	0	1	1	0
   10	0	0	1	1

Problem 2

Question

(Map method) Using the map method, determine the prime implicants of the following Boolean functions.

1. F = x1'x0'+y1y0+x1'x0y1'y0+x1'x0y1y0'+x1x0'y1y0'
2. F = w'x'+w'xy+wx'y'+wx
3. F = w'y'z'+xy'z+wyz+x'yz'
4. F = w'y+w'x'z+xyz'+wx'y'+wy'z'

Solution

1. X0X1\Y0Y1	00	01	11	10
   00	1	1	1	1
   01	0	1	1	0
   11	0	0	1	0
   10	0	1	1	1

   PI list: :x0'x1', y0y1, x0'y1, x1'y1, x1'y0

2. w\xy	00	01	11	10
   0	1	1	1	0
   1	1	0	1	1

   PI list: w'x', x'y', w'y, xy, wy', wx

3. wx\yz	00	01	11	10
   00	1	0	0	1
   01	1	1	0	0
   11	0	1	1	0
   10	0	0	1	1

   PI list: w'y'z', w'xy', xy'z, wxz, wyz, wx'y, x'yz', w'x'z'

4. wx\yz	00	01	11	10
   00	0	1	1	1
   01	0	0	1	1
   11	1	0	0	1
   10	1	1	0	0

   PI List :w'y, w'x'z, xyz', x'y'z, wy'z', wx'y'

Problem 3

Question

(Map method) Find all the minimal covers for the following Boolean functions.

1. F = w'x'+w'xy+wx+wx'y'+xy
2. F = yz+w'z'+wy'z
3. F = x'y'z'+wy'z+xyz+w'yz'
4. F = wy'z'+wx'y'+w'y+w'x'y'z+wxyz'

Solution

1. y\wx	00	01	11	10
   0	1	0	1	1
   1	1	1	1	0

   Minimal covers:
   F=xw+x'y'+w'y
   F=xy+x'w'+wy'

2. w\yz	00	01	11	10
   0	1	0	1	1
   1	0	1	1	0

   Minimal covers:
   F=w'z'+yz+wz
   F=w'z'+yw'+wz

3. wx\yz	00	01	11	10
   00	1	0	0	1
   01	0	0	1	1
   11	0	1	1	0
   10	1	1	0	0

   Minimal covers:
   F=w'x'z'+w'xy+wxz+wx'y'
   F=x'y'z'+wy'z+xyz+w'yz'

4. wx\yz	00	01	11	10
   00	0	1	1	1
   01	0	0	1	1
   11	1	0	0	1
   01	1	1	0	0

   Minimal covers:
   F=w'y+w'x'z+wxz'+wx'y'
   F=w'y+x'y'z+xyz'+wy'z'
   F=w'y+x'y'z+wxz'+wy'z'
   F=w'y+x'y'z+wxz'+wx'y'

Problem 4

Question

(Gate-array mapping) Convert the function wx'y'+yw'z'+yxz+yxw into

1. 2-input NAND gates
2. 3-input NAND gates
3. 4-input NAND gates

Solution

Problem 5

Question

(Technology mapping) Using the library defined by Tables 3.14, 3.15 and 3.16, perform technology mapping and minimize the delay for the following Boolean functions.

1. F = y1'(y0'+x0+x1)+x1(x0+y0')
2. F = w'(x'z'+xy) +w(xz+x'y')
3. F = w'x'z+w'xy+wxz+wx'y'
4. F = wx'y'+y(w'z'+x(z+w))

Solution

1. 
2. 
3. 
4. 

Problem 6

Question

(Technology mapping) Derive a minimum-delay implementation for the carry-look-ahead function c4 = g3+p3g2+p3p2g1+p3p2p1g0+p3p2p1p0c0 that use:

1. The custom library defined by Table 3.14.
2. The custom library defined by Tables 3.14 and 3.15.
3. The custom library defined by Tables 3.14, 3.15, 3.16.

Solution