# Binary sequences design using MGA.

IntroductionBinary codes have been widely used in radar and communication areas, but the synthesis of binary codes with good Discriminating factor is a nonlinear multivariable optimization problem, which is usually difficult to tackle.

The Genetic Algorithm (GA) technique proved to be an efficient and powerful tool to find optimal or near optimal solutions for complex multivariable nonlinear functions [1] but has slow convergence rate. The concept of Hamming scan algorithm has been employed for obtaining the pulse compression sequences at larger lengths with good correlation properties [2,3]. This algorithm has fast convergence rate but has demerit the viz., the tendency to be stuck with local minima. The MGA has global minimum estimation capability of GA algorithm and fast convergence rate of Hamming scan algorithm [2,3]. The MGA has proved more efficient and powerful tool to find optimal or near optimal solutions for complex multivariable nonlinear functions

Binary codes with low autocorrelation sidelobe levels and high Discriminating factors are useful for radar pulse compression [4], channel estimation, and spread spectrum communication applications.

The aperiodic autocorrelation function (ACF) of sequence S of length N is given as,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ... (1)

If all the sidelobes of the ACF of any binary sequence are bounded by

[absolute value of A (k)] [less than or equal to] 1, 1 [less than or equal to] | k [less than or equal to] N-1 ...(2)

then the sequence is called a generalized Barker sequence. In 1953[5] Barker introduced binary sequences for lengths N = 2,3,4,5,7,11, and 13, fulfilling the condition in (2).

Binary code is one of the most commonly used radar pulse compression signals due to the easy signal generation and processing. Therefore, binary code is increasingly becoming a favorable choice for radar signals and will be used as the basic code form for radar. In this paper, MGA is used for the design of Binary sequences which have good discriminating factors.

Binary Sequences Design

A binary coded sequence of length N bits is represented by

S = [ [s.sub.1], [s.sub.2], [s.sub.3],.... ,[s.sub.N]] ...(3)

where value of s is either 1 or -1. A more practical approach to design a binary sequences with low autocorrelation sidelobe levels and high discriminating factors is to numerically search the best Binary sequences by minimizing a cost function that measures the degree to which a specific result meets the design requirements. For the design of binary sequences, the cost function is based on the sum of autocorrelation sidelobes energy. Hence, from (1) the cost function can be written as,

E = [N-1.summation over (k [not equal to] 0)] [[absolute value of A(k)].sup.2] ...(4)

the minimization of cost function in (4) generate binary sequences with high discriminating factors.

Discriminating Factor (DF)

The discriminating factor (DF) is defined by Golay[6] as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ... (6)

Hence the largest value of DF better is the sequence S. One criterion for the selection of a sequence S is to have a larger value of DF even at larger lengths. This criterion has greater analytical tractability and constitutes accurate measures of self-generated clutter in applications such as radar and Spread-Spectrum (SS) techniques but is more demanding on computer time.

Genetic Algorithm (GA)

GA technique, introduced by John Holland at University of Michigan proved efficient and powerful tool to find optimal or near optimal solutions for complex multivariable nonlinear functions. The major advantage of the GA algorithm over the traditional "greedy" optimization algorithms is the ability to avoid becoming trapped in local optima during the search process.

The genetic algorithm creates a population of solutions and applies genetic operators such as crossover and mutation to evolve the solutions in order to find the best one(s). The three most important aspects of using genetic algorithms are: (1) definition of the objective function, (2) definition and implementation of the genetic representation, and (3) definition and implementation of the genetic operators. Once these three have been defined, the genetic algorithm should work fairly well. But the limitation of GA is slow convergence rate. This limitation is overcome in modified Genetic algorithm.

Hamming Scan Algorithm (HSA)

The HSA is a traditional greedy optimization algorithm, which searches in the neighborhood of the point in all directions to reduce the cost function and has fast convergence rate. The Mutation is a term metaphorically used for a change in an element in the sequence. For example if a code element 1 of sequence S, is mutated by -1, and the cost for mutated element is evaluated. If the cost is reduced due to mutation, the new element is accepted; otherwise, the original code element is retained. This process is recursively applied to the entire sequence. The HSA mutates all the code elements in the given sequence one by one and looks at all the first order-Hamming neighbors of the sequence. Thus, Hamming scan performs recursively local search among all the Hamming-1 neighbors of the sequence and selects the one whose objective function value is minimum.

Modified Genetic Algorithm (MGA)

Modified Genetic Algorithm is proposed as a statistical technique for obtaining approximate solutions to combinatorial optimization problems [7]. The MSA is a combination of Genetic Algorithm (GA) and Hamming Scan algorithms. It combines the good methodologies of the two algorithms like global minimum converging property of GA algorithm and fast convergence rate of Hamming scan algorithm. The demerit of Hamming scan algorithm is that it gets stuck in the local minimum point because it has no way to distinguish between local minimum point and a global minimum point. Hence it is sub-optimal. The drawback in Genetic algorithm is that it has a slow convergence rate because even though it may get closer to the global minimum point, it may skip it because of the methodology it employs. The MGA overcomes these drawbacks.

