Table 1.
Binary sequences of length 11 with nonlinear complexity 7 and their distribution
- Previous Article
- AMC Home
- This Issue
-
Next Article
Reduced access structures with four minimal qualified subsets on six participants
February
2018, 12(1): 215-230.
doi: 10.3934/amc.2018015
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 |
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. |
| [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. |
| [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.
|
| [4] |
F. T. Macwilliams and N. J. A. Sloane,
Psedo-Random sequences and arrays, Proc. IEEE, 64 (1976), 1715-1729.
|
| [5] |
W. Meidl and A. Winterhof,
On the linear complexity profile of some new explicit inverse pseudorandom numbers, J. Complexity, 20 (2004), 350-355.
|
| [6] |
H. Niederreite,
Random Number Generation and Quasi-Monte Carlo Methods, Soc. Ind. Appl. Math., Philadelphia, 1992. |
| [7] |
H. Niederreiter, Linear complexity and related complexity measures for sequences, in Progr.
Crypt. -INDOCRYPT 2003, 2003, 1–17. |
| [8] |
P. Rizomiliotis,
Constructing periodic binary sequences of maximum nonlinear span, IEEE Trans. Inf. Theory, 52 (2006), 4257-4261.
|
| [9] |
P. Rizomiliotis and N. Kalouptsidis,
Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1555-1563.
|
| [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.
|
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. |
| [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. |
| [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.
|
| [4] |
F. T. Macwilliams and N. J. A. Sloane,
Psedo-Random sequences and arrays, Proc. IEEE, 64 (1976), 1715-1729.
|
| [5] |
W. Meidl and A. Winterhof,
On the linear complexity profile of some new explicit inverse pseudorandom numbers, J. Complexity, 20 (2004), 350-355.
|
| [6] |
H. Niederreite,
Random Number Generation and Quasi-Monte Carlo Methods, Soc. Ind. Appl. Math., Philadelphia, 1992. |
| [7] |
H. Niederreiter, Linear complexity and related complexity measures for sequences, in Progr.
Crypt. -INDOCRYPT 2003, 2003, 1–17. |
| [8] |
P. Rizomiliotis,
Constructing periodic binary sequences of maximum nonlinear span, IEEE Trans. Inf. Theory, 52 (2006), 4257-4261.
|
| [9] |
P. Rizomiliotis and N. Kalouptsidis,
Results on the nonlinear span of binary sequences, IEEE Trans. Inf. Theory, 51 (2005), 1555-1563.
|
| [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.
|
| | Sequences | # Seq. |
| | 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 |
| | 00110011000, 11001100111, 00110110111, 11001001000, 01100110010 10011001101, 01100000001, 10011111110 | 8 |
| | 00010001001, 11101110110, 00010010011, 11101101100, 00010101011 11101010100, 00011111110, 11100000001, 00100000001, 11011111110 00100010000, 11011101111, 01000100011, 10111011100, 01011011010 10100100101, 01011111110, 10100000001, 01101010100, 10010101011 01110111010, 10001000101 | 22 |
| | Sequences | # Seq. |
| | 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 |
| | 00110011000, 11001100111, 00110110111, 11001001000, 01100110010 10011001101, 01100000001, 10011111110 | 8 |
| | 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 and 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, 2021, 15 (4) : 701-720. doi: 10.3934/amc.2020091 |
| [6] |
Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $ 4p^n $. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021019 |
| [7] |
Huaning Liu, Yixin Ren. On the pseudorandom properties of $ k $-ary Sidel'nikov sequences. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021038 |
| [8] |
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 |
| [9] |
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 |
| [10] |
Pinhui Ke, Panpan Qiao, Yang Yang. On the equivalence of several classes of quaternary sequences with optimal autocorrelation and length $ 2p$. Advances in Mathematics of Communications, 2022, 16 (2) : 285-302. doi: 10.3934/amc.2020112 |
| [11] |
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 |
| [12] |
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 |
| [13] |
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 |
| [14] |
Arne Winterhof, Zibi Xiao. Binary sequences derived from differences of consecutive quadratic residues. Advances in Mathematics of Communications, 2022, 16 (1) : 83-93. doi: 10.3934/amc.2020100 |
| [15] |
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 |
| [16] |
Ryuji Kajikiya, Daisuke Naimen. Two sequences of solutions for indefinite superlinear-sublinear elliptic equations with nonlinear boundary conditions. Communications on Pure and Applied Analysis, 2014, 13 (4) : 1593-1612. doi: 10.3934/cpaa.2014.13.1593 |
| [17] |
E. Camouzis, H. Kollias, I. Leventides. Stable manifold market sequences. Journal of Dynamics and Games, 2018, 5 (2) : 165-185. doi: 10.3934/jdg.2018010 |
| [18] |
Frank Fiedler. Small Golay sequences. Advances in Mathematics of Communications, 2013, 7 (4) : 379-407. doi: 10.3934/amc.2013.7.379 |
| [19] |
Nikolaos S. Papageorgiou, Vicenţiu D. Rădulescu, Jian Zhang. Sequences of high and low energy solutions for weighted (p, q)-equations. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022114 |
| [20] |
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 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]