Multi-level Area Optimization For Reed-muller Logic

Compared with traditional Boolean logic,Reed-Muller logic has better performance in area,speed,power consumption and verifiability when used in logic circuits such as communication circuits,arithmetic circuits,and parity circuits.Area optimization is an important part of Reed-Muller logic circuit design.Most of the existing optimization methods are mainly polarity optimization.By searching the best polarity to obtain the simplest Reed-Muller logic expression.These methods belong to two-level network optimization of Reed-Muller logic,and have limited optimization ability.Therefore,this thesis takes the area performance as the main optimization goal,and carries out multi-level network optimization for Reed-Muller logic circuit,and implements the following research work:(1)The node and path optimization of the binary decision diagram.Through the analysis of the circuit binary decision diagram structure,it is found that there is a diamond structure in the graph.On the basis of standardizing the definition of diamond structure,a binary decision diagram optimization method with diamond structure is proposed.By searching the diamond structure in the binary decision diagram,the structure to be optimized is divided,and then specific structure is reconstructed,finally,the node and path optimization of the binary decision diagram is completed.Since there are multiple optimization strategies for each diamond structure,an appropriate strategy can be selected to accomplish simultaneous optimization of the original circuit area and delay.(2)Reed-Muller multi-level logic optimization based on binary decision diagram.The control variables of the nodes are modified into a logical combination of several single variables in optimized binary decision diagram.Based on this,a Reed-Muller multi-level logic optimization method is proposed: using the feature that the fan-out paths of each node are disjointed,the disjointed products are extracted from the root node to the terminal.Then the polarity conversion method of the products is applied to obtain the Reed-Muller logic function under 0 polarity.Finally,the genetic algorithm is used to optimize the polaritys,and the Reed-Muller multi-level logic optimization algorithm based on binary decision diagram is completed.(3)Multi-level logical area optimization based on kernels.Starting from the application of kernels in Boolean logic function,the definitions of related terms such as kernels and co-kernels of FPRM logic functions are proposed,and the specific calculation methods of kernels and co-kernels are given.The matrix is constructed from the calculated kernels set and co-kernels set,and all the rectangular coverage are searched in the matrix.Based on this,a multi-level optimization method based on rectangular coverage for multi-output FPRM logic functions is proposed.This method performs the overall public variable extraction for Reed-Muller logic function,gives more reasonable kernels and co-kernels calculation method for larger-scale circuits.The matrix partitioning method and greedy strategy introduced during execution have improved the efficiency and operability of the method.The methods or algorithms proposed in this thesis have been implemented by C/C++ language programming and using MCNC benchmarks.The experimental results show that: The optimization effect of the binary decision diagrams is obvious,and the number of nodes and paths is greatly reduced;the area and delay of the mapping circuit can be synchronously optimized,which improve the reliability and effectiveness of the mapping circuit;compared with the parallel tabular technique and the disjoint product method,the results of proposed Reed-Muller multi-level optimization method based on binary decision diagrams only consumes about half of the area;the proposed kernels-based Reed-Muller multi-level logic area optimization method reduces the area about 65% compared with the best polarity Reed-Muller circuit,and reduces the area about 30% compared with multi-level MPRM circuit obtained by applying the onset table,moreover,the method is insensitive to the number of input and output of the circuit when executed,and is only related to the number of products.