American Institute of Mathematical Sciences

Advanced
November  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

Zilong Wang 1, and  Guang Gong 2,

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$.
Keywords: Binary sequences, multiplicative characters, correlation, Weil bound..
Mathematics Subject Classification: Primary: 94B25, 11T2.
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-307.  Google Scholar

[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.  Google Scholar

[3]

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

[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-1823. doi: 10.1109/TIT.2009.2013040.  Google Scholar

[5]

T. Helleseth and P. V. Kumar, Sequences with low correlation, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), Elsevier Science Publishers, 1998, 1765-1853.  Google Scholar

[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-3774. doi: 10.1109/TIT.2008.926428.  Google Scholar

[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-1224. doi: 10.1109/TIT.2006.890723.  Google Scholar

[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-315. doi: 10.1109/ISIT.2006.261604.  Google Scholar

[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-592. doi: 10.1109/18.485726.  Google Scholar

[10]

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

[11]

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

[12]

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

[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-3998. doi: 10.1109/TIT.2013.2243496.  Google Scholar

[14]

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

[15]

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

[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-6387. doi: 10.1109/TIT.2010.2079590.  Google Scholar

[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-4070. doi: 10.1109/TIT.2010.2050793.  Google Scholar

show all references

References:
[1]

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

[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.  Google Scholar

[3]

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

[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-1823. doi: 10.1109/TIT.2009.2013040.  Google Scholar

[5]

T. Helleseth and P. V. Kumar, Sequences with low correlation, in Handbook of Coding Theory (eds. V. Pless and C. Huffman), Elsevier Science Publishers, 1998, 1765-1853.  Google Scholar

[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-3774. doi: 10.1109/TIT.2008.926428.  Google Scholar

[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-1224. doi: 10.1109/TIT.2006.890723.  Google Scholar

[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-315. doi: 10.1109/ISIT.2006.261604.  Google Scholar

[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-592. doi: 10.1109/18.485726.  Google Scholar

[10]

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

[11]

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

[12]

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

[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-3998. doi: 10.1109/TIT.2013.2243496.  Google Scholar

[14]

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

[15]

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

[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-6387. doi: 10.1109/TIT.2010.2079590.  Google Scholar

[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-4070. doi: 10.1109/TIT.2010.2050793.  Google Scholar

[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, 2018, 38 (10) : 5085-5103. doi: 10.3934/dcds.2018223
[6]

Mariusz Lemańczyk, Clemens Müllner. Automatic sequences are orthogonal to aperiodic multiplicative functions. Discrete & Continuous Dynamical Systems, 2020, 40 (12) : 6877-6918. doi: 10.3934/dcds.2020260
[7]

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

Ferruh Özbudak, Eda Tekin. Correlation distribution of a sequence family generalizing some sequences of Trachtenberg. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020087
[10]

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

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

Chunlei Xie, Yujuan Sun. Construction and assignment of orthogonal sequences and zero correlation zone sequences for applications in CDMA systems. Advances in Mathematics of Communications, 2020, 14 (1) : 1-9. doi: 10.3934/amc.2020001
[13]

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

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

Arne Winterhof, Zibi Xiao. Binary sequences derived from differences of consecutive quadratic residues. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020100
[16]

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

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

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

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

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

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences