# American Institute of Mathematical Sciences

November  2017, 11(4): 693-703. doi: 10.3934/amc.2017050

## On cross-correlation of a binary $m$-sequence of period $2^{2k}-1$ and its decimated sequences by $(2^{lk}+1)/(2^l+1)$

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

Received  October 2015 Revised  March 2016 Published  November 2017

For two odd integers $l,k$ with $0<l<k$ and $\gcd(l,k)=1$, let $m=2k$ and $d=\frac{2^{lk}+1}{2^l+1}$. In this paper, we study the cross-correlation between a binary $m$-sequence $(s_t)$ of length $2^m-1$ and its $d$-decimated sequences $(s_{dt+u}), 0≤q u<\frac{2^k+1}{3}.$ It is shown that the maximum magnitude of cross-correlation values is $2^{\frac{m}{2}+1}+1.$ Moreover, a new sequence family with maximum correlation magnitude $2^{\frac{m}{2}+1}+1$ and family size $2^{\frac{m}{2}}$ is proposed.

Citation: 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
##### References:
 [1] S. T. Choi, J. Y. Kim and J. S. No, On the cross-correlation of a $p$-ary m-sequence and its decimated sequence by $d=\frac{p^n+1}{p^k+1}+\frac{p^n-1}{2}$, arXiv: 1205.5959v1, 2012 [2] 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. [3] H. Dobbertin, T. Helleseth, P. V. Kumar and H. Martinsen, Ternary $m$-sequences with three-valued cross-correlation function: New decimations of Welch and Niho type, IEEE Trans. Inf. Theory, 47 (2001), 1473-1481.  doi: 10.1109/18.923728. [4] H. Dobbertin, P. Felke, T. Helleseth and P. Rosendahl, Niho type cross-correlation functions via Dickson polynomials and Kloosterman sums, IEEE Trans. Inf. Theory, 52 (2006), 613-627.  doi: 10.1109/TIT.2005.862094. [5] R. Gold, Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Trans. Inf. Theory, 14 (1968), 154-156.  doi: 10.1109/TIT.1968.1054106. [6] 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. [7] T. Helleseth, Some results about the cross-correlation function between two maximal-linear sequences, Discrete Math., 16 (1976), 209-232.  doi: 10.1016/0012-365X(76)90100-X. [8] T. Helleseth and P. V. Kumar, Sequences with low correlation, Handbook of Coding Theory, Vol. Ⅰ, Ⅱ, 1765-1853, North-Holland, Amsterdam, 1998. [9] Z. Hu, X. Li, D. Mills, E. Muller, W. Williems, Y. Yang and Z. Zhang, On the cross-correlation of sequences with the decimation factor $d=\frac{p^n+1}{p+1}-\frac{p^n-1}{2}$, Appl. Algebra Eng. Commun. Comput., 12 (2001), 255-263. [10] 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-3829.  doi: 10.1109/TIT.2011.2133730. [11] 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. [12] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, 20. Cambridge University Press, Cambridge, 1997. [13] S. C. Liu and J. F. Komo, Nonbinary Kasami sequences over $GF(p)$, IEEE Trans. Inf. Theory, 38 (1992), 1409-1412.  doi: 10.1109/18.144728. [14] J. Luo, Binary sequences with three-valued cross correlations of different lengths, IEEE Transactions on Information Theory, 62 (2016), 7532-7537, arXiv: 1503.05650v1. doi: 10.1109/TIT.2016.2620432. [15] J. Luo, T. Helleseth and A. Kholosha, Two nonbinary sequences with six-valued cross correlation, in Proceeding of IWSDA'11, 2001, 44-47. doi: 10.1109/IWSDA.2011.6159435. [16] M. Moisio, A note on evaluations of some exponential sums, Acta Arith., 93 (2000), 117-119. [17] G. J. Ness and T. Helleseth, Cross correlation of $m$-sequences with different lengths, IEEE Trans. Inf. Theory, 52 (2006), 1637-1648.  doi: 10.1109/TIT.2006.871049. [18] G. J. Ness and T. Helleseth, A new three-valued cross correlation between $m$-sequences of different lengths, IEEE Trans. Inf. Theory, 52 (2006), 4695-4701.  doi: 10.1109/TIT.2006.881715. [19] G. J. Ness and T. Helleseth, Characterization of $m$-sequences of length $2^{2k}-1$ and $2^k-1$ with three-valued cross correlation, IEEE Trans. Inf. Theory, 53 (2007), 2236-2245.  doi: 10.1109/TIT.2007.896881. [20] J. S. No and P. V. Kumar, A new family of binary pseudorandom sequences having optimal periodic correlation properties and larger linear span, IEEE Trans. Inf. Theory, 35 (1989), 371-379.  doi: 10.1109/18.32131. [21] 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. [22] 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. [23] 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.

show all references

