## Design of zero reference codes using cross-entropy method

Optics Express, Vol. 17, Issue 24, pp. 22163-22170 (2009)

http://dx.doi.org/10.1364/OE.17.022163

Acrobat PDF (143 KB)

### 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* and *n*_{1} 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

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]

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. 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]

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. Description and problem definition

**30**, 2734–2736 (
2005). [CrossRef]

*n*as follows:

*c*=1 if a transparent slit is located at the ith position, and

_{i}*c*=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

_{i}**30**, 2734–2736 (
2005). [CrossRef]

*k*units in time. Hence, the autocorrelation of sequence (1) can be expressed as

*S*

_{0}=∑

^{n}_{i=1}

*c*

^{2}

*, that is, the number of the transparent slits in the code.*

_{i}*S*

_{1},…,

*S*

_{n-1}}, must be as low as possible. Given a fixed length of the ZRC,

*n*, and the number of transparent slits,

*n*

_{1}, the objective of the optical reference signal design is to search for an optimal ZRC that minimizes the second maximum of the autocorrelation signal σ. Consequently, we can formulate the optimal ZRC design as a combinatorial optimization problem as

*ω*^{*}denotes the global optimum of the objective function, and

*is the indicator of the selected subset of the feasible sequences, which can be defined by*

**ω**_{q}*i*is the index of the binary sequence and the indicator function

*I*shows whether a transparent slit is located at the ith position. Moreover, we denote the set of all

_{i}**Ω**={

*ω*

_{1},…,

*ω*}, where

_{Q}*a*!/[

*b*! (

*a*-

*b*)!].

**30**, 2734–2736 (
2005). [CrossRef]

*n*

_{1}that is restricted to the sensitivity of an optoelectronic receiver. In practical application, this electronic requirement establishes a minimum of the signal-to-noise ratio of zero-reference signals. Further, this requirement determines the minimum number of slits

*n*

_{1}of ZRC. According to the above-mentioned working requirements, we have

*n*and

*n*

_{1}predetermined. In this case, we can make sure the design of ZRC is workable. However, we do not consider other imperfect factors, such as diffraction and signal noise, in the proposed optical system in this study. The focus of our work is to introduce an efficient CE method to minimize the second maximum of the signal under the same scenario of previous works. Accordingly, the issue of imperfect factors is beyond the scope of this paper.

## 3. Design methodology

**Step 1**) Set the iteration counter

*t*:=1 and initialize probability vector

**p**=[

*p*

_{1},…,

*p*] is the only parameter needed for the proposed CE method, and

_{n}*p*indicates the probability of a transparent slit is located at the

_{i}*i*th position.

**Step 2**) Use the density function

*f*(

*,*

**ω**_{q}**p**

^{(t-1)}) to generate randomsamples

*M*is the total number of samples and each element of

*is modeled as an independent Bernoulli random variable with the probability distribution*

**ω**_{q}*P*(

*I*(

_{i}*)=1)=1-*

**ω**_{q}*P*(

*I*(

_{i}*)=0)=*

**ω**_{q}*p*,

_{i}*i*=1,…,

*n*. The probability distribution is defined as

**Step 3**) Calculate the fitness function according to (4) to obtain a set of performance values {

*C*(

_{sel}**ω**.

^{(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

*M*elite performance values according to the predetermined quantile parameter

^{elite}*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

**Step 6**) Update the parameter

**p**

^{(t)}smoothly via

*λ*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

**30**, 2734–2736 (
2005). [CrossRef]

*P*=0.6, mutation probability

_{c}*P*=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

_{m}**30**, 2734–2736 (
2005). [CrossRef]

*λ*is 0.7,

*M*=100,

*ρ*=0.1, and the algorithm is stopped when the iteration number exceeds 500.

**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 increases

^{1}; 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

*(*

_{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.

**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

**30**, 2734–2736 (
2005). [CrossRef]

^{2}. 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.

*n*=1000 elements and

*n*

_{1}=100. However, as shown in [1

**30**, 2734–2736 (
2005). [CrossRef]

*n*=1000 elements and

*n*

_{1}=100. Therefore, the proposed CE method can offer better ZRC while keeping a low complexity.

## 5. Conclusion

## Footnotes

1 | ^{1}If 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, σ. |

2 | ^{2}If no design was done, we may randomly generate a binary ZRC c=[c
_{1},c
_{2},…,c], where _{n}c∊{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 _{i}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 [99. 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. s to meet the number of the transparent slits. Assume the number of 1s in c and the restricted number are n and _{p}n
_{1}, respectively. If n<_{p}n
_{1}, the restricted search operator adds (n
_{1}-n) 1_{p}s randomly; and if n>_{p}n
_{1}, the restricted search operator randomly selects (n-_{p}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. |

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. |

3. | Y. Li, “Autocorrelation function of a bar code system,” J. Mod. Opt. |

4. | Y. Li, “Optical valve using bar codes,” Optik |

5. | Y. Li, “Characterization and design of bar code systems for accurate alignment,” Appl. Opt. |

6. | Y. Li and F. T. S. Yu, “Design of bar code systems for accurate alignment: a new method,” Appl. Opt. |

7. | J. Saez-Landete, J. Alonso, and E. Bernabeu, “Design of zero reference codes by means of a global optimization method,” Opt. Express , |

8. | R. Y. Rubinstein and D. P. Kroese, |

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. |

**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: Year | Journal | Reset

### References

- 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]
- 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]
- Y. Li, "Autocorrelation function of a bar code system," J. Mod. Opt. 34, 1571-1575 (1987). [CrossRef]
- Y. Li, "Optical valve using bar codes," Optik 79, 67-74 (1988).
- Y. Li, "Characterization and design of bar code systems for accurate alignment," Appl. Opt. 27, 2612-2620 (1988). [CrossRef] [PubMed]
- 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]
- 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]
- R. Y. Rubinstein and D. P. Kroese, The Cross-Entropy Method. (Berlin, Germany, Springer, 2004).
- 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.