Abstract: In modern spread spectrum communications, how to generate spread spectrum sequence quickly is important in system modeling and design and therefore has received wide attentions. Accordingly, this study investigates the fast generation of Bent sequences, where we use a single generator to generate multiple Bent sequences simultaneously and therefore significantly reduce the realization cost. The proposed fast generator comes from the intrinsic relations between the m-sequence and the Bent sequence, i.e., the m-sequence and its shift versions can construct a trace based generator of Bent sequence family with sequence number approaching 2n/2. Moreover, we realize such fast generators in Agilent ADS (Advanced Design System) 2005A software and two examples are provided: four order Bent sequence and twelve order Bent sequence. Then, both fast generators are verified by comparing the simulated autocorrelation and crosscorrelation with the corresponding theoretical values and the results prove that the proposed method is effective and beneficial for spread spectrum communications.
INTRODUCTION
Spread spectrum communication systems have many advantages, such as security, Low Probability of Intercept (LPI) and strong anti-jamming ability. Hence, they had been widely used in modem military communications, accoustic communications and mobile communications (Britto and Sankaranarayanan, 2006; Tachikawa et al., 2007; Todorovic and Orlic, 2009; Mingxin et al., 2008; Yang and Yang, 2008). Since, the preformance of spread spectrum systems depend on the spread spectrum sequence significantly, studies on spread spectrum sequences have become important topics in spread spectrum systems (Tanimoto et al., 2008; Zhang and Hao, 2008; Tachikawa, 2007).
Conventionally, m-sequence and Gold sequence are widely exploited and in order to obtain better correlation properties as well as high security, people also studied m-sequence, GMW sequence and Bent sequence (Golomb and Gong, 2005). Among these sequences, the Bent sequence has large linear complexity, good balance characteristic and excellent pseudo-randomness (Kavut et al., 2007; No et al., 2003). Moreover, the number of nth-order Bent sequence can approach 2n/2 and the corresponding cross-corrrelation (autocorrelation) is triple valued and controllable. Therefore, Bent sequence is a kind of good spread spectrum sequence and receives much attention (Canteaut and Charpin, 2003; Budaghyan et al., 2006).
Generally, the study on Bent sequence can be classified as two types: Bent function construction and sequence generation. The former focused on the basic principle of Bent sequence, such as Izbenko et al. (2009), Budaghyan et al. (2006), Canteaut and Charpin (2003) and Kavut et al. (2007), while the latter emphasized on the realization and application of Bent sequence (Guo and Cai, 1993; No et al., 2003; Pin-Hei et al., 2007; Wen-Feng, 2006). In present study, we focus on the generation of Bent sequence.
Trace transform methods (No et al., 2003; Pin-Hui et al., 2007; Wen-Feng, 2006) and feed-forward generation method (Guo and Cai, 1993) are two most popular methods to generate Bent sequence. Generally, the trace transform method requires large implementation cost and the feed-forward method must design multiple feed-forward networks to account for multiple sequence generations.
In order to reduce the realization cost, this study presents a simple method to generate a family of Bent sequences (with number 2n/2), which combines the trace based method and the feed-forward network method, then produce multiple Bent sequence only through one feed-forward network. In fact, the proposed method exploits the intrinsic relations between the m-sequence and the Bent sequence, i.e., the m-sequence generator (trace based) and its shift versions (feed-forward network) can construct a generator for a certain Bent sequence family. Moreover, we realize such fast generators in Agilent ADS (Advanced Design System) 2005A software and two examples are provided: four order Bent sequence and twelve order Bent sequence. Then, both fast generators are verified by comparing the simulated autocorrelation and crosscorrelation with the corresponding theoretical values and the results validate its effectivity.
BENT SEQUENCE GENERATION
Definition of Bent sequence: In Galois Field (GF), the trace function maps x ∈ GF(2n) into GF(2) (Golomb and Gong, 2005):
| (1) |
Then, the Bent sequence is defined as:
| (2) |
where, z∈ GF(2m), x0 ∈ GF(2n)|GF(2m), n = 2m = 4k and k is any positive integer. Moreover, r1, r2....,rm are basises of GF(2m) over GF(2) and α is a primitive element of GF(2n).
Given T = 2m+1, αT is a primitive element of GF(2m) and {α0, αT....α(m–1)T} also are basises of GF(2m). Accordingly, X0 = α-1 ∈ GF(2n)|GF(2m) and Eq. 2 is equivalent to Eq. 3 (Golomb and Gong, 2005):
| (3) |
Combination of trace transform and feed-forward network: In Eq. 3, we have feed-forward function,
| (4) |
and m-sequence expression based on trace transform.
| (5) |
where, f(x) is a bent function and at+T = tr1n(αt+T) is the T-step shift equivalent sequence of m-sequence (at), which means that the stage register to output at+T is T-step ahead that to produce at.
From Eq. 1-5, we explicitly see that the key of Bent sequence generation is generating iT-step shift equivalent sequence of m-sequence, where i = 1…m-1. As an example, we take the four order Bent sequence into consideration, i.e., n = 4, m = 2 and T = 2m+1 = 5, then we have the primitive polynomial of the m-sequence x4+x+1 (Golomb and Gong, 2005). Accordingly, we can derive,
| (6) |
From Eq. 6, we can obtain the iT-step shift equivalent sequence of m-sequence to generate Bent sequence. Moreover, the derivations in Eq. 6 can be extended to more general cases, i.e., any n. Due to the space limitation, we only provide such analogous derivations of four different n’s in Table 1.
According to the previous derivation, we can conclude that the m inputs of fz(x) are at, at+T, at+2T,…at+(m-1)T and zTx denotes the combinations of these inputs. Since z has 2n/2 values, the number of such a Bent sequence family is 2n/2.
| Table 1: | iT-step shift equivalent sequence of m-sequence |
Fast generation of Bent sequence family: In order to show the generation process clearly, we study the example in the above subsection again, where the Bent function is f(x) = x1x2. After some tedious derivations, we obtain Table 2, where the inputs at, at+5 can replace x2, x1 during the generation process and the Bent sequence is obtained by XOR at+1 and the outputs of fz(x).
It’s easy to find in Table 2 that Bent 2 = Bent 1+at+5, Bent 3 = Bent 1+at and Bent 4 = Bent 1+at+at+5. Hence, we conclude that one Bent sequence XOR any combination of at, at+T, at+2T, …, at+(m-1)T produces another Bent sequence of the same family. In this way, we can generat 2n/2 Bent sequences quickly and avoid constructing many feed-forward networks, thus the proposed method is superior to conventional ones (Pin-Hui et al., 2007; Wen-Feng, 2006; Guo and Cai, 1993).
| Table 2: | Four-order Bent sequence (Modulo-2) |
BENT SEQUENCE GENERATOR IN ADS2005A
Before detailed descriptions, we must highlight that modelling and simulation are necessary for spread-spectrum systems. Therefore, this section will demonstrate the Bent sequence generator in ADS2005A, which is a popular software in communication modelling and simulation.
Note that Fig. 3 and 4, the X-coordinate and the Y-coordinate denote the sequence shift and the value of correlation, respectively.
Four-order Bent sequence: The schematic diagram of four-order Bent sequence family is shown in Fig. 1, where we exploit two kinds of kernel devices, i.e., delay device (InitDelay) and XOR device (LogicXOR2). In Fig. 1, first we explicitly see that there is only one feed-forward network by which four Bent sequences are produced at the same time and then we can derive the logic relations of Bent 1~4 as:
| (7) |
| Fig. 1: | The schematic diagram of four-order Bent sequence family in ADS2005A |
| Fig. 2: | The auto-correlation characteristics, (a) Bent 1 and (b) Bent 2 |
Besides kernel devices, Fig. 1 also utilizes DF (data flow control device) and NumericSink (data terminal device). In order to verify our design, we further run simulations and compare sequences’ auto/cross correlation with corresponding theoretical values. According to previous presentations, the four-order Bent sequence (period fifteen) should have triple-valued auto/cross-correlation sidelobes, i.e., 3/15, -1/15 and -5/15.
Looking at Fig. 2, we find that zero shift causes the largest autocorrelation and non-zero shifts significantly reduce the autocorrelation, where the three sidelobes are valued (3/15, -1/15, -5/15), which is consistent with theoretical results. Meanwhile, Fig. 3 shows the crosscorrelation of different Bent sequences, where X-coordinate denotes shift between two sequences and Y-coordinate represents the values of correlation. From Fig. 3, we can conclude that different Bent sequences produce small crosscorrelations and the crosscorrelation value are triple-valued and consistent with the theoretical result.
Twelve-order Bent sequence: Next, we further construct a twelve-order Bent sequence generator in ADS2005A, where the detailed schematic diagram isn’t presented due to the space limitation.
The proposed Bent sequence generator uses the Bent function f(x)=x1x4+x2x5+x3x6 and without loss of generality, we only provide results of auto/cross correlation of Bent 5 and 6, where,
| • | z = [0 0 0 0 0 0] for Bent 5, results in feed-forward function fz(x) = f(x) |
| • | z = [0 0 0 0 0 1] for Bent 6, results in feed-forward function fz(x) = f(x)+x6= Bent 5+x6 |
| Fig. 3: | The cross-correlation characteristics, (a) Bent 1 and 4 and (b) Bent 2 and 3 |
| Fig. 4: | The autocorrelation of Bent 5 |
Figure 4 and 5 show the autocorrelation of Bent 5 and 6, where we explicitly see that zero shift produces the largest autocorrelation and non-zero shifts produce small and triple-valued autocorrelations, i.e., 63/4095, -1/4095 and -65/4095 as predicted by theoretical analysis. These results prove that the Bent sequence has excellent pseudo-randomness.
Figure 6 shows crosscorrelations of Bent 5 and 6. Though, the sequence shift only ranges from zero to one hundred for the sake of good curve resolution, we point out that other shifts lead to the same results as Fig. 6.
| Fig. 5: | The autocorrelation of Bent 6 |
| Fig. 6: | The crosscorrelation of Bent 5 and 6 |
From Fig. 6, we explicitly see that Bent sequences have small cross-corrrelations. Most importantly, the crosscorrelation is consistent with the theory derivation, i.e., 63/4095, -1/4095 and -65/4095. Taken into consideration both Fig. 5 and 6, we know that the Bent sequence has excellent autocorrelation and crosscorrelation performance and thus is suitable for spread spectrum communications.
To summarize, the proposed fast generation method constructs a compact architecture to generate 2n/2 Bent sequences simultaneously, which not only avoids duplication of multiplication, but also eliminates the resource waste of constructing many feed-forward functions. Hence, the proposed method is much simpler than conventional methods (Pin-Hui et al., 2007; Wen-Feng, 2006; No et al., 2003; Guo and Cai, 1993).
CONCLUSIONS
Spread spectrum sequences require both excellent correlation performance and large sequence numbers. Meeting these requirements, Bent sequence, including its fast generation, has received much attention. Accordingly, this study presents a fast Bent sequence generation method, which can simply and effectively generate many Bent sequences simultaneously. As an application, this method has been implemented and evaluated in ADS2005A, the results show that it can completely achieve the theoretical performance and have a smaller computing load for multiple sequence generation. Furthermore, the Agilent ADS is a powerful design software in wireless system, hence designing Bent sequence generator will benefit the simulation of spread spectrum systems in ADS.
ACKNOWLEDGMENTS
This study is sponsored by science foundation for the excellent youth scholars of Zhejiang province (2010), Zhejiang provincial NSF of China under Grant No. Y1090645 (2010-2011) and the open fund of state key laboratory of information engineering in survey, mapping and remote sensing, Wuhan university, China (No. (08)03).