Graph representation of logic functions to design two-level MOS networks

✍ Scribed by Yasuaki Nishitani; Kensuke Shimizu; Masahiko Nagumo

• Book ID: 104591472
• Publisher: John Wiley and Sons
• Year: 1992
• Tongue: English
• Weight: 837 KB
• Volume: 23
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/scj.4690230102

✦ Synopsis

Abstract

The design problem of two‐level MOS networks with a minimum number of cells is reduced to the covering problem of graphs with a minimum number of cliques.

When every node of the graph corresponds to a minterm, an algorithm which generates an MOS network with a minimum number of cells is presented. The time complexity of this algorithm is O(M)^2^, where M is the number of minterms.

When every node of the graph corresponds to a prime implicant, a procedure which generates near optimum solutions by selecting prime implicants with special properties is presented. About 2 percent of designed networks for four‐variable functions are not minimal ones.