American Institute of Mathematical Sciences

November  2017, 11(4): 671-691. doi: 10.3934/amc.2017049

A new nonbinary sequence family with low correlation and large size

 1 School of Mathematical Sciences, Huaiyin Normal University, Huaian 223300, China 2 School of Mathematics & Computation Science, Anqing Normal University, Anqing 246133, China 3 School of Mathematics and Statistics, & Hubei Key Laboratory of Mathematical Sciences, Central China Normal University, Wuhan 430079, China 4 School of Mathematical Sciences, Yangzhou University, Yangzhou 225002, China

* Corresponding author

Received  May 2015 Revised  February 2016 Published  November 2017

Let $p$ be an odd prime, $n≥q3$ and $k$ positive integers with $e=\gcd(n,k)$. In this paper, a new family $\mathcal{S}$ of $p$-ary sequences with period $N=p^n-1$ is proposed. The sequences in $\mathcal{S}$ are constructed by adding a $p$-ary sequence to its two decimated sequences with different phase shifts. The correlation distribution among sequences in $\mathcal{S}$ is completely determined. It is shown that the maximum magnitude of nontrivial correlations of $\mathcal{S}$ is upper bounded by $p^e\sqrt{N+1}+1$, and the family size of $\mathcal{S}$ is $N^2$. Our sequence family has a large family size and low correlation.

