摘要： 为进一步提高逻辑函数的化简速度，提出一种改进的Q-M逻辑函数化简方法。在迭代比较过程中设置2个权值以缩减可合并蕴涵项集合的大小，只对满足条件的蕴涵项进行合并处理，得到全部质蕴涵项。构造质蕴涵项与最小项关联图，利用启发式规则得到能蕴涵全部最小项的最少质蕴涵项集合，从而得到逻辑函数的最小覆盖，完成逻辑函数化简。实验结果表明，该算法能降低迭代次数，减少逻辑函数的化简时间。
关键词:
逻辑函数化简,
Q-M方法,
质蕴涵项,
二分图,
最小覆盖
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
中图分类号:
徐俊平, 程利新. 改进的Q-M逻辑函数化简方法[J]. 计算机工程, 2011, 37(20): 30-32.
XU Dun-Beng, CHENG Li-Xin. Improved Q-M Method for Simplification of Logic Functions[J]. Computer Engineering, 2011, 37(20): 30-32.