Optimization of code constructions of binary sequences class on a basis of set-theoretical representation

Authors

  • Volodymyr-Myron V. Miskiv Lviv Polytechnic National University, Ukraine
  • Ivan N. Prudyus Lviv Polytechnic National University, Ukraine https://orcid.org/0000-0003-3331-0892
  • Roman V. Yankevych Lviv Polytechnic National University, Ukraine

DOI:

https://doi.org/10.3103/S0735272718070026

Keywords:

binary sequence, aperiodoc correlation function, periodic correlation function, Barker code, minimal level of side lobes of autocorrelation function, code construction optimization

Abstract

In this paper there are solved two related problems: the development of the method and correspondent algorithm of code binary sequences synthesis with property of minimal level of side lobes of their aperiodic autocorrelation functions. The method is based on discrete representation of autocorrelation function in form of equations system considered on a set of integer numbers, set-theoretical representation of components of the sequence, their integer-number transformations, mutual properties and relations. There are obtained the expressions defining the dependences of absolute value of the sequence elements on a sum of levels of side lobes of aperiodic and periodic correlation functions; there are defined the necessary conditions of existence binary code sequences ; there are developed the mathematical models of binary code sequences components transformations.

The efficiency criterion of each proposed algorithm is the relation of amount of all possible variants of binary code sequences of definite size l to amount of defined by proposed algorithms; the expressions for these quantities are obtained. The efficiency of proposed method and algorithms is verified by simulation results and it increases with increase of size l.

References

BARKER, R.H. “Group synchronizing of binary digital systems,” in: JACKSON, W. (ed.), Communication Theory. New York: Academic Press, 1953, p.273-287.

VARAKIN, L.E. Communication Systems with Noise-Like Signals [in Russian]. Moscow: Radio i Svyaz’, 1985.

SKOLNIK, M.I. Radar Handbook, 3rd ed. New York: McGraw-Hill, 2008.

IRIG STANDARD 106-04. Telemetry Standards.

JEDWAB, J. “What can be used instead of a Barker sequence?” Contemp. Math., v.461, p.153-178, 2008. DOI: http://doi.org/10.1090/conm/461/08991.

LEUNG, K.H.; SCHMIDT, B. “The field descent method,” Des. Codes Crypt., v.36, n.2, p.171-188, 2005. DOI: https://doi.org/10.1007/s10623-004-1703-7.

JEDWAB, J.; PARKER, M.G. “Golay complementary array pairs,” Des. Codes Crypt., v.44, n.1-3, p.209-216, 2007. DOI: https://doi.org/10.1007/s10623-007-9088-z.

ALQUADDOOMI, S.; SCHOLTZ, R.A. “On the nonexistence of Barker arrays and related matters,” IEEE Trans. Inf. Theory, v.35, n.5, p.1048-1057, 1989. DOI: https://doi.org/10.1109/18.42220.

DAVIS, J.A.; JEDWAB, J.; SMITH, K.W. “Proof of the Barker array conjecture,” Proc. Amer. Math. Soc., v.135, p.2011-2018, 2007. DOI: http://doi.org/10.1090/S0002-9939-07-08703-5.

JEDWAB, J.; PARKER, M.G. “There are no Barker arrays having more than two dimensions,” Des. Codes Crypt., v.43, n.2-3, p.79-84, 2007. DOI: https://doi.org/10.1007/s10623-007-9060-y.

GOLOMB, S.W.; GONG, G. Signal Design for Good Correlation: for Wireless Communication, Cryptography, and Radar. New York: CUP, 2005.

MOON, J.W.; MOSER, L. “On the correlation function of random binary sequences,” SIAM J. Appl. Math., v.16, n.2, p.340-343, 1968. URI: https://www.jstor.org/stable/2099297.

JEDWAB, J.; YOSHIDA, K. “The peak sidelobe level of families of binary sequences,” IEEE Trans. Inf. Theory, v.52, n.5, p.2247-2254, 2006. DOI: https://doi.org/10.1109/TIT.2006.872863.

