用于二级优化的有限搜索算法  

SEARCHING LIMITED ALGORITHM (SLA) FOR TWO LEVEL LOGIC MINIMIZATION

作　　者：张巨泉[1] 朱立新[1] 孙适[2] 

机构地区：[1]解放军电子工程学院,合肥230037 [2]中国科学技术大学计算机系,合肥230026

出　　处：《计算机学报》1991年第11期871-875,共5页Chinese Journal of Computers

摘　　要：在计算机辅助逻辑设计理论中,最小项(零多维体)的相邻度是一个基本且十分有用的概念,一系列重要的二级优化算法都是以最小项相邻度概念为基础的.本文把最小项相邻度的概念推广到任意维多维体,定义了多维体方向集概念.并利用方向集概念成功地提出了优于张弛算法的二级优化算法:有限搜索法,即有限搜索法在造价优于张弛法的前提下,求取质蕴涵项的速度比张弛法快一到几个数量级,且有限搜索法扩展了张弛法的适用范围,可以综合输入变量大于20的布尔函数.The concept of adjacency degree of zero degree cube is adapted to highdegree cube, and a new concept 'Direction set' for high degree cube is defined. The concept is used to successfully put forth a new two level logic minimization algorithm-SLA. which is better than the Relaxation algorithm, e.g., when the cost of result of our algorithm is cheaper than that of Relaxation, the speed of finding the largest implicant covering a cube of cur algorithm is ten to thousand times faster than that of Relaration. SLA can be used for synthesis of high input variables (n>20) Boolean functions.

关 键 词：计算机 二级优化 逻辑设计 算法 

分 类 号：TP302.2[自动化与计算机技术—计算机系统结构]