|
|
|
| GRAPH THEORY METHODS FOR SIMPLIFICATION OF SWITCHING FUNCTIONS |
| Huang Ruji |
| Beijing Uaiversity of Science and Technology,Beijing 100083 |
|
|
|
|
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.
|
|
Received: 18 January 1993
|
|
|
|
|
|
|
|
|
1994, Vol. 16 
