OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 17, Iss. 24 — Nov. 23, 2009
  • pp: 22163–22170
« Show journal navigation

Design of zero reference codes using cross-entropy method

Jung-Chieh Chen  »View Author Affiliations


Optics Express, Vol. 17, Issue 24, pp. 22163-22170 (2009)
http://dx.doi.org/10.1364/OE.17.022163


View Full Text Article

Acrobat PDF (143 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

This paper considers the use of autocorrelation properties to design zero reference codes (ZRCs) for optical applications. Based on the properties of the autocorrelation function, the design of an optimum ZRC problem is transformed into a minimization problem with binary variables, and the objective is to minimize the second maximum of the autocorrelation signal σ. However, the considerable computational complexity for an exhaustive search through all combinations of ( n n 1 ) different code patterns is a potential problem especially for large codes, where n and n1 are the length of the ZRC and the number of transparent slits, respectively. To minimize σ while reducing the computational complexity at the same time, we introduce the Cross-Entropy (CE) method, an effective algorithm that solves various combinatorial optimization problems to obtain a good code. The computer simulation results show that compared with the conventional genetic algorithm (GA), the proposed CE obtains the better σ with low computational complexity.

© 2009 Optical Society of America

1. Introduction

To design optimum ZRCs, various methods have been proposed [1

1. J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, “Optimal design of optical reference signals using a genetic algorithm,” Opt. Lett. 30, 2734–2736 ( 2005). [CrossRef]

]–[7

7. J. Saez-Landete, J. Alonso, and E. Bernabeu, “Design of zero reference codes by means of a global optimization method,” Opt. Express , 13, 195–201 ( 2005). [CrossRef] [PubMed]

]. Among these methods, the performance of the genetic algorithm (GA) [1

1. J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, “Optimal design of optical reference signals using a genetic algorithm,” Opt. Lett. 30, 2734–2736 ( 2005). [CrossRef]

] is the best. However, although the GA has the design capabilities for obtaining the size of the ZRCs up to 100 elements, its performance is still not good enough. Moreover, the complexity of the GA is still high. In this paper, we consider using autocorrelation properties to design optimum ZRCs for optical applications based on the Cross-Entropy (CE) method [8

8. R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method. (Berlin, Germany, Springer, 2004).

]. In the proposed CE method, we first define the secondary maximum of the autocorrelation signal as the score function. The score function is then translated into a stochastic approximation problem that can be solved effectively. The computer simulation results show that compared with the conventional GA, the proposed CE method obtains better performance with low computational complexity.

2. Description and problem definition

The problem definition and assumption of this paper basically follows [1

1. J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, “Optimal design of optical reference signals using a genetic algorithm,” Opt. Lett. 30, 2734–2736 ( 2005). [CrossRef]

]. Let us consider a ZRC comprised of a group of unequally spaced transparent and opaque slits, where the transparent and opaque regions in the ZRC are assumed integer multiples of the width of a single slit. Mathematically, a ZRC can be described by a binary sequence with length n as follows:

c=[c1,c2,,cn],ci{0,1},
(1)

where ci=1 if a transparent slit is located at the ith position, and ci=0 elsewhere. In order to calculate the reference signal, we assume a parallel ray beam and neglect the distance between the two ZRCs, as done in [1

1. J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, “Optimal design of optical reference signals using a genetic algorithm,” Opt. Lett. 30, 2734–2736 ( 2005). [CrossRef]

]. Accordingly, we can use the autocorrelation approximation to design a good optical reference signal. The autocorrelation function provides a measure of how closely the sequence matches a copy of itself as the copy is shifted k units in time. Hence, the autocorrelation of sequence (1) can be expressed as

Sk(c)=i=1nkcici+k,
(2)

where the maximum value of the autocorrelation signal occurs at the origin S 0=∑n i=1 c 2 i, that is, the number of the transparent slits in the code.

ω*=argminωqΩCsel(ωq),
(3)

where

Csel(ωq)=max{S1(ωq),,Sn1(ωq)},
(4)

ω * denotes the global optimum of the objective function, and ωq is the indicator of the selected subset of the feasible sequences, which can be defined by

ωq={Ii}i=1n,Ii{0,1},q=1,2,,Q
(5)

where i is the index of the binary sequence and the indicator function Ii shows whether a transparent slit is located at the ith position. Moreover, we denote the set of all Q=(nn1) possible subsets as Ω={ω 1,…,ωQ}, where (ab) denotes the binomial coefficient, a!/[b! (a-b)!].

3. Design methodology

Step 1) Set the iteration counter t :=1 and initialize probability vector P(0)={pi(0)}i=ln,, pi(0)=12, where the probability vector p=[p 1,…, pn] is the only parameter needed for the proposed CE method, and pi indicates the probability of a transparent slit is located at the ith position.

