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

View Questions Only
View Questions with Solutions

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'

Strategy

Method1:

  1. Expand the standard form into a canonical form first.
  2. Convert the canonical form into a map by inserting a '1' for each minterm in the form.

Method2:

  1. directly convert a standard form by inserting(n-m) 1's into each (n-m)-subcub in the map for each m-literal term in the standard form.

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'

Strategy

  1. Inspect each 1-minterm in question one by one.
  2. Find all the largest possible subcubes of 1-minterms that includes this minterm in question.
  3. If those subcubes are not in the list of prime implicants, add them to the list of prime implicants.

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'

Strategy

  1. Map Generation(4.2)
  2. Prime Implicant Generation(4.4)
  3. Essential Implicant selection
  4. Create minimal cover. Find the prime implicant that contains the geratest number of not-coverd 1-minterms.Move it from the prime implicant list to the cover list. If we happen to have two prime implicants that both include the same number of not-covered minterms, one is chosen randomly. This procedure is then repeated until all the minterms have been coverd.

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

Strategy

  1. Use AND and OR(same number of input) and NOT gates to represent the function.
  2. Change AND and OR and NOT to NAND gates.

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))

Strategy

  1. Table 3.16 is more powerful than Table 3.15, Table 3.15 is more powerful than Table 3.14. Therefore, Try to use the gates in Table3.16 first , then 3.15, 3.14.
  2. Try to find some different solutions and chose the best one as the result.

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.

Strategy

  1. Try to find the optimized decomposition using AND , OR, and NOT.
  2. Change it to the possible gates in the custom library.