US5486775A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multiplexer structures for use in making controllable interconnections in integrated circuits.
Assignee: Altera Corp
•
Filing: 1993-11-22
•
Granted: 1996-01-23
•
Expires: 2013-11-22
Abstract
Abstract Communication networks for integrated circuits such as programmable logic devices have a plurality of input conductors each of which is connected to two output multiplexers. For good signal routability through the network, no two multiplexers are connected to the same two input conductors. The girth of the multiplexer allocation graph associated with the network is four, and the graph is preferably a highly regular structure known as a cage or a regular structure derived from a cage. The input conductors are assigned to the edges in this regular graph in such a way that a highly regular pattern of connections between the input conductors and the multiplexers results to facilitate physical implementation of the network in the integrated circuit.
Inventors
- 👤 Kerry Veenstra
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 14:02
CPC Classifications
H; H03; H03K; H03K19/00; H03K19/02; H03K19/173; H03K19/1731; H03K19/177; H03K19/17704
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
173 words
A method for producing integrated circuit communication networks of the type having a plurality of substantially parallel, side by side, input conductors connected to inputs of a plurality of multiplexers in such a way that each of said input conductors is connected to the inputs of two of said multiplexers, said method comprising the steps of: selecting a cage having girth four and a number of vertices equal to the number of multiplexers in said plurality of multiplexers, said cage having a plurality of edges; associating each of said multiplexers with a respective one of said vertices; identifying bands of edges in said cage; associating each of said input conductors with a respective one of said edges in such a way that no two physically adjacent input conductors are associated with edges in different bands that have any vertices in common; and fabricating one of said integrated circuit communication networks by connecting each input conductor associated with an edge to the inputs of the multiplexers associated with vertices which that edge extends between.
Claim 2
Independent Claim
173 words
A method for producing integrated circuit communication networks of the type having a plurality of substantially parallel, side by side, input conductors connected to inputs of a plurality of multiplexers in such a way that each of said input conductors is connected to the inputs of two of said multiplexers, said method comprising the steps of: selecting a cage having girth four and a number of vertices equal to the number of multiplexers in said plurality of multiplexers, said cage having a plurality of edges; associating each of said multiplexers with a respective one of said vertices; identifying bands of edges in said cage; associating each of said input conductors with a respective one of said edges in such a way that no two physically adjacent input conductors are associated with edges in different bands that have any vertices in common; and fabricating one of said integrated circuit communication networks by connecting each input conductor associated with an edge to the inputs of the multiplexers associated with vertices which that edge extends between.
Claim 3
Dependent Claim
70 words
The method defined in claim 1 wherein the cage selected in said selecting step has a number of edges greater than the number of input conductors in said plurality of input conductors, and wherein in said step of associating each of said input conductors with a respective one of said edges no input conductors are associated with any of the edges in at least one of said bands of edges.
Claim 4
Dependent Claim
103 words
An integrated circuit communication network comprising: a plurality of substantially parallel, side by side, input conductors; and a predetermined plural number of multiplexers, each of said multiplexers having a plurality of inputs, each of said input conductors being connected to an input of two of said multiplexers, wherein said input conductors form a plurality of adjacent, mutually exclusive groups of input conductors, each group having half as many input conductors as there are multiplexers, each multiplexer having inputs that are connected to said input conductors in said groups, such that each multiplexer is connected to one input conductor in each of said groups.
Claim 5
Dependent Claim
103 words
An integrated circuit communication network comprising: a plurality of substantially parallel, side by side, input conductors; and a predetermined plural number of multiplexers, each of said multiplexers having a plurality of inputs, each of said input conductors being connected to an input of two of said multiplexers, wherein said input conductors form a plurality of adjacent, mutually exclusive groups of input conductors, each group having half as many input conductors as there are multiplexers, each multiplexer having inputs that are connected to said input conductors in said groups, such that each multiplexer is connected to one input conductor in each of said groups.
Claim 6
Dependent Claim
48 words
The apparatus defined in claim 3 wherein each input conductor in a group which is adjacent to another input conductor in an adjacent group is connected to the inputs of two multiplexers which are both different from the two multiplexers having inputs connected to said another input conductor.
Claim 7
Dependent Claim
88 words
The apparatus defined in claim 3 wherein the connections between said input conductors and said inputs of said multiplexers are such that, when each multiplexer is associated with a respective one of a plurality of vertices and each input conductor is associated with a respective one of a plurality of edges each of which extends between a respective unique pair of said vertices, said vertices and said edges collectively comprise vertices and at least a plurality of bands of edges of a cage having a girth of four.
Claim 8
Dependent Claim
19 words
The apparatus defined in claim 5 wherein said edges comprise less than all bands of edges of said cage.
Claim 9
Dependent Claim
17 words
The apparatus defined in claim 5 wherein said edges comprise all bands of edges of said cage.
Claim 10
Dependent Claim
29 words
The apparatus defined in claim 5 wherein the input conductors in each of said groups are associated with the edges in a respective band of edges in said cage.
Claim 11
Dependent Claim
56 words
The apparatus defined in claim 5 wherein said vertices form two mutually exclusive sets, all vertices in each set having no direct edge connection to any other vertex in the same set, and wherein the multiplexers associated with each of said sets of vertices are grouped together side by side in said integrated circuit communication network.
References Cited (Backward Citations)
US5225719A
Cited
US4870304A
Cited
US4933575A
Cited
US4933575B1
Cited
US4899067A
Cited
US4965474A
Cited
US5095523A
Cited
US5241224A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-22 | 1999-07-24 | 2000-01-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-22 | 2003-07-24 | 2004-01-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-22 | 2007-07-24 | 2008-01-23 | $7700.00 | Window Closed / Lapsed |