Four Families of Binary Sequences with Low Correlation and Large Linear Complexity
In this paper, four new families S 1, S 2, S 3 and S 4 of binary sequences of period 2 n − 1 with low correlation are presented, where S 1, S 3 are defined for odd n, and S 2, S 4 for even n. The family S 1 has six-valued correlations, while S 2 and S 3 h
- PDF / 544,673 Bytes
- 15 Pages / 430 x 660 pts Page_size
- 75 Downloads / 201 Views
Introduction
Families of binary sequences with low correlation have important applications in CDMA communication systems and cryptography[1][2]. Sidelnikov’s bound[3] is used to test the optimality of sequence families, which states that for any family of k binary sequences of period N , if k ≥ N , then Cmax ≥ (2N − 2)1/2 , where Cmax is the maximum magnitude of correlation values except for the in-phase autocorrelation value. The Gold family[4] is the best known binary sequence family which satisfies Sidelnikov’s bound. It has correlations 2n − 1, −1, −1 ± 2(n+1)/2 , where n is odd. But the linear span of Gold sequences is too small to resist attacks based on Berlekamp-Massey algorithm. So the Goldlike families with larger linear span were constructed. The odd case of Gold-like sequence family was discovered by Boztas and Kumar[5] , whose correlations are identical to those of Gold sequences. While for even n, Udaya[6] introduced families of binary sequences with correlations 2n − 1, −1, −1 ± 2n/2 , −1 ± 2n/2+1 , which corresponds to even case Gold-like sequence family. To get more sequence families with low correlation, Kim and No[7] constructed families S and U . The family S has correlations 2n − 1, −1, −1 ± 2(n+e)/2 , while U has correlations 2n − 1, −1, −1 ± 2n/2 , −1 ± 2n/2+e , where n and e are positive integers, e|n. In this paper, we present four new families S1 , S2 , S3 and S4 of binary sequences with low correlation and large linear span.
This work was supported by the National Natural Science Foundation of China (Grant 60673081) and the National “863” Project(Grant 2006AA01Z417).
Dingyi Pei et al. (Eds.): Inscrypt 2007, LNCS 4990, pp. 216–230, 2008. c Springer-Verlag Berlin Heidelberg 2008
Four Families of Binary Sequences
2
217
Preliminaries
Let GF (2n ) be the finite field with 2n elements, then the trace function from GF (2n ) to GF (2) is defined as[8] tr1n (x) =
n−1
i
x2 .
i=0
Let S = {(s i (t))t≥0 |0 ≤ i ≤ M − 1} be a family of M binary sequences with period N , then the correlation function between two sequences s i and s j is Ci,j (τ ) =
N −1
(−1)si (t)+sj (t+τ ) ,
(1)
t=0
where 0 ≤ i, j ≤ M − 1, 0 ≤ τ ≤ N − 1. When i = j, then Ci,i (τ ) is called the autocorrelation function. Denote Cmax = max{|Ci,j (τ )| | either i = j, or i = j and τ = 0}. Let α be a primitive element of GF (2n ) and f (x) a function from GF (2n ) to GF (2). Replacing x by αt , then f (x) defines a binary sequence a = (a(t))t≥0 of period dividing N = 2n − 1, where a(t) = f (αt ), t = 0, 1, · · · Remark 1. Without extra explanation, we always assume that α is a primitive element of GF (2n ) in this paper. If fi (x) and fj (x) define sequence s i and s j , then Ci,j (τ ) defined in (1) can also be represented as (−1)fi (δx)+fj (x) =R ˆ i,j (δ), Ci,j (τ ) = x∈GF (2n )∗
where δ = ατ ∈ GF (2n )∗ . Let f (x) be a function from GF (2n ) to GF (2), the Hadamard transform of f (x) is defined as: n (−1)f (x)+tr1 (λx) , fˆ(λ) = x∈GF (2n )
where λ ∈ GF (2n ). It is easy to get n fˆ(λ)2 = (−1)f (w)+tr1 (λw) ·
Data Loading...
