On the stability of periodic binary sequences with zone restriction
- PDF / 2,083,342 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 25 Downloads / 219 Views
On the stability of periodic binary sequences with zone restriction Ming Su1 · Qiang Wang2 Received: 31 March 2019 / Revised: 12 June 2020 / Accepted: 26 September 2020 © The Author(s) 2020
Abstract Traditional global stability measure for sequences is hard to determine because of large search space. We propose the k-error linear complexity with a zone restriction for measuring the local stability of sequences. For several classes of sequences, we demonstrate that the k-error linear complexity is identical to the k-error linear complexity within a zone, while the length of a zone is much smaller than the whole period when the k-error linear complexity is large. These sequences have periods 2n , s s or 2v r (r odd prime and 2 is primitive modulo r), or 2v p11 ⋯ pnn ( pi is an odd prime and 2 is primitive modulo p2i , where 1 ≤ i ≤ n ) respectively. In particular, we completely determine the spectrum of 1-error linear complexity with any zone length for an arbitrary 2n-periodic binary sequence. Keywords Stability · Linear complexity · k-error linear complexity · Zone restriction · Binary sequences Mathematics Subject Classification 94A60 · 94A55 · 65C10 · 68P25
Ming Su is supported by the China Scholarship Council and partially by Tianjin Key Research and Development Project 19YFZCSF00900. The research of Qiang Wang is partially funded by NSERC of Canada. * Ming Su [email protected] Qiang Wang [email protected] 1
Department of Computer Science, Nankai University, Tianjin, China
2
School of Mathematics and Statistics, Carleton University, Ottawa, Canada
13
Vol.:(0123456789)
M. Su, Q. Wang
1 Introduction Let S = (s0 , s1 , s2 , …) be an N-periodic sequence with terms in the finite field 𝔽q of q elements. We note that N need not be the least period of the sequence. We denote S = (s0 , s1 , … , sN−1 )∞ and define SN (x) = s0 + s1 x + ⋯ + sN−1 xN−1 . The linear complexity of a periodic sequence over 𝔽q is the length of the shortest linear recurrence relation which the sequence satisfies. In algebraic terms the linear complexity of an N-periodic sequence is given by L(S) = N − deg(gcd(1 − xN , SN (x))) ; see for example [3, p. 28]. For an integer k, 0 ≤ k ≤ N , the minimum linear complexity of those sequences with not more than k term changes in a period N from the original sequence S is called the k-error linear complexity of S, denoted as LN,k (S) , i.e.,
LN,k (S) = min {L(S + T)}, WH (T)≤k
where T is an N-periodic sequence, WH (T) is the Hamming weight of T in one period, the addition “ + ” for two sequences is defined elementwise in 𝔽q . A sequence T reaching the LN,k (S) is called an error vector of the k-error linear complexity. When N = 2n , denote the k-error linear complexity of S by Lk (S). In addition to the Berlekamp–Massey algorithm [11] for computing the linear complexity with computational complexity O(N 2 ) , there are efficient algorithms of several types of periodic sequences with computational complexity O(N), such as the Games-Chan algorithm [7] for computing the linear complexi
Data Loading...
