2013, 7(4): 475-484. doi: 10.3934/amc.2013.7.475

Correlation of binary sequence families derived from the multiplicative characters of finite fields

1. 

State Key Laboratory of Integrated Service Networks, Xidian University, Xi'an, Shanxi 710071, China

2. 

Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

Received  November 2012 Published  October 2013

In this paper, new constructions of the binary sequence families of period $q-1$ with large family size and low correlation, derived from multiplicative characters of finite fields for odd prime powers, are proposed. For $m ≥ 2$, the maximum correlation magnitudes of new sequence families $\mathcal{S}_m$ are bounded by $(2m-2)\sqrt{q}+2m+2$, and the family sizes of $\mathcal{S}_m$ are given by $q-1$ for $m=2$, $2(q-1)-1$ for $m=3$, $(q^2-1)q^{\frac{m-4}{2}}$ for $m$ even, $m>2$, and $2(q-1)q^{\frac{m-3}{2}}$ for $m$ odd, $m>3$. It is shown that the known binary Sidel'nikov-based sequence families are equivalent to the new constructions for the case $m=2$.
Citation: 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
References:
[1]

P. Deligne, La conjecture de Weil I,, Publ. Math. IHES, 43 (1974), 273.

[2]

S. W. Golomb and G. Gong, Signal Design with Good Correlation: for Wireless Communications, Cryptography and Radar Applications,, Cambridge University Press, (2005). doi: 10.1017/CBO9780511546907.

[3]

L. Goubin, C. Mauduit and A. Sárközy, Construction of large families of pseudorandom binary sequences,, J. Number Theory, 106 (2004), 56. doi: 10.1016/j.jnt.2003.12.002.

[4]

Y. K. Han and K. Yang, New $M$-ary sequence families with low correlation and large size,, IEEE Trans. Inf. Theory, 55 (2009), 1815. doi: 10.1109/TIT.2009.2013040.

[5]

T. Helleseth and P. V. Kumar, Sequences with low correlation,, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), (1998), 1765.

[6]

Y. Kim, J. Chung, J. S. No and H. Chung, New families of $M$-ary sequences with low correlation constructed from Sidel'nikov sequences,, IEEE Trans. Inf. Theory, 54 (2008), 3768. doi: 10.1109/TIT.2008.926428.

[7]

Y. J. Kim and H. Y. Song, Cross correlation of Sidel'nikov sequences and their constant multiples,, IEEE Trans. Inf. Theory, 53 (2007), 1220. doi: 10.1109/TIT.2006.890723.

[8]

Y. J. Kim, H. Y. Song, G. Gong and H. Chung, Crosscorrelation of $q$-ary power residue sequences of period $p$,, in Proc. IEEE ISIT, (2006), 311. doi: 10.1109/ISIT.2006.261604.

[9]

P. V. Kumar, T. Helleseth, A. R. Calderbank and A. R. Hammons, Large families of quaternary sequences with low correlation,, IEEE Trans. Inf. Theory, 42 (1996), 579. doi: 10.1109/18.485726.

[10]

V. M. Sidel'nikov, Some $k$-valued pseudo-random sequences and nearly equidistant codes,, Probl. Inf. Transm., 5 (1969), 12.

[11]

V. M. Sidel'nikov, On mutual correlation of sequences,, Soviet Math. Dokl, 12 (1971), 197.

[12]

D. Wan, Generators and irreducible polynomials over finite fields,, Math. Comput., 66 (1997), 1195. doi: 10.1090/S0025-5718-97-00835-1.

[13]

Z. Wang and G. Gong, New polyphase sequence families with low correlation derived from the Weil bound of exponential sums,, IEEE Trans. Inf. Theory, 59 (2013), 3990. doi: 10.1109/TIT.2013.2243496.

[14]

A. Weil, On some exponential sums,, Proc. Natl. Acad. Sci. USA, 34 (1948), 204. doi: 10.1073/pnas.34.5.204.

[15]

L. R. Welch, Lower bounds on the minimum correlation of signal,, IEEE Trans. Inf. Theory, 20 (1974), 397.

[16]

N. Y. Yu and G. Gong, Multiplicative characters, the Weil Bound, and polyphase sequence families with low correlation,, IEEE Trans. Inf. Theory, 56 (2010), 6376. doi: 10.1109/TIT.2010.2079590.

[17]

N. Y. Yu and G. Gong, New construction of $M$-ary sequence families with low correlation from the structure of Sidelnikov sequences,, IEEE Trans. Inf. Theory, 56 (2010), 4061. doi: 10.1109/TIT.2010.2050793.

show all references

References:
[1]

P. Deligne, La conjecture de Weil I,, Publ. Math. IHES, 43 (1974), 273.

[2]

S. W. Golomb and G. Gong, Signal Design with Good Correlation: for Wireless Communications, Cryptography and Radar Applications,, Cambridge University Press, (2005). doi: 10.1017/CBO9780511546907.

[3]

L. Goubin, C. Mauduit and A. Sárközy, Construction of large families of pseudorandom binary sequences,, J. Number Theory, 106 (2004), 56. doi: 10.1016/j.jnt.2003.12.002.

[4]

Y. K. Han and K. Yang, New $M$-ary sequence families with low correlation and large size,, IEEE Trans. Inf. Theory, 55 (2009), 1815. doi: 10.1109/TIT.2009.2013040.

