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

Previous Article
Empirical optimization of divisor arithmetic on hyperelliptic curves over $\mathbb{F}_{2^m}$
AMC Home
This Issue
Next Article
($\sigma,\delta$)-codes

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

Abstract
Related Papers

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.
[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-69. 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-1823. 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), Elsevier Science Publishers, 1998, 1765-1853.
[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.
[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.
[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.
[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.
[10]	V. M. Sidel'nikov, Some $k$-valued pseudo-random sequences and nearly equidistant codes, Probl. Inf. Transm., 5 (1969), 12-16.
[11]	V. M. Sidel'nikov, On mutual correlation of sequences, Soviet Math. Dokl, 12 (1971), 197-201.
[12]	D. Wan, Generators and irreducible polynomials over finite fields, Math. Comput., 66 (1997), 1195-1212. 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-3998. doi: 10.1109/TIT.2013.2243496.
[14]	A. Weil, On some exponential sums, Proc. Natl. Acad. Sci. USA, 34 (1948), 204-207. 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-399.
[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.
[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.

show all references

References:

[1]	P. Deligne, La conjecture de Weil I, Publ. Math. IHES, 43 (1974), 273-307.
[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-69. 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-1823. 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), Elsevier Science Publishers, 1998, 1765-1853.
[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.
[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.
[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.
[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.
[10]	V. M. Sidel'nikov, Some $k$-valued pseudo-random sequences and nearly equidistant codes, Probl. Inf. Transm., 5 (1969), 12-16.
[11]	V. M. Sidel'nikov, On mutual correlation of sequences, Soviet Math. Dokl, 12 (1971), 197-201.
[12]	D. Wan, Generators and irreducible polynomials over finite fields, Math. Comput., 66 (1997), 1195-1212. 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-3998. doi: 10.1109/TIT.2013.2243496.
[14]	A. Weil, On some exponential sums, Proc. Natl. Acad. Sci. USA, 34 (1948), 204-207. 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-399.
[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.
[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.

[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 and 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 and 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]	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
[10]	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
[11]	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
[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]	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
[16]	Arne Winterhof, Zibi Xiao. Binary sequences derived from differences of consecutive quadratic residues. Advances in Mathematics of Communications, 2022, 16 (1) : 83-93. doi: 10.3934/amc.2020100
[17]	Fuqing Sun, Qin Yue, Xia Li. on the 2-adic complexity of cyclotomic binary sequences of order three. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022049
[18]	Harish Garg. Novel correlation coefficients under the intuitionistic multiplicative environment and their applications to decision-making process. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1501-1519. doi: 10.3934/jimo.2018018
[19]	Minjia Shi, Liqin Qian, Tor Helleseth, Patrick Solé. Five-weight codes from three-valued correlation of M-sequences. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021022
[20]	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

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Zilong Wang Guang Gong
on Google Scholar
Zilong Wang Guang Gong

[Back to Top]