Step 2) Use the density function f(ωq,p (t-1)) to generate randomsamples {ωq(m)}m=1M,, where M is the total number of samples and each element of ωq is modeled as an independent Bernoulli random variable with the probability distribution P(Ii(ωq)=1)=1-P(Ii(ωq)=0)=pi, i=1,…,n. The probability distribution is defined as

f(ωq,p)=i=1npiIi(ωq)(1pi)1Ii(ωq).
(6)

Step 3) Calculate the fitness function according to (4) to obtain a set of performance values {Csel(ω.(m,t) q)}M m=1.

Step 4) Order the performance values from the smallest to the biggest, C (1) sel≤⋯≤C (M) sel, and select the best Melite elite performance values according to the predetermined quantile parameter r(t)=C (⌈ρM⌉) sel, where ρ denotes the fraction of the best samples and ⌈ρM⌉ is the integer part of ρM.

Step 5) Calculate the parameter p (t) according to

pi(t)=m=1MI{Csel(ωq(m,t))r(t)}Ii(ωq(m,t))m=1MI{Csel(ωq(m,t))r(t)}.
(7)

where I{Csel(ωq(m,t))r(t)} is an indicated variable defined by

I{Csel(ωq(m,t))r(t)}={1,ifCsel(ωq(m,t))r(t)0,otherwise.
(8)

Step 6) Update the parameter p (t) smoothly via

p(t)=λ×p(t)+(1λ)×p(t1),
(9)

where λ is the smoothing parameter, with 0<λ≤1. It is obvious that we have the original updating rule for λ=1.

Step 7) Repeat step 2 to step 6 for t:=t+1 until the stopping criterion is met. Here, the stopping criterion is the predefined number of iterations.

4. Results and discussion

Simulations were conducted to verify the performance improvement of the ZRC introduced by the proposed algorithm. For comparison, we also tested the conventional GA [1

1. J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, “Optimal design of optical reference signals using a genetic algorithm,” Opt. Lett. 30, 2734–2736 ( 2005). [CrossRef]

], which was run with crossover probability Pc=0.6, mutation probability Pm=0.1, 500 generations, and a population of 100 individuals. It should be noted that the simulation parameters described above for GA is exactly the same as that in [1

1. J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, “Optimal design of optical reference signals using a genetic algorithm,” Opt. Lett. 30, 2734–2736 ( 2005). [CrossRef]

]. Furthermore, in order to clarify the performance differences among the algorithms, we also numerically evaluated the theoretical lower bound for the second maximum. This lower bound was established by Li [4

4. Y. Li, “Optical valve using bar codes,” Optik 79, 67–74 ( 1988).

] and is expressed as

σ(2n+1)(2n+1)24n1(n11)2.
(10)

Regarding the parameters used in the proposed CE algorithm, the smoothing parameter λ is 0.7, M=100, ρ=0.1, and the algorithm is stopped when the iteration number exceeds 500.

Fig. 1. Comparison of the second maximum reached with the GA, the CE method, and the theoretical lower bound. The code length is 200, and n 1 varies from 1 to 199.

Experiment 1:We fix the number of elements, n=200, and determine how the second maximum s of various algorithms are affected by a variable number of slits, n 1, in the interval from 1 to 199. Fig. 1 shows the value of the second maximum reached using the GA, the CE method, and the theoretical lower bound. It is observed that 1) the height of the second maximum increases when the number of slits increases1; 2) when the number of slits is small, it is possible for the GA and the CE method to reach the theoretical lower bound; and 3) the proposed algorithm is superior to the GA. In order to make it more easy for readers to distinguish the improvement of the proposed CE method as compared to GA, Fig. 2 shows the improved percentage of CE as compared to GA versus the number of slits n 1, where the improved percentage with the number of slits n 1 is defined as

