Browse Prior Art Database

Alignment Algorithm for Determining Via Centers of Substrate Layers

IP.com Disclosure Number: IPCOM000112094D
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 8 page(s) / 159K

Publishing Venue

IBM

Related People

Feig, E: AUTHOR [+2]

Abstract

A technique is described whereby an algorithm is used in substrate layer alignment to determine the appropriate scaling, translation and rotation parameters so that the maximum distance between corresponding centers of vias can be minimized. The concept achieves the minimization by translating, scaling and rotating one layer so that it is optimally fitted against the other.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Alignment Algorithm for Determining Via Centers of Substrate Layers

      A technique is described whereby an algorithm is used in
substrate layer alignment to determine the appropriate scaling,
translation and rotation parameters so that the maximum distance
between corresponding centers of vias can be minimized.  The concept
achieves the minimization by translating, scaling and rotating one
layer so that it is optimally fitted against the other.

      In the first step, given two sets of complex numbers of equal
cardinality lbrace z sub <j> rbrace and lbrace x sub <j> rbrace,
determine two complex numbers alpha and beta which minimize the
maximum distance vbar z sub <j> - ax sub <j> - beta vbar.  The
following illustrates the formation of the algorithm for estimating
the two numbers:

o   The algorithm contains three basic subroutines, as shown in Fig.
    1:  CHOOSE3, MOVE3, INCREMENT and CIRCLE.  A particular
    implementation, written in APL, called ALGORITHM is shown in Fig.
    2.

o   The routine CHOOSE3 selects three pairs z sub <j>, x sub <j>
    whose distance vbar z sub J - x sub <j> vbar are maximal.  The
    routine MOVE3 accepts as input three pairs of complex numbers v
    sub <1>, w sub <1>, v sub <2>, w sub <2> and v sub <3>, w sub
    <3>, and returns two complex numbers A and B which minimize the
    maximum absolute value vbar v sub <j> - Aw sub <j> - B vbar,
    j=1,2,3.  This routine is based on a closed-form solution, as in
    [1].

First, the algorithm computes the three real numbers

a sub <1> = arg (w sub <1> - w sub <2>)(w sub <1> - w sub <3>)

a sub <2> = arg (w sub <1> - w sub <2>)(w sub <3> - w sub <2>)

a sub <3> = arg (w sub <1> - w sub <3>)(w sub <2> - w sub <3>)

where arg donates the phase (Argument) of the complex number.  It
then solves the linear equation

V barunder = M V tilde barunder
where V barunder = (v sub <1>%v sub <2>%v sub <3>) sup t and M is the
3x3 matrix whose first column entries are all 1, whose second column
is (w sub <1>%w sub <2>%w sub <3>) sup t, and whose third column is
(a sub <1>%a sub <2>%a sub <3>) sup t.  The output A and B are the
second and first entries, respectively, of the vector V tilde
barunder.

      The routine INCREMENT accepts, as input, a set of complex
numbers lbrace x sub <j> rbrace, two complex numbers A and B, and a
real number S, which is greater than zero, but less than one.  Its
output is the set of...