Patent ID: 6535222
Filing Date: 2003-03-18
Classification: G06F,G06T,Y10S

Abstract:
A method of synthesizing a masking layer on a semiconductor surface in the production of large-scale integrated circuits comprising the steps of:mapping proposed structures for the semiconductor surface and converting the proposed structures into hypothetical trapezoidal figures having upper and lower sides in parallel with an X-axis on a numerical coordinate grid comprising the X-axis and a Y-axis; repeatedly determining locations of intersection of selected figures of the masking layer and removing a portion of at least one intersecting figure until there are no intersecting figures to obtain a mask plan with no intersecting figures; and synthesizing a masking layer into a mask according to the mask plan with no intersecting figures, wherein the step of determining locations of intersecting figures of the masking layer includes the steps of: grouping the trapezoidal figures into a plurality of groups, wherein the figures are grouped such that all figures within a group have the lower sides of the same Y-coordinate values; sorting the groups into a series of sorted groups based on the Y-coordinate values of said lower sides; sorting the trapezoidal figures within each group based on minimum X-coordinate values of the trapezoidal figures; selecting a to-be-judged group from the groups in order of sorting; performing an intra-group judging step using any one of said trapezoidal figures included in said to-be-judged group as a to-be-judged figure in order of sorting, using any other trapezoidal figures in said to-be-judged group sorted after said to-be-judged figure as a to-be-compared figure successively in order of sorting, and repetitively executing an intersection judgement processing only when a maximum X-coordinate value of the to-be-judged figure is greater than a minimum X-coordinate value of the to-be-compared figure while comparing the maximum X-coordinate value of the to-be-judged figure with the minimum X-coordinate value of said to-be-compared figure until the maximum X-coordinate value of the to-be-judged figure becomes smaller than the minimum X-coordinate value of the to-be-compared figure or until the minimum X-coordinate of the to-be-compared figure equals the maximum X-coordinate of the to-be-compared figure and the to-be-compared figure disappears; performing an inter-group judging step for using any one of said group sorted before said to-be-judged group as a to-be-compared group in order of sorting, said judging step comprising comparing the Y-coordinate values of the lower sides of the trapezoidal figures included in said first to-be-judged group with a maximum Y-coordinate value of a trapezoidal figure included in said to-be-compared group, and executing the intersection judgement processing between the trapezoidal figures included in said to-be-judged group and the trapezoidal figures included in said to-be-compared group only when the Y-coordinate value of the lower side of said to-be-judged group is smaller than said maximum Y-coordinate value of said to-be compared group; and repeating said selecting a to-be-judged group step through said performing an inter-group judging step until there is no group that can be used as said to-be-judged group in said to-be-judged group-determining step.