基于分层超立方体的精确ESOP最小化  

Exact Minimization of ESOP Expressions Based on Hierarchical Hypercube

作　　者：张巧文[1,2] 汪鹏君[1] 胡江[1] 

机构地区：[1]宁波大学电路与系统研究所,宁波315211 [2]浙江万里学院宁波市DSP重点实验室,宁波315100

出　　处：《计算机辅助设计与图形学学报》2016年第1期172-179,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：浙江省自然科学基金(LY14F040002);国家自然科学基金(61274132;61234002);宁波市自然科学基金(2013A610006;2013A610008;2013A610010);宁波市科技创新团队(2013B82009)

摘　　要：针对大变量逻辑函数的ESOP最小化求解问题,提出一种面向任意完全规定逻辑函数的精确ESOP最小化方法.该方法引入逻辑函数的n维分层超立方体表示模型,采用立方体几何图形映射Exorlink操作,实现一种立方体EXOR转换图的精确最小化转换;使用立方体集合划分与变量置换完成逻辑函数的分层超立方体结构映射以减少函数覆盖;在此基础上,给出基于分层超立方体的ESOP精确最小化算法.在MCNC基准电路上的实验结果表明,与其他ESOP最小化方法相比,文中方法可在多项式计算时间内实现大变量逻辑函数的ESOP最小化.To cope with the problem of minimization of exclusive-or sum-of-products(ESOP) expressions for large logic functions, a minimization method is proposed that finds an exact ESOP expression for an arbitrary completely specified function. The n-dimensional hierarchical hypercube(HHC) model is presented to represent logic functions, and a cube EXOR-based transformation diagram is introduced to obtain exact solutions, based on cube geometrical mapping of Exorlink operation. The method also uses a reduced covering function by mapping logic function into HHC model after cube grouping and variable permutation. Then an exact ESOP minimization algorithm based on HHC is obtained. Experimental results on MCNC benchmark circuits show that, in comparison with existing algorithms, the proposed method can be used to find a minimum ESOP expression of a given n-variable function in polynomial time.

关 键 词：逻辑综合 Reed-Muller展开 分层超立方体 ESOP最小化 

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