US 2007/0106480 A1Application

Method and system for generating sequences with specific characteristics using adaptive genetic algorithm

Publication Date:2007-05-10

•31 Claims

•8 Drawing Sheets

Abstract

Embodiments of the present invention relates to generating sequences, wherein the sequences are used in a communication system and the method comprises the following operations: 1) generating a plurality of sequences with a predetermined length randomly; 2) computing a specific parameter value of each sequence; 3) selecting a plurality of sequences whose computed specific parameter value accords with a certain conditions; 4) mutating the selected sequences with an adaptive genetic algorithm and adaptively selecting the sequences with the mutated and optimized specific parameter value according to the probability; 5) repeating the above operations until the predetermined number of times and selecting the sequences with the optimal specific parameter value among the final sequences as the output sequences. An embodiment of the present invention includes a system for generating sequences with specific characteristics. According to one embodiment of the present invention, sequences with specific characteristics can be obtained in a broad range and the present invention is highly adaptive and versatile. Once the evaluation indicator corresponding to the specific characteristic is designated, sequences used in many fields can be found.

Metadata

Assignee

NTT DoCoMo Inc.

Inventors

Xiaoming Dai
Lan Chen

Application Information

Application Number:US 11/510,355

Filing Date:2006-08-25

Priority Date:2005-08-26

Classifications

IPC:

G06F19/00G06F15/18

Patent Drawings (8 sheets)

Description

Priority

[0001] The present patent application claims priority to the corresponding Chinese patent application serial no. 200510093526.X, titled, “Method and System for Generating Sequences with Specific Characteristics Using Adaptive Genetic Algorithm” filed on Aug. 26, 2005.

Field of the Invention

[0002] The present invention relates to a method and system for generating sequences, especially to a method and system for generating sequences with low autocorrelation function and low sidelobe using an adaptive genetic algorithm.

Background of the Invention

[0003] Sequences such as pseudorandom sequence with specific length are widely used in many science and project fields, such as in the wireless communication, the satellite communication and the optical fiber communication, etc.

[0004] Since the frequency of the digital baseband signal is high, the new generation broadband wireless communication system requires for sequences with high performance in order to satisfy specific needs, for example, sequences with good aperiodic autocorrelation function characteristic and low sidelobe for cell selection, synchronization and channel estimation, etc.

[0005] Currently, two types of methods are available to design sequences with specific characteristics. The first method generates these sequences with exhaustive search. However, generally the length of these sequences is comparatively short, since for a sequence with the length L, there are 2^Lprobabilities. Accordingly, for a sequence with L=64, the number of probabilities is 2⁶⁴=1.8447e+019, which is far beyond the current computing capability, while generally the sequence length of the new generation broadband wireless communication system is more than 64.

[0006] The second method generates the sequences with a fixed length (63, 127, etc.) with theory of numbers such as Golay code. However, this method cannot generate sequences of any length with low autocorrelation function and cannot meet the requirements of different wireless communication system designs.

[0007] Currently (even in the foreseeable future), it is impossible to generate a 128-bit downlink synchronization sequence used in Wimax with an exhaustive search.

[0008] Therefore, a method and system that can overcome the above disadvantages and generate sequences with specific characteristics is needed.

Summary of the Invention

[0009] A method and system for generating sequences with specific characteristics using adaptive genetic algorithm is described. In one embodiment, the method for generating sequences, wherein the sequences are used in a communication system, comprises following operations: generating a plurality of sequences with a predetermined length randomly; computing a specific parameter value of each sequence; selecting a plurality of sequences whose computed specific parameter value accords with a certain condition; mutating the selected sequences with an adaptive genetic algorithm and adaptively selecting the sequences with the mutated and optimized specific parameter value according to the probability; repeating the above operations a predetermined number of times and selecting the sequences with the optimal specific parameter value among the final sequences as output sequences.

Description of the Drawings

[0010] The present invention will be understood more fully from the detailed description given below and from the accompanying drawings of various embodiments of the invention, which, however, should not be taken to limit the invention to the specific embodiments, but are for explanation and understanding only.

[0011] FIG. 1 is the overall flow diagram showing the method for generating sequences with specific characteristics according to one embodiment of the present invention;

[0012] FIG. 2 is the schematic diagram showing the random generated sequences;

[0013] FIG. 3 is the schematic diagram showing the genetic selection operation of the sequences;

[0014] FIG. 4 is the schematic diagram showing the genetic crossover over operation of the sequences;

[0015] FIG. 5 is the schematic diagram showing the adaptive mutation operation of the sequences;

[0016] FIG. 6 is the schematic diagram showing the operation of whether adopting the mutated sequences;

[0017] FIG. 7 is the schematic diagram showing the mutation operation of the sequences.

[0018] FIG. 8a is the curve diagram showing the aperiodic autocorrelation function of Golay code in prior art.

[0019] FIG. 8b is the curve diagram showing the aperiodic autocorrelation function of SYNC according to one embodiment of the present invention;

[0020] FIG. 9 is the block diagram showing the system for generating sequences with specific characteristics according to one embodiment of the present invention.

[0021] The same reference sign represents the same, similar of corresponding features or functions in the above drawings.

Detailed Description of the Present Invention

[0022] A method and system for generating sequences with specific characteristics using adaptive genetic algorithm is described, wherein sequences of different length and different amount and with near theoretical value performance are generated and as a result, the communication quality is improved.

[0023] Therefore, the present invention provides a method for generating sequences, wherein the sequences are used in a communication system. In one embodiment, the method comprises following operations:

[0024] 1) generating a plurality of sequences with a predetermined length randomly;
[0025] 2) computing a specific parameter value of each sequence;
[0026] 3) selecting a plurality of sequences whose computed specific parameter value accords with a certain condition;
[0027] 4) mutating the selected sequences with an adaptive genetic algorithm and adaptively selecting the sequences with the mutated and optimized specific parameter value according to the probability;
[0028] 5) repeating operation 2) to operation 4) until a predetermined number of times and selecting the sequences with the optimal specific parameter value among the final sequences as output sequences.

[0029] In one embodiment, another operation between the operation 3) and operation 4) performs crossover over operation on the selected plurality of sequences.

[0030] In one embodiment, the specific parameter is relative to the autocorrelation function.

[0031] In another embodiment, the specific parameter is the fitness and its computation formula is:

\begin{matrix} fitness (j) = \sum_{τ = 1}^{L - 1} {θ_{u, u} (τ)}^{2} + β \cdot {PSL}_{j}^{2} & 0 \leq j \leq P - 1 \end{matrix}

θ_{u, u} (τ) = \sum_{t = 0}^{L - 1 - τ} u (t) u (t + τ), {PSL}_{j} = {{\max θ}_{u, u} (τ)}^{2}

wherein θ_u,u(τ) is the autocorrelation function of each sequence, j is the serial number of the sequence, P is the whole number of the sequences, L is the length of each sequence, PSL_jis the peak sidelobe value of each sequence and β is the equilibrium coefficient for balancing the sum of the peak sidelobe with the autocorrelation value.
The adaptive genetic mutation comprises following operations:

- [0032] a) computing the fitness of a sequence j before mutation;
- [0033] b) mutating the sequence j and getting a sequence j′ while maintaining a backup of the sequence j, computing the fitness of the sequence j′ and generating a random number r, wherein 0<r<1;
- [0034] c) determining whether the fitness of the sequence j′ is less than that of the sequence j, with r>^P^a;
- [0035] d) if yes, accepting the mutated sequence j′; if no, rejecting the mutated sequence j′ and maintaining the former sequence j;
- [0036] e) repeating operations a) to d) and continuing to mutate other sequences; wherein j is the serial number of the sequence, P_a, is a predetermined value.
  Operation 3) may comprise the following steps:
[0037] I) generating a random number r, and setting the initial numbers of integers a and j as 0,
wherein 0<r<1; $II)$ $computing \frac{P * fitness (j)}{\sum_{j = 0}^{P - 1} fitness (j)},$
if the result is less than r, putting the sequence to the next generation population and setting the serial number of the selected sequence in the new population to a and then computing a=a+1 and proceeding to operation III); if the result is equal to or bigger than r, determining the current value of j, if j<P−1, computing j=j+1; if j is equal to or bigger than P−1, computing j=j−P+1; and then returning to operation I); and thus the sequence in the next operation becoming the next sequence and operating each sequence with this cycle order;
[0038] III) determining whether the current serial number a is bigger than or equal to P−1, if yes, proceeding to operation 4); if no, determining the current value of j, if j<P−1, computing j=j+1; if j is equal to or bigger than P−1, computing j=j−P+1; and then returning to operation I).

