改进的Q_M逻辑函数化简方法_徐俊平.pdf

第37 卷 第20 期 计 算 机 工 程 2011 年10 月 Vol.37 No.20 Computer Engineering October 2011 ·软件技术与数据库· 文章编号：1000—3428(2011)20—0030—03 文献标识码：A 中图分类号：TP331.1 改进的Q-M 逻辑函数化简方法 徐俊平，程利新 (哈尔滨工程大学计算机科学与技术学院，哈尔滨 150001) 摘 要：为进一步提高逻辑函数的化简速度，提出一种改进的 Q-M 逻辑函数化简方法。在迭代比较过程中设置 2 个权值以缩减可合并蕴 涵项集合的大小，只对满足条件的蕴涵项进行合并处理，得到全部质蕴涵项。构造质蕴涵项与最小项关联图，利用启发式规则得到能蕴涵 全部最小项的最少质蕴涵项集合，从而得到逻辑函数的最小覆盖，完成逻辑函数化简。实验结果表明，该算法能降低迭代次数，减少逻辑 函数的化简时间。 关键词：逻辑函数化简；Q-M 方法；质蕴涵项；二分图；最小覆盖 Improved Q-M Method for Simplification of Logic Functions XU Jun-ping, CHENG Li-xin (College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China) 【Abstract 】In order to improve the simplification speed of logic functions, this paper proposes an improved Q-M method for simplification of logic functions. The size of implicants set is decreased by using a pair of weights in the iteration process of comparison, only the implicants which satisfy the conditions is merged. And all prime implicants are obtained at last. Bipartite graph which is consists of prime implications and minterms is structured. The least prime implicants containing all of the minterns, that is, the minimum coverage of logic functions is obtained by heuristic approach. Experimental results show that the number of iterations can be reduced, and the speed of simplification can be accelerated. 【Key words 】simplification of logic functions; Q-M method; prime implicants; bipartite graph; minimum coverage DOI: 10.3969/j.issn.1000-3428.2011.20.011 1 概述