# 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] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [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] 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 [11] 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 [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] 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 [14] Yixiao Qiao, Xiaoyao Zhou. Zero sequence entropy and entropy dimension. Discrete & Continuous Dynamical Systems - A, 2017, 37 (1) : 435-448. doi: 10.3934/dcds.2017018 [15] 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 [16] 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 [17] 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 [18] Godofredo Iommi, Bartłomiej Skorulski. Multifractal analysis for the exponential family. Discrete & Continuous Dynamical Systems - A, 2006, 16 (4) : 857-869. doi: 10.3934/dcds.2006.16.857 [19] Jana Majerová. Correlation integral and determinism for a family of $2^\infty$ maps. Discrete & Continuous Dynamical Systems - A, 2016, 36 (9) : 5067-5096. doi: 10.3934/dcds.2016020 [20] José S. Cánovas. Topological sequence entropy of $\omega$–limit sets of interval maps. Discrete & Continuous Dynamical Systems - A, 2001, 7 (4) : 781-786. doi: 10.3934/dcds.2001.7.781

2017 Impact Factor: 0.564

## Tools

Article outline

Figures and Tables