[0039] The sequences are the downlink synchronization sequences in the wireless communication system.

[0040] The sequences are the uplink synchronization sequences in the wireless communication system.

[0041] An embodiment of the present invention also includes a system for designing and generating sequences with specific characteristics, and the system comprises:

[0042] a generation unit for generating a plurality of sequences with a predetermined length randomly;
[0043] a computation unit for computing a specific parameter value of each sequence and selecting a plurality of sequences whose computed specific parameter value accords with a certain condition;
[0044] a genetic adaptive mutation unit for performing adaptive genetic mutation on sequences and adaptively selecting sequences with the mutated and optimized specific parameter value according to the probability;
[0045] a cyclic control unit for controlling the number of cycle times of process from the computation unit to the genetic adaptive mutation unit; and
[0046] a selection unit for selecting the sequences with the optimal specific parameter value among the final sequences as the output sequences.

[0047] A genetic crossover over operation unit exists between the computation unit and the genetic adaptive mutation unit, for performing the crossover over operation on the selected plurality of sequences and sending the processed sequences to the genetic adaptive mutation unit.

[0048] According to one embodiment of the present invention, sequences with specific characteristics can be designed. And the present invention is highly adaptive and feasible. Sequences applicable in many fields can be designed through specifying the evaluation indicator function corresponding to the specific characteristic.

[0049] The preferable embodiment of the present invention will be described with reference to the drawings. And the other features, purposes and effects of the present invention will become apparent.

[0050] The present invention will be further described with reference to the drawings.

[0051] The embodiment of the present invention will be described with reference to the method for generating the binary downlink synchronization sequence in TD-SCDMA. Of course, the present invention is not limited to this embodiment for one skilled in the art. The present invention can generate sequences in other communication system, such as the uplink or downlink synchronization sequence of CDMA2000, WCDMA or WiMax. Of course, the present invention can generate sequences for other purposes.

[0052] The first step of the mobile station accessing the system is to synchronize with the current optimal cell. This process is implemented through capturing the downlink synchronization sequence (SYNC) transmitted by the cell in the downlink pilot slot. In the TD-system, system, SYNC is a 64-bit sequence predetermined by the system, and has 32 different SYNC codes. The neighboring cells in the system choose different SYNC sequences and SYNC seqences of the unneighbored cells can be multiplexed. According to the architecture of the TD-SCDMA wireless frame, the SYNC is sent every 5 ms. When the mobile station accesses the system, the 32 SYNC sequences are searched one by one (i.e. correlating the received signals with the 32 probable SYNC sequences code by code), and the sequence with the largest correlation peak is regarded as the SYNC used in the current cell. At the same time, the timing of the downlink of the system can be preliminarily determined according to the time position of the correlated peak.

[0053] FIG. 1 is the flow diagram showing the method for generating sequences with specific characteristics according to the embodiment of the present invention, i.e., the flow diagram showing the generation of the SYNC sequence with good correlation characteristics.

[0054] Firstly, the maximum number of iterations is set and the initial value of the number of iteration is 0. The maximum number of iterations can be specifically set according to the storage capacity of the computing equipment and the CPU speed, such as 10,000 times, 100,000 times or more. The higher the iterative number is, the better the characteristics of the computed sequences are. Then, the method proceeds to the following steps:

[0055] In the step S101, P sequences are generated randomly. FIG. 2 shows an example of randomly generated sequences, in which 10 binary sequences, each with the length of 42, are generated, wherein every sequence is comprised of 0 and 1 (in practice, 0 in the sequence is −1 and 1 is 1, i.e., −1 and 1 comprise the sequences in practical use) and has a serial number. Of course the value of P may be far bigger than 10 in practice and the length of the sequence may be longer than 42, such as of 64, 128, 256 or even longer length at will.

