RM logic circuit delay optimization method in unit delay model
RM logic circuit delay optimization method in unit delay model
 CN 106,027,032 A
 Filed: 05/20/2016
 Published: 10/12/2016
 Est. Priority Date: 05/20/2016
 Status: Active Application
First Claim
1. RM logic circuit delay Optimization method under a unit delay model, it is characterised in that:
 the method concrete steps include;
Step 1, reads in boolean'"'"'s Boolean logic circuit；
Step 2, utilizes RM expression formula simplifying method to obtain containing the simplest RM logical expression minimum with item number；
Step 3, carries out time delay based on Huffman Huffman tree construction algorithm to each and item in the simplest RM logical expression and dividesSolve so that each minimum with the time delay of item；
Step 4, divides being carried out time delay by all the simplest RM logical expressions formed with item based on Huffman tree construction algorithmSolve so that the time delay of the simplest RM logical expression is minimum；
Step 5, exports the minimum time delay of the simplest RM logical expression；
Wherein, RM implication is Reed Muller ReedMuller.
Chinese PRB Reexamination
Abstract
The invention provides an RM logic circuit delay optimization method in a unit delay model. The method is characterized by specifically comprising the following steps: step 1, reading a Boolean logic circuit; step 2, acquiring the simplest RM logic expression containing the least terms by using an RM expression simplification method; step 3, performing delay decomposition on each term in the simplest RM logic expression based on the Huffman tree construction algorithm so as to enable the delay of each term to be minimum; step 4, performing delay decomposition on the simplest RM logic expression composed of the all terms based on the Huffman tree construction algorithm, so as to enable the delay of the simplest RM logic expression to be minimum; and step 5, outputting the minimum delay of the simplest RM logic expression. Through adoption of the delay optimization method provided by the invention, the Boolean logic circuit can be quickly and effectively converted to the RM logic circuit with the minimum delay, so that the circuit delay is reduced, a working speed of the circuit is accelerated, and the performance of the circuit is improved.

3 Citations
A kind of FPRM circuit areas and delay Optimization method  
Patent #
CN 107,194,023 A
Filed 03/30/2017

Current Assignee

Optimization method for time delay and area of fixedpolarity ReedMuller circuit  
Patent #
CN 102,592,013 A
Filed 12/31/2011

Current Assignee

Best mixed polarity searching method of AND/XOR circuit  
Patent #
CN 102,054,102 A
Filed 12/27/2010

Current Assignee

6 Claims

1. RM logic circuit delay Optimization method under a unit delay model, it is characterised in that:
 the method concrete steps include;
Step 1, reads in boolean'"'"'s Boolean logic circuit； Step 2, utilizes RM expression formula simplifying method to obtain containing the simplest RM logical expression minimum with item number； Step 3, carries out time delay based on Huffman Huffman tree construction algorithm to each and item in the simplest RM logical expression and dividesSolve so that each minimum with the time delay of item； Step 4, divides being carried out time delay by all the simplest RM logical expressions formed with item based on Huffman tree construction algorithmSolve so that the time delay of the simplest RM logical expression is minimum； Step 5, exports the minimum time delay of the simplest RM logical expression； Wherein, RM implication is Reed Muller ReedMuller.
 the method concrete steps include;

2.
RM logic circuit delay Optimization method under a kind of unit delay model the most according to claim 1, it is characterised in that:  Simplifying method in step 2 is algebraical simplification or outlier abbreviation method.

3.
RM logic circuit delay Optimization method under a kind of unit delay model the most according to claim 1, it is characterised in that:  Step 3 includes;
Step 31, the input variable number n calculating and containing in item； Step 32, if input variable number n is equal to 1, is then set to the time delay of this input variable by this time delay with item；
If input becomesAmount number n, more than 1, is first that n input variable creates n leafy node, secondly according to d_{1},d_{2},...,d_{i},...,d_{n}BuildThere is the forest F={T of n binary tree_{1},T_{2},...,T_{i},...T_{n}, 1≤
i≤
n, wherein every binary tree T_{i}Only there is one prolongTime be d_{i}Node, finally repeat following operation until forest F only has a binary tree;
from forest F, select rootTwo tree l and r that node time delay is minimum；
Create one using l as left subtree and using r as the new tree of right subtree, 1≤
i≤
n,d_{i}Represent the time delay of ith input variable, d_{n}Represent the time delay of the nth input variable.
 Step 3 includes;

4.
RM logic circuit delay Optimization method under a kind of unit delay model the most according to claim 1, it is characterised in that:  Step 4 includes;
Step 41, calculate the simplest RM expression formula contains with item number m； Step 42, creates m leafy node for m with item； Step 43, according to the time delay of m with item, builds the forest F with m binary tree； Step 44, repeats following operation until only having a binary tree in forest F, selects root node to prolong from forest FTime minimum two tree l and r；
Create one using l as left subtree and using r as the new tree of right subtree；Step 45, is set to the time delay of Huffman tree root node by the time delay of this simplest RM expression formula.
 Step 4 includes;

5.
RM logic circuit delay Optimization method under a kind of unit delay model the most according to claim 3, it is characterised in that:  What the time delay of new tree root node was bigger equal in two subtree time delays adds 1；
Selected two tree l and r are deleted from forest F；
WillThe new tree created adds forest F；
Finally this time delay with item is set to the time delay of Huffman tree root node.
 What the time delay of new tree root node was bigger equal in two subtree time delays adds 1；

6.
RM logic circuit delay Optimization method under a kind of unit delay model the most according to claim 4, it is characterised in that:  What the time delay of new tree root node was bigger equal in two subtree time delays adds 1；
Selected two tree l and r are deleted from forest F；
WillNewly created tree adds forest F.
 What the time delay of new tree root node was bigger equal in two subtree time delays adds 1；
Specification(s)