American Institute of Mathematical Sciences

Advanced
February  2018, 12(1): 215-230. doi: 10.3934/amc.2018015

Finite length sequences with large nonlinear complexity

Jiarong Peng , Xiangyong Zeng and  Zhimin Sun ,

The Faculty of Mathematics and Statistics, Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan, Hubei 430062, China

* Corresponding author: Zhimin Sun

Received  May 2017 Revised  November 2017 Published  March 2018

Fund Project: The authors were supported by the National Natural Science Foundation of China Grant (No. 61472120). X. Zeng and Z. Sun were also granted by National Natural Science Foundation of Hubei Province of China (No. 2017CFB143) and China Scholarship Council, respectively.

Finite length sequences with large nonlinear complexity over $\mathbb{Z}_{p}\, (p≥ 2)$ are investigated in this paper. We characterize all $p$-ary sequences of length $n$ having nonlinear complexity $n-j$ for $j=2, 3$, where $n$ is an integer satisfying $n≥ 2j$. For $n≥ 8$, all binary sequences of length $n$ with nonlinear complexity $n-4$ are obtained. Furthermore, the numbers and $k$-error nonlinear complexity of these sequences are completely determined, respectively.

Keywords: Binary sequences, p-ary sequences, nonlinear complexity, k-error nonlinear complexity, finite length sequences.
Mathematics Subject Classification: Primary: 94A55; Secondary: 94A60.
Citation: Jiarong Peng, Xiangyong Zeng, Zhimin Sun. Finite length sequences with large nonlinear complexity. Advances in Mathematics of Communications, 2018, 12 (1) : 215-230. doi: 10.3934/amc.2018015
References:
[1]

C. J. A. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph. D thesis, Technical Univ. Delft, 1989.  Google Scholar

[2]

C. J. A. Jansen and D. E. Boekee, The shortest feedback shift register that can generate a given sequence, in Adv. Crypt. -CRYPTO'89, 1990, 90–99.  Google Scholar

[3]

N. Li and X. Tang, On the linear complexity of binary sequences of period $4N$ with optimal autocorrelation value/magnitude, IEEE Trans. Inf. Theory, 57 (2011), 7597-7604.   Google Scholar

[4]

F. T. Macwilliams and N. J. A. Sloane, Psedo-Random sequences and arrays, Proc. IEEE, 64 (1976), 1715-1729.   Google Scholar

[5]

W. Meidl and A. Winterhof, On the linear complexity profile of some new explicit inverse pseudorandom numbers, J. Complexity, 20 (2004), 350-355.   Google Scholar

[6]

H. Niederreite, Random Number Generation and Quasi-Monte Carlo Methods, Soc. Ind. Appl. Math., Philadelphia, 1992.  Google Scholar

[7]

H. Niederreiter, Linear complexity and related complexity measures for sequences, in Progr. Crypt. -INDOCRYPT 2003, 2003, 1–17.  Google Scholar

[8]

P. Rizomiliotis, Constructing periodic binary sequences of maximum nonlinear span, IEEE Trans. Inf. Theory, 52 (2006), 4257-4261.   Google Scholar

[9]

P. Rizomiliotis and N. Kalouptsidis, Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1555-1563.   Google Scholar

[10]

Z. Sun, X. Zeng, C. Li and T. Helleseth, Investigations on periodic sequences with maximum nonlinear complexity, IEEE Trans. Inf. Theory, 63 (2017), 6188-6198.   Google Scholar

show all references

References:
[1]

C. J. A. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph. D thesis, Technical Univ. Delft, 1989.  Google Scholar

[2]

C. J. A. Jansen and D. E. Boekee, The shortest feedback shift register that can generate a given sequence, in Adv. Crypt. -CRYPTO'89, 1990, 90–99.  Google Scholar

[3]