[0056] The value of P can be determined according to conditions, such as, the storage capacity of the computing equipment and the CPU speed, etc. The principle is that the bigger the value of P is, the better the result will be. However, when P exceeds a certain value, the improvement of the result will be limited. In the embodiment of the present invention, P=500.

[0057] In addition, the length L of each sequence can be any value. In the embodiment of the present invention, the length of each SYNC sequence is 64.

[0058] In the step S102, the fitness of each sequence is computed and the iteration number is increased by 1.

[0059] The fitness is an evaluation indicator, which can be designated by the user and represents the fitness of each sequence to the specific characteristic. If the user requires for a sequence with a specific characteristic, the corresponding fitness can be designated.

[0060] In the embodiment of the present invention, the evaluation indicator for the fitness adopted by each sequence is:

\begin{matrix} \begin{matrix} fitness (j) = \sum_{τ = 1}^{L - 1} {θ_{u, u} (τ)}^{2} + β \cdot {PSL}_{j}^{2} & 0 \leq j \leq P - 1 \end{matrix} θ_{u, u} (τ) = \sum_{t = 0}^{L - 1 - τ} u (t) u (t + τ), {PSL}_{j} = {{\max θ}_{u, u} (τ)}^{2} & (1) \end{matrix}

wherein θ_u,u(τ) is the autocorrelation function for each sequence, L is the length of each sequence, and PSL_jis the largest sidelobe value of each sequence, and β is the equilibrium coefficient for balancing the sum of the peak sidelobe with the autocorrelation value. The β is related with the length of the sequence and in the embodiment of the present invention, β is √{square root over (64)}=8 for the SYNC. Of course, the value of β can be other values according to the specific requirements. Since the formulas of computing the sequence autocorrelation and the peak sidelobe are known to those skilled in the art, they will not be illustrated in detail here.

[0061] The formula for computing the fitness of the sequence has been provided above and the computation of a sequence with the length of 5 bits is explained as the following:

[0062] The sequence code is [I 1 1 1 1 1]
[0063] The computation of its aperiodic autocorrelation function is:
with one bit shifted:
with two bits shifted:
with three bits shifted:
with three bits shifted:
[0064] By analogy, the aperiodic autocorrelation function is [4 3 2 1].
[0065] The peak sidelobe PSL 4, assuming β=1.
And the adaptive function $\begin{matrix} fitness (j) = \sum_{τ = 1}^{L - 1} {θ_{u, u} (τ)}^{2} + β \cdot {PSL}^{2} \\ = (4 * 4 + 3 * 3 + 2 * 2 + 1 * 1) + 1 * 4 * 4 = 46 \end{matrix}$

[0066] Obviously, the less the fitness (j) is, the better the autocorrelation characteristic of the sequence is. Therefore, in the embodiment of the present invention, the less the fitness (j) is, the better the characteristic of the sequence is.

[0067] After the step S102, the genetic selection is done in the step S103 to determine the sequence which can evolve to the population of the next generation.

[0068] As described above, since the fitness indicates the degree of adaptiveness of a sequence to the environment, i.e., the degree of satisfying the users' need, the sequence with a higher fitness conforms to the environment better. In the present embodiment, a sequence with a good autocorrelation characteristic is needed, i.e., the sequence with a small fitness (j) is needed. The smaller the autocorrelation function is, the better it can be adaptive to the environment, i.e., the fitness is bigger. (If a sequence with a bad autocorrelation characteristic is needed, it will be better to choose one with a big fitness. The sequence is selected in accordance with the practical condition.) According to the Darwin's evolutionism, the sequence has a better chance to exist and be passed down to the next generation. According to the embodiment of the present invention, the sequences are queued according to the fitness, and the one with the biggest fitness is put on the utmost top and the one with the smallest fitness is put on the utmost bottom. FIG. 3 describes the detailed strategy, including-the following steps:

[0069] 1) Summing the fitness of all the sequences in the population to be selected (the population to be selected is the one created last time and the original population to be selected in the one comprised by the initially generated P sequences), i.e., computing the value of $\sum_{j = 0}^{P - 1} fitness (j),$
and at the same time setting the initial values of j and a as 0, wherein j is the serial number of the sequence in the population to be selected and a is the number of iteration in step S103. If P sequences are selected for one time, the biggest value of a is P−1; if one sequence is selected for one time, the current value of a is the serial number of the selected sequence in the new population.
[0070] 2) Generating a random number r, wherein 0<r<1;
[0071] 3) $Computing \frac{P * fitness (j)}{\sum_{j = 0}^{P - 1} fitness (j)},$
if the result is less than r, putting the sequence to the next generation population and setting the serial number of the selected sequence in the new population to a and then computing a=a+1 and proceeding to the step 4); if the result is equal to or bigger than r, determining the current value of j, computing j=j+1 if j<P−1 and computing j=j−P+1 if j is equal to or bigger than P−1, and then returning to step 2); and thus the sequence in the next operation becoming the next sequence and operating each sequence with this cycle order;
[0072] 4) Determining whether the current serial number a is bigger than or equal to P−1, if yes, proceeding to step S104 for genetic crossover over operation; if no, determining the current value of j, computing j=j+1 if j<P−1 and computing j=j−P+1 if j is equal to or bigger than P−1, and then returning to step 2).

[0073] In one embodiment of the present invention, the smaller the autocorrelation function is (the smaller the fitness is in formula (1)), the better chance the sequence will be selected, which fully reflects the basic idea of “survival of the fittest” of the evolutionism. The number of the selected sequences in the present embodiment is P also, however, the number doesn't need to be the same with the number of the initial generated sequences and it can be either bigger than P or smaller than P. The newly selected population can include a plurality of the same sequences and the sequence with a smaller autocorrelation function will have a better chance to be selected for more times.

[0074] After the fitness of each sequence in the selected population is obtained according to the embodiment of the present invention, the step S104 will be taken to get the next generation population by performing the genetic crossover over operation. The process is performed in the genetic crossover over operation apparatus 93, which randomly selects the individuals in the population to perform the pairwise genetic crossover. FIG. 4 explains the basic operations of genetic crossover, which intersects the two sequences and separates each individual into two segments at the crossover point; the segments of different individual is combined at the crossover point the crossover point 401 can be selected randomly.

[0075] Then, the adaptive genetic mutation S105 is taken to determine whether a certain sequence needs to be adaptively mutated. The process is performed in the genetic adaptive unit 94.

[0076] In the embodiment of the present invention, for every sequence, a random number r between 0 and 1 is generated during each time of iteration. The following formula is used to determine whether a sequence needs to be mutated.

\begin{matrix} \frac{P * fitness (j)}{\sum_{j = 0}^{P - 1} fitness (j)} > r & (2) \end{matrix}

[0077] The meaning of the symbols in the formula is the same as those described above. When the above formula (2) is satisfied, the fitness (j) of the sequence is comparatively high, i.e., the autocorrelation function is comparatively big and since the sequence with a comparatively low autocorrelation function is needed, the sequence should be mutated; however, when the above formula (2) is not satisfied, the fitness (j) of the sequence is comparatively small, i.e., the autocorrelation function is comparatively small so the sequence has a comparatively good characteristic and need not be mutated. FIG. 5 explains the above process in detail and the steps are as following:

[0078] 1) Setting the initial value of the serial number j to 0;
[0079] 2) Generating a random number r, wherein 0<r<1;
[0080] 3) Determining whether the result of $\frac{P * fitness (j)}{\sum_{j = 0}^{P - 1} fitness (j)}$
is bigger than r;
[0081] 4) If the result is bigger than r, mutating the sequence and computing j=j+1 with the serial number unchanged; proceeding to step 5); if the result is smaller than r, computing j=j+1 and returning to step 2);
[0082] 5) Determining whether j is bigger than P−1;
[0083] 6) If j is bigger than P−1, proceeding to step 7); if j is equal to or smaller than P−1, returning to step 2);
[0084] 7) Determining whether the iterative times has reached the maximum number, if not, returning to step S102; if yes, selecting in the selecting unit 95. The selection includes the following process:
[0085] (1) Computing the fitness of all the sequences in the population obtained after the selection of maximum iterative times, genetic crossover and adaptive mutation;
[0086] (2) Comparing the values of the fitness of all the sequences and selecting the sequence with the smallest fitness as the output sequence (If there are more than one sequence with the smallest fitness, selecting one randomly as the output sequence.); and then the flow of generating the sequence ended.

