| Switching functions can be represented as either AND/OR/NOT based traditional Boolean (briefly, TB) forms or AND/XOR based Reed-Muller forms (briefly, RM). Many researches on TB logic synthesis and optimization have been done extensively and deeply, and many EDA tools based on TB logic have been proposed and used in the IC design. Recently, methods for the efficient representation and minimization of XOR based RM functions continue to engage the interest of researchers. Reasons for this interest include the fact:(1) During the past years, the speed, power and area of XOR gate have been improved greatly with the development of IC technology; (2) Many applications where AND/XOR realizations are more efficient than their equivalent AND/OR realizations, which include arithmetic circuits, telecommunications circuits and so on; (3) Circuits with AND/XOR gates are highly testability. Compare to the circuits which are realized with only TB logic or RM logic, in the fact, most of the circuits are the mixture of the TB logic and RM logic. Therefore the good way for the logic synthesis and optimization of a circuit is implementation both TB logic and RM logic, namely dual logic, at the same time. In this thesis we will focus on the Reed-Muller functions optimization with mixed polarity and its implementation in the dual logic optimization.The study of the logic optimization of Reed-Muller functions under mixed polarity includes two sections. One is the two-level mixed-polarity RM(MPRM) optimization and the other is the multi-level mixed-polarity RM optimization. Compared to the fixed-polarity RM (FPRM) optimization, the optimization of the MPRM is more difficult and time consuming because the MPRM forms are very huge and it makes the published algorithms for the MPRM optimization work slowly, epically for the large functions. In this thesis an improved algorithm for two-level MPRM optimization has been proposed which includes (1) Using disjointed products instead of minterms, which greatly reduces the number of terms that the algorithms need to deal with and makes the proposed algorithm work fast; (2) Proposing a operator named products bit-wise operation. Comparing to the hamming distance based methods, the products bit-wise operation can find more products which are suitable for RM logic synthesis and optimization; (3) Proposing a majority cubes based two level MPRM optimization algorithm. The experimental results show that the proposed algorithm can work fast and the number of variables of the function has little effect on the running time of the algorithm. And it is usually more efficient for the large functions. In the multi-level mixed-polarity RM(MLMPRM) logic optimization, some methods we proposed before are discussed in detail which include (1) Truth vector based MLMPRM logic synthesis and optimization algorithm; (2) Onset table based MLMPRM logic synthesis and optimization algorithm and (3) Improved Onset table based algorithm. Compared to the original one, the improved algorithm can make about 82% running time saving but with about 8% area increased. Moreover, the improved algorithm can optimize the multi-output functions while the original one can only deal with the single-output functions.In dual logic optimization, some logic detection and searching algorithm for those sub-covers which are suitable for RM logic synthesis are proposed. Those algorithms include the disjointed products based searching algorithm and majority cubes based algorithm. By implementing both the searching algorithm and the two-level MPRM optimization algorithm, an approach for the dual logic optimization based on logic decomposition is proposed. Moreover, a functional verification method for TB logic, RM logic and dual logic is proposed to verify whether a function is functional equal or not after logic optimization. Experimental results show that most circuits are suitable for dual logic synthesis, and most circuits can be further optimized with dual logic.
|
PDF Full Text Request