Method and apparatus for quick search for identities applicable to specified formula
AssigneeLSI Logic Corporation
InventorsAndrej A. Zolotykh, Elyar E. Gasanov, Alexander S. Podkolzin, Valery B. Kudryavtsev
Life of this patent
Estimating the term…
Abstract
The present invention is a method for searching an identity base for identities that can be applied to a given formula. The method includes transforming the formulas from an identity base into a standard form, creating a set of code words for said identity base, constructing a lexicographical tree of a code word set of said identity base, and outputting a list of formula numbers from said identity base.
Claims18
A method for searching an identity base for identities that can be applied to a target formula, comprising:
- (a) inputting an identity base containing pairs of equivalent formulas;
- (b) obtaining a set of code words corresponding to the pairs of equivalent formulas, wherein each code word has been generated based on a representation of a formula in one of the pairs of equivalent formulas, all of said representations being in a standard form;
- (c) obtaining an address structure that has been generated by organizing the set of code words;
- (d) inputting a target formula to be implemented in an electronic circuit;
- (e) transforming the target formula into a representation in the standard form;
- and
- (f) processing the target formula in the standard form using said address structure in order to determine which pairs of equivalent formulas are applicable to the target formula.
An apparatus for searching an identity base for identities that can be applied to a target formula, comprising:
- (a) means for inputting an identity base containing pairs of equivalent formulas;
- (b) means for obtaining a set of code words corresponding to the pairs of equivalent formulas, wherein each code word has been generated based on a representation of a formula in one of the pairs of equivalent formulas, all of said representations being in a standard form;
- (c) means for obtaining an address structure that has been generated by organizing the set of code words;
- (d) means for inputting a target formula to be implemented in an electronic circuit;
- (e) means for transforming the target formula into a representation in the standard form;
- and
- (f) means for processing the target formula in the standard form using said address structure in order to determine which pairs of equivalent formulas are applicable to the target formula.
A computer-readable medium encoded with computer-executable process steps for searching an identity base for identities that can be applied to a target formula, wherein said computer-executable process steps include steps to:
- (a) input an identity base containing pairs of equivalent formulas;
- (b) obtain a set of code words corresponding to the pairs of equivalent formulas, wherein each code word has been generated based on a representation of a formula in one of the pairs of equivalent formulas, all of said representations being in a standard form;
- (c) obtain an address structure that has been generated by organizing the set of code words;
- (d) input a target formula to be implemented in an electronic circuit;
- (e) transform the target formula into a representation in the standard form;
- and
- (f) process the target formula in the standard form using said address structure in order to determine which pairs of equivalent formulas are applicable to the target formula.
Dependencies are inferred from the claim text.