N. Li and X. Tang, On the linear complexity of binary sequences of period $4N$ with optimal autocorrelation value/magnitude, IEEE Trans. Inf. Theory, 57 (2011), 7597-7604.   Google Scholar

[4]

F. T. Macwilliams and N. J. A. Sloane, Psedo-Random sequences and arrays, Proc. IEEE, 64 (1976), 1715-1729.   Google Scholar

[5]

W. Meidl and A. Winterhof, On the linear complexity profile of some new explicit inverse pseudorandom numbers, J. Complexity, 20 (2004), 350-355.   Google Scholar

[6]

H. Niederreite, Random Number Generation and Quasi-Monte Carlo Methods, Soc. Ind. Appl. Math., Philadelphia, 1992.  Google Scholar

[7]

H. Niederreiter, Linear complexity and related complexity measures for sequences, in Progr. Crypt. -INDOCRYPT 2003, 2003, 1–17.  Google Scholar

[8]

P. Rizomiliotis, Constructing periodic binary sequences of maximum nonlinear span, IEEE Trans. Inf. Theory, 52 (2006), 4257-4261.   Google Scholar

[9]

P. Rizomiliotis and N. Kalouptsidis, Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1555-1563.   Google Scholar

[10]

Z. Sun, X. Zeng, C. Li and T. Helleseth, Investigations on periodic sequences with maximum nonlinear complexity, IEEE Trans. Inf. Theory, 63 (2017), 6188-6198.   Google Scholar

Table 1.  Binary sequences of length 11 with nonlinear complexity 7 and their distribution
$Set$Sequences # Seq.
$K_1$00000001000, 11111110111, 00000001001, 11111110011, 00000001101
11111110110, 00000001010, 11111110101, 00000001011, 00000001100
11111110100, 11111110010, 00000001110, 11111110001, 00000001111
11111110000, 01010101100, 10101010011, 01010101101, 10101010010
01010101110, 10101010001, 01010101111, 10101010000, 01111111000
10000000111, 01111111001, 10000000110, 01111111010, 10000000101
01111111011, 10000000100, 00100100110, 11011011001, 00100100111
11011011000, 00101010110, 11010101001, 00101010111, 11010101000
00111111100, 11000000011, 00111111101, 11000000010, 01001001010
10110110101, 01001001011, 10110110100, 01000000010, 10111111101
01000000011, 10111111100, 01101101110, 10010010001, 01101101111
10010010000		56
$K_2$00110011000, 11001100111, 00110110111, 11001001000, 01100110010
10011001101, 01100000001, 10011111110		8
$K_3$00010001001, 11101110110, 00010010011, 11101101100, 00010101011
11101010100, 00011111110, 11100000001, 00100000001, 11011111110
00100010000, 11011101111, 01000100011, 10111011100, 01011011010
10100100101, 01011111110, 10100000001, 01101010100, 10010101011
01110111010, 10001000101		22
Table Options

Download as excel

$Set$Sequences # Seq.
$K_1$00000001000, 11111110111, 00000001001, 11111110011, 00000001101
11111110110, 00000001010, 11111110101, 00000001011, 00000001100
11111110100, 11111110010, 00000001110, 11111110001, 00000001111
11111110000, 01010101100, 10101010011, 01010101101, 10101010010
01010101110, 10101010001, 01010101111, 10101010000, 01111111000
10000000111, 01111111001, 10000000110, 01111111010, 10000000101
01111111011, 10000000100, 00100100110, 11011011001, 00100100111
11011011000, 00101010110, 11010101001, 00101010111, 11010101000
00111111100, 11000000011, 00111111101, 11000000010, 01001001010
10110110101, 01001001011, 10110110100, 01000000010, 10111111101
01000000011, 10111111100, 01101101110, 10010010001, 01101101111
10010010000		56
$K_2$00110011000, 11001100111, 00110110111, 11001001000, 01100110010
10011001101, 01100000001, 10011111110		8
$K_3$00010001001, 11101110110, 00010010011, 11101101100, 00010101011
11101010100, 00011111110, 11100000001, 00100000001, 11011111110
00100010000, 11011101111, 01000100011, 10111011100, 01011011010
10100100101, 01011111110, 10100000001, 01101010100, 10010101011
01110111010, 10001000101		22
[1]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016
[2]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[3]

Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[4]

Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047
[5]

