EE382m — Logic SynthesisMidterm 1October 17, 2001Name:11. Boolean functions(a) 6 marksIsan essential prime of   ?(b) 8 marksA functionis a threshold function if there exists a set of real numbers   (weights) and a number(threshold) such that !"$#&%if and only if'(*)( (,+.Show each threshold function is unate (positive or negative) in all its variables.Is every unate function a threshold function? (Hint: consider-/.10!2.)22. Unate covering(a) 4 marksWe can generalize the unate covering problem by associating a weight (a nonnegativereal number) to each column.The problem then is to find a collection of columns which cover each row, and hasminimum cost (where the cost of a set of columns is the sum of the weights of thecolumns).How would you generalize the concepts of (1.) essential prime, (2.) row dominance,and (3.) column dominance for this problem?3(b) 8 marks Describe how you would formulate the following problem as a unate coveringproblem with weights on the columns:Given a set of distinct positiveintegers3#54-6--87, find a least weight1subset9#&4:26;2/!<2"=>7having the property that for every-(,?3, there is a2:@?9suchthat-(ACBED2F@G#IH(i.e., there is a number in9which evenly divides-().Apply your approach to the set4/%JH%JK6LE;K%FME%FNE6MOH87.Looking at the structure of the matrix, can you suggest of a more direct (and quicker)way of solving this problem? (Hint — keeping the numbers in sorted order when youbuild the matrix will make it easier to see the pattern.)1The weight of a set of positive integers is the sum of the elements, i.e., the weight ofP<QJRTSFRVU:WisX.43. Heuristic 2-level minimization(a) 4 marks Give a (brief) explanation of why in ESPRESSO we need a reduce step, inaddition to irredundant and expand.(b) 8 marks Illustrate the use of the unate recursive paradigm to complement-ZY-2/0-/.2.54. BDDs(a) 10 marksDraw BDDs for the following functions under the variable ordering-\[].[0[2.F = a b + c;G = b’ + c’;E = c’ d’;Compute iteV^;_C<`a, using the algorithm presented in class. Show all steps; give thecontents of the ITE cache at each step (assume it starts empty). Draw the final BDD.6(b) 9 marksHere is part of a BDD-based procedure for solving the unate covering problem:Use a variable for each column, and create a logic function on these variables whichevaluates to one on an input when the set of columns corresponding to the positionswhich are set to one in the input covers each row of the matrix.bHow would you obtain the BDD for this function?bHow would you use this BDD to find a minimum column cover?75. Multilevel logic(a) 8 marksGive a convincing argument that there is no smaller factored form representing thefunction given by the factored formc-d!.eV-d.. (Hint — argue that there are nofactored forms for this function with 0, 1, 2, or 3 literals.)8(b) 10 marksCompute all kernels of the algebraic expressions^and_given below. Extract amulticube algebraic divisor common to both.F = a*c + b’*c + a*d’ + b’*d’ + a*e + b’*eG = a*c + a*d’ + b’*c + b’*d’ + c*e +