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.

[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.

[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.

[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.

[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.

[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.

[7]

H. Eggers, "Synthese zweidimensionaler Folgen mit guten Autokorrelationseigenschaften,'', Ph.D thesis, (1986).

[8]

T. A. Gulliver and M. G. Parker, The multivariate merit factor of a Boolean function,, in, (2005), 58.

[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.

[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.

[11]

J. Jedwab, A survey of the merit factor problem for binary sequences,, in, (2005), 30. 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.

[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, (1989), 306.

[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.

[16]

R. Lidl and H. Niederreiter, "Finite Fields,'' 2nd edition,, Cambridge University Press, (1997).

[17]

J. E. Littlewood, "Some Problems in Real and Complex Analysis,'', D. C. Heath and Co. Raytheon Education Co., (1968).

[18]

M. J. Mossinghoff, Wieferich pairs and Barker sequences,, Des. Codes Cryptogr., 53 (2009), 149. doi: 10.1007/s10623-009-9301-3.

[19]

D. V. Sarwate, Mean-square correlation of shift-register sequences,, IEE Proc., 131 (1984), 101.

[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.

[21]

M. R. Schroeder, "Number Theory in Science and Communication: with Applications in Cryptography, Physics, Digital Information, Computing, and Self-similarity,'', 3rd edition, (1997).

[22]

R. Turyn and J. Storer, On binary sequences,, Proc. Amer. Math. Soc., 12 (1961), 394. 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. 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. 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. doi: 10.1016/0165-1684(93)90047-E.

[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.

[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.

[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.

[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.

[7]

H. Eggers, "Synthese zweidimensionaler Folgen mit guten Autokorrelationseigenschaften,'', Ph.D thesis, (1986).

[8]

T. A. Gulliver and M. G. Parker, The multivariate merit factor of a Boolean function,, in, (2005), 58.

[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.

[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.

[11]

J. Jedwab, A survey of the merit factor problem for binary sequences,, in, (2005), 30. 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.

[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, (1989), 306.

[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.

[16]

R. Lidl and H. Niederreiter, "Finite Fields,'' 2nd edition,, Cambridge University Press, (1997).

[17]

J. E. Littlewood, "Some Problems in Real and Complex Analysis,'', D. C. Heath and Co. Raytheon Education Co., (1968).

[18]

M. J. Mossinghoff, Wieferich pairs and Barker sequences,, Des. Codes Cryptogr., 53 (2009), 149. doi: 10.1007/s10623-009-9301-3.

[19]

D. V. Sarwate, Mean-square correlation of shift-register sequences,, IEE Proc., 131 (1984), 101.

[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.

[21]

M. R. Schroeder, "Number Theory in Science and Communication: with Applications in Cryptography, Physics, Digital Information, Computing, and Self-similarity,'', 3rd edition, (1997).

[22]

R. Turyn and J. Storer, On binary sequences,, Proc. Amer. Math. Soc., 12 (1961), 394. 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. 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]

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

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (3)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]