Finite length sequences with large nonlinear complexity

Jiarong Peng; Xiangyong Zeng; Zhimin Sun

doi:10.3934/amc.2018015

Article Contents

2018, Volume 12, Issue 1: 215-230. Doi: 10.3934/amc.2018015

This issue Previous Article Reduced access structures with four minimal qualified subsets on six participants Next Article

Finite length sequences with large nonlinear complexity

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

^* Corresponding author: Zhimin Sun
^* Corresponding author: Zhimin Sun

Received: April 30, 2017

Revised: October 31, 2017

Published: February 2018

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

Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 94A55; Secondary: 94A60.

Citation:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	C. J. A. Jansen, Investigations on Nonlinear Streamcipher Systems: Construction and Evaluation Methods, Ph. D thesis, Technical Univ. Delft, 1989.
	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.
	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.
	F. T. Macwilliams and N. J. A. Sloane , Psedo-Random sequences and arrays, Proc. IEEE, 64 (1976) , 1715-1729.
	W. Meidl and A. Winterhof , On the linear complexity profile of some new explicit inverse pseudorandom numbers, J. Complexity, 20 (2004) , 350-355.
	H. Niederreite, Random Number Generation and Quasi-Monte Carlo Methods, Soc. Ind. Appl. Math., Philadelphia, 1992.
	H. Niederreiter, Linear complexity and related complexity measures for sequences, in Progr. Crypt. -INDOCRYPT 2003, 2003, 1–17.
	P. Rizomiliotis , Constructing periodic binary sequences of maximum nonlinear span, IEEE Trans. Inf. Theory, 52 (2006) , 4257-4261.
	P. Rizomiliotis and N. Kalouptsidis , Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005) , 1555-1563.
	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.