The merit factor of binary arrays derived from the quadratic character

Previous Article
On the number of bent functions from iterative constructions: lower bounds and hypotheses
AMC Home
This Issue
Next Article
Codes over $\mathbb{Z}_{2^k}$, Gray map and self-dual codes

November 2011, 5(4): 589-607. doi: 10.3934/amc.2011.5.589

The merit factor of binary arrays derived from the quadratic character

Kai-Uwe Schmidt ^1,

1.	Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, BC, V5A 1S6, Canada

Received July 2010 Revised July 2011 Published November 2011

Abstract
Related Papers

We calculate the asymptotic merit factor, under all cyclic rotations of rows and columns, of two families of binary two-dimensional arrays derived from the quadratic character. The arrays in these families have size $p\times q$, where $p$ and $q$ are not necessarily distinct odd primes, and can be considered as two-dimensional generalisations of a Legendre sequence. The asymptotic values of the merit factor of the two families are generally different, although the maximum asymptotic merit factor, taken over all cyclic rotations of rows and columns, equals $36/13$ for both families. These are the first non-trivial theoretical results for the asymptotic merit factor of families of truly two-dimensional binary arrays.

Keywords: Binary array, quadratic character., finite field, merit factor, Legendre sequence.

Mathematics Subject Classification: Primary: 94A55; Secondary: 68P30, 05B1.

Citation: Kai-Uwe Schmidt. The merit factor of binary arrays derived from the quadratic character. Advances in Mathematics of Communications, 2011, 5 (4) : 589-607. doi: 10.3934/amc.2011.5.589

References:

[1]	S. Alquaddoomi and R. A. Scholtz, On the nonexistence of Barker arrays and related matters, IEEE Trans. Inform. Theory, 35 (1989), 1048-1057. doi: 10.1109/18.42220.
[2]	L. Bömer and M. Antweiler, Optimizing the aperiodic merit factor of binary arrays, Signal Process, 30 (1993), 1-13. doi: 10.1016/0165-1684(93)90047-E.
[3]	L. Bömer, M. Antweiler and H. Schotten, Quadratic residue arrays, Frequenz, 47 (1993), 190-196. doi: 10.1515/FREQ.1993.47.7-8.190.
[4]	P. Borwein, K.-K. S. Choi, and J. Jedwab, Binary sequences with merit factor greater than $6.34$, IEEE Trans. Inform. Theory, 50 (2004), 3234-3249. doi: 10.1109/TIT.2004.838341.
[5]	D. Calabro and J. K. Wolf, On the synthesis of two-dimensional arrays with desirable correlation properties, Inform. Control, 11 (1967), 537-560. doi: 10.1016/S0019-9958(67)90755-3.
[6]	J. A. Davis, J. Jedwab and K. W. Smith, Proof of the Barker array conjecture, Proc. Amer. Math. Soc., 135 (2007), 2011-2018. doi: 10.1090/S0002-9939-07-08703-5.
[7]	H. Eggers, "Synthese zweidimensionaler Folgen mit guten Autokorrelationseigenschaften,'' Ph.D thesis, RWTH Aachen, Germany, 1986.
[8]	T. A. Gulliver and M. G. Parker, The multivariate merit factor of a Boolean function, in "Coding and Complexity'' (ed. M.J. Dinneen), IEEE, (2005), 58-62.
[9]	T. Høholdt and H. E. Jensen, Determination of the merit factor of Legendre sequences, IEEE Trans. Inform. Theory, 34 (1988), 161-164. doi: 10.1109/18.2620.
[10]	T. Høholdt, H. E. Jensen and J. Justesen, Aperiodic correlations and the merit factor of a class of binary sequences, IEEE Trans. Inform. Theory, IT-31 (1985), 549-552. doi: 10.1109/TIT.1985.1057071.
[11]	J. Jedwab, A survey of the merit factor problem for binary sequences, in "Sequences and Their Applications'' (eds. T. Helleseth et al.), Springer-Verlag, (2005), 30-55. doi: 10.1007/11423461_2.
[12]	J. Jedwab and K.-U. Schmidt, The merit factor of binary sequence families constructed from $m$-sequences, Contemp. Math., 518 (2010), 265-278.
[13]	J. Jedwab and K.-U. Schmidt, The $L_4$ norm of Littlewood polynomials derived from the Jacobi symbol,, to appear in Pacific J. Math., ().
[14]	H. E. Jensen and T. Høholdt, Binary sequences with good correlation properties, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes'' (eds. L. Huguet and A. Poli), Springer-Verlag, (1989), 306-320.
[15]	J. M. Jensen, H. E. Jensen and T. Høholdt, The merit factor of binary sequences related to difference sets, IEEE Trans. Inform. Theory, 37 (1991), 617-626. doi: 10.1109/18.79917.
[16]	R. Lidl and H. Niederreiter, "Finite Fields,'' 2^nd edition, Cambridge University Press, 1997.
[17]	J. E. Littlewood, "Some Problems in Real and Complex Analysis,'' D. C. Heath and Co. Raytheon Education Co., Lexington, MA, 1968.
[18]	M. J. Mossinghoff, Wieferich pairs and Barker sequences, Des. Codes Cryptogr., 53 (2009), 149-163. doi: 10.1007/s10623-009-9301-3.
[19]	D. V. Sarwate, Mean-square correlation of shift-register sequences, IEE Proc., 131 (1984), 101-106.
[20]	K.-U. Schmidt, J. Jedwab and M. G. Parker, Two binary sequence families with large merit factor, Adv. Math. Commun., 3 (2009), 135-156. doi: 10.3934/amc.2009.3.135.
[21]	M. R. Schroeder, "Number Theory in Science and Communication: with Applications in Cryptography, Physics, Digital Information, Computing, and Self-similarity,'' 3^rd edition, Springer, Berlin, 1997.
[22]	R. Turyn and J. Storer, On binary sequences, Proc. Amer. Math. Soc., 12 (1961), 394-399. doi: 10.1090/S0002-9939-1961-0125026-2.
[23]	R. G. van Schyndel, A. Z. Tirkel, I. D. Svalbe, T. E. Hall and C. F. Osborne, Algebraic construction of a new class of quasi-orthogonal arrays for steganography, Proc. SPIE, 3657 (1999), 354-364. doi: 10.1117/12.344685.

