[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Some new balanced and almost balanced quaternary sequences with low autocorrelation

  • Published:
Cryptography and Communications Aims and scope Submit manuscript

Abstract

Quaternary sequences of both even and odd period having low autocorrelation are studied. We construct new families of balanced quaternary sequences of odd period and low autocorrelation using cyclotomic classes of order eight, as well as investigate the linear complexity of some known quaternary sequences of odd period. We discuss a construction given by Chung et al. in “New Quaternary Sequences with Even Period and Three-Valued Autocorrelation” (IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E93-A(1), 309–315 2010) first by pointing out a slight modification and then by showing that, in certain cases, this slight modification generalizes the construction given by Shen et al. in “New Families of Balanced Quaternary Sequences of Even Period with Three-level Optimal Autocorrelation” (IEEE Commun. Lett. 2017(10), 2146–2149 2017). We investigate the linear complexity of these sequences as well.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Arasu, K.T., Ding, C., Helleseth, T., Kumar, P.V., Martinsen, H.M.: Almost difference sets and their sequences with optimal autocorrelation. IEEE Trans. Inf. Theory 47(7), 2934–2943 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  2. Cai, Y., Ding, C.: Binary sequences with optimal autocorrelation. Theor. Comput. Sci. 410(24-25), 2316–2322 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Chung, J., Han, Y.K., Yang, K.: New quaternary sequences with even period and three-valued autocorrelation. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E93-A(1), 309–315 (2010)

    Article  Google Scholar 

  4. Cusick, T.W., Ding, C., Renvall, A.: Stream Ciphers and Number Theory, Volume 55 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam (1998)

    MATH  Google Scholar 

  5. Dillon, J.F., Dobbertin, H.: New cyclic difference sets with Singer parameters. Finite Fields and Their Applications 10(1), 342–289 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Ding, C.: Codes from Difference Sets. World Scientific Publishing Co. Pte. Ltd, Hackensack (2015)

    Google Scholar 

  7. Ding, C., Helleseth, T., Martinsen, H.M.: New families of binary sequences with optimal three-level autocorrelation. IEEE Trans. Inf. Theory 47(1), 428–433 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  8. Edemskiy, V., Ivanov, A.: Autocorrelation and linear complexity of quaternary sequences of period 2p based on cyclotomic classes of order four. IEEE ISIT 47, 3120–3124 (2013)

    Google Scholar 

  9. Edemskiy, V., Ivanov, A.: Linear complexity of quateranary sequences of length pq wtih low autocorrelation. J. Comput. Appl. Math. 259, 555–560 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. Edemskiy, V.: On the linear complexity of binary sequences on the basis of biquadratic and sextic residue classes. Discret. Math. 22(1), 74–82 (2010)

    MathSciNet  Google Scholar 

  11. Fan, P., Darnell, M.: Sequence Design for Communications Applications. Wiley, New York (1996)

    Google Scholar 

  12. Golomb, S.W., Gong, G.: Signal Design for Good Correlation. For Wireless Communication, Cryptography, and Radar. Cambridge University Press, Cambridge (2005)

    Book  MATH  Google Scholar 

  13. Green, D.H., Green, P.R.: Polyphase-related prime sequences. IEE Proc. Comput. Digit. Tech. 148, 53–62 (2001)

    Article  Google Scholar 

  14. Green, D.H., Green, P.R.: Polyphase power residue sequences. Proc. R. Soc. Lond. A 459, 817–827 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  15. Han, Y.K., Yang, K.: Generalized m-ary related-prime sequences. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E91-A, 3685–3690 (2008)

    Article  Google Scholar 

  16. Helleseth, T., Kumar, P.V.: Sequences with low correlation. In: Pless, V.S., Huffman, W.C. (eds.) Handbook of Coding Theory, vol. II, pp. 1765–1854. Elsevier, New York (1998)

  17. Jang, J.W., Kim, Y.S., Kim, S.H., No, J.S.: New quaternary sequences with ideal autocorrelation constructed from binary sequences with ideal autocorrelation. In: Proc. ISIT, Seoul, Korea, pp. 162–166 (2007)

  18. Kim, Y.J., Hong, Y.P., Song, H.Y.: Autocorrelation of some quaternary cyclotomic sequences of length 2p. In: Proc. IWSDA, Chengdu, China, pp. 282–285 (2009)

  19. Kim, Y.S., Jang, J.W., Kim, S.H., No, J.S.: New quaternary sequences with ideal autocorrelation from legendre sequences. In: Proc. ISIT, Seoul, Korea, pp. 282–285 (2009)

  20. Kim, Y.S., Jang, J.W., Kim, S.H., No, J.S.: New quaternary sequences with optimal autocorrelation. In: Proc. ISIT, Seoul, Korea, pp. 278–281 (2009)

  21. Kim, Y.S., Jang, J.W., Kim, S.H., No, J.S.: Linear complexity of quaternary sequences constructed from binary legendre sequences. In: Proc. ISITA, Honolulu, Hawaii, USA, pp. 611–614 (2012)

  22. Krone, S.M., Sarwate, D.V.: Quadriphase sequences for spread spectrum multiple access communinication. IEEE Trans. Inf. Theory 30(3), 520–529 (1984)

    Article  MATH  Google Scholar 

  23. Lempel, A., Cohn, M., Eastman, W.L.: A class of balanced binary sequences with optimal autocorrelation properties. IEEE Trans. Inf. Theory IT-23(1), 38–42 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  24. Lidl, R., Niederreiter, H.: Finite Fields, Volume 20 of Encyclopedia of Mathematics and its Applications. With a Foreword by P. M. Cohn, 2nd edn. Cambridge University Press, Cambridge (1997)

    Google Scholar 

  25. Luke, H.D.: Sequences and arrays with perfect periodic correlation. IEEE Trans. Aerosp. Electron. Syst. 24, 287–294 (1988)

    Article  Google Scholar 

  26. Maschietti, A.: Difference sets and hyperovals. Des. Codes Crypt. 14(1), 89–98 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  27. Michel, J.: Experimental construction of binary matrices with good peak-sidelobe distances. J. Vac. Sci. Technol. B 34, 1–8 (2016)

    Article  Google Scholar 

  28. No, J.S., Chung, H., Song, H.Y., Yang, K., Lee, J.D.: New contruction for binary sequences of period p m,− 1 with optimal autocorrelation using (z + 1)d + a z d + b. IEEE Trans. Inf. Theory 47, 1638–1644 (2001)

    Article  MATH  Google Scholar 

  29. Scholtz, R.A., Welch, L.R.: GMW sequences. IEEE Trans. Inf. Theory 30(3), 548–553 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  30. Shen, X., Jia, Y., Wang, J., Zhang, L.: New families of balanced quaternary sequences of even period with three-level optimal autocorrelation. IEEE Commun. Lett. 21(10), 2146–2149 (2017)

    Article  Google Scholar 

  31. Sidelnikov, V.M.: Some k-valued pseudo-random sequences and nearly equidistant codes. Problemy Peredaci Informacii 5(1), 16–22 (1969)

    MathSciNet  Google Scholar 

  32. Simon, M.K., Omura, J.K., Scholtz, R.A., Levitt, B.K.: Spread Spectrum Communications, vol. 1–3. Computer Science Press, Inc., New York (1986)

    Google Scholar 

  33. Storer, T.: Cyclotomy and Difference Sets, pp. 65–72. Markham, Chicago (1967)

  34. Su, W., Yang, Y., Zhou, Z.C., Tang, X.H.: New Quaternary Sequences of Even Length with Optimal Autocorrelation. Science China. To appear (2017)

  35. Tang, X.H., Ding, C.: New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value. IEEE Trans. Inf. Theory 56(12), 6398–6405 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  36. Tang, X.H., Linder, J.: Almost quadriphase sequence with ideal autocorrelation property. IEEE Signal Process Lett. 16(1), 38–40 (2009)

    Article  Google Scholar 

  37. Uehara, S., Imamura, K.: The linear complexity of periodic sequences from a sequence over G F(q) with period p n − 1 by one-symbol deletion. IEICE Trans. Fundament. E80-A, 1164–1166 (1997)

    Google Scholar 

  38. Wang, Q., Du, X.: The linear complexity of binary sequences with optimal autocorrelation. IEEE Trans. Inf. Theory 56(12), 6388–6397 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  39. Yang, Z., Ke, P.H.: Quaternary sequences with odd period and low autocorrelation. Electron. Lett. 46(15), 1–2 (2010)

    Article  Google Scholar 

  40. Yang, Z., Ke, P.H.: Construction of quateranry sequences of length pq and low autocorrelation. Cryptogr. Commun. 3, 55–64 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  41. Zhang, J., Zhao, C.A.: The linear complexity of a class of binary sequences with period 2p. Appl. Algebra Eng. Commun. Comput. 26(5), 475–491 (2015)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to thank the anonymous referees and the Editor-in-Chief, Professor Claude Carlet, for the valuable comments and suggestions that greatly improved this paper.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, 518055, China

    Jerod Michel & Qi Wang

Authors
  1. Jerod Michel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qi Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jerod Michel.

Additional information

The authors were supported in part by the Ministry of Science and Technology (MOST) of China under Grant No. 2017YFC0804002, the Shenzhen fundamental research programs under Grant No. JCYJ20150630145302234, and the National Natural Science Foundation of China under Grant No. 11601220 and Grant No. 61672015.

Appendix

Appendix

For convenience, we denote the cyclotomic classes \({D}_{i}^{(4,p)}\) of order four modulo a prime p, simply by Di. We will need the following lemma.

Lemma 7

[33] The five distinct cyclotomic numbers modulop of order four for odd f are

$$\begin{array}{@{}rcl@{}} (0,0) & = & (2,2) = (2,0) = \frac{p-7 + 2a}{16} \ (=A), \\ (0,1) & = & (1,3) = (3,2) = \frac{p + 1 + 2a-8b}{16} \ (=B), \\ (1,2) & = & (0,3) = (3,1) = \frac{p + 1 + 2a + 8b}{16} \ (=D), \\ (0,2) & = & \frac{p + 1-6a}{16} \ (=C), \\ \text{all others} & = & \frac{p-3-2a}{16} \ (=E), \end{array} $$

and those for evenf are

$$\begin{array}{@{}rcl@{}} (0,0) & = & \frac{p-11-6a}{16} \ (=A), \\ (0,1) & = & (1,0) = (3,3) = \frac{p-3 + 2a + 8b}{16} \ (=B), \\ (0,2) & = & (2,0) = (2,2) = \frac{p-3 + 2a}{16} \ (=C), \\ (0,3) & = & (3,0) = (1,1) = \frac{p-3 + 2a-8b}{16} \ (=D), \\ \text{all others} & = & \frac{p + 1-2a}{16} \ (=E). \end{array} $$

Here we give the proof of Lemma 2.

Proof

Let h ∈{0, 1, 2, 3}∖{i, j, l}. The balancedness comesfrom the simple fact that \(\overline {C}_{0}\cap \overline {C}_{1}=D_{h}\),\(\overline {C}_{0}\cap C_{1}=D_{l}\cup \{0\}\),C0 ∩ C1 = Djand\(C_{0}\cap \overline {C}_{1}=D_{i}\). By Lemma 1 wehave

$$R_{\mathbf{u}}(\tau)=\frac{1}{2}\left[R_{\mathbf{s}_{C_{0}}}(\tau)+R_{\mathbf{s}_{C_{1}}}(\tau)\right]+\frac{\omega}{2}\left[R_{\mathbf{s}_{C_{0}},\mathbf{s}_{C_{1}}}(\tau) +R_{\mathbf{s}_{C_{1}},\mathbf{s}_{C_{0}}}(\tau)\right]. $$

We show the case (i, j, l) = (1, 2, 3).The other cases are almost identical. First notice that, by Lemma 7, when f is even resp. odd, the numbern0,1(k)of t suchthat \(s_{C_{0}}(t)=s_{C_{1}}(t+\tau )\)for τ− 1 ∈ Dkis

$$\left\{\begin{array}{ll} 4E+A+B+C+D + 1,&\text{ if }k = 0,\\ 2(B+C+D+E),&\text{ if }k = 1,\\ 4E+A+B+C+D + 1,&\text{ if }k = 2,\\ 2(B+C+D+E)+ 2,&\text{ if }k = 3, \end{array}\right.\text{ resp. } \left\{\begin{array}{ll} 2(A+B+D+E)+ 2,&\text{ if }k = 0,\\ 4E+A+B+C+D + 1,&\text{ if }k = 1,\\ 2(A+B+D+E),&\text{ if }k = 2,\\ 4E+A+B+C+D + 1,&\text{ if }k = 3. \end{array}\right. $$

Thenumbers n1,0(k),for k = 0, 1, 2, 3,can be calculated in the same way. When f is even, we haven0,1(k) = n1,0(k)for all k. Whenf is odd, n0,1(k) = n1,0(k)when k = 1or 3,and n0,1(k) = n1,0(k) − 2ifk = 0, andn0,1(k) = n1,0(k) + 2ifk = 2.We also have, by Lemma 7, when f is even resp. odd, the numbern0,0(k)of t suchthat \(s_{C_{0}}(t)=s_{C_{0}}(t+\tau )\)for τ− 1 ∈ Dkis

$$\left\{\begin{array}{ll} 2E + 3D+A+B+C + 2,&\text{ if }k = 0,\\ 2E + 3B+A+C+D + 2,&\text{ if }k = 1,\\ 2E + 3D+A+B+C,&\text{ if }k = 2,\\ 2E + 3B+A+C+D,&\text{ if }k = 3, \end{array}\right.\text{ resp. } \left\{\begin{array}{ll} 4E + 2(A+D)+ 1,&\text{ if }k = 0,\\ 4E + 2(A+B)+ 1,&\text{ if }k = 1,\\ 4E + 2(A+D)+ 1,&\text{ if }k = 2,\\ 4E + 2(A+B)+ 1,&\text{ if }k = 3. \end{array}\right. $$

The numbersn1,0(k)can be calculated in the sameway. When f even, we have n0,0(k) = n1,1(k)when k = 1or 3,and n0,0(k) = n1,1(k) + 2whenk = 0or 2. When f odd,we have n0,0(k) = n1,1(k)for all k.The result follows. □

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Michel, J., Wang, Q. Some new balanced and almost balanced quaternary sequences with low autocorrelation. Cryptogr. Commun. 11, 191–206 (2019). https://doi.org/10.1007/s12095-018-0281-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12095-018-0281-x

Keywords

Mathematics Subject Classification (2010)

Search

Navigation