An Algorithm for Exact Extended Algebraic Division

Giuseppe CARUSO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.2   pp.462-471
Publication Date: 2003/02/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: VLSI Design Technology and CAD
multilevel logic synthesis,  division,  factorization,  

Full Text: PDF>>
Buy this Article

Methods usually employed for carrying out division in logic are based on algebraic or Boolean techniques. Algebraic division is fast but results may be less than optimal. Boolean division will yield better results but generally it is much slower because a minimization step is required. In [4], Kim and Dietmeyer proposed a new type of division, called extended algebraic division, and described a heuristic algorithm for it. A feature is that, unlike Boolean division, it does not require a minimization step. The present paper is concerned with an efficient algorithm for exact extended algebraic division. The algorithm was developed within the SIS environment, a program for logic synthesis developed at U.C. Berkeley. Experiments on factoring PLA's demonstrate a significant improvement in quality with a reasonable increase in run time.