Citation: Hua Liang, Wenbing Chen, Jinquan Luo, Yuansheng Tang. A new nonbinary sequence family with low correlation and large size. Advances in Mathematics of Communications, 2017, 11 (4) : 671-691. doi: 10.3934/amc.2017049
References:
 [1] S. T. Choi, T. Lim, J. S. No and H. Chung, On the cross-correlation of a $p$-ary m-sequence of period $p^{2m}-1$ and its decimated sequence by $\frac{(p^{m}+1)^{2}}{2(p+1)}$, IEEE Trans. Inf. Theory, 58 (2012), 1873-1879.  doi: 10.1109/TIT.2011.2177573.  Google Scholar [2] G. Gong, New designs for signal sets with low cross correlation, balance property, and large linear span: GF(p) case, IEEE Trans. Inf. Theory, 48 (2002), 2847-2867.  doi: 10.1109/TIT.2002.804044.  Google Scholar [3] T. Helleseth, Some results about the cross-correlation function between two maximal-linear sequence, Discrete Math., 16 (1976), 209-232.  doi: 10.1016/0012-365X(76)90100-X.  Google Scholar [4] T. Kasami, Weight distribution of Bose-Chaudhuri-Hocquenghem codes, in Combinatorial Mathematics and Its Applications, Chapel Hill, NC: Univ. North Carolina Press, 1969,335-357.  Google Scholar [5] T. Kasami, Weight Distribution Formular for Some Class of Cyclic Codes, Coordinated Science Lab., Univ. Illinois at Urbana-Champaign, Urbana, IL, Tech. Rep. R-285(AD 637524), 1966. Google Scholar [6] J. Y. Kim, S. T. Choi, J. S. No and H. Chung, A new family of $p$-ary sequences of period $(p^n-1)/2$ with low correlation, IEEE Trans. Inf. Theory, 57 (2011), 3825-3830.  doi: 10.1109/TIT.2011.2133730.  Google Scholar [7] D. S. Kim, H. J. Chae and H. Y. Song, A generalizaton of the family of $p$-ary decimated sequences with low correlation, IEEE Trans. Inf. Theory, 57 (2011), 7614-7617.  doi: 10.1109/TIT.2011.2159576.  Google Scholar [8] P. V. Kumar and O. Moreno, Prime-phase sequences with periodic correlation properites better than binary sequences, IEEE Trans. Inf. Theory, 37 (1991), 603-616.   Google Scholar [9] H. Liang and Y. Tang, The cross correlation distribution of a $p$-ary $m$-sequence of period $p^m-1$ and its decimated sequences by $(p^k+1)(p^m+1)/4$, Finite Fields Appl., 31 (2015), 137-161.  doi: 10.1016/j.ffa.2014.10.005.  Google Scholar [10] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and Its Applications, Addison-Wesley, Reading, MA, 1983.  Google Scholar [11] S. C. Liu and J. J. Komo, Nonbinary Kasami sequences over $GF(p)$, IEEE Trans. Inf. Theory, 38 (1992), 1409-1412.  doi: 10.1109/18.144728.  Google Scholar [12] J. Luo and K. Feng, On the weight distribution of two classes of cyclic codes, IEEE Trans. Inf. Theory, 54 (2008), 5332-5344.  doi: 10.1109/TIT.2008.2006424.  Google Scholar [13] J. Luo and K. Feng, Cyclic codes and sequences from generalized Coulter-Matthews function, IEEE Trans. Inf. Theory, 54 (2008), 5345-5353.  doi: 10.1109/TIT.2008.2006394.  Google Scholar [14] J. Luo, T. Helleseth and A. Kholosha, Two nonbinary sequences with six-valued cross correlation, in Proceeding of IWSDA'11, 2011, 44-47. doi: 10.1109/IWSDA.2011.6159435.  Google Scholar [15] E. N. Muller, On the crosscorrelation of sequences over $GF(p)$ with short periods, IEEE Trans. Inf. Theory, 45 (1999), 289-295.  doi: 10.1109/18.746820.  Google Scholar [16] G. J. Ness, T. Helleseth and A. Kholosha, On the correlation distribution of the Coulter-Matthews decimation, IEEE Trans. Inf. Theory, 52 (2006), 2241-2247.  doi: 10.1109/TIT.2006.872857.  Google Scholar [17] E. Y. Seo, Y. S. Kim, J. S. No and D. J. Shin, Cross-correlation distribution of p-ary m-sequence of period $p^{4k}-1$ and its decimated sequences by $(\frac{p^{2k}+1}{2})^{2}$, IEEE Trans. Inf. Theory, 54 (2008), 3140-3149.  doi: 10.1109/TIT.2008.924694.  Google Scholar [18] Y. Sun, Z. Wang, H. Li and T. Yan, The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$, Adv. Math. Commun., 7 (2013), 409-424.  doi: 10.3934/amc.2013.7.409.  Google Scholar [19] Y. Xia, X. Zeng and L. Hu, Further crosscorrelation properties of sequences with the decimation factor $d=\frac{p^n+1}{p+1}-\frac{p^n-1}{2}$, Appl. Algebra Eng. Commun. Comput., 21 (2010), 329-342.  doi: 10.1007/s00200-010-0128-y.  Google Scholar [20] Y. Xia and S. Chen, A new family of $p$-ary sequences with low correlation constructed from decimated sequences, IEEE Trans. Inf. Theory, 58 (2012), 6037-6046.  doi: 10.1109/TIT.2012.2201132.  Google Scholar [21] N. Y. Yu and G. Gong, A new binary sequence family with low correlation and large size, IEEE Trans. Inf. Theory, 52 (2006), 1624-1636.  doi: 10.1109/TIT.2006.871062.  Google Scholar

show all references

