# American Institute of Mathematical Sciences

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

## The merit factor of binary arrays derived from the quadratic character

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

Received  July 2010 Revised  July 2011 Published  November 2011

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.
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. doi: 10.1109/18.42220. Google Scholar [2] L. Bömer and M. Antweiler, Optimizing the aperiodic merit factor of binary arrays,, Signal Process, 30 (1993), 1. doi: 10.1016/0165-1684(93)90047-E. Google Scholar [3] L. Bömer, M. Antweiler and H. Schotten, Quadratic residue arrays,, Frequenz, 47 (1993), 190. doi: 10.1515/FREQ.1993.47.7-8.190. Google Scholar [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. doi: 10.1109/TIT.2004.838341. Google Scholar [5] D. Calabro and J. K. Wolf, On the synthesis of two-dimensional arrays with desirable correlation properties,, Inform. Control, 11 (1967), 537. doi: 10.1016/S0019-9958(67)90755-3. Google Scholar [6] J. A. Davis, J. Jedwab and K. W. Smith, Proof of the Barker array conjecture,, Proc. Amer. Math. Soc., 135 (2007), 2011. doi: 10.1090/S0002-9939-07-08703-5. Google Scholar [7] H. Eggers, "Synthese zweidimensionaler Folgen mit guten Autokorrelationseigenschaften,'', Ph.D thesis, (1986). Google Scholar [8] T. A. Gulliver and M. G. Parker, The multivariate merit factor of a Boolean function,, in, (2005), 58. Google Scholar [9] T. Høholdt and H. E. Jensen, Determination of the merit factor of Legendre sequences,, IEEE Trans. Inform. Theory, 34 (1988), 161. doi: 10.1109/18.2620. Google Scholar [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. doi: 10.1109/TIT.1985.1057071. Google Scholar [11] J. Jedwab, A survey of the merit factor problem for binary sequences,, in, (2005), 30. doi: 10.1007/11423461_2. Google Scholar [12] J. Jedwab and K.-U. Schmidt, The merit factor of binary sequence families constructed from $m$-sequences,, Contemp. Math., 518 (2010), 265. Google Scholar [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., (). Google Scholar [14] H. E. Jensen and T. Høholdt, Binary sequences with good correlation properties,, in, (1989), 306. Google Scholar [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. doi: 10.1109/18.79917. Google Scholar [16] R. Lidl and H. Niederreiter, "Finite Fields,'' 2nd edition,, Cambridge University Press, (1997). Google Scholar [17] J. E. Littlewood, "Some Problems in Real and Complex Analysis,'', D. C. Heath and Co. Raytheon Education Co., (1968). Google Scholar [18] M. J. Mossinghoff, Wieferich pairs and Barker sequences,, Des. Codes Cryptogr., 53 (2009), 149. doi: 10.1007/s10623-009-9301-3. Google Scholar [19] D. V. Sarwate, Mean-square correlation of shift-register sequences,, IEE Proc., 131 (1984), 101. Google Scholar [20] K.-U. Schmidt, J. Jedwab and M. G. Parker, Two binary sequence families with large merit factor,, Adv. Math. Commun., 3 (2009), 135. doi: 10.3934/amc.2009.3.135. Google Scholar [21] M. R. Schroeder, "Number Theory in Science and Communication: with Applications in Cryptography, Physics, Digital Information, Computing, and Self-similarity,'', 3rd edition, (1997). Google Scholar [22] R. Turyn and J. Storer, On binary sequences,, Proc. Amer. Math. Soc., 12 (1961), 394. doi: 10.1090/S0002-9939-1961-0125026-2. Google Scholar [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. doi: 10.1117/12.344685. Google Scholar

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. doi: 10.1109/18.42220. Google Scholar [2] L. Bömer and M. Antweiler, Optimizing the aperiodic merit factor of binary arrays,, Signal Process, 30 (1993), 1. doi: 10.1016/0165-1684(93)90047-E. Google Scholar [3] L. Bömer, M. Antweiler and H. Schotten, Quadratic residue arrays,, Frequenz, 47 (1993), 190. doi: 10.1515/FREQ.1993.47.7-8.190. Google Scholar [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. doi: 10.1109/TIT.2004.838341. Google Scholar [5] D. Calabro and J. K. Wolf, On the synthesis of two-dimensional arrays with desirable correlation properties,, Inform. Control, 11 (1967), 537. doi: 10.1016/S0019-9958(67)90755-3. Google Scholar [6] J. A. Davis, J. Jedwab and K. W. Smith, Proof of the Barker array conjecture,, Proc. Amer. Math. Soc., 135 (2007), 2011. doi: 10.1090/S0002-9939-07-08703-5. Google Scholar [7] H. Eggers, "Synthese zweidimensionaler Folgen mit guten Autokorrelationseigenschaften,'', Ph.D thesis, (1986). Google Scholar [8] T. A. Gulliver and M. G. Parker, The multivariate merit factor of a Boolean function,, in, (2005), 58. Google Scholar [9] T. Høholdt and H. E. Jensen, Determination of the merit factor of Legendre sequences,, IEEE Trans. Inform. Theory, 34 (1988), 161. doi: 10.1109/18.2620. Google Scholar [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. doi: 10.1109/TIT.1985.1057071. Google Scholar [11] J. Jedwab, A survey of the merit factor problem for binary sequences,, in, (2005), 30. doi: 10.1007/11423461_2. Google Scholar [12] J. Jedwab and K.-U. Schmidt, The merit factor of binary sequence families constructed from $m$-sequences,, Contemp. Math., 518 (2010), 265. Google Scholar [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., (). Google Scholar [14] H. E. Jensen and T. Høholdt, Binary sequences with good correlation properties,, in, (1989), 306. Google Scholar [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. doi: 10.1109/18.79917. Google Scholar [16] R. Lidl and H. Niederreiter, "Finite Fields,'' 2nd edition,, Cambridge University Press, (1997). Google Scholar [17] J. E. Littlewood, "Some Problems in Real and Complex Analysis,'', D. C. Heath and Co. Raytheon Education Co., (1968). Google Scholar [18] M. J. Mossinghoff, Wieferich pairs and Barker sequences,, Des. Codes Cryptogr., 53 (2009), 149. doi: 10.1007/s10623-009-9301-3. Google Scholar [19] D. V. Sarwate, Mean-square correlation of shift-register sequences,, IEE Proc., 131 (1984), 101. Google Scholar [20] K.-U. Schmidt, J. Jedwab and M. G. Parker, Two binary sequence families with large merit factor,, Adv. Math. Commun., 3 (2009), 135. doi: 10.3934/amc.2009.3.135. Google Scholar [21] M. R. Schroeder, "Number Theory in Science and Communication: with Applications in Cryptography, Physics, Digital Information, Computing, and Self-similarity,'', 3rd edition, (1997). Google Scholar [22] R. Turyn and J. Storer, On binary sequences,, Proc. Amer. Math. Soc., 12 (1961), 394. doi: 10.1090/S0002-9939-1961-0125026-2. Google Scholar [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. doi: 10.1117/12.344685. Google Scholar
 [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] Moulay Rchid Sidi Ammi, Ismail Jamiai. Finite difference and Legendre spectral method for a time-fractional diffusion-convection equation for image restoration. Discrete & Continuous Dynamical Systems - S, 2018, 11 (1) : 103-117. doi: 10.3934/dcdss.2018007 [7] 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 [8] Chun-Hao Teng, I-Liang Chern, Ming-Chih Lai. Simulating binary fluid-surfactant dynamics by a phase field model. Discrete & Continuous Dynamical Systems - B, 2012, 17 (4) : 1289-1307. doi: 10.3934/dcdsb.2012.17.1289 [9] Guangmei Shao, Wei Xue, Gaohang Yu, Xiao Zheng. Improved SVRG for finite sum structure optimization with application to binary classification. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019052 [10] Valery Y. Glizer, Oleg Kelis. Singular infinite horizon zero-sum linear-quadratic differential game: Saddle-point equilibrium sequence. Numerical Algebra, Control & Optimization, 2017, 7 (1) : 1-20. doi: 10.3934/naco.2017001 [11] 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. [12] Martino Bardi. Explicit solutions of some linear-quadratic mean field games. Networks & Heterogeneous Media, 2012, 7 (2) : 243-261. doi: 10.3934/nhm.2012.7.243 [13] Olivier Guéant. New numerical methods for mean field games with quadratic costs. Networks & Heterogeneous Media, 2012, 7 (2) : 315-336. doi: 10.3934/nhm.2012.7.315 [14] Kai Du, Jianhui Huang, Zhen Wu. Linear quadratic mean-field-game of backward stochastic differential systems. Mathematical Control & Related Fields, 2018, 8 (3&4) : 653-678. doi: 10.3934/mcrf.2018028 [15] Denis Danilov, Britta Nestler. Phase-field modelling of nonequilibrium partitioning during rapid solidification in a non-dilute binary alloy. Discrete & Continuous Dynamical Systems - A, 2006, 15 (4) : 1035-1047. doi: 10.3934/dcds.2006.15.1035 [16] 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 [17] Sabyasachi Karati, Palash Sarkar. Connecting Legendre with Kummer and Edwards. Advances in Mathematics of Communications, 2019, 13 (1) : 41-66. doi: 10.3934/amc.2019003 [18] Zhenlin Guo, Ping Lin, Guangrong Ji, Yangfan Wang. Retinal vessel segmentation using a finite element based binary level set method. Inverse Problems & Imaging, 2014, 8 (2) : 459-473. doi: 10.3934/ipi.2014.8.459 [19] Xiao-Hong Liu, Wei Wu. Coerciveness of some merit functions over symmetric cones. Journal of Industrial & Management Optimization, 2009, 5 (3) : 603-613. doi: 10.3934/jimo.2009.5.603 [20] Oğul Esen, Partha Guha. On the geometry of the Schmidt-Legendre transformation. Journal of Geometric Mechanics, 2018, 10 (3) : 251-291. doi: 10.3934/jgm.2018010

2018 Impact Factor: 0.879