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

Gate-Array Mapping Problem 4 Figure

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. Technology mapping Figure A
  2. Technology mapping Figure B
  3. Technology mapping Figure C
  4. Technology mapping Figure D

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

Technology mapping Problem 6 Figure