improvedpercentage(n1)=σGA(n1)σCE(n1)σGA(n1)×100%,
(11)

where σGA (n 1) and σCE (n 1) are the value of the second maximum of GA with the number of slits n 1 and the value of the second maximum of CE with the number of slits n 1, respectively. As shown in Fig. 2, we can see that the proposed CE method has better improvement in most cases. In a fewer cases, the proposed CE method at least provides the same performance as that of GA.

Next, let us explain the reason for the improvement of the proposed CE method. As compared to conventional evolution algorithms, such as GA, the CE method has two special characteristics. First, instead of maintaining a simple solution candidate in each time step for conventional optimization algorithms, the main idea of the CE method is to maintain a distribution of possible solutions, which makes evolutionary computing with the distribution representation have a better characteristic in terms of solutions diversity. Second, the update rules are very simple. Instead of selection, crossover, and mutation operators in GA, CE adaptively updates this distribution according to Kullback-Leibler distance, that is, cross entropy, between the associated density and the optimal importance sampling density. As a result, one constructs a random sequence of solutions which converges (probabilistically) to the optimal or, at the least, to a reasonable solution.

Fig. 2. The improved percentage of CE as compared to GA versus the number of slits n 1.

Experiment 2: We consider another scenario for large codes with n=1000 elements and n 1=100. In Fig. 3, we show one of the resulting ZRCs provided by the proposed algorithm for n=1000 elements and n 1=100. Fig. 4 shows the optimal autocorrelation signal with respect to the relative displacement between the codes. In Fig. 4, the value of the second maximum is 11 after performing the proposed CE method. However, with the same scenario, the value of the second maximum of the GA is 13 [1

1. J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, “Optimal design of optical reference signals using a genetic algorithm,” Opt. Lett. 30, 2734–2736 ( 2005). [CrossRef]

]. It is obvious that the proposed algorithm outperforms the GA. It should be noted that if no design was done, the value of the second maximum is 152. However, after performing GA and the proposed CE method, the second maximums can be further reduced to 13 and 11, respectively. In this case, there are 13% and 27% reductions in the second maximum value for GA and CE, respectively, as compared to that without design.

Fig. 3. A ZRC found by the proposed CE method with n=1000 and n 1=100.
Fig. 4. Autocorrelation signal generated with an optimum code. The length of the code is 1000, and n 1=100. The value of the second maximum is 11.
Fig. 5. Average height of the second maximum versus iterations.

5. Conclusion

Footnotes

11If the number of slits is less, the second maximum is less. However, if the number of slits is even lesser, the corresponding maximum value of the autocorrelation signal is also less. In this case, the signal registered in the photodiode will be decreased. This is because such signal is the autocorrelation of the transmittances of ZRC. As a result, it is difficult for a photodiode to detect a small signal amplitude since we have to take dark noise and environmental noise into consideration. In general, the lower bound of the number of slits is restricted to the sensitivity of a optoelectronic receiver. In practical application, this electronic requirement establish a minimum of the signal-to-noise ratio of the zero reference signal. This requirement determines the minimum number of slits of ZRC. Based on the above-mentioned requirement, we have n and n 1 predetermined, and we have to minimize the second maximum of the signal, σ.
22If no design was done, we may randomly generate a binary ZRC c=[c 1,c 2,…,cn], where ci∊{0,1}. In this case, however, we still need an extra operation to fit the problem definition. This is because ZRC c is a binary vector subject to constraint, which is the restricted number of the transparent slits n 1. Therefore, we need an extra operation to fix the number of 1s in the binary vector c; that is, the restricted number of the transparent slits n 1. This can be carried out by the restricted search operator [9

9. S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, “Enhancing genetic feature selection through restricted search and Walsh analysis,” IEEE Trans. Syst., Man, Cybern. C, Appl. Rev. 34, 398–406 ( 2004). [CrossRef]

], which randomly adds or removes the necessary 1s to meet the number of the transparent slits. Assume the number of 1s in c and the restricted number are np and n 1, respectively. If np<n 1, the restricted search operator adds (n 1-np) 1s randomly; and if np>n 1, the restricted search operator randomly selects (np-n 1) 1s and removes them from the binary vector c. After performing the restricted search operation, a randomly generated ZRC will meet the problem constraint. However, the secondary maximum of the autocorrelation of a randomly generated ZRC with extra operation is almost equal to 15 according to our numerical experiments.

