1. Introduction

The grating measurement systems are widely used to measure the relative displacement which occurs between one grating and another. Typically, one large grating serves as a measuring reference, and is named scale grating. The other one is smaller, it is named index grating and is used to “read” position along the scale grating. This set-up, along with adequate opto-electronic elements, is allows to achieve motion control and is known as optical encoder. Relative motion is detected through any of the typical effects appearing in a double grating system: moire, self-imaging or Lau effects. In many cases, a zero reference signal is necessary in order to obtain an absolute measure. To acquire a zero reference signal, gratings with adjacent Zero Reference Codes (ZRC) have been developed since the seventies. The ZRC consist of a group of unequally spaced slits. In general, a ZRC can be described by the following sequence of binary data

where n+1 is the length of the ZRC, c_i =1 if a transparent slit is located at the i-position, and c_j =0 elsewhere. The sizes of the transparent and opaque regions in the code are integer multiples of the width of a single slit, that we will name b. Finally, the number of transparent and opaque slits are respectively n ₁ and n ₀, so that n ₁+n ₀=n+1.

The transmittance of a code can be expressed as the following sum

where the rect function is defined by

When the index grating moves with respect to the scale grating, the two ZRC overlap. A parallel ray beam propagates through both codes and the total amount of transmitted light is registered by means of a photodiode. The output signal is the correlation between the two ZRC’s. In order to increase the maximum of this signal, the two codes are made identical so that the reference signal becomes the autocorrelation of the ZRC.

The design of optimum codes to obtain suitable reference signals has been studied in references [1–5]. In all these works, the authors consider the properties of the autocorrelation function and they establis h the necessary conditions to achieve a suitable signal. The main difficulty in designing good ZRCs, is that there is not a systematic method of calculus from which arbitrary length ZRCs can be obtained. Some hints are given by Yajun [2–5] to heuristically construct optimum ZRCs according to predefined criteria. The method consists of filling the code with ones or zeros to fulfill the necessary conditions of optimality, these conditions are only applicable to small-length ZRC, up to 10–12 elements. We address this problem and we present an algorithm for the design of ZRC which generate optimum reference signal for arbitrary size of codes by means of a direct search algorithm.

2. General considerations

We will assume that the illuminating light is a parallel ray beam, and diffraction effects are negligible. This approach is valid when the gap between ZRC’s is close with regard to the width of the code slits and the width of the code slits is greater than wavelength of the illuminating light. Under these conditions, the light flux that passes through the two codes when one of them is shifted by displacement t is

where the triangle function is defined as

and the components of the vector a is defined by

If the signal S is sampled at integer multiples of the slit width, it coincides with the vector a,

We will work with this sampled version of the autocorrelation signal. Further simplification can be made if we take into account the symmetry of the autocorrelation signal. As S_k=S_-k , only the last n+1 terms are needed, and we define de vector S=[S ₀,…S_n ]. The next propert ies can be easily demonstrated:

1. The maximum of the autocorrelation signal, S ₀, is the number of transparent slits of the ZRC, S ₀=${\sum }_{j=0}^n$ $c_j^2$ =${\sum }_{j=0}^n$ c_j =n ₁.

2. The width of the central peak is twice the width of the slits of the ZRC.

3. From equation (4) and (7), the value of S_k is equal to the number of subsequences in the ZRC of the type $\left(\underset{k-1}{\underbrace{1,X,\dots ,X,1}}\right)$, with X∊{0,1}. When the relative shift between the two codes is kb, the first “one” of the subsequence of the shifted code is faced with the last “one” of the same subsequence in the other code. This property is used to design a suitable ZRC.

The parameters that characterize a zero reference signal are presented in [1] but in metrological applications, the most important parameter is

where σ is the second maximum of the signal, σ=max{S ₁,…,S_n }. A good zero reference signal must be a single and well distinct peak, so the secondary maxima of the correlation signal are regarded as noise. According to this, the parameter K quantifies the noise in relation to the signal peak. The smaller its value, the higher the sensitivity and robustness of the zero reference signal.

In the design procedure of Yang and Yin [2], the parameters S ₀ and K (and henceforth also σ) are previously selected and fixed. Then the code with the smallest length is chosen. The ZRC design process consists on the addition of subsequences (see property 3.) while the number of repeated subsequences is not greater than σ. There are several possibilities depending on the order in which the subsequences are arranged, and it is necessary to compare these structures one by one to get an optimum result. This process is difficult to program and ZRC longer than 40 bits are very difficult to obtain.

Considering property 3, Yajun [3] has calculated an inferior bound for σ

Although there are some simple cases in which this bound is reached, up to now there is no evidence that for any values of n and n1, at least one ZRC could be found for which the equality sign holds. In the design procedure of Yajun [3], once n and n1 has been fixed, the lower bound is computed. Then a ZRC for which the bound is reached is searched using property 3. If it is not possible, the bound is increased in one unit and the search starts once again. The process is repeated until a ZRC with the lowest K is obtained.

Yajun have proposed other designing methods in [4]. He proposes a computer program to calculate all possible ZRC with fixed values of n and n ₁, and compare the performance of the obtained autocorrelation signals to obtain the optimal. The computer must consider $C\left(n-1,n_1-2\right)=\frac{\left(n-1\right)!}{\left(n_1-2\right)!\left(n-n_1+1\right)!}$ ZRC’s. This problem is named “the combinatorial explosion”: the most powerful computer in this moment (Earth Simulator Center, Japan) takes 5×10²⁸ years in the case of n=170 and n ₁=85.

In [5], Yajun proposes a method for calculating the ZRC when the autocorrelation signal is known but in general, the optimum signal is not known.

