A Novel Essential Prime Implicant Identification Method for Exact Direct Cover Logic Minimization.
Şirzat Kahramanlı, Süleyman Tosun · CDES · 2006
Abstract - Most of the direct-cover Boolean minimization techniques use a four step cyclic algorithm. First, the algorithm chooses an On-minterm; second, it generates the set of prime implicants that covers the chosen minterm; third, it identifies the essential prime implicant; and fourth, it performs a covering operation. In this study, we focus on the third step and propose a new essential prime implicant identification method. In this method, when the identification of the essential prime implicant is impossible, we postpone dealing with current On-minterm and save a status word for it. Eventually, we retrieve the status words whenever a new essential prime implicant is identified. We compared the proposed minimization method with ESPRESSO-EXACT. The results show that our method obtains exact results faster than other ones. Keywords: Logic minimization, prime implicant, branch and bound technique, cover. 1 Introduction Two-level logic minimization is a basic problem in logic synthesis [1]. Due to the exponential nature of this problem, state-of-the-art algorithms can typically handle functions with up to hundred products [2]. Therefore, most of the practical applications rely on heuristic minimization methods [2,3] with a complexity which is roughly quadratic in the number of products. There are also methods that produce the optimal (exact) solutions [1,2,3,4]. However, they can only be used for consistently small SOP realizations since they take long run time (CPU time) to find the final result. Heuristic algorithms are noticeably faster than the exact ones; however, they are still noticeably slow considering the exponential nature of the problem and they do not always obtain the optimal solutions [2]. Furthermore, the heuristic algorithms display diversity in realizations. That is, no single heuristic algorithm is consistently better than the others for all logic functions. There are classes of functions where one heuristic algorithm is better than the others [3]. Our studies show that the diversities in realizations of heuristic algorithms arise from the imperfect rules used for the identification of the essential prime implicant (EPI). In this study, we propose a new EPI identification method that obtains exact minimal solutions. Our minimization algorithm randomly chooses an On-minterm to be handled (named as target minterm (TM)) from the On-set of the function being minimized. It obtains the set of prime implicants that include TM. If this set consists of a single PI this our algorithm selects this PI as EPI to cover the On-set. If there is more than one PI then, to find the EPI, we apply a rule, which selects the PI that covers all On-minterms included by other PIs. If such a PI does not exist in the set then we form a status word (MSW) for the current TM and for the PIs that include this TM. We use MSWs to obtain a new EPI. This procedure is repeated until all of the On-minterms are covered. Our algorithm has the following differences than the existing ones. First, it is invariant to PIs generating method. Second, the minterm handling order can have a little effect on runtime, but it does not affect the final result. Third, it works in only one loop. Therefore, it is as fast as any heuristic one but generates only exact results. The rest of the paper is organized as follows: The next section lists the abbreviations and notations used in this paper. Section 3 discusses branch-and-bound technique based EPI identification rules and their problems. Section 4 presents our approach. Section 5 gives the experimental data. Finally, Section 6 concludes this paper.