-
Previous Article
Codes over $ \frak m $-adic completion rings
- AMC Home
- This Issue
-
Next Article
Optimal antiblocking systems of information sets for the binary codes related to triangular graphs
On finite length nonbinary sequences with large nonlinear complexity over the residue ring $ \mathbb{Z}_{m} $
Hubei Key Laboratory of Applied Mathematics, Faculty of Mathematics and Statistics, Hubei University, Wuhan 430062, China |
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} $.
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, in Advanced in Cryptography - CRYPTO'89, LNCS 435 (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, LNCS 2904 (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. |
show all 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, in Advanced in Cryptography - CRYPTO'89, LNCS 435 (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, LNCS 2904 (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. |
set | Sequences | |
0000000001000, 0000000001100, 0000000001010, 0000000001110, 0000000001001 | ||
0000000001101, 0000000001011, 0000000001111, 1111111110000, 1111111110100 | 16 | |
1111111110010, 1111111110110, 1111111110001, 1111111110101, 1111111110011 | ||
1111111110111 | ||
0101010101100, 0101010101110, 0101010101101, 0101010101111, 0111111111000 | ||
0111111111010, 0111111111001, 0111111111011, 1010101010000, 1010101010010 | 16 | |
1010101010001, 1010101010011, 1000000000100, 1000000000110, 1000000000101 | ||
1000000000111 | ||
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 | ||
0011001100111, 0011011011010, 1100110011000, 1100100100101, 0110011001101 | 8 | |
0110000000001, 1001100110010, 1001111111110 | ||
0001000100011, 0001001001000, 0001010101011, 0001111111110, 1110111011100 | ||
1110110110111, 1110101010100, 1110000000001, 0010001000101, 0010000000001 | ||
1101110111010, 1101111111110, 0100010001001, 1011101110110, 0101101101100 | 22 | |
0101111111110, 1010010010011, 1010000000001, 0110101010100, 1001010101011 | ||
0111011101111, 1000100010000 |
set | Sequences | |
0000000001000, 0000000001100, 0000000001010, 0000000001110, 0000000001001 | ||
0000000001101, 0000000001011, 0000000001111, 1111111110000, 1111111110100 | 16 | |
1111111110010, 1111111110110, 1111111110001, 1111111110101, 1111111110011 | ||
1111111110111 | ||
0101010101100, 0101010101110, 0101010101101, 0101010101111, 0111111111000 | ||
0111111111010, 0111111111001, 0111111111011, 1010101010000, 1010101010010 | 16 | |
1010101010001, 1010101010011, 1000000000100, 1000000000110, 1000000000101 | ||
1000000000111 | ||
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 | ||
0011001100111, 0011011011010, 1100110011000, 1100100100101, 0110011001101 | 8 | |
0110000000001, 1001100110010, 1001111111110 | ||
0001000100011, 0001001001000, 0001010101011, 0001111111110, 1110111011100 | ||
1110110110111, 1110101010100, 1110000000001, 0010001000101, 0010000000001 | ||
1101110111010, 1101111111110, 0100010001001, 1011101110110, 0101101101100 | 22 | |
0101111111110, 1010010010011, 1010000000001, 0110101010100, 1001010101011 | ||
0111011101111, 1000100010000 |
[1] |
Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067 |
[2] |
Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $ 8p^s $ over $ \mathbb F_{p^m} + u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020123 |
[3] |
Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167 |
[4] |
Hongwei Liu, Jingge Liu. On $ \sigma $-self-orthogonal constacyclic codes over $ \mathbb F_{p^m}+u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020127 |
[5] |
Junchao Zhou, Yunge Xu, Lisha Wang, Nian Li. Nearly optimal codebooks from generalized Boolean bent functions over $ \mathbb{Z}_{4} $. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020121 |
[6] |
Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020465 |
[7] |
Wenjun Liu, Hefeng Zhuang. Global attractor for a suspension bridge problem with a nonlinear delay term in the internal feedback. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 907-942. doi: 10.3934/dcdsb.2020147 |
[8] |
Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079 |
[9] |
Xiu Ye, Shangyou Zhang, Peng Zhu. A weak Galerkin finite element method for nonlinear conservation laws. Electronic Research Archive, 2021, 29 (1) : 1897-1923. doi: 10.3934/era.2020097 |
[10] |
Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007 |
[11] |
Yuanfen Xiao. Mean Li-Yorke chaotic set along polynomial sequence with full Hausdorff dimension for $ \beta $-transformation. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 525-536. doi: 10.3934/dcds.2020267 |
[12] |
Linglong Du, Min Yang. Pointwise long time behavior for the mixed damped nonlinear wave equation in $ \mathbb{R}^n_+ $. Networks & Heterogeneous Media, 2020 doi: 10.3934/nhm.2020033 |
[13] |
Saadoun Mahmoudi, Karim Samei. Codes over $ \frak m $-adic completion rings. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020122 |
[14] |
Guoliang Zhang, Shaoqin Zheng, Tao Xiong. A conservative semi-Lagrangian finite difference WENO scheme based on exponential integrator for one-dimensional scalar nonlinear hyperbolic equations. Electronic Research Archive, 2021, 29 (1) : 1819-1839. doi: 10.3934/era.2020093 |
[15] |
Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045 |
[16] |
Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089 |
[17] |
Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077 |
[18] |
Divine Wanduku. Finite- and multi-dimensional state representations and some fundamental asymptotic properties of a family of nonlinear multi-population models for HIV/AIDS with ART treatment and distributed delays. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021005 |
[19] |
Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380 |
[20] |
Wenjun Liu, Yukun Xiao, Xiaoqing Yue. Classification of finite irreducible conformal modules over Lie conformal algebra $ \mathcal{W}(a, b, r) $. Electronic Research Archive, , () : -. doi: 10.3934/era.2020123 |
2019 Impact Factor: 0.734
Tools
Metrics
Other articles
by authors
[Back to Top]