Lin Yi, Xiangyong Zeng, Zhimin Sun. On finite length nonbinary sequences with large nonlinear complexity over the residue ring $ \mathbb{Z}_{m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020091
[6]

Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297
[7]

Xiaoni Du, Chenhuang Wu, Wanyin Wei. An extension of binary threshold sequences from Fermat quotients. Advances in Mathematics of Communications, 2016, 10 (4) : 743-752. doi: 10.3934/amc.2016038
[8]

Pinhui Ke, Yueqin Jiang, Zhixiong Chen. On the linear complexities of two classes of quaternary sequences of even length with optimal autocorrelation. Advances in Mathematics of Communications, 2018, 12 (3) : 525-539. doi: 10.3934/amc.2018031
[9]

Denis Dmitriev, Jonathan Jedwab. Bounds on the growth rate of the peak sidelobe level of binary sequences. Advances in Mathematics of Communications, 2007, 1 (4) : 461-475. doi: 10.3934/amc.2007.1.461
[10]

Xiwang Cao, Wun-Seng Chou, Xiyong Zhang. More constructions of near optimal codebooks associated with binary sequences. Advances in Mathematics of Communications, 2017, 11 (1) : 187-202. doi: 10.3934/amc.2017012
[11]

Arne Winterhof, Zibi Xiao. Binary sequences derived from differences of consecutive quadratic residues. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020100
[12]

Hua Liang, Jinquan Luo, Yuansheng Tang. On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$. Advances in Mathematics of Communications, 2017, 11 (4) : 693-703. doi: 10.3934/amc.2017050
[13]

Ryuji Kajikiya, Daisuke Naimen. Two sequences of solutions for indefinite superlinear-sublinear elliptic equations with nonlinear boundary conditions. Communications on Pure & Applied Analysis, 2014, 13 (4) : 1593-1612. doi: 10.3934/cpaa.2014.13.1593
[14]

E. Camouzis, H. Kollias, I. Leventides. Stable manifold market sequences. Journal of Dynamics & Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010
[15]

Frank Fiedler. Small Golay sequences. Advances in Mathematics of Communications, 2013, 7 (4) : 379-407. doi: 10.3934/amc.2013.7.379
[16]

Nam Yul Yu. A Fourier transform approach for improving the Levenshtein's lower bound on aperiodic correlation of binary sequences. Advances in Mathematics of Communications, 2014, 8 (2) : 209-222. doi: 10.3934/amc.2014.8.209
[17]

Yanfeng Qi, Chunming Tang, Zhengchun Zhou, Cuiling Fan. Several infinite families of p-ary weakly regular bent functions. Advances in Mathematics of Communications, 2018, 12 (2) : 303-315. doi: 10.3934/amc.2018019
[18]

Lanqiang Li, Shixin Zhu, Li Liu. The weight distribution of a class of p-ary cyclic codes and their applications. Advances in Mathematics of Communications, 2019, 13 (1) : 137-156. doi: 10.3934/amc.2019008
[19]

Nian Li, Xiaohu Tang, Tor Helleseth. A class of quaternary sequences with low correlation. Advances in Mathematics of Communications, 2015, 9 (2) : 199-210. doi: 10.3934/amc.2015.9.199
[20]

Anna Gierzkiewicz, Klaudiusz Wójcik. Lefschetz sequences and detecting periodic points. Discrete & Continuous Dynamical Systems - A, 2012, 32 (1) : 81-100. doi: 10.3934/dcds.2012.32.81

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (160)
  • HTML views (239)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences