化简开关函数的图论方法
GRAPH THEORY METHODS FOR SIMPLIFICATION OF SWITCHING FUNCTIONS
-
摘要: 本文引入了n变量开关函数F(x1,,xn)的伴随图G和伴随超图H的概念,导出了下列方法和算法:(1)求F的所有本原蕴含项的图论方法和分支定界算法BBAPI;(2)应用超图理论求F的最小和表达式的算法AMSHT。这些方法简单、直观;既便于手算,也便于用计算机实现;计算效率高于常用的卡诺图法和Q-M列表法。Abstract: The concepts of associated graph G and associated hypergraph H are introduced for a switching function F(x1,,xn) with n variables. Then, the following methods and algorithms are derived: (1) The graph theory methods and branch-and-bound algorithm BBAPI for finding all prime implicants of F, (2) Algorithm AMSHT for finding a minimal sum for F by hypergraph theory. These methods are simple and intuitive. They are convenient not only for computation by hand but also for realization by a computer. Their computation efficency are higher than that of Karnaugh map method and Q-M tabular method which are customarily used.
-
Samuel C L. Mo.iern Switching Theory and Digital Design. Englewood Cliffs, N.J.: Prentice-[2]Hall, Inc., 1978.[3]Karnaugh M. Communications and Electronics, 1953, (9): 593-599.[4]Muroga S. Logic Des.ign and Fwitching Theory, New York: John Wiley Sons, 3-4.[5]Quine W V. American Mathematics Monthly, 1952, 59(8): 521-531.[6]McCluskey E J. Bell Systems Technical Journal, 1956, 35(6): 1417-1444.[7]1979, Chapter Swamy M N S,等著,左恺主译.图、网络与算法.北京:高等教育出版社,1988年,第一章.[8]黄汝激.电子科学学刊,1987,9(3): 244-255.
计量
- 文章访问数: 2253
- HTML全文浏览量: 183
- PDF下载量: 503
- 被引次数: 0