Normally, the period of the grating of the measuring system fixes the wide of the slits of the ZRC. The diameter of the light beam limits the length of the code and the electronic requirement establish a minimum of the S/N ratio of the zero reference signal. This requirement determines the minimum number of slits of the ZRC. According with these working requirements, we have n and n ₁ predetermined and we have to minimize the second maximum of the signal, σ. A new design method must therefore be sought.

3. Direct algorithm

DIRECT is an algorithm developed by Donald R. Jones et al. [6] for finding the global minimum of a multivariate function subject to simple bounds, using no derivative information. DIRECT is a sampling algorithm. That is, the algorithm samples points in the domain of the function, and uses the information it has obtained to decide where to search next. DIRECT can be useful when the objective function is a “black box” function and we do not know the gradient function. It is guaranteed to converge to the global minimum value if the objective function is continuous in the neighborhood of a global minimum.

The name DIRECT comes from “DIviding RECTangles”, which describes the way the algorithm moves towards the minimum. The first step in the algorithm is to transform the search space in a unit hypercube. The function is then sampled at the center of this hypercube. The hypercube is then divided into smaller hyperrectangles whose center-points are also sampled. Normally, the Lipschitz constant of the objective function is utilized for determining the next rectangle to sample. As the Lipschitz is not known, DIRECT identifies a set of “potentially optimal” rectangles corresponding to all the combinations of Lipschitz constants and rectangles sizes in each iteration. All “potentially optimal” rectangles are further divided into smaller rectangles whose centers are sampled. This method does not have a natural way of defining convergence and DIRECT typically terminates when a user-supplied limit of function evaluations is reached. Unless the global minimum value is known, there is no way to assure that it is reached. In practice, if the optimal value does not change when increasing the number of evaluations we can consider it a global minimum.

4. Description of the modeling and results

The DIRECT algorithm deals with problems of the type [7]:

x,L_x,U_x ∊ℝn, A∊ℝm×n and LB, UB∊ℝm.

where L_x and U_x are lower and upper bound for the solution. LB and UB are lower and upper linear constraints, A is a matrix with the linear coefficients of the constraints and x′ is the transpose of x.

For the designing of ZRC, the function to optimize is

where f(c)=σ is the second maximum of the autocorrelation signal. The vector c=[c ₁,…c_n ] is a integer vector and the integer are binary, that is, L_x =[0,…,0] and U_x =[1,…,1]. A is a vector which contains ones and A·c′ is the number of transparent slits in the ZRC, which is bounded between n_1L and n_1U . Physically, n_1L is the minimum value allowed in the center of the autocorrelation signal, its value is matched with the sensibility of the detector, and n _1U is the maximum number of allowed slits, which we can set as the total number of elements of the ZRC.

In order to test the performance of the algorithm, we have first applied it to a low dimension case, which can be treated with previous techniques obtaining the same results. There is a class of ZRC’s for which the second maximum of the autocorrelation signal is one. For these codes, the equality sign in Eq. (9) holds, and the theoretical lower bound is reached. Then, from property 3, the number of repeated subsequences (1,X,…,X,1) cannot be greater than one and the design procedure consists of the addition of subsequences without repetition. Moreover, the optimal objective function value in equation (11) is 1 and this is the global minimum.

An example with 21 elements is: [1,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1]. In [8], Yajun compute the ZRC’s necessary to obtain an autocorrelation signal whose second maximum is one and he show the number of elements and slits of these ZRC’s. We have applied the DIRECT algorithm in these cases and it reaches the global minimum with values up to: n=100 and n ₁=11. With these parameters, the number of points in the feasible region is 1.4×10¹⁴.

In a general case, a comparison between the theoretical lower bound of s given by the Eq. (9) and the value of the second maximum reached with DIRECT is shown in Fig. 1. The optimizations were done with a fixed number of elements, n=50, and with a variable number of slits in the interval from 1 to 49. From this figure, it can be seen that in few cases it is possible to reach the theoretical lower bound and this takes place when the number of slits is small. There are two reasons to think that the optimal is the global optimal. First, in all cases the number of points in the feasible region is smaller than 1.4×10¹⁴, in which case DIRECT find the global optimum. Second, the solution does not change when the number of function evaluations is increased, although the increase of the function evaluations is limited for the computer memory.

 

Fig. 1. Height of the second maximum of the autocorrelation signal respect to the number of slits in the ZRC. The ZRC has 50 elements. The continuous graph is the reached with the optimization and the dotted one is a lower bound calculated theoretically.

Download Full Size | PDF

In Fig. 2 we display some of the optimum autocorrelation signals found by DIRECT in a case whose dimension makes it unmanageable for others design methods: n=50 and n ₁=25. The algorithm finds 136 solutions with σ=11.

 

Fig. 2. Six of the 136 autocorrelation signals found by the algorithm with n=50 and s=25. The value of the second maximum is S₁ =11.

Download Full Size | PDF

The ZRC’s which generate the autocorrelation signals presented in the Fig. 2 are shown in Fig. 3. From the point of view of the optimization of the autocorrelation, all these codes are equivalent. Another advantage of the DIRECT method is that, among the 136 solutions it finds, it is possible the selection of the ZRC’s by taking into consideration other secondary (optical) criteria : sensibility to diffraction, sensibility to non-uniformity of the light beams, etc.

 

Fig. 3. Six of the 136 ZRC’s found by the algorithm with n=50 and s=25.

Download Full Size | PDF

5. Conclusions

The necessary calculations for the design of the zero reference marks are laborious. The generation of long codes can even be impracticable with the currently available designing tools. We have proposed a method for designing zero reference codes with global optimization techniques. A simple model of the problem is presented and global optimal results are obtained. The results have been proved in known cas es and the optimal is reached up to codes of 100 elements. Moreover, the algorithm obtains all solutions with the same optimal value of the objective function. A selection is possible in order to obtain codes with other properties.