Article Contents
Article Contents

# Partial direct product difference sets and almost quaternary sequences

• * Corresponding author

This paper is a part of Büşra Özden's PhD thesis

• In this paper, we study the $m$-ary sequences with (non-consecutive) two zero-symbols and at most two distinct autocorrelation coefficients, which are known as almost $m$-ary nearly perfect sequences. We show that these sequences are equivalent to $\ell$-partial direct product difference sets (PDPDS), then we extend known results on the sequences with two consecutive zero-symbols to non-consecutive case. Next, we study the notion of multipliers and orbit combination for $\ell$-PDPDS. Finally, we present two construction methods for a family of almost quaternary sequences with at most two out-of-phase autocorrelation coefficients.

Mathematics Subject Classification: 05B10 and 94A55.

 Citation:

• Table 1.  Orbits of $G = {\mathbb Z}_{10} \times {\mathbb Z}_3$ under $x \rightarrow 19x$

 orbits of length 1 (0, 0)}, {(0, 1)}, {(0, 2)}, {(5, 0)}, {(5, 1)}, {(5, 2) orbits of length 2 (4, 0), (6, 0)}, {(1, 1), (9, 1)}, {(7, 0), (3, 0)}, {(8, 2), (2, 2)}, (9, 0), (1, 0)} {(7, 2), (3, 2)}, {(7, 1), (3, 1)}, {(1, 2), (9, 2)}, (8, 1), (2, 1)}, {(6, 2), (4, 2)}, {(6, 1), (4, 1)}, {(2, 0), (8, 0)

Table 2.  Sequences, their autocorrelation and alphabet

 Construction Out-of-phase autocorrelation Alphabet [29], [36] 0 $p$-ary [17], [18] -1 $p$-ary [3], [10], [15], [16], [30], [32], [35], [41], [42], [43], [44] -1 binary [12], [27], [40], [44] $\pm 2$ binary [2], [40], [27], [44] $(0,-4)$ binary [45], [50] $(0,\pm 4)$ binary [4], [11], [44] $(1,-3)$ binary [25] $(2p,-2)$ or $(\pm 2p, \pm 2)$ binary [1], [19], [21] -1 ternary [23] $(0,-3,3\zeta_3,3\zeta_3^2)$ ternary $(0,\pm 2i,-4,-2,-2\pm 2i)$ or $(0,\pm 2i,\pm2,-2\pm 2i)$ quaternary [24] $(-2,\pm 2i)$ quaternary [25], [44] $(0,-2)$ quaternary [31] $(-1,\pm 3)$ quaternary [46] $(-1,\pm(1+2i))$ or $(\pm 1,-3)$ quaternary [48] $(\frac{p^{n-1}(p-7)}{2},\frac{p^{n-1}(p-3)}{2},p^n)$ quaternary [6] $0$ $p$-ary with one zero $-1$ $p$-ary with one zero [38] $-1$ $m$-ary with one zero [13] $(0,3q^{n-1})$ $6$-ary with one zero [47] $(0,p^{(k-1)n})$ $p^{kn}$-ary with zeros $(0,p^{(k-1)n})$ $\frac{p^{n-1}}{\gcd(t,p^{n-1})}$-ary with zeros $0$ $m$-ary with one zero Theorem 3.7 $\frac{q-3}{2}$ quaternary with one zero Proposition 7 $(-1,0)$ $m$-ary with $\frac{q}{2}+1$ zeros
•  [1] K. T. Arasu, J. F. Dillon and K. J. Player, Character sum factorizations yield sequences with ideal two-level autocorrelation, IEEE Transactions on Information Theory, 61 (2015), 3276-3304.  doi: 10.1109/TIT.2015.2418204. [2] K. T. Arasu, C. Ding, T. Helleseth, P. V. Kumar and H. M. Martinsen, Almost difference sets and their sequences with optimal autocorrelation, IEEE Transactions on Information Theory, 47 (2001), 2934-2943.  doi: 10.1109/18.959271. [3] T. Beth,  D. Jungnickel and  H. Lenz,  Design Theory: Volume 1, Cambridge University Press, 1999. [4] Y. Cai and C. Ding, Binary sequences with optimal autocorrelation, Theoretical Computer Science, 410 (2009), 2316-2322.  doi: 10.1016/j.tcs.2009.02.021. [5] A. Çeșmelioǧlu and O. Olmez, Graphs of vectorial plateaued functions as difference sets, Finite Fields and Their Applications, 71 (2021), 101795. doi: 10.1016/j.ffa.2020.101795. [6] Y. M. Chee, Y. Tan and Y. Zhou, Almost p-ary perfect sequences, in International Conference on Sequences and Their Applications doi: 10.1007/978-3-642-15874-2_34. [7] I. Chih-Lin and R. D. Gitlin, Multi-code CDMA wireless personal communications networks, Proceedings IEEE International Conference on Communications ICC'95, 2 (1995), 1060-1064.  doi: 10.1109/ICC.1995.524263. [8] C. J. Colbourn and  J. H. Dinitz,  Handbook of Combinatorial Designs, CRC press, 2006.  doi: 10.1201/9781420049954. [9] L. E. Dickson, Cyclotomy, higher congruences, and Waring's problem, American Journal of Mathematics, 57 (1935), 391-424.  doi: 10.2307/2371217. [10] J. F. Dillon and H. Dobbertin, New cyclic difference sets with singer parameters, Finite Fields and Their Applications, 10 (2004), 342-389.  doi: 10.1016/j.ffa.2003.09.003. [11] C. Ding, T. Helleseth and K. Y. Lam, Several classes of binary sequences with three-level autocorrelation, IEEE Transactions on Information Theory, 45 (1999), 2606-2612.  doi: 10.1109/18.796414. [12] C. Ding, T. Helleseth and H. Martinsen, New families of binary sequences with optimal three-level autocorrelation, IEEE Transactions on Information Theory, 47 (2001), 428-433.  doi: 10.1109/18.904555. [13] V. E. Gantmakher and M. V. Zaleshin, Almost six-phase sequences with perfect periodic autocorrelation function, in International Conference on Sequences and Their Applications doi: 10.1007/978-3-319-12325-7_8. [14] S. W. Golomb and  G. Gong,  Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar, Cambridge University Press, 2005.  doi: 10.1017/CBO9780511546907. [15] B. Gordon, W. Mills and L. Welch, Some new difference sets, Canadian Journal of Mathematics, 14 (1962), 614-625.  doi: 10.4153/CJM-1962-052-2. [16] M. Hall, A survey of difference sets, Proceedings of the American Mathematical Society, 7 (1956), 975-986.  doi: 10.1090/S0002-9939-1956-0082502-7. [17] T. Helleseth and G. Gong, New nonbinary sequences with ideal two-level autocorrelation, IEEE Transactions on Information Theory, 48 (2002), 2868-2872.  doi: 10.1109/TIT.2002.804052. [18] T. Helleseth and P. V. Kumar, Sequences with low correlation, in Handbook of coding theory, Vol. I, II [19] T. Helleseth, P. V. Kumar and H. Martinsen, A new family of ternary sequences with ideal two-level autocorrelation function, Des. Codes Cryptogr., 23 (2001), 157-166.  doi: 10.1023/A:1011208514883. [20] J. R. Hollon, M. Rangaswamy and P. Setlur, New families of optimal high-energy ternary sequences having good correlation properties, Journal of Algebraic Combinatorics, 50 (2019), 1-38.  doi: 10.1007/s10801-018-0835-1. [21] H. Hu, S. Shao, G. Gong and T. Helleseth, The proof of Lin's conjecture via the decimation-Hadamard transform, IEEE Transactions on Information Theory, 60 (2014), 5054-5064.  doi: 10.1109/TIT.2014.2327625. [22] D. Jungnickel and A. Pott, Perfect and almost perfect sequences, Discrete Applied Mathematics, 95 (1999), 331-359.  doi: 10.1016/S0166-218X(99)00085-2. [23] Y.-S. Kim, J.-S. Chung, J.-S. No and H. Chung, On the autocorrelation distributions of Sidel'nikov sequences, IEEE Transactions on Information Theory, 51 (2005), 3303-3307.  doi: 10.1109/TIT.2005.853310. [24] Y.-S. Kim, J.-W. Jang, S.-H. Kim and J.-S. No, New quaternary sequences with optimal autocorrelation, ISIT, (2009), 286–289. [25] Y.-S. Kim, J.-W. Jang, S.-H. Kim and J.-S. No, New quaternary sequences with ideal autocorrelation constructed from Legendre sequences, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 96 (2013), 1872-1882.  doi: 10.1587/transfun.E96.A.1872. [26] P. V. Kumar, R. A. Scholtz and L. R. Welch, Generalized bent functions and their properties, Journal of Combinatorial Theory, Series A, 40 (1985), 90-107.  doi: 10.1016/0097-3165(85)90049-4. [27] A. Lempel, M. Cohn and W. Eastman, A class of balanced binary sequences with optimal autocorrelation properties, IEEE Transactions on Information Theory, 23 (1977), 38-42.  doi: 10.1109/tit.1977.1055672. [28] S. L. Ma and W. S. Ng, On non-existence of perfect and nearly perfect sequences, International Journal of Information and Coding Theory, 1 (2009), 15-38.  doi: 10.1504/IJICOT.2009.024045. [29] S. L. Ma and B. Schmidt, On $(p^a, p, p^a, p^a-1)$-relative difference sets, Designs, Codes and Cryptography, 6 (1995), 57-71.  doi: 10.1007/BF01390771. [30] A. Maschietti, Difference sets and hyperovals, Designs, Codes and Cryptography, 14 (1998), 89-98.  doi: 10.1023/A:1008264606494. [31] J. Michel and Q. Wang, Some new balanced and almost balanced quaternary sequences with low autocorrelation, Cryptography and Communications, 11 (2019), 191-206.  doi: 10.1007/s12095-018-0281-x. [32] J.-S. No, H. Chung and M.-S. Yun, Binary pseudorandom sequences of period $2^n-1$ with ideal autocorrelation generated by the polynomial $z^d+(z+ 1)^d$, IEEE Transactions on Information Theory, 44 (1998), 1278-1282.  doi: 10.1109/18.669400. [33] B. Özden and O. Yayla, Cryptographic functions and bit-error-rate analysis with almost $p$-ary sequences, International Journal of Information Security Science, 8.3 (2019), 44-52.  doi: 10.1007/s12095-020-00423-5. [34] B. Özden and O. Yayla, Almost p-ary sequences, Cryptography and Communications, 12 (2020), 1057-1069.  doi: 10.1007/s12095-020-00423-5. [35] R. E. Paley, On orthogonal matrices, Journal of Mathematics and Physics, 12 (1933), 311-320.  doi: 10.1002/sapm1933121311. [36] A. Pott, Finite Geometry and Character Theory, Lecture Notes in Mathematics, 1601, Springer-Verlag, Berlin, 1995. doi: 10.1007/BFb0094449. [37] K.-U. Schmidt, Quaternary constant-amplitude codes for multicode CDMA, IEEE Trans. Information Theory, 55 (2009), 1824-1832.  doi: 10.1109/TIT.2009.2013041. [38] X. Shi, X. Zhu, X. Huang and Q. Yue, A family of $m$-ary $\sigma$-sequences with good autocorrelation, IEEE Communications Letters, 23 (2019), 1132-1135.  doi: 10.1109/LCOMM.2019.2915234. [39] G. L. Sicuranza and A. Carini, Nonlinear system identification using quasi-perfect periodic sequences, Signal Processing, 120 (2016), 174-184.  doi: 10.1016/j.sigpro.2015.08.018. [40] V. M. Sidel'nikov, Some k-valued pseudo-random sequences and nearly equidistant codes, Problemy Peredachi Informatsii, 5 (1969), 16-22. [41] J. Singer, A theorem in finite projective geometry and some applications to number theory, Transactions of the American Mathematical Society, 43 (1938), 377-385.  doi: 10.1090/S0002-9947-1938-1501951-4. [42] R. G. Stanton and D. Sprott, A family of difference sets, Canadian Journal of Mathematics, 10 (1958), 73-77.  doi: 10.4153/CJM-1958-008-5. [43] T. Storer, Cyclotomy and Difference Sets, Lectures in Advanced Mathematics, 2, Markham Publishing Co., Chicago, IL, 1967. [44] X. Tang and C. Ding, New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value, IEEE Transactions on Information Theory, 56 (2010), 6398-6405.  doi: 10.1109/TIT.2010.2081170. [45] X. Tang and G. Gong, New constructions of binary sequences with optimal autocorrelation value/magnitude, IEEE Transactions on Information Theory, 56 (2010), 1278-1286.  doi: 10.1109/TIT.2009.2039159. [46] X. Tang and J. Lindner, Almost quadriphase sequence with ideal autocorrelation property, IEEE Signal Processing Letters, 16 (2008), 38-40. [47] A. Tirkel and T. Hall, New quasi-perfect and perfect sequences of roots of unity and zero, in International Conference on Sequences and Their Applications [48] Q. Wang, W. Kong, Y. Yan, C. Wu and M. Yang, Autocorrelation of a class of quaternary sequences of period $2 p^m$, preprint, arXiv: 2002.00375. [49] O. Yayla, Nearly perfect sequences with arbitrary out-of-phase autocorrelation, Advances in Mathematics of Communications, 10 (2016), 401-411.  doi: 10.3934/amc.2016014. [50] N. Y. Yu and G. Gong, New binary sequences with optimal autocorrelation magnitude, IEEE Transactions on Information Theory, 54 (2008), 4771-4779.  doi: 10.1109/TIT.2008.928999.

Tables(2)