References:
 [1] S. T. Choi, T. Lim, J. S. No and H. Chung, On the cross-correlation of a $p$-ary m-sequence of period $p^{2m}-1$ and its decimated sequence by $\frac{(p^{m}+1)^{2}}{2(p+1)}$, IEEE Trans. Inf. Theory, 58 (2012), 1873-1879.  doi: 10.1109/TIT.2011.2177573.  Google Scholar [2] G. Gong, New designs for signal sets with low cross correlation, balance property, and large linear span: GF(p) case, IEEE Trans. Inf. Theory, 48 (2002), 2847-2867.  doi: 10.1109/TIT.2002.804044.  Google Scholar [3] T. Helleseth, Some results about the cross-correlation function between two maximal-linear sequence, Discrete Math., 16 (1976), 209-232.  doi: 10.1016/0012-365X(76)90100-X.  Google Scholar [4] T. Kasami, Weight distribution of Bose-Chaudhuri-Hocquenghem codes, in Combinatorial Mathematics and Its Applications, Chapel Hill, NC: Univ. North Carolina Press, 1969,335-357.  Google Scholar [5] T. Kasami, Weight Distribution Formular for Some Class of Cyclic Codes, Coordinated Science Lab., Univ. Illinois at Urbana-Champaign, Urbana, IL, Tech. Rep. R-285(AD 637524), 1966. Google Scholar [6] J. Y. Kim, S. T. Choi, J. S. No and H. Chung, A new family of $p$-ary sequences of period $(p^n-1)/2$ with low correlation, IEEE Trans. Inf. Theory, 57 (2011), 3825-3830.  doi: 10.1109/TIT.2011.2133730.  Google Scholar [7] D. S. Kim, H. J. Chae and H. Y. Song, A generalizaton of the family of $p$-ary decimated sequences with low correlation, IEEE Trans. Inf. Theory, 57 (2011), 7614-7617.  doi: 10.1109/TIT.2011.2159576.  Google Scholar [8] P. V. Kumar and O. Moreno, Prime-phase sequences with periodic correlation properites better than binary sequences, IEEE Trans. Inf. Theory, 37 (1991), 603-616.   Google Scholar [9] H. Liang and Y. Tang, The cross correlation distribution of a $p$-ary $m$-sequence of period $p^m-1$ and its decimated sequences by $(p^k+1)(p^m+1)/4$, Finite Fields Appl., 31 (2015), 137-161.  doi: 10.1016/j.ffa.2014.10.005.  Google Scholar [10] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and Its Applications, Addison-Wesley, Reading, MA, 1983.  Google Scholar [11] S. C. Liu and J. J. Komo, Nonbinary Kasami sequences over $GF(p)$, IEEE Trans. Inf. Theory, 38 (1992), 1409-1412.  doi: 10.1109/18.144728.  Google Scholar [12] J. Luo and K. Feng, On the weight distribution of two classes of cyclic codes, IEEE Trans. Inf. Theory, 54 (2008), 5332-5344.  doi: 10.1109/TIT.2008.2006424.  Google Scholar [13] J. Luo and K. Feng, Cyclic codes and sequences from generalized Coulter-Matthews function, IEEE Trans. Inf. Theory, 54 (2008), 5345-5353.  doi: 10.1109/TIT.2008.2006394.  Google Scholar [14] J. Luo, T. Helleseth and A. Kholosha, Two nonbinary sequences with six-valued cross correlation, in Proceeding of IWSDA'11, 2011, 44-47. doi: 10.1109/IWSDA.2011.6159435.  Google Scholar [15] E. N. Muller, On the crosscorrelation of sequences over $GF(p)$ with short periods, IEEE Trans. Inf. Theory, 45 (1999), 289-295.  doi: 10.1109/18.746820.  Google Scholar [16] G. J. Ness, T. Helleseth and A. Kholosha, On the correlation distribution of the Coulter-Matthews decimation, IEEE Trans. Inf. Theory, 52 (2006), 2241-2247.  doi: 10.1109/TIT.2006.872857.  Google Scholar [17] E. Y. Seo, Y. S. Kim, J. S. No and D. J. Shin, Cross-correlation distribution of p-ary m-sequence of period $p^{4k}-1$ and its decimated sequences by $(\frac{p^{2k}+1}{2})^{2}$, IEEE Trans. Inf. Theory, 54 (2008), 3140-3149.  doi: 10.1109/TIT.2008.924694.  Google Scholar [18] Y. Sun, Z. Wang, H. Li and T. Yan, The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$, Adv. Math. Commun., 7 (2013), 409-424.  doi: 10.3934/amc.2013.7.409.  Google Scholar [19] Y. Xia, X. Zeng and L. Hu, Further crosscorrelation properties of sequences with the decimation factor $d=\frac{p^n+1}{p+1}-\frac{p^n-1}{2}$, Appl. Algebra Eng. Commun. Comput., 21 (2010), 329-342.  doi: 10.1007/s00200-010-0128-y.  Google Scholar [20] Y. Xia and S. Chen, A new family of $p$-ary sequences with low correlation constructed from decimated sequences, IEEE Trans. Inf. Theory, 58 (2012), 6037-6046.  doi: 10.1109/TIT.2012.2201132.  Google Scholar [21] N. Y. Yu and G. Gong, A new binary sequence family with low correlation and large size, IEEE Trans. Inf. Theory, 52 (2006), 1624-1636.  doi: 10.1109/TIT.2006.871062.  Google Scholar
 [1] Yuhua Sun, Zilong Wang, Hui Li, Tongjiang Yan. The cross-correlation distribution of a $p$-ary $m$-sequence of period $p^{2k}-1$ and its decimated sequence by $\frac{(p^{k}+1)^{2}}{2(p^{e}+1)}$. Advances in Mathematics of Communications, 2013, 7 (4) : 409-424. doi: 10.3934/amc.2013.7.409 [2] 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 [3] Xiaohui Liu, Jinhua Wang, Dianhua Wu. Two new classes of binary sequence pairs with three-level cross-correlation. Advances in Mathematics of Communications, 2015, 9 (1) : 117-128. doi: 10.3934/amc.2015.9.117 [4] Wenbing Chen, Jinquan Luo, Yuansheng Tang, Quanquan Liu. Some new results on cross correlation of $p$-ary $m$-sequence and its decimated sequence. Advances in Mathematics of Communications, 2015, 9 (3) : 375-390. doi: 10.3934/amc.2015.9.375 [5] Ferruh Özbudak, Eda Tekin. Correlation distribution of a sequence family generalizing some sequences of Trachtenberg. Advances in Mathematics of Communications, 2021, 15 (4) : 647-662. doi: 10.3934/amc.2020087 [6] Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021044 [7] Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475 [8] Aixian Zhang, Zhengchun Zhou, Keqin Feng. A lower bound on the average Hamming correlation of frequency-hopping sequence sets. Advances in Mathematics of Communications, 2015, 9 (1) : 55-62. doi: 10.3934/amc.2015.9.55 [9] Samuel T. Blake, Thomas E. Hall, Andrew Z. Tirkel. Arrays over roots of unity with perfect autocorrelation and good ZCZ cross-correlation. Advances in Mathematics of Communications, 2013, 7 (3) : 231-242. doi: 10.3934/amc.2013.7.231 [10] Zhenyu Zhang, Lijia Ge, Fanxin Zeng, Guixin Xuan. Zero correlation zone sequence set with inter-group orthogonal and inter-subgroup complementary properties. Advances in Mathematics of Communications, 2015, 9 (1) : 9-21. doi: 10.3934/amc.2015.9.9 [11] Huaning Liu, Xi Liu. On the correlation measures of orders $3$ and $4$ of binary sequence of period $p^2$ derived from Fermat quotients. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021008 [12] Limengnan Zhou, Daiyuan Peng, Hongyu Han, Hongbin Liang, Zheng Ma. Construction of optimal low-hit-zone frequency hopping sequence sets under periodic partial Hamming correlation. Advances in Mathematics of Communications, 2018, 12 (1) : 67-79. doi: 10.3934/amc.2018004 [13] Valery Y. Glizer, Oleg Kelis. Singular infinite horizon zero-sum linear-quadratic differential game: Saddle-point equilibrium sequence. Numerical Algebra, Control & Optimization, 2017, 7 (1) : 1-20. doi: 10.3934/naco.2017001 [14] Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015 [15] Yixiao Qiao, Xiaoyao Zhou. Zero sequence entropy and entropy dimension. Discrete & Continuous Dynamical Systems, 2017, 37 (1) : 435-448. doi: 10.3934/dcds.2017018 [16] Walter Briec, Bernardin Solonandrasana. Some remarks on a successive projection sequence. Journal of Industrial & Management Optimization, 2006, 2 (4) : 451-466. doi: 10.3934/jimo.2006.2.451 [17] Kai-Uwe Schmidt, Jonathan Jedwab, Matthew G. Parker. Two binary sequence families with large merit factor. Advances in Mathematics of Communications, 2009, 3 (2) : 135-156. doi: 10.3934/amc.2009.3.135 [18] Matthew Macauley, Henning S. Mortveit. Update sequence stability in graph dynamical systems. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1533-1541. doi: 10.3934/dcdss.2011.4.1533 [19] Wenjun Xia, Jinzhi Lei. Formulation of the protein synthesis rate with sequence information. Mathematical Biosciences & Engineering, 2018, 15 (2) : 507-522. doi: 10.3934/mbe.2018023 [20] Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2021, 14 (8) : 3017-3025. doi: 10.3934/dcdss.2020465

2020 Impact Factor: 0.935