[0087] It is necessary to select in the mutated sequences since mutation may bring better sequences and also may bring worse ones. FIG. 6 shows the strategy to select the mutated sequences. If the mutated sequences are better, they have better opportunities to be selected but if the mutated sequences are worse, they have worse opportunities to be selected. P_ais a fixed value set according to the requirement, which represents the probability of changing mutation and P_a=0.1 in the present invention. The strategy to select is as follows:

[0088] 1) Computing the fitness of the sequence j before mutation;
[0089] 2) Mutating the sequence j and getting sequence j′ while maintaining a backup of sequence j, computing the fitness of the sequence j′ and generating a random number r, wherein 0<r<1;
[0090] 3) Determining whether the fitness of the sequence j′ is less than that of the sequence j, with r>P_a;
[0091] 4) If yes, accepting the mutated sequence j′; if no, rejecting the mutated sequence j′ and maintaining the former sequence j;
[0092] 5) Continuing to mutate other sequences.

[0093] In the embodiment of the present invention, the mutation operation of the sequence is very simple, i.e. changing the sign of a random bit in the sequence such as changing negative 1 to positive 1 or positive 1 to negative 1. FIG. 7 shows the mutation operation. The mutation point can be selected randomly.

[0094] Those skilled in the art will find the step 103, in which the sequences can be added to the final sequence set are selected, i.e. the fitness of each sequence is computed, can be performed before the genetic crossover step S104 and also can be performed after the genetic adaptive mutation step S105, i.e., the sequences selected from the P sequences are added to the final sequence set after the maximum number of iteration.

[0095] Those skilled in the art will also find the sequences with less fitness can be added to the final sequence set according the fitness of each sequence without the above condition for adding it to the final sequence set.

[0096] Those skilled in the art will also find different mutation probabilities, mutation methods and mutation strategies of sequences can be selected according to the practical situation.

[0097] Currently, the SYNC sequence used in TD-SCDMA is Golay code.

[0098] FIG. 8a and FIG. 8b are the curve diagrams showing the aperiodic autocorrelation function of SYNC and Golay code respectively according the embodiment of the present invention, wherein the ordinate represents the normalized value of the aperiodic autocorrelation function and the abscissa represents the off-peak autocorrelation index. FIG. 8a shows the maximum normalized value of the autocorrelation function of Golay code is 0.0158 reference sign 801) and the corresponding gain is −18.0610 dB; FIG. 8b shows the maximum normalized value of the autocorrelation function of SYNC is 0.0088 (reference sign 802) according to the embodiment of the present invention and the corresponding gain is −20.5606 dB, so the difference between the peak sidelobe values of SYNC and Golay code in the present invention (i.e. the relative gain according to the embodiment of the present invention) is (−18.0610)−(−20.5606)=2.4996 dB.

[0099] As shown in FIG. 9, the system 90 has a generation unit 91, which is used to generate at least one random sequence such as P sequences; computation unit 92, which is used to compute the fitness of sequences according to the designated evaluation indicator corresponding to the specific characteristic; and selection unit 95, which is used to select the specific sequences among the sequences in accordance with the requirements of the user. The selection unit 95 can select the specific sequences among the sequences according to the fitness of each sequence or according to the specific characteristic of each sequence (evaluation indicator for the fitness).

[0100] The system 90 may also have a genetic crossover unit 93, adaptive genetic mutation unit 94, which are used to perform genetic crossover and adaptive mutation on the sequences according to the fitness computed by the computation unit 92; the system 90 may also have repetition control unit 96, which is used to control the repetition times of the processes from the computation unit and the genetic crossover unit to the genetic adaptive mutation unit and to send the sequences obtained after cycling to the selection unit 95.

[0101] In FIG. 9, sequences pass the computation unit 92, the genetic crossover unit 93 and the genetic mutation unit 94 for several times and finally the selection unit 95 determines the output sequences.

[0102] The above is only the preferred embodiment of the present invention. It should be noted that those skilled in the art might make improvements and modifications. It is intended that the invention be construed as including all such improvements and modifications insofar they come within the scope of the appended claims or the equivalents thereof.

Claims

We claim:

1. A method for generating sequences, wherein the sequences are used in a communication system and the method comprises following steps:

