基于二进制区分矩阵的约简算法研究  

A Reduction Algorithm Based on Binary Discernibility Matrix

作　　者：杨帆[1] 朱新坚[1] 曹广益[1] 

机构地区：[1]上海交通大学电子信息与电气工程学院自动化系,上海200240

出　　处：《计算机仿真》2007年第2期79-83,140,共6页Computer Simulation

摘　　要：给出了一种基于二进制区分矩阵的约简方法。首先基于粗糙集理论定义了二进制区分矩阵及运算规则、基于二进制区分矩阵的最小约简的判别及属性重要性的计算方法。在定义的基础上,给出了基于二进制区分矩阵的求核算法、相对属性约简算法及值约简算法。该约简方法以位操作为主与传统的约简方法比较不包括复杂的逻辑化简和集合运算,在一定程度上简化了计算,提高了约简效率。将该算法应用于数字电路设计的开关电路综合中,得到最简数字电路的逻辑表达,从而说明了算法的有效性。A novel reduction method based on the binary discernibility matrix is presented. In this reduction method, binary discernibility matrix and its operation rules are defined based on rough set. Minimal reduction discrimination and calculation method about attribute significance of binary discernibility matrix are redefined. Based on the definitions, the core finding algorithm, the relative attribute reduction algorithm and value reduction of information decision system are presented based on binary discernibility matrix. The proposed algorithms of binary discernibility matrix rely mainly on bit operation without complicated logic minimization and set operation. Therefore, compared to traditional reduction model, the novel calculation is simplified and reduction efficiency is improved. This method has been applied to switch circuit integration of digital circuit design and got the logic expression of briefest digital circuit, which can prove the validity of the algorithm .

关 键 词：粗糙集 二进制区分矩阵 约简 

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