DMITRIEV, D.; JEDWAB, J. “Bounds on the growth rate of the peak sidelobe level of binary sequences,” Adv. Math. Commun., v.1, n.4, p.461-475, 2007. DOI: http://dx.doi.org/10.3934/amc.2007.1.461.

ZENG, Xiangyong; HU, Lei; LIU, Qingchong. “A family of binary sequences with optimal correlation property and large linear span,” The Computing Research Repository, August 2005. URI: https://arxiv.org/abs/cs/0508114.

JENSEN, H.E.; HOHOLDT, T. “Binary sequences with good correlation properties,” Proc. of 5th Int. Conf. on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-5 15-19 Jun. 1987. Berlin: Springer-Verlag, 1989, p.306-320.

BORWEIN, P.; CHOI, K.-K.S.; JEDWAB, J. “Binary sequences with merit factor greater than 6.34,” IEEE Trans. Inf. Theory, v.50, n.12, p.3234-3249, 2004. DOI: https://doi.org/10.1109/TIT.2004.838341.

BANKET, V.L.; TOKAR, M.S. “The composite Barker’s codes,” Digital Technologies, v.2, p.8-18, 2007. URI: https://ojs.onat.edu.ua/index.php/digitech/article/view/592.

NUNN, Carroll J.; COXSON, Gregory E. “Best-known autocorrelation peak sidelobe levels for binary codes of length 71 to 105,” IEEE Trans. Aerosp. Electron. Syst., v.44, n.1, p.392-395, 2008. DOI: https://doi.org/10.1109/TAES.2008.4517015.

SCHMIDT, Kai-Uwe. “Binary sequences with small peak sidelobe level,” IEEE Trans. Inf. Theory, v.58, n.4, p.2512-2515, 2012. DOI: https://doi.org/10.1109/TIT.2011.2178391.

PACKEBUSCH, T.; MERTENS, S. “Low autocorrelation binary sequences,” J. Phys. A: Math. Theor., v.49, n.16, p.165001, 2016. DOI: https://doi.org/10.1088/1751-8113/49/16/165001.

BOBALO, Y.; MISKIV, V.-M.; MISKIV, A.; PRUDYUS, I.; YANKEVYCH, R. “Aspects of code constructions optimization,” Proc. of Int. Sci. and Practical Conf., 3-5 Nov. 2016, Chernivtsi, Ukraine. Chernivtsi, 2016, p.191-192.

MISKIV, Volodymyr-Myron; PRUDYUS, I.; YANKEVYCH, R. “Properties of binary code sequences on the periodical convolution,” Proc. of 2017 IEEE Int. Conf. on Information and Telecommunication Technologies and Radio Electronics, UkrMiCo’2017. 11-15 Sept. 2017, Odessa, Ukraine. IEEE, 2017, p.95-98. DOI: https://doi.org/10.1109/UkrMiCo.2017.8095373.

MIS’KIV, A.; MIS’KIV, V.-M.; PRUDYUS, I.; YANKEVYCH, R. “Discrete sequencies with optimal aperiodic autocorrelation functions. Conditions for existance,” Proc. of 14th Int. Conf. on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering, TCSET, 20-24 Feb. 2018, Lviv-Slavske, Ukraine. IEEE, 2018, p.1264-1267. DOI: https://doi.org/10.1109/TCSET.2018.8336424.

PRUDNIKOV, A.P.; BRYCHKOV, Y.A.; MARICHEV, O.I. Integrals and Series [in Russian]. Moscow: Nauka, 1981.

MENSHIKOV, M.V. et al., Combinatorial Analysis. Tasks and Exercises [in Russian]. Moscow: Nauka, 1982.

Downloads

Published

2018-07-30

Issue

Vol. 61 No. 7 (2018)

Section

Research Articles