It is quite effective to combine GA with Hamming Scan (HSA) Algorithm. GA tends to be quite good at finding generally good global solutions, but quite inefficient at finding the last few mutations to find the absolute optimum. Hamming Scan is quite efficient at finding absolute optimum in a limited region. Alternating MGA improve the efficiency of GA while overcoming the lack of robustness of HSA.

MGA are introduced as a computational analogy of adaptive systems. They are modeled loosely on the principles of the evolution via natural selection, employing a population of individuals that undergo selection in the presence of variation-inducing operators such as mutation and recombination. A fitness function is used to evaluate individuals, and reproductive success varies with fitness.

Binary Sequences Design Using MGA

The flowchart of MGA for optimizing the binary codes is shown in Fig.1. The MGA is a combination of both GA and Hamming scan algorithms. In this flow chart ; g, L, DF, N, i, [p.sub.c], [p.sub.m] mean number of desired iteration, desired number of optimum sequences, desired discriminating factor, sequence length, iteration counter, probability of crossover and probability of mutation. The computational cost for searching the best binary, sequence of length N, through an exhaustive search, i.e., minimizing eq. (4), is grows exponentially with the code length. Therefore, the numerical optimization of Binary sequences is an NP-complete problem. During the optimization process of Binary sequences, the random search is carried out through "crossover" and "mutation", i.e., randomly selecting an entry in the eq. (3) and replacing it with different admissible value with probability of [p.sub.c] and [p.sub.m] respectively. The next step of the algorithm is to invoke the Hamming scan to find the optimum sequence in the vicinity of sequence selected by GA.

[FIGURE 1 OMITTED]

Result Analysis

Binary sequences are designed using the MGA. The cost function for the optimization is based on eq.(4). In this paper all the synthesized results are single realizations obtained using Pentium-IV, processor. Some of the synthesized binary sequences, with good autocorrelation properties are presented. Table I shows the comparison between Literature and synthesized sequences of different length varying from 71 to 4098. In table 1, column 1, shows sequence length, N, column 2 shows the Autocorrelation sidelobes peaks (ASPs) reported in the literature, column 3 shows the synthesized ASPs and column 4 shows the reference of literature in which column two values are reported. The ASP is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ... (7)

From the table I it can be shown the synthesized values are better than literature values. Table II shows the comparison of Discriminating Factors (DF) of Literature and synthesized sequences of length from 71 to 4098. In table II, column 1, shows code lengths, column 2 shows the DFs reported in the literature, column 3, shows DFs of synthesized sequence. As shown in the table II the synthesized DFs are better than literature DF values.

Table III shows the comparison between Literature and synthesized value of sequence of length 126 only. In table III, column 1, shows Hex format of code, column 2 shows the Autocorrelation Sidelobe Peak(ASP), column 3, shows Discriminating Factor (DF) and column 4 shows the source of information. As shown in the table the DF of literature is 11.45 while synthesized code DF value is 15.75. The synthesized sequence has discriminating factor 37.5% better than sequences reported in the literature [8].

Fig. 2 shows Autocorrelation Function (ACF) of designed sequence of length 4096. The ACF is almost an impulse function, which indicates that synthesized code generate very less self clutter. So we can say that design sequences are very useful for radar as well as for communication system. From above results it is clear that synthesized sequences autocorrelation properties are far better than literature values. These result proved the efficiency of MGA.

[FIGURE 2 OMITTED]

Conclusions

An effective Modified Genetic algorithm has been used for designing the Binary sequences which can be used in radar systems and spread spectrum communications for significantly improving performance of the system. This new approach combines the GA and the Hamming Scan algorithms and provides a powerful tool for the design of binary sequences. With the proposed optimization algorithm, the binary sequences are designed with different code lengths, N.

The designed sequences have better autocorrelation value than literature which has proved the efficiency of MGA. The synthesized binary sequences are promising for practical application to radars and communications.

References

[1] De Jong. K. A., "Genetic algorithms: a 10 year perspective", In J.J. Grefenstette (Ed.). Proc. First Internat. Conference on Genetic Algorithms. Lawrence Erlbaum Associates, Hillsdade: pp. 169-177, 1985.

[2] Moharir.P.S, Singh.R.and Maru. V.M., "S-K-H algorithm for signal design", Electronics letters, Vol 32, no 18, Aug 1996, pp.1642-1649.

[3] Moharir.P.S and Maru. V.M and Singh.R., "Bi-parental Product algorithm for coded waveform design in radar", Sadhana, Vol.22, no.5, Oct. 1997, pp 589599.

[4] E. C. Farnett and G. H. Stevens, "Pulse compression radar," Radar Handbook, Second ed. New York: McGraw-Hill, 1990.

[5] Barker, R.H: "Group synchronizing of binary digital system" in Jackson, W, (Ed): Communication theory ( Butterworths, London, 1953), pp. 273-287.

[6] Golay. M.J.E., "The merit factor of long low autocorrelation binary sequences", IEEE Trans. on Inform. Theory, IT-28, 1982, pp 543-549.

[7] S.P Singh., and K. Subba Rao., "Sixty-phase Code Design Using Modified GA" Proc of RACE -08, OU, Hyderabad, Dec 08.

