Fast computation of the prime implicants by exact direct-cover algorithm based on the new partial ordering operation rule

被引：5

作者：

Basciftci, Fatih ^{[1
]}

Kahramanli, Sirzat ^{[2
]}

机构：

[1] Selcuk Univ, Dept Elect & Comp Educ, Tech Educ Fac, TR-42003 Selcuklu, Konya, Turkey

[2] Selcuk Univ, Dept Comp Engn, Engn & Architecture Fac, TR-42003 Selcuklu, Konya, Turkey

来源：

ADVANCES IN ENGINEERING SOFTWARE | 2011年 / 42卷 / 06期

关键词：

Two-level logic minimization; Logic operations; Direct-cover; Partial ordering operation; Prime implicants; Exact minimization algorithm; CUBE ALGEBRA; MINIMIZATION;

D O I：

10.1016/j.advengsoft.2011.02.009

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this study, a novel OFF-set based direct-cover Exact Minimization Algorithm (EMA) is proposed for single-output Boolean functions represented in a sum-of-products form. To obtain the complete set of prime implicants covering the given Target Minterm (ON-minterm), the proposed method uses OFF-cubes (OFF-minterms) expanded by this Target Minterm. The amount of temporary results produced by this method does not exceed the size of the OFF-set. In order to achieve the goal of this study, which is to make faster computations, logic operations were used instead of the standard operations. Expansion OFF-cubes, commutative absorption operations and intersection operations are realized by logic operations for fast computation. The proposed minimization method is tested on several classes of benchmarks and then compared with the ESPRESSO algorithm. The results show that the proposed algorithm obtains more accurate and faster results than ESPRESSO does. (C) 2011 Elsevier Ltd. All rights reserved.

引用

页码：316 / 321

页数：6

共 28 条

[1] A fault tolerant routing algorithm based on cube algebra for hypercube systems [J].

Allahverdi, NM ;

Kahramanli, SS ;

Erciyes, K .

JOURNAL OF SYSTEMS ARCHITECTURE, 2000, 46 (02) :201-205

[2] MULTILEVEL LOGIC MINIMIZATION USING IMPLICIT DONT CARES [J].

BARTLETT, KA ;

BRAYTON, RK ;

HACHTEL, GD ;

JACOBY, RM ;

MORRISON, CR ;

RUDELL, RL ;

SANGIOVANNIVINCENTELLI, A ;

WANG, AR .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1988, 7 (06) :723-740

[3]

Basciftci Fatih, 2007, EUROCON 2007. International Conference on "Computer as a Tool", P432, DOI 10.1109/EURCON.2007.4400396

[4]

Basciftci F., 2006, THESIS SELCUK U

[5]

Basciftci F., 2006, P INT C MOD SIM ASS, VII, P595

[6]

Bergamaschi RA, 1995, 1995 IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN, P272, DOI 10.1109/ICCAD.1995.480023

[7]

BRAYTON R, 1989, INT S CIRC SYST MAY, P738

[8]

Brayton R.K., 1984, Logic minimization algorithms for VLSI synthesis

[9] MCBOOLE - A NEW PROCEDURE FOR EXACT LOGIC MINIMIZATION [J].

DAGENAIS, MR ;

AGARWAL, VK ;

RUMIN, NC .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1986, 5 (01) :229-238

[10] Finding a fault tolerant routing on neighbour-faulty hypercube [J].

Dündar, P ;

Kiliç, E .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2004, 81 (09) :1043-1049

← 1 2 3 →