GrC-based Optimization For Logic Information System

Combinational logic optimization is one of the important research contents in digital logic circuits.Truth table is a common form of combinational logic circuit and it is also a bridge for combinational logic optimization technology.The traditional combinational logic optimization methods include formula method,graph method,list method and improved algorithms of these methods,but these traditional algorithms have some flaws to some extent.Granular computing can be considered as a mathematical model which includes a set of theories,methods,techniques and tools.As a result,it can help people solve complex problems more easily.Although the granular computing has been developed for only a few decades,the theory of granular computing has been widely used in various fields of social life,such as artificial intelligence(AI),data mining and analysis,machine learning and so on.With the deeper study and maturity of the theory of granular computing,we try to apply the theory of granular computing to the combinational logic circuits optimization and then get a new and efficient algorithm.In this paper,we mainly use the idea of granular computing to optimize the digital logic circuits and combine the granular computing and the combinational logic optimization together.Then,we transform the simplification process of the truth table into the rule extraction process and propose two new algorithms.These two algorithms are suitable for multiple input multiple output(MIMO)truth table and multiple input single output(MISO)incomplete truth table separately.Firstly,this paper constructs an equivalence relation model based on the granule matrix.In this model,the equivalence matrix and the equivalence relation matrix are defined respectively and a multi-output truth table reduction algorithm based on the equivalence relation is proposed.In this paper,the simplest logic rules are obtained by mining the implicit information in the equivalence relation matrix.In addition,by defining the heuristic operator,the convergence speed of the algorithm is improved.We use the seven segments display as an example to describe the algorithm steps in details.We analyze the complexity of the algorithm and through theoretical analysis to prove the effectiveness of the proposed algorithm.Secondly,a tolerance relation model based on granule matrix is constructed and the manifestation of incomplete truth table is defined.On the basis of incomplete truth table,the tolerance matrix and the tolerance relation matrix are defined respectively.A logic expression reduction algorithm based on tolerance relation is proposed for any logic expressions in digital logic circuits.In this paper,according to the relationship between the elements in the tolerance relation matrix,the simplest logic rules in the incomplete truth table are obtained quickly.In addition,by setting the termination condition of the algorithm,the operation efficiency of the algorithm is improved.After that,the complexity of the algorithm is analyzed,and the correctness of the algorithm is verified by the example and the theoretical analysis.Finally,this paper designs a reduction platform of logic information system based on granular computing.This platform can run the two algorithms proposed in this paper and the traditional Q-M truth table reduction algorithm.The two algorithms proposed in this paper not only fix the problem of lengthy and complexity in computing process when using the traditional algorithms to make the simplification process simpler and more clear,but also overcome the inapplicability in large-scale data when using the traditional algorithms.Thus,they better solve the optimization problem of large-scale logic circuits.