Reference no: EM132156590
1. Prob. 3.58 (from the text) with the change that for 3.58(a) the least-cost set of PIs to cover all minterms should be determined using Petrick's algorithm and not the PI table part of QM and for (b) QM+ needs to be used; the set of all PIs are, however, to be determined using the first stage of the QM method.
2. Determine a min-cost SOP expression f and its cost for the PIT given below using: (a) QM+; (b) Petrick's algorithm. Comment on the difference in cost, if any, using the two difference algorithms, and determine where the cost difference arises from (in other words, what makes QM+ non-optimal for this problem-note that Petrick's algorithm is optimal).
3. In the above problem, use the following extended QM+ technique to obtain a better solution (this technique will apply in general to PITs/RPITs that are either cyclic or have no good row coverings):
(a) Form all PI pairs and check if there are good covers between them and also from single PIs to PI pairs. If so, apply the good row covering rule (exclusion delete [ED] the good-covered PI pairs), and check if any PI-pair has become a pseudo-EPI pair by ignoring the check marks of the single PI rows (since we are unable to select a single PI, it is correct to ignore such check marks).
(b) If pseudo-EPI pair(s) have come forth, inclusion delete (ID) them, delete the MTs/cols they cover as well as the single PIs that constitute the pseudo-EPI PI pair(s) (the single PI deletions are essentially IDs, but the inclusion of these PIs have already been done when the pseudo-EPI PI pair(s) were included in the SOP expression, and thus obviously do not need to be repeated). After this, go back to a PIT with the remaining single PIs and MTs, and repeat the process.
(c) (c) If no pseudo-EPI pair(s) have been identified, then we essentially have a cyclic PIT among PI pairs. In this case, form a limited number of PI triples by extending those from the remaining
PI pairs (some may have been EDed via good covering), to which a single PI can be added to form triples that cover the most number of MTs (among these extended triples). Then proceed among triples as you did for pairs: see if there are good coverings among such triples, and if any become pseudo-EPI-triples (only looking at the triples part of the PIT), etc.
4. (a) One of the sources of sub-optimality of QM is the use of heuristics to choose a PI to break a cyclic PIT or RPIT. Devise a simple method that is optimal in the case of a cyclic PIT or RPIT (state the method clearly in words; a pseudo-code of the type given for QM in the notes is not needed, though you can give one if you think it will be more explanatory).
Hint: Determine a subset of PIs in a cyclic PIT/RPIT, at least one of which needs to be in the final solution (note that this does not mean that the others will not be in the final solution)-this is similar to the idea in Petrick's, though this is not about devising a Petrick's-like technique but about devising a QM+-like technique using this Petrick's-type idea. Using such a subset of PIs, explore different ways for breaking the cyclic PIT; by definition, at least one of these will give an optimal solution.
(b) In a 2-level logic minimization problem in which a cyclic PIT or RPIT is encountered only once, what will be the time-complexity of your method in θnotation (discussed in the notes).
Attachment:- SOP expression.rar