show all references

References:

[1]	S. Alquaddoomi and R. A. Scholtz, On the nonexistence of Barker arrays and related matters, IEEE Trans. Inform. Theory, 35 (1989), 1048-1057. doi: 10.1109/18.42220.
[2]	L. Bömer and M. Antweiler, Optimizing the aperiodic merit factor of binary arrays, Signal Process, 30 (1993), 1-13. doi: 10.1016/0165-1684(93)90047-E.
[3]	L. Bömer, M. Antweiler and H. Schotten, Quadratic residue arrays, Frequenz, 47 (1993), 190-196. doi: 10.1515/FREQ.1993.47.7-8.190.
[4]	P. Borwein, K.-K. S. Choi, and J. Jedwab, Binary sequences with merit factor greater than $6.34$, IEEE Trans. Inform. Theory, 50 (2004), 3234-3249. doi: 10.1109/TIT.2004.838341.
[5]	D. Calabro and J. K. Wolf, On the synthesis of two-dimensional arrays with desirable correlation properties, Inform. Control, 11 (1967), 537-560. doi: 10.1016/S0019-9958(67)90755-3.
[6]	J. A. Davis, J. Jedwab and K. W. Smith, Proof of the Barker array conjecture, Proc. Amer. Math. Soc., 135 (2007), 2011-2018. doi: 10.1090/S0002-9939-07-08703-5.
[7]	H. Eggers, "Synthese zweidimensionaler Folgen mit guten Autokorrelationseigenschaften,'' Ph.D thesis, RWTH Aachen, Germany, 1986.
[8]	T. A. Gulliver and M. G. Parker, The multivariate merit factor of a Boolean function, in "Coding and Complexity'' (ed. M.J. Dinneen), IEEE, (2005), 58-62.
[9]	T. Høholdt and H. E. Jensen, Determination of the merit factor of Legendre sequences, IEEE Trans. Inform. Theory, 34 (1988), 161-164. doi: 10.1109/18.2620.
[10]	T. Høholdt, H. E. Jensen and J. Justesen, Aperiodic correlations and the merit factor of a class of binary sequences, IEEE Trans. Inform. Theory, IT-31 (1985), 549-552. doi: 10.1109/TIT.1985.1057071.
[11]	J. Jedwab, A survey of the merit factor problem for binary sequences, in "Sequences and Their Applications'' (eds. T. Helleseth et al.), Springer-Verlag, (2005), 30-55. doi: 10.1007/11423461_2.
[12]	J. Jedwab and K.-U. Schmidt, The merit factor of binary sequence families constructed from $m$-sequences, Contemp. Math., 518 (2010), 265-278.
[13]	J. Jedwab and K.-U. Schmidt, The $L_4$ norm of Littlewood polynomials derived from the Jacobi symbol,, to appear in Pacific J. Math., ().
[14]	H. E. Jensen and T. Høholdt, Binary sequences with good correlation properties, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes'' (eds. L. Huguet and A. Poli), Springer-Verlag, (1989), 306-320.
[15]	J. M. Jensen, H. E. Jensen and T. Høholdt, The merit factor of binary sequences related to difference sets, IEEE Trans. Inform. Theory, 37 (1991), 617-626. doi: 10.1109/18.79917.
[16]	R. Lidl and H. Niederreiter, "Finite Fields,'' 2^nd edition, Cambridge University Press, 1997.
[17]	J. E. Littlewood, "Some Problems in Real and Complex Analysis,'' D. C. Heath and Co. Raytheon Education Co., Lexington, MA, 1968.
[18]	M. J. Mossinghoff, Wieferich pairs and Barker sequences, Des. Codes Cryptogr., 53 (2009), 149-163. doi: 10.1007/s10623-009-9301-3.
[19]	D. V. Sarwate, Mean-square correlation of shift-register sequences, IEE Proc., 131 (1984), 101-106.
[20]	K.-U. Schmidt, J. Jedwab and M. G. Parker, Two binary sequence families with large merit factor, Adv. Math. Commun., 3 (2009), 135-156. doi: 10.3934/amc.2009.3.135.
[21]	M. R. Schroeder, "Number Theory in Science and Communication: with Applications in Cryptography, Physics, Digital Information, Computing, and Self-similarity,'' 3^rd edition, Springer, Berlin, 1997.
[22]	R. Turyn and J. Storer, On binary sequences, Proc. Amer. Math. Soc., 12 (1961), 394-399. doi: 10.1090/S0002-9939-1961-0125026-2.
[23]	R. G. van Schyndel, A. Z. Tirkel, I. D. Svalbe, T. E. Hall and C. F. Osborne, Algebraic construction of a new class of quasi-orthogonal arrays for steganography, Proc. SPIE, 3657 (1999), 354-364. doi: 10.1117/12.344685.

