摘要: This paper surveys research conducted by Prof. Tsutomu Sasao’s group on the design of combinational logic circuits. The projects can be roughly divided into following groups: 1) Conservative circuits; 2) AND-OR two-level networks; 3) Logic using EXOR gates; 4) Representation functions decision diagrams; 5) Functional decompositions; 6) Cascade realizations; 7) Complexity 8) Design three-level 9) Easily Testable designs; 10) FPGA 11) Spectral analysis functions; and 12) Others. 1 Circuits is a model computation which explicitly reflects number fundamental principles physics, such as reversibility dynamical laws conservation certain additive quantities [137]. series IEEETC papers [142, 143, 145, 146] (1976-1979) conservative circuits contain class reversible His work opened an important area theoretical computing defined later Fredkin Toffoli 2 Two-Level Networks An arbitrary function realized twolevel circuit. In integrated circuits, are often programmable arrays (PLA’s). Because PLAs have regular structure, they easy to design, modify, test. [138], Sasao showed use decoders input PLA’s. insight allowed PLA’s made with 20%-25% fewer components. [134], he formulated optimization problem for these improved That is, way choose variables produce near-minimal With heuristic approaches, demonstrated that PLA size reduced 30% over without decoders. same paper, also ”the output phase PLA’s,” proposed method obtain near-optimum solutions. technique reduces considerably. was used commercial microprocessors including INTEL 80386 [127]. He presented fast algorithm detect all essential prime implicants. Fast implicant detection quite in minimization programs. ESPRESSO [157], widely program, uses SASAO’s method. [131], developed find expression complement given expression. large 10 20 times faster than conventional technique. has it possible minimize could not minimized previous algorithms because excessive memory requirements. books [52, 88] comprehensively describe methods. applied his methods multiple-valued [118, 122], multiplevalued binary [125]. tautology checking [132, 133]. 3 gates Most synthesis tools AND OR basic elements. Arithmetic error correcting many gates, if available well gates. Such derived from ANDEXOR So ExclusiveOR sum-of-products expressions (ESOPs), corresponds AND-EXOR important. During 1990-1992, called EXMIN2