• 1. AIMS Journals
  2. {{journal.titleEn}}  {{journal.titleEn}} 

     {{journal.titleEn}}  {{journal.titleEn}} 
  4. AIMS Press Math Journals
  5. {{journal.titleEn}}  {{journal.titleEn}} 
  7. Book Series
  8. {{book.nameEn}}
  1. {{subColumn.name}}

Abstract

• Abstract

  In this paper, we characterize all nonbinary sequences of length $ n $ with nonlinear complexity $ n-4 $ for $ n\geq9 $ and establish a formula on the number of such sequences. More generally, we characterize other finite length nonbinary sequences with large nonlinear complexity over $ \mathbb{Z}_{m} $.

  Keywords:
  • Finite length sequence,
  • nonbinary sequence over $ \mathbb{Z}_{m} $,
  • nonlinear complexity,
  • $ k $-error nonlinear complexity,
  • feedback shift register.
  Mathematics Subject Classification:Primary: 94A55; Secondary: 94A60.

  Citation:

  \begin{equation} \\ \end{equation}
Full Text(HTML)
• 

• Table 1. Binary sequences of length 13 with nonlinear complexity 9 and their distribution

  set	Sequences	$ \# $ Seq.
  $ E_3(A_{10}) $	0000000001000, 0000000001100, 0000000001010, 0000000001110, 0000000001001
  	0000000001101, 0000000001011, 0000000001111, 1111111110000, 1111111110100	16
  	1111111110010, 1111111110110, 1111111110001, 1111111110101, 1111111110011
  	1111111110111
  $ E_2(A_{11}) $	0101010101100, 0101010101110, 0101010101101, 0101010101111, 0111111111000
  	0111111111010, 0111111111001, 0111111111011, 1010101010000, 1010101010010	16
  	1010101010001, 1010101010011, 1000000000100, 1000000000110, 1000000000101
  	1000000000111
  $ E_1(A_{12}) $	0010010010000, 0010010010001, 0010101010110, 0010101010111, 0011111111100
  	0011111111101, 1101101101110, 1101101101111, 1101010101000, 1101010101001	24
  	1100000000010, 1100000000011, 0100100100110, 0100100100111, 0100000000010
  	0100000000011, 1011011011000, 1011011011001, 1011111111100, 1011111111101
  	0110110110100, 0110110110101, 1001001001010, 1001001001011
  $ B_1 $	0011001100111, 0011011011010, 1100110011000, 1100100100101, 0110011001101	8
  	0110000000001, 1001100110010, 1001111111110
  $ B_2 $	0001000100011, 0001001001000, 0001010101011, 0001111111110, 1110111011100
  	1110110110111, 1110101010100, 1110000000001, 0010001000101, 0010000000001
  	1101110111010, 1101111111110, 0100010001001, 1011101110110, 0101101101100	22
  	0101111111110, 1010010010011, 1010000000001, 0110101010100, 1001010101011
  	0111011101111, 1000100010000

   | Show Table

  DownLoad:CSV
Related Papers
Cited by
References

• References

  [1]	C. Ding, Linear complexity of generalized cyclotomic binary sequences of order 2,Finite Fields Appl.,3 (1997), 159-174. doi: 10.1006/ffta.1997.0181.
  [2]	O. Geil, O. Ferruh and D. Ruano, Constructing sequences with high nonlinear complexity using the Weierstrass semigroup of a pair of distinct points of a hermitian curve,Semigroup Forum,98 (2019), 543-555. doi: 10.1007/s00233-018-9976-8.
  [3]	C. J. A. Jansen,Investigations on Nonlinear Streamciper Systems: Construction and Evaluation Methods, Ph.D thesis, Dept. Elect. Eng., TU Delft, Delft, The Netherlands, 1989.
  [4]	C. J. A. Jansen and D. E. Boekee, The shortest feedback shift register that can generate a given sequence, inAdvanced in Cryptography - CRYPTO'89, LNCS435 (1990), 90–99.doi: 10.1007/0-387-34805-0_10.
  [5]	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. doi: 10.1109/TIT.2011.2159575.
  [6]	K. Limniotis, N. Kolokotronis and N. Kalouptsidis, On the nonlinear complexity and lempel-Ziv complexity of finite length sequences,IEEE Trans. Inf. Theory,53 (2007), 4293-4302. doi: 10.1109/TIT.2007.907442.
  [7]	Y. Luo, C. Xing and L. You, Construction of sequences with high nonlinear complexity from function fields,IEEE Trans. Inf. Theory,63 (2017), 7646-7650. doi: 10.1109/TIT.2017.2736545.
  [8]	J. L. Massey, Shift-register synthesis and BCH decoding,IEEE Trans. Inf. Theory,15 (1969), 122-127. doi: 10.1109/tit.1969.1054260.
  [9]	W. Meidl and A. Winterhof, On the linear complexity profile of some new explicit inversive pseudorandom numbers,J. Complexity,20 (2004), 350-355. doi: 10.1016/j.jco.2003.08.017.
  [10]	H. Niderreiter, Linear complexity and related complexity measures for sequences,Progress in Cryptology - INDOCRYPT 2003, LNCS2904 (2003), 1–17.doi: 10.1007/978-3-540-24582-7_1.
  [11]	H. Niderreiter and C. Xing, Sequences with high nonlinear complexity,IEEE Trans. Inf. Theory,60 (2014), 6696-6701. doi: 10.1109/TIT.2014.2343225.
  [12]	J. Peng, X. Zeng and Z. Sun, Finite length sequences with large nonlinear complexity,Advance in Mathematics of Communication,12 (2018), 215-230. doi: 10.3934/amc.2018015.
  [13]	P. Rizomiliotis, Constructing periodic binary sequences with maximum nonlinear span,IEEE Trans. Inf. Theory,52 (2006), 4257-4261. doi: 10.1109/TIT.2006.880054.
  [14]	P. Rizomiliotis and N. Kalouptsidis, Results on the nonlinear span of binary sequences,IEEE Trans. Inf. Theory,51 (2005), 1555-1563. doi: 10.1109/TIT.2005.844090.
  [15]	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. doi: 10.1109/TIT.2017.2714681.
  [16]	Z. Xiao, X. Zeng, C. Li and Y. Jiang, Binary sequences with period $N$ and nonlinear complexity $N-2$,Cryptography and Communications,11 (2019), 735-757. doi: 10.1007/s12095-018-0324-3.

Access History

• Access History

  

Citation

Format

Content