US5359537A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Automatic synthesis of integrated circuits employing controlled input dependency during a decomposition process
Assignee: Callahan Cellular LLC
•
Filing: 1990-05-14
•
Granted: 1994-10-25
•
Expires: 2010-05-14
Abstract
Abstract A method of automatic synthesis of a very large scale integrated circuit includes controlling the decomposition process in accordance with a reference order of inputs in a lexicographical expression of a Boolean function. The process improves the routability of the circuit by a reduction of complexity of wiring between cells of the circuit and external wiring to blocks connected to the synthesized circuit. The process also promotes an increase in speed and/or a decrease in area of the circuit, avoids ineffective decompostions which would be broken later during an optimization process and also helps to speed up the entire process of synthesis.
Inventors
- 👤 Gabriele Saucier
- 👤 Franck J. Poirot
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 17:40
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/327
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
124 words
A method of automatic synthesis and physical realization of an integrated circuit having a multiplicity of inputs and at least one output, comprising the steps of: (i) providing at least one Boolean function relating a multiplicity of inputs and at least one output of an integrated circuit; (ii) performing by means of a programmed computer factorization of said at least one function to produce a factorized expression in which the order of precedence of said inputs is compatible with a reference order of said inputs in a lexicographical expression of said at least one function; and (iii) making said integrated circuit in accordance with said factorized expression whereby in said integrated circuit said inputs enter in a physical order corresponding to said reference order.
Claim 2
Independent Claim
124 words
A method of automatic synthesis and physical realization of an integrated circuit having a multiplicity of inputs and at least one output, comprising the steps of: (i) providing at least one Boolean function relating a multiplicity of inputs and at least one output of an integrated circuit; (ii) performing by means of a programmed computer factorization of said at least one function to produce a factorized expression in which the order of precedence of said inputs is compatible with a reference order of said inputs in a lexicographical expression of said at least one function; and (iii) making said integrated circuit in accordance with said factorized expression whereby in said integrated circuit said inputs enter in a physical order corresponding to said reference order.
Claim 3
Dependent Claim
55 words
A method as set forth in claim 1 wherein said factorization step comprises: extracting kernels from said at least one function; examining precedence relations in factorizations associated with said kernels and co-kernels thereof for compatibility with the said reference order; and selecting factorizations that are found to be compatible by means of the examining step.
Claim 4
Dependent Claim
29 words
A method as set forth in claim 2 wherein said step of examining includes: examining factorizations in an order of decreasing gain in terms of speed and/or area saved.
Claim 5
Dependent Claim
69 words
A method as set forth in claim 3 wherein the step of examining precedence relations includes establishing for each factorization a precedence matrix in accordance with said lexicographical order, said matrix having N×N elements where N is the number of said inputs, the elements denoting in binary manner the precedence relation between the literals of any co-kernel associated with a respective kernel and the literals of the respective kernel.
Claim 6
Dependent Claim
42 words
A method as set forth in claim 4 wherein said step of examining precedence relations includes establishing for each successive factorization a current precedence matrix combining the precedence relation of that factorization and the precedence relations associated with all previous compatible factorizations.
Claim 7
Dependent Claim
15 words
A method as set forth in claim 1 further comprising predefining the said lexicographical order.
Claim 8
Independent Claim
161 words
A method of automatic synthesis and physical realization of an integrated circuit for the performance of at least one predefined function relating a multiplicity of inputs to at least one output, comprising the steps of: (i) providing Boolean functions representing at least one predefined function; (ii) performing by means of a programmed computer: (a) extracting from said at least one function a plurality of kernels and associated co-kernels; (b) establishing for each kernel whether the order of precedence of the literals of the said at least one co-kernel and the literals of the kernel is compatible with a reference order in a lexicographical expression of said Boolean functions; and (c) factorizing the expression into a factorization in accordance with kernels for which the said order of precedence is compatible with said reference order; and (iii) making an integrated circuit in accordance with said factorization, said integrated circuit having a multiplicity of inputs in a physical order corresponding to said reference order.
Claim 9
Independent Claim
161 words
A method of automatic synthesis and physical realization of an integrated circuit for the performance of at least one predefined function relating a multiplicity of inputs to at least one output, comprising the steps of: (i) providing Boolean functions representing at least one predefined function; (ii) performing by means of a programmed computer: (a) extracting from said at least one function a plurality of kernels and associated co-kernels; (b) establishing for each kernel whether the order of precedence of the literals of the said at least one co-kernel and the literals of the kernel is compatible with a reference order in a lexicographical expression of said Boolean functions; and (c) factorizing the expression into a factorization in accordance with kernels for which the said order of precedence is compatible with said reference order; and (iii) making an integrated circuit in accordance with said factorization, said integrated circuit having a multiplicity of inputs in a physical order corresponding to said reference order.
Claim 10
Dependent Claim
51 words
A method as set forth in claim 7 wherein the step of establishing comprises establishing a precedence matrix in accordance with the said lexicographical order, said matrix having elements denoting the precedence relation between the literals of any co-kernel associated with a respective kernel and the literals of the respective kernel.
Claim 11
Dependent Claim
29 words
A method as set forth in claim 8 further comprising establishing a current precedence matrix representing the precedence relations of a set of compatible factorizations of the Boolean functions.
Claim 12
Dependent Claim
15 words
A method as set forth in claim 9 further comprising predefining the said reference order.
Claim 13
Dependent Claim
70 words
A method as set forth in claim 10 wherein the step of predefining the reference order is performed by at least one of: (i) performing the synthesis by taking into account interconnections of a logic block with other blocks; (ii) predetermining the location of the inputs to improve utilization of area; and (iii) predetermining the locations of input connectors such that relatively late inputs are disposed close to the output.
Claim 14
Dependent Claim
30 words
A method according to claim 7 wherein the step of factorization avoids factorizations liable to be broken during a subsequent optimization step, whereby to speed up the process of synthesis.
References Cited (Backward Citations)
US4703435A
Cited
US4792909A
Cited
US5095441A
Cited
US5029102A
Cited
US5005136A
Cited
US5003487A
Cited
US5041986A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-10-24 | 1998-04-25 | 1998-10-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-10-24 | 2002-04-25 | 2002-10-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-10-24 | 2006-04-25 | 2006-10-25 | $7700.00 | Window Closed / Lapsed |