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.
- F = w'x' + xy +wy' +wx
- F = x1'x0'+x1'y0+y1y0+x1'y1+x0'y1
- F = w'z' +wz+w'y+yz
- F = w'x'z'+w'xy+wxz+wx'y+w'yz'
Strategy
Method1:
- Expand the standard form into a canonical form first.
- Convert the canonical form into a map by inserting a '1' for each minterm in the form.
Method2:
- 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.
- F = x1'x0'+y1y0+x1'x0y1'y0+x1'x0y1y0'+x1x0'y1y0'
- F = w'x'+w'xy+wx'y'+wx
- F = w'y'z'+xy'z+wyz+x'yz'
- F = w'y+w'x'z+xyz'+wx'y'+wy'z'
Strategy
- Inspect each 1-minterm in question one by one.
- Find all the largest possible subcubes of 1-minterms that includes this minterm in question.
- 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.
- F = w'x'+w'xy+wx+wx'y'+xy
- F = yz+w'z'+wy'z
- F = x'y'z'+wy'z+xyz+w'yz'
- F = wy'z'+wx'y'+w'y+w'x'y'z+wxyz'
Strategy
- Map Generation(4.2)
- Prime Implicant Generation(4.4)
- Essential Implicant selection
- 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
- 2-input NAND gates
- 3-input NAND gates
- 4-input NAND gates
Strategy
- Use AND and OR(same number of input) and NOT gates to represent the function.
- 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.
- F = y1'(y0'+x0+x1)+x1(x0+y0')
- F = w'(x'z'+xy) +w(xz+x'y')
- F = w'x'z+w'xy+wxz+wx'y'
- F = wx'y'+y(w'z'+x(z+w))
Strategy
- 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.
- 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:
- The custom library defined by Table 3.14.
- The custom library defined by Tables 3.14 and 3.15.
- The custom library defined by Tables 3.14, 3.15, 3.16.
Strategy
- Try to find the optimized decomposition using AND , OR, and NOT.
- Change it to the possible gates in the custom library.