1) generating a plurality of sequences with a predetermined length randomly;

2) computing a specific parameter value of each sequence;

3) selecting a plurality of sequences whose computed specific parameter value accords with a certain condition;

4) mutating the selected sequences with an adaptive genetic algorithm and adaptively selecting the sequences with the mutated and optimized specific parameter value according to the probability;

5) repeating operations of computing the specific parameter value of each sequence, selecting the plurality of sequences whose computed specific parameter value accords with the certain condition, and mutating the selected sequences until a predetermined number of times and selecting the sequences with the optimal specific parameter value among the final sequences as output sequences.

2. The method for generating sequences as defined in claim 1, further comprising, between selecting the plurality of sequences and mutating the selected sequences, performing crossover over operation on the selected plurality of sequences.

3. The method for generating sequences as defined in claim 1, wherein the specific parameter is relative to the autocorrelation function.

4. The method for generating sequences as defined in claim 2, wherein the specific parameter is relative to the autocorrelation function.

5. The method for generating sequences as defined in any one of claims 1-3, wherein the specific parameter is the fitness and its computation formula is:

fitness (j) = \sum_{τ = 1}^{L - 1} {θ_{u, u} (τ)}^{2} + β \cdot {PSL}_{j}^{2}

0 \leq j \leq P - 1

θ_{u, u} (τ) = \sum_{t = 0}^{L - 1 - τ} u (t) u (t + τ), {PSL}_{j} = \max {θ_{u, u} (τ)}^{2}

wherein θ_u,u(τ) is the autocorrelation function of each sequence, j is the serial number of the sequence, P is the size of the sequences, L is the length of each sequence, PSL_jis the peak sidelobe value of each sequence and β is the equilibrium coefficient for balancing the peak sidelobe with the sum of the autocorrelation value.

6. The method for generating sequences as defined in any one of claims 1-3, wherein, mutating the selected sequences comprises the following operations:

a) computing the fitness of a sequence j before mutation;

b) mutating the sequence j and getting a sequence j′ while maintaining a backup of the sequence j, computing the fitness of the sequence j′ and generating a random number r, wherein 0<r<1;

c) determining whether the fitness of the sequence j′ is less than that of the sequence j, with r>P_a;

d) if the fitness of the sequences j′ is less than that of the sequence j, then accepting the mutated sequence j′; if the fitness of the sequences j′ not less than that of the sequence j, then rejecting the mutated sequence j′ and maintaining the former sequence j;

e) repeating the operations a)-d) and continuing to mutate other sequences;

wherein j is the serial number of the sequence, P_ais a predetermined value.

7. The method for generating sequences as defined in claim 5, wherein, the adaptive genetic mutation includes the following operations:

a) computing the fitness of a sequence j before mutation;

b) mutating the sequence j and getting a sequence j′ while maintaining a backup of the sequence j, computing the fitness of the sequence j′ and generating a random number r, wherein 0<r<1;

c) determining whether the fitness of the sequence j′ is less than that of the sequence j, with r>P_a;

d) if the fitness of the sequence j′ is less than that of the sequence j, then accepting the mutated sequence j′; if the fitness of the sequence j′ is not less than that of the sequence j, then rejecting the mutated sequence j′ and maintaining the former sequence j;

e) repeating the operations a)-d) and continuing to mutate other sequences;

wherein j is the serial number of the sequence, P_ais a predetermined value.

8. The method for generating sequences as defined in claim 5 or 7, wherein selecting the sequences includes the following operations:

I) generating a random number r, and setting the initial numbers of integers a and j as 0, wherein 0<r<1;

computing \frac{P * fitness (j)}{\sum_{j = 0}^{P - 1} fitness (j)},

if the result is less than r, putting the sequence to the next generation population and setting the serial number of the selected sequence in the new population to a and then computing a=a+1 and proceeding to operation III); if the result is equal to or bigger than r, determining the current value of j, if j<P−1, computing j=j+l; if j is equal to or bigger than P−1, computing j=j−P+1; and then returning to operation I); and thus the sequence in the next operation becoming the next sequence and operating each sequence with this cycle order;