[1]	Kai-Uwe Schmidt, Jonathan Jedwab, Matthew G. Parker. Two binary sequence families with large merit factor. Advances in Mathematics of Communications, 2009, 3 (2) : 135-156. doi: 10.3934/amc.2009.3.135
[2]	Richard Hofer, Arne Winterhof. On the arithmetic autocorrelation of the Legendre sequence. Advances in Mathematics of Communications, 2017, 11 (1) : 237-244. doi: 10.3934/amc.2017015
[3]	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
[4]	Ji-Woong Jang, Young-Sik Kim, Sang-Hyo Kim. New design of quaternary LCZ and ZCZ sequence set from binary LCZ and ZCZ sequence set. Advances in Mathematics of Communications, 2009, 3 (2) : 115-124. doi: 10.3934/amc.2009.3.115
[5]	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
[6]	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
[7]	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
[8]	Moulay Rchid Sidi Ammi, Ismail Jamiai. Finite difference and Legendre spectral method for a time-fractional diffusion-convection equation for image restoration. Discrete and Continuous Dynamical Systems - S, 2018, 11 (1) : 103-117. doi: 10.3934/dcdss.2018007
[9]	Amer Rasheed, Aziz Belmiloudi, Fabrice Mahé. Dynamics of dendrite growth in a binary alloy with magnetic field effect. Conference Publications, 2011, 2011 (Special) : 1224-1233. doi: 10.3934/proc.2011.2011.1224
[10]	Chun-Hao Teng, I-Liang Chern, Ming-Chih Lai. Simulating binary fluid-surfactant dynamics by a phase field model. Discrete and Continuous Dynamical Systems - B, 2012, 17 (4) : 1289-1307. doi: 10.3934/dcdsb.2012.17.1289
[11]	Hélène Hibon, Ying Hu, Shanjian Tang. Mean-field type quadratic BSDEs. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022009
[12]	Guangmei Shao, Wei Xue, Gaohang Yu, Xiao Zheng. Improved SVRG for finite sum structure optimization with application to binary classification. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2253-2266. doi: 10.3934/jimo.2019052
[13]	Valery Y. Glizer, Oleg Kelis. Singular infinite horizon zero-sum linear-quadratic differential game: Saddle-point equilibrium sequence. Numerical Algebra, Control and Optimization, 2017, 7 (1) : 1-20. doi: 10.3934/naco.2017001
[14]	Yoshikazu Katayama, Colin E. Sutherland and Masamichi Takesaki. The intrinsic invariant of an approximately finite dimensional factor and the cocycle conjugacy of discrete amenable group actions. Electronic Research Announcements, 1995, 1: 43-47.
[15]	Grégory Berhuy, Jean Fasel, Odile Garotta. Rank weights for arbitrary finite field extensions. Advances in Mathematics of Communications, 2021, 15 (4) : 575-587. doi: 10.3934/amc.2020083
[16]	Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks and Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243
[17]	Kai Du, Jianhui Huang, Zhen Wu. Linear quadratic mean-field-game of backward stochastic differential systems. Mathematical Control and Related Fields, 2018, 8 (3&4) : 653-678. doi: 10.3934/mcrf.2018028
[18]	Olivier Guéant. New numerical methods for mean field games with quadratic costs. Networks and Heterogeneous Media, 2012, 7 (2) : 315-336. doi: 10.3934/nhm.2012.7.315
[19]	Zhenghong Qiu, Jianhui Huang, Tinghan Xie. Linear-Quadratic-Gaussian mean-field controls of social optima. Mathematical Control and Related Fields, 2021 doi: 10.3934/mcrf.2021047
[20]	Denis Danilov, Britta Nestler. Phase-field modelling of nonequilibrium partitioning during rapid solidification in a non-dilute binary alloy. Discrete and Continuous Dynamical Systems, 2006, 15 (4) : 1035-1047. doi: 10.3934/dcds.2006.15.1035

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Kai-Uwe Schmidt
on Google Scholar
Kai-Uwe Schmidt

[Back to Top]