##### References:
 [1] S. T. Choi, J. Y. Kim and J. S. No, On the cross-correlation of a $p$-ary m-sequence and its decimated sequence by $d=\frac{p^n+1}{p^k+1}+\frac{p^n-1}{2}$, arXiv: 1205.5959v1, 2012 [2] 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. [3] H. Dobbertin, T. Helleseth, P. V. Kumar and H. Martinsen, Ternary $m$-sequences with three-valued cross-correlation function: New decimations of Welch and Niho type, IEEE Trans. Inf. Theory, 47 (2001), 1473-1481.  doi: 10.1109/18.923728. [4] H. Dobbertin, P. Felke, T. Helleseth and P. Rosendahl, Niho type cross-correlation functions via Dickson polynomials and Kloosterman sums, IEEE Trans. Inf. Theory, 52 (2006), 613-627.  doi: 10.1109/TIT.2005.862094. [5] R. Gold, Maximal recursive sequences with 3-valued recursive cross-correlation functions, IEEE Trans. Inf. Theory, 14 (1968), 154-156.  doi: 10.1109/TIT.1968.1054106. [6] 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. [7] T. Helleseth, Some results about the cross-correlation function between two maximal-linear sequences, Discrete Math., 16 (1976), 209-232.  doi: 10.1016/0012-365X(76)90100-X. [8] T. Helleseth and P. V. Kumar, Sequences with low correlation, Handbook of Coding Theory, Vol. Ⅰ, Ⅱ, 1765-1853, North-Holland, Amsterdam, 1998. [9] Z. Hu, X. Li, D. Mills, E. Muller, W. Williems, Y. Yang and Z. Zhang, On the cross-correlation of sequences with the decimation factor $d=\frac{p^n+1}{p+1}-\frac{p^n-1}{2}$, Appl. Algebra Eng. Commun. Comput., 12 (2001), 255-263. [10] 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-3829.  doi: 10.1109/TIT.2011.2133730. [11] 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. [12] R. Lidl and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and its Applications, 20. Cambridge University Press, Cambridge, 1997. [13] S. C. Liu and J. F. Komo, Nonbinary Kasami sequences over $GF(p)$, IEEE Trans. Inf. Theory, 38 (1992), 1409-1412.  doi: 10.1109/18.144728. [14] J. Luo, Binary sequences with three-valued cross correlations of different lengths, IEEE Transactions on Information Theory, 62 (2016), 7532-7537, arXiv: 1503.05650v1. doi: 10.1109/TIT.2016.2620432. [15] J. Luo, T. Helleseth and A. Kholosha, Two nonbinary sequences with six-valued cross correlation, in Proceeding of IWSDA'11, 2001, 44-47. doi: 10.1109/IWSDA.2011.6159435. [16] M. Moisio, A note on evaluations of some exponential sums, Acta Arith., 93 (2000), 117-119. [17] G. J. Ness and T. Helleseth, Cross correlation of $m$-sequences with different lengths, IEEE Trans. Inf. Theory, 52 (2006), 1637-1648.  doi: 10.1109/TIT.2006.871049. [18] G. J. Ness and T. Helleseth, A new three-valued cross correlation between $m$-sequences of different lengths, IEEE Trans. Inf. Theory, 52 (2006), 4695-4701.  doi: 10.1109/TIT.2006.881715. [19] G. J. Ness and T. Helleseth, Characterization of $m$-sequences of length $2^{2k}-1$ and $2^k-1$ with three-valued cross correlation, IEEE Trans. Inf. Theory, 53 (2007), 2236-2245.  doi: 10.1109/TIT.2007.896881. [20] J. S. No and P. V. Kumar, A new family of binary pseudorandom sequences having optimal periodic correlation properties and larger linear span, IEEE Trans. Inf. Theory, 35 (1989), 371-379.  doi: 10.1109/18.32131. [21] 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. [22] 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. [23] 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.
 [1] 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 [2] 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 [3] 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 [4] 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 [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] 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 [7] 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 [8] 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 and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044 [9] 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 [10] 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 [11] Ji-Woong Jang, Young-Sik Kim, Sang-Hyo Kim. New design of quaternary LCZ and ZCZ sequence set from binary LCZ and ZCZ sequence set. Advances in Mathematics of Communications, 2009, 3 (2) : 115-124. doi: 10.3934/amc.2009.3.115 [12] 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 [13] 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 [14] 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 [15] Valery Y. Glizer, Oleg Kelis. Singular infinite horizon zero-sum linear-quadratic differential game: Saddle-point equilibrium sequence. Numerical Algebra, Control and Optimization, 2017, 7 (1) : 1-20. doi: 10.3934/naco.2017001 [16] Xiujie Zhang, Xianhua Niu, Xin Tan. Constructions of optimal low hit zone frequency hopping sequence sets with large family size. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2021071 [17] 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 [18] Yixiao Qiao, Xiaoyao Zhou. Zero sequence entropy and entropy dimension. Discrete and Continuous Dynamical Systems, 2017, 37 (1) : 435-448. doi: 10.3934/dcds.2017018 [19] Walter Briec, Bernardin Solonandrasana. Some remarks on a successive projection sequence. Journal of Industrial and Management Optimization, 2006, 2 (4) : 451-466. doi: 10.3934/jimo.2006.2.451 [20] Matthew Macauley, Henning S. Mortveit. Update sequence stability in graph dynamical systems. Discrete and Continuous Dynamical Systems - S, 2011, 4 (6) : 1533-1541. doi: 10.3934/dcdss.2011.4.1533

2020 Impact Factor: 0.935