III) determining whether the current serial number a is bigger than or equal to P−1, if the current serial number a is bigger than or equal to P−1, proceeding to mutating the selected sequence); if the current serial number a is not bigger than or equal to P−1, determining the current value of j, if j<P−1, computing j=j+1; if j is equal to or bigger than P−1, computing j=j−P+1; and then returning to operation I).

9. The method for generating sequences as defined in claim 2, wherein the crossover point of the crossover over operation is selected randomly.

10. The method for generating sequences as defined in any one of claims 1-4, wherein, the sequences are downlink synchronization sequences in the wireless communication system.

11. The method for generating sequences as defined in claim 5, wherein the sequences are downlink synchronization sequences in the wireless communication system.

12. The method for generating sequences as defined in claim 6, wherein the sequences are downlink synchronization sequences in the wireless communication system.

13. The method for generating sequences as defined in claim 7, wherein the sequences are downlink synchronization sequences in the wireless communication system.

14. The method for generating sequences as defined in claim 8, wherein the sequences are the downlink synchronization sequences in the wireless communication system.

15. The method for generating sequences as defined in any one from claim 1 to claim 4, wherein, the sequences are the uplink synchronization sequences in the wireless communication system.

16. The method for generating sequences as defined in claim 5, wherein the sequences are the uplink synchronization sequences in the wireless communication system.

17. The method for generating sequences as defined in claim 6, wherein the sequences are the uplink synchronization sequences in the wireless communication system.

18. The method for generating sequences as defined in claim 7, wherein the sequences are the uplink synchronization sequences in the wireless communication system.

19. The method for generating sequences as defined in claim 8, wherein the sequences are the uplink synchronization sequences in the wireless communication system.

20. An apparatus for generating sequences, wherein the sequences are used in the communication system, the apparatus comprising:

a generation unit to generate a plurality of sequences with a predetermined length randomly;

a computation unit to compute a specific parameter value of each sequence and to select a plurality of sequences whose computed specific parameter value accords with a certain condition;

a genetic adaptive mutation unit to perform adaptive genetic mutation on sequences and adaptively selecting sequences with the mutated and optimized specific parameter value according to the probability;

a cyclic control unit to control the number of cycle times of process from the computation unit to the genetic adaptive mutation unit;

a selection unit to select the sequences with the optimal specific parameter value among the final sequences as the output sequences.

21. The apparatus for generating sequences as defined in claim 20, further comprising a genetic crossover over operation unit which exists between the computation unit and the genetic adaptive mutation unit, to perform crossover over operation on the selected plurality of sequences and to send the processed sequences to the genetic adaptive mutation unit.

22. The apparatus for generating sequences as defined in claim 20, wherein the specific parameter is relative to the autocorrelation function.

23. The apparatus for generating sequences as defined in claim 21, wherein the specific parameter is relative to the autocorrelation function.

24. The apparatus for generating sequences as defined in any one of claims 20-22, wherein the specific parameter is the fitness and its computation formula is:

fitness (j) = \sum_{τ = 1}^{L - 1} {θ_{u, u} (τ)}^{2} + β \cdot {PSL}_{j}^{2}

0 \leq j \leq P - 1

θ_{u, u} (τ) = \sum_{t = 0}^{L - 1 - τ} u (t) u (t + τ), {PSL}_{j} = \max {θ_{u, u} (τ)}^{2}

25. The apparatus for generating sequences as defined in claim 21, wherein the crossover point of the crossover over operation is selected randomly.

26. The apparatus for generating sequences as defined in any one of claims 20-23, wherein the sequences are the downlink synchronization sequences in the wireless communication system.

27. The apparatus for generating sequences as defined in claim 24, wherein the sequences are the downlink synchronization sequences in the wireless communication system.

28. The apparatus for generating sequences as defined in claim 25, wherein the sequences are the downlink synchronization sequences in the wireless communication system.

29. The apparatus for generating sequences as defined in any one of claims 20-23, wherein the sequences are the uplink synchronization sequences in the wireless communication system.

30. The apparatus for generating sequences as defined in claim 24, wherein the sequences are the uplink synchronization sequences in the wireless communication system.

31. The apparatus for generating sequences as defined in claim 25, wherein the sequences are the uplink synchronization sequences in the wireless communication system.

Abstract