[8] Maryam Amin Nasrabadi "A new approach for long Low autocorrelation binary sequence problem using genetic algorithm" IEEE proceeding, 2006.

[9] Ferrara, M. "Near-optimal peak sidelobe binary codes". Presented at the IEEE 2006 National Radar conference, Syracuse, NY, Apr. 2006.

[10] Kerdock, A., Mayer, R., and Bass, D. "Longest binary pulse compression codes with given peak sidelobe levels" Proceedings of the IEEE, 74, 2 (Feb. 1986), 366.

[11] Golay, M. J. E., and Harris. D. J. "A new search for skew symmetric binary sequences with optimal merit factors" IEEE Transactions on Information Theory, 36, 5 (Sept.1990), 1163-1166.

[12] Jedwab, J., Ferguson, R., and Knauer, J. "Merit factor records" Simon Fraser University, CECM, Oct. 2004. Reported at http://www.cecm.sfu.ca/~jknauer/lbs/recores.html.

[13] Deng, X., and Fan, P. "New binary sequences with good aperiodic autocorrelations obtained by evolutionary algorithm" IEEE Communication Letters, 3, 10 (Oct. 1999), 288-290.

[14] Militzer, B., Zamparelli, M., and Beule, D. "Evolutionary search for low autocorrelated binary sequences" IEEE Transactions on Evolutionary Computing, 2 (1998), 34-39.

[15] Coxson, G. E., and Russo, J. "Efficient exhaustive search for optimal peak sidelobe binary codes" In Proceedings of the IEEE 2004 National Radar Conference, Philadelphia, PA, Apr. 2004.

[16] Beenker, G. F. M., Claasen, T. A. C. M., and Hermens, P. W. C. "Binary sequences with a maximally flat amplitude spectrum" Phillips Journal of Research, 40 (1989), 289-304.

[17] Anna Dzvonkovskaya, Hermann Rohling "Long Binary Phase Codes with Good Autocorrelation Properties" IEEE Xplore 2008.

(1) S.P Singh, (2) S. Srinivasa Rao and (3) S. Babu Rao

(1,2) ECE Dept, MGIT, Hyderabad, India E-mail: singh_spgahlot@rediffmail.com

(3) ECE Dept, MRCET, HYDERABAD. India

Table 1: Comparison of ASP of literature and Synthesized sequences. Sequence Literature Synthesized Ref Length ASP ASP 71 5 4 [16] 73 6 4 [12] 75 6 4 [12] 77 6 4 [13] 79 6 4 [12] 81 6 4 [12] 83 6 5 [13] 86 6 5 [12] 87 6 5 [12] 89 6 5 [12] 91 7 5 [11] 93 6 5 [12] 95 7 5 [13] 97 7 5 [13] 100 7 5 [13] 101 7 5 [14] 103 7 5 [13] 104 8 5 [12] 105 11 5 [11] 250 12 11 [17] 300 14 13 [17] 304 14 13 [17] 512 20 19 [17] 550 20 19 [17] 800 26 24 [17] 900 26 25 [17] 950 28 27 [17] 1024 30 28 [17] 1500 40 36 [17] 2000 44 43 [17] 2048 44 41 [17] 2197 47 46 [17] 3000 58 54 [17] 4096 68 63 [17] Table II: Comparison of DF of literature and synthesized sequences. Sequence Literature Synthesized Length DF DF 71 14.2 17.75 73 12.17 18.25 75 12.50 18.75 77 12.83 19.25 79 13.17 19.75 81 13.50 20.25 83 13.83 16.6 85 14.17 17 87 14.50 17.4 89 14.83 17.8 91 13.00 18.2 93 15.50 18.6 95 13.57 19 97 13.86 19.4 100 14.29 20 101 14.43 20.2 103 14.71 20.6 104 13.00 20.8 105 9.55 21 250 20.83 22.73 300 21.43 23.08 304 21.71 23.38 512 25.60 26.95 550 27.50 28.95 800 30.77 33.33 900 34.62 36.00 950 33.93 35.19 1024 34.13 36.57 1500 37.50 41.67 2000 45.45 46.51 2048 46.55 49.95 2197 46.74 47.76 3000 51.72 55.56 4096 60.24 65.00 Table III: Comparison between literature value [8] and synthesized sequences value. Hex format of binary Code ASP DF Source 2 E 2 0 0 6 A 6 3 11 11.45 Ref [8] 0 B C 6 C C 9 0 7 9 6 2 8 4 2 B E 1 F D 2 1 A 0 5 D 1 7 E 9 D 8 15.75 Synthesized B 5 2 0 2 2 4 9 E 5 0 0 7 5 A 8 C 4 E 6 1 C 7 6

Printer friendly Cite/link Email Feedback | |

Author: | Singh, S.P.; Rao, S. Srinivasa; Rao, S. Babu |
---|---|

Publication: | International Journal of Computational Intelligence Research |

Date: | Oct 1, 2010 |

Words: | 2614 |

Previous Article: | Intelligent path planning with A* search algorithm. |

Next Article: | Visitor tunes in social networks: concept and implementation. |

Topics: |