[5]

T. Helleseth and P. V. Kumar, Sequences with low correlation,, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), (1998), 1765.

[6]

Y. Kim, J. Chung, J. S. No and H. Chung, New families of $M$-ary sequences with low correlation constructed from Sidel'nikov sequences,, IEEE Trans. Inf. Theory, 54 (2008), 3768. doi: 10.1109/TIT.2008.926428.

[7]

Y. J. Kim and H. Y. Song, Cross correlation of Sidel'nikov sequences and their constant multiples,, IEEE Trans. Inf. Theory, 53 (2007), 1220. doi: 10.1109/TIT.2006.890723.

[8]

Y. J. Kim, H. Y. Song, G. Gong and H. Chung, Crosscorrelation of $q$-ary power residue sequences of period $p$,, in Proc. IEEE ISIT, (2006), 311. doi: 10.1109/ISIT.2006.261604.

[9]

P. V. Kumar, T. Helleseth, A. R. Calderbank and A. R. Hammons, Large families of quaternary sequences with low correlation,, IEEE Trans. Inf. Theory, 42 (1996), 579. doi: 10.1109/18.485726.

[10]

V. M. Sidel'nikov, Some $k$-valued pseudo-random sequences and nearly equidistant codes,, Probl. Inf. Transm., 5 (1969), 12.

[11]

V. M. Sidel'nikov, On mutual correlation of sequences,, Soviet Math. Dokl, 12 (1971), 197.

[12]

D. Wan, Generators and irreducible polynomials over finite fields,, Math. Comput., 66 (1997), 1195. doi: 10.1090/S0025-5718-97-00835-1.

[13]

Z. Wang and G. Gong, New polyphase sequence families with low correlation derived from the Weil bound of exponential sums,, IEEE Trans. Inf. Theory, 59 (2013), 3990. doi: 10.1109/TIT.2013.2243496.

[14]

A. Weil, On some exponential sums,, Proc. Natl. Acad. Sci. USA, 34 (1948), 204. doi: 10.1073/pnas.34.5.204.

[15]

L. R. Welch, Lower bounds on the minimum correlation of signal,, IEEE Trans. Inf. Theory, 20 (1974), 397.

[16]

N. Y. Yu and G. Gong, Multiplicative characters, the Weil Bound, and polyphase sequence families with low correlation,, IEEE Trans. Inf. Theory, 56 (2010), 6376. doi: 10.1109/TIT.2010.2079590.

[17]

N. Y. Yu and G. Gong, New construction of $M$-ary sequence families with low correlation from the structure of Sidelnikov sequences,, IEEE Trans. Inf. Theory, 56 (2010), 4061. doi: 10.1109/TIT.2010.2050793.

[1]

Nam Yul Yu. A Fourier transform approach for improving the Levenshtein's lower bound on aperiodic correlation of binary sequences. Advances in Mathematics of Communications, 2014, 8 (2) : 209-222. doi: 10.3934/amc.2014.8.209

[2]

Xing Liu, Daiyuan Peng. Sets of frequency hopping sequences under aperiodic Hamming correlation: Upper bound and optimal constructions. Advances in Mathematics of Communications, 2014, 8 (3) : 359-373. doi: 10.3934/amc.2014.8.359

[3]

Nian Li, Xiaohu Tang, Tor Helleseth. A class of quaternary sequences with low correlation. Advances in Mathematics of Communications, 2015, 9 (2) : 199-210. doi: 10.3934/amc.2015.9.199

[4]

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

[5]

Yu Zheng, Li Peng, Teturo Kamae. Characterization of noncorrelated pattern sequences and correlation dimensions. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 5085-5103. doi: 10.3934/dcds.2018223

[6]

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

[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]

Wei-Wen Hu. Integer-valued Alexis sequences with large zero correlation zone. Advances in Mathematics of Communications, 2017, 11 (3) : 445-452. doi: 10.3934/amc.2017037

[9]

Xing Liu, Daiyuan Peng. Frequency hopping sequences with optimal aperiodic Hamming correlation by interleaving techniques. Advances in Mathematics of Communications, 2017, 11 (1) : 151-159. doi: 10.3934/amc.2017009

[10]

Yael Ben-Haim, Simon Litsyn. A new upper bound on the rate of non-binary codes. Advances in Mathematics of Communications, 2007, 1 (1) : 83-92. doi: 10.3934/amc.2007.1.83

[11]

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

[12]

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

[13]

Harish Garg. Novel correlation coefficients under the intuitionistic multiplicative environment and their applications to decision-making process. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1501-1519. doi: 10.3934/jimo.2018018

[14]

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

[15]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016

[16]

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

[17]

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

[18]

David Kazhdan and Yakov Varshavsky. Endoscopic decomposition of characters of certain cuspidal representations. Electronic Research Announcements, 2004, 10: 11-20.

[19]

Lassi Roininen, Markku S. Lehtinen, Sari Lasanen, Mikko Orispää, Markku Markkanen. Correlation priors. Inverse Problems & Imaging, 2011, 5 (1) : 167-184. doi: 10.3934/ipi.2011.5.167

[20]

Ming Su, Arne Winterhof. Hamming correlation of higher order. Advances in Mathematics of Communications, 2018, 12 (3) : 505-513. doi: 10.3934/amc.2018029

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]