Form vector-based reduction method for multi-input multi-output truth table

Abstract

The invention discloses a form vector-based reduction method for a multi-input multi-output truth table, and belongs to the technical field of logic circuit optimization. The technical problem to be solved is to provide a form vector-based reduction method for a multi-input multi-output truth table. The technical scheme for solving the technical problem comprises the following steps: 1, converting a truth table into a decision form background; 2, solving all single-attribute non-zero form vectors according to the conditional form background and the decision form background, and respectively storing the vectors into a conditional form vector set and a decision form vector set; 3, for any conditional form vector and decision form vector, if a rule reduction condition is met, calculating a heuristic operator of the corresponding conditional form vector, and storing the conditional form vector completing the rule extraction operation into a redundant form vector set. The method is used for optimizing the logic relation between the input and the output of the digital logic circuit.

Description

technical field [0001] The invention relates to a reduction method of a multi-input multi-output truth table based on a formal vector, and belongs to the technical field of logic circuit optimization. Background technique [0002] The combinational logic circuit is an important type of digital circuit. The design of the combinational logic circuit requires the circuit to be functionally complete, but at the same time considering the cost and design complexity, the circuit is also required to be the simplest and most optimized. Therefore, combinatorial logic circuit optimization is an important research content of digital circuit optimization. Truth tables are usually used to represent the logical relationship between the input and output of digital logic circuits. It is a commonly used method and model in the design and optimization of combinational logic circuits. Therefore, the optimization of combinational logic circuits is essentially the simplification of truth tables. ...

AI Technical Summary

Problems solved by technology

[0003] In the optimization of combinational logic circuits, the commonly used truth table simplification methods mainly include formula method, cube method, Karnaugh map method, Q-M algorithm and its improved algorithm, but when faced with a large-scale multi-input multi-output truth table When simplifying the problem, the above-mentioned traditional methods have great limitations: the formula method is highly dependent on experience, the reduction result is not unique, lacks a unified reduction model, and is difficult to program; the Karnaugh map method has chance and trial and error As the number of logical variables increases, the simplification of the truth table based on the Karnaugh map will become quite complicated; the Quine-McCluskey algorithm is a more direct, systematic and computable method, but its The exponential complexity makes it only suitable for the simplification of small truth tables; the cube method is an improved algorithm based on the Karnaugh map simplification method, which is easy to implement in computer programming, but the calculation of its prime implicants is more complicated , the computational efficiency of this type of method is still not ideal

[0004] When the number of logic input variables increases, the complexity of traditional algorithms increases sharply, which is not conducive to processing large-scale digital logic circuits; traditional algorithms are generally only suitable for processing truth tables of single logic output variables, and for large-scale The truth table simplification problem, how to improve the simplification efficiency of the algorithm and avoid the generation of a large number of redundant operations is a problem to be solved at present

Images