US5311442A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Technology mapping apparatus for a combination circuit for use in automatically synthesizing an LSI logic circuit
Assignee: Fujitsu Ltd
•
Filing: 1991-09-19
•
Granted: 1994-05-10
•
Expires: 2011-09-19
Abstract
Abstract A graph converter converts functionally descriptive information expressing a combination circuit into a graph expression having only NOR and inversion circuits. A multiple input NOR converter detects from the above graph expression a circuit element having a NOR circuit and an inversion circuit alternately connected in series and converts the circuit element to a graph expression where a multiple input NOR circuit replaces the circuit element. A cell mapper detects from the above graph expression a circuit element having NOR circuits connected together in series, maps the circuit element to gate cells with or without a composite cell, and outputs the mapping result with the least number of gates as the mapping output for the circuit element. A circuit element having a NOR circuit and an inversion circuit alternately connected in series is substituted by a unique multiple input NOR circuit. A circuit element mapped to a composite cell is efficiently determined just by detecting a circuit element where "nor" circuits are connected together in series. It is possible to replace NOR circuits by NAND circuits.
Inventors
- 👤 Hisayo Fukushima
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 12:37
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/327
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
177 words
A technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NOR and inversion circuits; multiple input NOR converting means for detecting from the first graph expression a circuit element having a NOR circuit and an inversion circuit alternately connected in series and for converting said circuit element to a second graph expression where a multiple input NOR circuit replaces said circuit element; and cell mapping means for detecting from at least one of the first and second graph expressions a circuit element having NOR circuits connected together in series, for mapping said circuit element to at least one of a plurality of sets of gate cells, at least some of the sets of the gate cells including a composite cell, and for outputting a mapping result with a minimum number of gates as a mapping output for said circuit element.
Claim 2
Dependent Claim
177 words
A technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NOR and inversion circuits; multiple input NOR converting means for detecting from the first graph expression a circuit element having a NOR circuit and an inversion circuit alternately connected in series and for converting said circuit element to a second graph expression where a multiple input NOR circuit replaces said circuit element; and cell mapping means for detecting from at least one of the first and second graph expressions a circuit element having NOR circuits connected together in series, for mapping said circuit element to at least one of a plurality of sets of gate cells, at least some of the sets of the gate cells including a composite cell, and for outputting a mapping result with a minimum number of gates as a mapping output for said circuit element.
Claim 3
Dependent Claim
59 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit my mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 1, wherein said graph converting means further comprises graph separating means for individually outputting graphs separated by a net having at least one fanout from the first graph expression.
Claim 4
Dependent Claim
118 words
A technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NOR and inversion circuits; multiple input NOR converting means for detecting from the first graph expression a circuit element having a NOR circuit and an inversion circuit alternately connected in series and for converting said circuit element to a second graph expression where a multiple input NOR circuit replaces said circuit element; and means for executing technology mapping for the second graph expression obtained by said multiple input NOR converting means.
Claim 5
Dependent Claim
118 words
A technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NOR and inversion circuits; multiple input NOR converting means for detecting from the first graph expression a circuit element having a NOR circuit and an inversion circuit alternately connected in series and for converting said circuit element to a second graph expression where a multiple input NOR circuit replaces said circuit element; and means for executing technology mapping for the second graph expression obtained by said multiple input NOR converting means.
Claim 6
Dependent Claim
59 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 3, wherein said graph converting means further comprises graph separating means for individually outputting graphs separated by a net having at least one fanout from the first graph expression.
Claim 7
Dependent Claim
158 words
A technology mapping apparatus for automatically synthesizing an LSI logic circuit my mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NOR and inversion circuits; multiple input NOR converting means for detecting from the first graph expression a circuit element having a NOR circuit and an inversion circuit alternately connected in series and for converting said circuit element to a second graph expression where a multiple input NOR circuit replaces said circuit element; and cell mapping means for detecting from at least one of the first and second graph expressions a circuit element having NOR circuits connected together in series, and for mapping said circuit element to at least one of a plurality of sets of gate cells, at least some of the sets of the gate cells including a composite cell.
Claim 8
Dependent Claim
158 words
A technology mapping apparatus for automatically synthesizing an LSI logic circuit my mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NOR and inversion circuits; multiple input NOR converting means for detecting from the first graph expression a circuit element having a NOR circuit and an inversion circuit alternately connected in series and for converting said circuit element to a second graph expression where a multiple input NOR circuit replaces said circuit element; and cell mapping means for detecting from at least one of the first and second graph expressions a circuit element having NOR circuits connected together in series, and for mapping said circuit element to at least one of a plurality of sets of gate cells, at least some of the sets of the gate cells including a composite cell.
Claim 9
Dependent Claim
58 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit my mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 5, said graph converting means further comprises graph separating means for individually outputting graphs separated by a net having at least one fanout from the first graph expression.
Claim 10
Dependent Claim
54 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 5, wherein said cell mapping means outputs a mapping result with a minimum number of gate as a mapping output for said circuit element.
Claim 11
Dependent Claim
54 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 6, wherein said cell mapping means outputs a mapping result with a minimum number of gate as a mapping output for said circuit element.
Claim 12
Dependent Claim
177 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NAND and inversion circuits; multiple input NAND converting means for detecting from the first graph expression a circuit element having a NAND circuit and an inversion circuit alternately connected in series and for converting said circuit element to a second graph expression where a multiple input NAND circuit replaces said circuit element; and cell mapping means for detecting from at least one of the first and second graph expressions a circuit element having NAND circuits connected together in series, for mapping said circuit element to at least one of a plurality of sets of gate cells, at least some of the sets of the gate cells including a composite cell, and for outputting a mapping result with a minimum number of gates as a mapping output for said circuit element.
Claim 13
Dependent Claim
177 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NAND and inversion circuits; multiple input NAND converting means for detecting from the first graph expression a circuit element having a NAND circuit and an inversion circuit alternately connected in series and for converting said circuit element to a second graph expression where a multiple input NAND circuit replaces said circuit element; and cell mapping means for detecting from at least one of the first and second graph expressions a circuit element having NAND circuits connected together in series, for mapping said circuit element to at least one of a plurality of sets of gate cells, at least some of the sets of the gate cells including a composite cell, and for outputting a mapping result with a minimum number of gates as a mapping output for said circuit element.
Claim 14
Dependent Claim
59 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 9, wherein said graph converting means further comprises graph separating means for individually outputting graphs separated by a net having at least one fanout from the first graph expression.
Claim 15
Dependent Claim
118 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NAND and inversion circuits; multiple input NAND converting means for detecting from the first graph expression a circuit element having a NAND circuit and an inversion circuit alternatively connected in series and for converting said circuit element to a second graph expression where a multiple input NAND circuit replaces said circuit element; and means for executing technology mapping for the second graph expression obtained by said multiple input NAND converting means.
Claim 16
Dependent Claim
118 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NAND and inversion circuits; multiple input NAND converting means for detecting from the first graph expression a circuit element having a NAND circuit and an inversion circuit alternatively connected in series and for converting said circuit element to a second graph expression where a multiple input NAND circuit replaces said circuit element; and means for executing technology mapping for the second graph expression obtained by said multiple input NAND converting means.
Claim 17
Dependent Claim
59 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 11, wherein said graph converting means further comprises graph separating means for individually outputting graphs separated by a net having at least one fanout from the first graph expression.
Claim 18
Dependent Claim
157 words
A technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NAND and inversion circuits; multiple input NAND converting means for detecting from the first graph expression a circuit element having a NAND circuit and an inversion circuit alternatively connected in series and for converting said circuit element to a second graph expression where a multiple input NAND circuit replaces said circuit element; and cell mapping means for detecting from at least one of the first and second graph expressions a circuit element having NAND circuits connected together in series, for mapping said circuit element to at least one of a plurality of sets of gate cells, at least some of the sets of the gate cells including a composite cell.
Claim 19
Dependent Claim
157 words
A technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, comprising: graph converting means for converting functionally descriptive information expressing a combination circuit into a first graph expression having only NAND and inversion circuits; multiple input NAND converting means for detecting from the first graph expression a circuit element having a NAND circuit and an inversion circuit alternatively connected in series and for converting said circuit element to a second graph expression where a multiple input NAND circuit replaces said circuit element; and cell mapping means for detecting from at least one of the first and second graph expressions a circuit element having NAND circuits connected together in series, for mapping said circuit element to at least one of a plurality of sets of gate cells, at least some of the sets of the gate cells including a composite cell.
Claim 20
Dependent Claim
59 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 13, wherein said graph converting means further comprises graph separating means for individually outputting graphs separated by a net having at least one fanout from the first graph expression.
Claim 21
Dependent Claim
54 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 13, wherein said cell mapping means outputs a mapping result with a minimum number of gates as a mapping output for said circuit element.
Claim 22
Dependent Claim
54 words
The technology mapping apparatus for automatically synthesizing an LSI logic circuit by mapping circuit elements of a combination circuit to cells which form said LSI logic circuit, according to claim 14, wherein said cell mapping means outputs a mapping result with a minimum number of gates as a mapping output for said circuit element.
References Cited (Backward Citations)
US4703435A
Cited
US4701860A
Cited
US4942536A
Cited
US4803636A
Cited
US4827427A
Cited
US4964056A
Cited
US4816999A
Cited
US4922432A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-05-09 | 1997-11-08 | 1998-05-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-05-09 | 2001-11-08 | 2002-05-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-05-09 | 2005-11-08 | 2006-05-10 | $7700.00 | Window Closed / Lapsed |