化簡開關(guān)函數(shù)的圖論方法
GRAPH THEORY METHODS FOR SIMPLIFICATION OF SWITCHING FUNCTIONS
-
摘要: 本文引入了n變量開關(guān)函數(shù)F(x1,,xn)的伴隨圖G和伴隨超圖H的概念,導(dǎo)出了下列方法和算法:(1)求F的所有本原蘊(yùn)含項(xiàng)的圖論方法和分支定界算法BBAPI;(2)應(yīng)用超圖理論求F的最小和表達(dá)式的算法AMSHT。這些方法簡單、直觀;既便于手算,也便于用計(jì)算機(jī)實(shí)現(xiàn);計(jì)算效率高于常用的卡諾圖法和Q-M列表法。
-
關(guān)鍵詞:
- 開關(guān)函數(shù); 圖論; 超圖理論; 分支定界法
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,等著,左愷主譯.圖、網(wǎng)絡(luò)與算法.北京:高等教育出版社,1988年,第一章.[8]黃汝激.電子科學(xué)學(xué)刊,1987,9(3): 244-255. -
計(jì)量
- 文章訪問數(shù): 2288
- HTML全文瀏覽量: 192
- PDF下載量: 506
- 被引次數(shù): 0
下載:
