In this paper, we introduce a Shared Multiple Rooted XOR-based Decomposition Diagram (XORDD) to represent functions with multiple outputs. Based on the XORDD representation, we develop a synthesis algorithm for general Exclusive Sum-of-Product forms (ESOP). By iteratively applying transformations and reductions, we obtain a compact XORDD which gives a minimized ESOP. Our method can synthesize larger circuits than previously possible. The compact ESOP representation provides a form that is easier to synthesize for XOR heavy multi-level circuits, such as arithmetic functions. We have applied our synthesis techniques to a large set of benchmark circuits in both PLA and combinational formats. Results of the minimized ESOP forms obtained from our synthesis algorithm are also compared to the SOP forms generated by ESPRESSO. Among the 74 circuits we have experimented with, the minimized ESOP's have fewer product terms than those of SOP's in 39 circuits.

This paper presents an exact minimization algorithm for AND-OR-EXOR three-level networks, where a single two-input exclusive-OR (EXOR) gate is used. The network realizes an EXOR of two sum-of-products expressions (EX-SOP), where the two sum-of-products expressions (SOP) can share products. The objective is to minimize the total number of different products in the two SOPs. An algorithm for the exact minimization of EX-SOPs with up to five variables are shown. Up to five variables, EX-SOPs for all the representative functions of NP-equivalence classes were minimized. For five-variable functions, we confirmed that minimum EX-SOPs require up to 9 products. For n-variable functions, minimum EX-SOPs require at most 92n-5 (n6) products.

This paper deals with minimization of ESOPs (exclusive-or sum-of-products) which represent symmetric functions. Se propose an efficient simplification algorithm for symmetric functions, which guarantees the minimality for some subclass of symmetric functions, and present the minimum ESOPs for all 6-variable symmetric functions.

In this paper, an exact-minimization method for an AND-EXOR expression (ESOP) using O-suppressed binary decision diagrams (ZBDDs) is considered. The proposed method is an improvement of Sasao's MRCF-based method. From experimental results, it is shown that required ZBDD size is reduced to 1/3 in the best case compared with the MRCF-based method.

A generalized Reed-Muller expression (GRM) is obtained by negating some of the literals in a positive polarity Reed-Muller expression (PPRM). There are at most 2(n2)^(n-1) different GRMs for an n-variable function. A minimum GRM is one with the fewest products. This paper presents certain properties and an exact minimization algorithm for GRMs. The minimization algorithm uses binary decision diagrams. Up to five variables, all the representative functions of NP-equivalence classes were generated and minimized. Tables compare the number of products necessary to represent four-and five-variable functions for four classes of expressions: PPRMs, FPRMs, GRMs and SOPs. GRMs require, on the average, fewer products than sum-of-products expressions (SOPs), and have easily testable realizations.

Recently, various efficient algorithms for solving combinatorial optimization problems using BDD-based set manipulation techniques have been developed. Minato proposed O-suppressed BDDs (ZBDDs) which is suitable for set manipulation, and it is utilized for various search problems. In terms of practical limits of space, however, there are still many search problems which are solved much better by using conventional branch-and-bound techniques than by using BDDs or ZBDDs, while the ability of conventional branch-and-bound approaches is limited by computation time. In this paper, an extension of APPLY operation, named APPRUNE (APply + PRUNE) operation, is proposed, which performs APPLY operation (ZBDD construction) and pruning simultaneously in order to reduce the required space for intermediate ZBDDs. As a prototype, a specific algorithm of APPRUNE operation is shown by assuming that the given condition for pruning is a threshold function, although it is expected that APPRUNE operation will be more effective if more sophisticated condition are considered. To reduce size of ZBDDs in intermediate steps, this paper also pay attention to the number of cared variables. As an application, an exact-minimization algorithm for generalized Reed-Muller expressions (GRMs) is implemented. From experimental results, it is shown that time and memory usage improved 8.8 and 3.4 times, respectively, in the best case using APPRUNE operation. Results on generating GRMs of exact-minimum number of not only product terms but also literals is also shown.

To reduce the phase noise of MMIC phase-locked oscillators (PLOs), we study the phase noise properties of PLOs given that the oscillator Q factor is relatively low in monolithic circuits. Such PLOs must have wide bandwidth in order to suppress monolithic oscillator noise. Therefore, to reduce MMIC PLO phase noise, the phase noise in the PLO passband has to be decreased. Noise generation by each component of the PLO, and its contribution to the output are discussed with emphasis on experimental estimation and rigorous analysis of the component phase- or baseband-noise. Based on these results, a new loop configuration is proposed for reducing phase noise in the PLO using a low Q-factor oscillator. It is demonstrated experimentally that PLOs based on the new loop exhibit 7 dB lower phase noise than conventional PLOs.

This paper presents an optimization method for pseudo-Kronecker expressions of p-valued input two-valued output functions by using multi-place decision diagrams for p2 and p4. A conventional method using extended truth tables requires memory of O (3n) to simplify an n-variable expression, and is only practical for functions of up to n14 variables when p2. The method presented here utilizes multi-place decision diagrams, and can optimize considerably larger problems. Experimental results for up to n39 variables are shown.