US3654615A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Element placement system
Assignee: International Business Machines Corp
•
Filing: 1965-12-01
•
Granted: 1972-04-04
•
Expires: 1985-12-01
Abstract
Abstract The disclosure describes a system for assigning a plurality of interrelated circuit elements to element positions in an array of element positions on a circuit board. The system includes means for storing an indication of the interrelationship of the elements being assigned and the order in which the elements are to be assigned. Apparatus is provided for assigning the first element to be assigned to a selected position in the array, selecting candidate positions related in a predetermined manner to the position which has just had an element assigned to it; determining the best candidate position for the next element to be assigned and assigning the next element to be assigned to the position determined above; the system repeats the above three steps until all elements have been assigned.
Inventors
- 👤 Harlow Freitag
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 02:50
CPC Classifications
H; H10; H10D; H10D89/00; H10D89/10; G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/392; H10D99/00
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
163 words
A system for fabricating an interconnected circuit on a substrate having a plurality of circuit element positions comprising: means for applying to the system information as to the interconnected circuit including the relationship of the elements of the circuit to each other; means for utilizing the relationship of the elements of the circuit to determine the order in which the elements of the circuit are to be assigned to circuit element positions on the substrate; means for assigning the first element to be assigned to a selected element position on said substrate; means operative after each element is assigned to an element position on the substrate for selecting candidate positions related in a predetermined manner to positions which have already had an element assigned to them; means for determining the best candidate position for the next element to be assigned; and means, including in part said first element assigning means, for assigning the next element to be assigned to said best candidate position.
Claim 2
Independent Claim
163 words
A system for fabricating an interconnected circuit on a substrate having a plurality of circuit element positions comprising: means for applying to the system information as to the interconnected circuit including the relationship of the elements of the circuit to each other; means for utilizing the relationship of the elements of the circuit to determine the order in which the elements of the circuit are to be assigned to circuit element positions on the substrate; means for assigning the first element to be assigned to a selected element position on said substrate; means operative after each element is assigned to an element position on the substrate for selecting candidate positions related in a predetermined manner to positions which have already had an element assigned to them; means for determining the best candidate position for the next element to be assigned; and means, including in part said first element assigning means, for assigning the next element to be assigned to said best candidate position.
Claim 3
Dependent Claim
85 words
A system of the type described in claim 1 including: means operative when all the elements of said interconnected circuit have been assigned to element positions for initiating the interconnecting of the element positions having elements assigned to them into said interconnected means, means operative in response to said interconnecting initiating means for determining a suitable wiring pattern for interconnecting the element positions having elements assigned to them into said interconnected circuit; AND means for interconnecting said element positions in accordance with said suitable pattern.
Claim 4
Dependent Claim
44 words
A system of the type described in claim 1 further including means operative when all the elements of said interconnected circuit have been assigned to element positions for initiating the interconnecting of the element positions having elements assigned to them into said interconnected circuit.
Claim 5
Dependent Claim
71 words
A system of the type described in claim 1 wherein said means for assigning said first element to a selected element position operates to assign said element to a centralized position on said substrate; and said means for selecting candidate positions operate to select elements positions which have not yet had an element assigned to them and are adjacent to a position which has already had an element assigned to it.
Claim 6
Dependent Claim
62 words
A system of the type described in claim 1 wherein said means for assigning the next element to said best candidate position operated to assign the candidate position for which the eventual interconnections between the next element to be assigned and the elements to which it is connected which have already been assigned is, on the average, the shortest and the simplest.
Claim 7
Dependent Claim
68 words
A system of the type described in claim 1 wherein it is possible that less than 100 percent of the element positions will be useable including: means for applying to the system information as to the useable condition of each of the element positions on the substrate; and means for inhibiting the selection of an unuseable element position as a candidate position by said candidate position selecting means.
Claim 8
Dependent Claim
71 words
A system of the type described in claim 6 wherein said means for assigning said first element to a selected element position operates to assign said element to a centralized position on said substrate; and said means for selecting candidate positions operate to select element positions which have not yet had an element assigned to them and are adjacent to a position which has already had an element assigned to it.
Claim 9
Dependent Claim
93 words
A system of the type described in claim 7 wherein said means for determining the best candidate position includes: means for determining, for each candidate position, the sum of the square of the distance between the candidate position and each position having assigned to it an element related to the next element to be assigned times the relationship of the next element to be assigned to the element assigned to the position; and means for selecting as the best candidate position the candidate position for which the above determined sum is a minimum.
Claim 10
Independent Claim
141 words
A system for assigning a plurality of interrelated elements to element positions in an array of element positions comprising: means for storing a coefficient of interrelationship between each of said elements; means for utilizing said coefficients of interrelationship to determine the order in which the elements are to be assigned to element positions in said array; means for assigning the first element to be assigned to a selected element position in said array; means operative after each element is assigned to an element position for selecting candidate positions related in a predetermined manner to positions which have already had an element assigned to them; means for determining the best candidate position for the next element to be assigned; and means, including in part said first element assigning means, for assigning the next element to be assigned to said best candidate position.
Claim 11
Independent Claim
141 words
A system for assigning a plurality of interrelated elements to element positions in an array of element positions comprising: means for storing a coefficient of interrelationship between each of said elements; means for utilizing said coefficients of interrelationship to determine the order in which the elements are to be assigned to element positions in said array; means for assigning the first element to be assigned to a selected element position in said array; means operative after each element is assigned to an element position for selecting candidate positions related in a predetermined manner to positions which have already had an element assigned to them; means for determining the best candidate position for the next element to be assigned; and means, including in part said first element assigning means, for assigning the next element to be assigned to said best candidate position.
Claim 12
Dependent Claim
71 words
A system of the type described in claim 9 wherein said means for assigning said first element to a selected element position operates to assign said element to a centralized position in said array; and said means for selecting candidate positions operate to select element positions which have not yet had an element assigned to them and are adjacent to a position which has already had an element assigned to it.
Claim 13
Dependent Claim
95 words
A system of the type dEscribed in claim 9 wherein said means for determining the best candidate position includes: means for determining, for each candidate position, the sum of the square of the distance between the candidate position and each position having assigned to it an element related to the next element to be assigned times the coefficient of interrelationship of the next element to be assigned to the element assigned to the position; and means for selecting as the best candidate position the candidate position for which the above determined sum is a minimum.
Claim 14
Dependent Claim
84 words
A system of the type described in claim 11 including: means operative when two or more candidate positions have the same minimum-determined-sum for determining for which of those candidate positions the average distance in each coordinate direction between the candidate position and the positions having elements related to the next element to be assigned to them are most nearly equal; and means for selecting the candidate position determined to have the minimum average distance difference, by the above means, as the best candidate position.
Claim 15
Dependent Claim
68 words
A system of the type described in claim 10 wherein it is possible that less than 100 percent of the element positions will be useable including: means for applying to the system information as to the useable condition of each of the element positions of the array; and means for inhibiting the selection of an unuseable element position as a candidate position by said candidate position selecting means.
Claim 16
Dependent Claim
56 words
A system of the type described in claim 13 including: means operative after said candidate position selecting means for determining if there are any candidate positions; and means operative in response to a determination by said above means that there are no candidate positions, for making all useable positions in said array available as candidate positions.
Claim 17
Independent Claim
162 words
A system for assigning a plurality of interrelated elements to element positions in an array of element positions wherein the interrelated elements are circuit elements of an interconnected circuit and wherein the element positions are circuit positions on a substrate, said system comprising: means for storing a coefficient of interrelationship between each of said elements; means for storing a list of said interrelated elements in the order in which they are to be assigned; means for assigning the first element to be assigned to a selected element position in said array; means operative after each element is assigned to an element position in said array for selecting candidate positions related in a predetermined manner to positions which have already had an element assigned to them; means for determining the best candidate position for the next element to be assigned; and means, including in part said first element assigning means, for assigning the next element to be assigned to said best candidate position.
Claim 18
Independent Claim
162 words
A system for assigning a plurality of interrelated elements to element positions in an array of element positions wherein the interrelated elements are circuit elements of an interconnected circuit and wherein the element positions are circuit positions on a substrate, said system comprising: means for storing a coefficient of interrelationship between each of said elements; means for storing a list of said interrelated elements in the order in which they are to be assigned; means for assigning the first element to be assigned to a selected element position in said array; means operative after each element is assigned to an element position in said array for selecting candidate positions related in a predetermined manner to positions which have already had an element assigned to them; means for determining the best candidate position for the next element to be assigned; and means, including in part said first element assigning means, for assigning the next element to be assigned to said best candidate position.
Claim 19
Dependent Claim
71 words
A system of the type described in claim 15 wherein said means for assigning said first element to a selected element position operates to assign said element to a centralized position of said array; and said means for selecting candidate positions operate to select element positions which have not yet had an element assigned to them and are adjacent to a position which has already had an element assigned to it.
Claim 20
Dependent Claim
93 words
A system of the type described in claim 15 wherein said means for determining the best candidate position includes: means for determining, for each candidate position, the sum of the square of the distance between the candidate position and each position having assigned to it an element related to the next element to be assigned times the relationship of the next element to be assigned to the element assigned to the position; and means for selecting as the best candidate position the candidate position for which the above determined sum is a minimum.
Claim 21
Dependent Claim
87 words
A system of the type described iN claim 17 including: means operative when two or more candidate positions have the same minimum determined sum for determining for which of those candidate positions the average distance in each coordinate direction between the candidate position and the positions having elements, related to the next element to be assigned, assigned to them are most nearly equal; and means for selecting the candidate position determined to have the minimum average distance difference by the above means as the best candidate position.
Claim 22
Dependent Claim
65 words
A system of the type described in claim 15 wherein it is possible that less than 100 percent of the element positions will be useable including: means for applying to the system information as to the useable condition of each of the element positions; and means for inhibiting the selection of an unuseable element position as a candidate position by said candidate position selecting means.
Claim 23
Dependent Claim
56 words
A system of the type described in claim 19 including: means operative after said candidate position selecting means for determining if there are any candidate positions; and means operative in response to a determination by said above means that there are no candidate positions, for making all useable positions in said array available as candidate positions.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1975-04-04 | 1975-10-04 | 1976-04-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1979-04-04 | 1979-10-04 | 1980-04-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1983-04-04 | 1983-10-04 | 1984-04-04 | $7700.00 | Window Closed / Lapsed |