References and links

1.

J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, “Optimal design of optical reference signals using a genetic algorithm,” Opt. Lett. 30, 2734–2736 ( 2005). [CrossRef]

2.

X. Yang and C. Yin, “A new method for the design of zero reference marks for grating measurement systems,” J. Phys. E, Sci. Instrum. 19, 34–37 ( 1986). [CrossRef]

3.

Y. Li, “Autocorrelation function of a bar code system,” J. Mod. Opt. 34, 1571–1575 ( 1987). [CrossRef]

4.

Y. Li, “Optical valve using bar codes,” Optik 79, 67–74 ( 1988).

5.

Y. Li, “Characterization and design of bar code systems for accurate alignment,” Appl. Opt. 27, 2612–2620 ( 1988). [CrossRef] [PubMed]

6.

Y. Li and F. T. S. Yu, “Design of bar code systems for accurate alignment: a new method,” Appl. Opt. 29, 723–725 ( 1990). [CrossRef] [PubMed]

7.

J. Saez-Landete, J. Alonso, and E. Bernabeu, “Design of zero reference codes by means of a global optimization method,” Opt. Express , 13, 195–201 ( 2005). [CrossRef] [PubMed]

8.

R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method. (Berlin, Germany, Springer, 2004).

9.

S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, “Enhancing genetic feature selection through restricted search and Walsh analysis,” IEEE Trans. Syst., Man, Cybern. C, Appl. Rev. 34, 398–406 ( 2004). [CrossRef]

OCIS Codes
(050.2770) Diffraction and gratings : Gratings
(120.0120) Instrumentation, measurement, and metrology : Instrumentation, measurement, and metrology
(120.3940) Instrumentation, measurement, and metrology : Metrology
(220.0220) Optical design and fabrication : Optical design and fabrication
(230.0230) Optical devices : Optical devices

ToC Category:
Diffraction and Gratings

History
Original Manuscript: August 18, 2009
Revised Manuscript: November 14, 2009
Manuscript Accepted: November 15, 2009
Published: November 19, 2009

Citation
Jung-Chieh Chen, "Design of zero reference codes using cross-entropy method," Opt. Express 17, 22163-22170 (2009)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-17-24-22163


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. J. Saez-Landete, S. Salcedo-Sanz, M. Rosa-Zurera, J. Eusebio, and A. Bernabeu, "Optimal design of optical reference signals using a genetic algorithm," Opt. Lett. 30, 2734-2736 (2005). [CrossRef]
  2. X. Yang and C. Yin, "A new method for the design of zero reference marks for grating measurement systems," J. Phys. E., Sci. Instrum. 19, 34-37 (1986). [CrossRef]
  3. Y. Li, "Autocorrelation function of a bar code system," J. Mod. Opt. 34, 1571-1575 (1987). [CrossRef]
  4. Y. Li, "Optical valve using bar codes," Optik 79, 67-74 (1988).
  5. Y. Li, "Characterization and design of bar code systems for accurate alignment," Appl. Opt. 27, 2612-2620 (1988). [CrossRef] [PubMed]
  6. Y. Li and F. T. S. Yu, "Design of bar code systems for accurate alignment: a new method," Appl. Opt. 29, 723-725 (1990). [CrossRef] [PubMed]
  7. J. Saez-Landete, J. Alonso, and E. Bernabeu, "Design of zero reference codes by means of a global optimization method," Opt. Express 13, 195-201 (2005). [CrossRef] [PubMed]
  8. R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method. (Berlin, Germany, Springer, 2004).
  9. S. Salcedo-Sanz, G. Camps-Valls, F. Perez-Cruz, J. Sepulveda-Sanchis, and C. Bousono-Calzon, "Enhancing genetic feature selection through restricted search and Walsh analysis," IEEE Trans. Syst., Man. Cybern. C, Appl. Rev. 34, 398-406 (2004). [CrossRef]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited