American Institute of Mathematical Sciences

Advanced
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

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.  Google Scholar

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

[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.  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-3249. 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-560. 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-2018. doi: 10.1090/S0002-9939-07-08703-5.  Google Scholar

[7]

H. Eggers, "Synthese zweidimensionaler Folgen mit guten Autokorrelationseigenschaften,'' Ph.D thesis, RWTH Aachen, Germany, 1986. Google Scholar

[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. 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-164. 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-552. doi: 10.1109/TIT.1985.1057071.  Google Scholar

[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.  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-278.  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 "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes'' (eds. L. Huguet and A. Poli), Springer-Verlag, (1989), 306-320.  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-626. 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., Lexington, MA, 1968.  Google Scholar

[18]

M. J. Mossinghoff, Wieferich pairs and Barker sequences, Des. Codes Cryptogr., 53 (2009), 149-163. 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-106. 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-156. 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, Springer, Berlin, 1997.  Google Scholar

[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.  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-364. 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-1057. 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-13. 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-196. 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-3249. 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-560. 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-2018. doi: 10.1090/S0002-9939-07-08703-5.  Google Scholar

[7]

H. Eggers, "Synthese zweidimensionaler Folgen mit guten Autokorrelationseigenschaften,'' Ph.D thesis, RWTH Aachen, Germany, 1986. Google Scholar

[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. 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-164. 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-552. doi: 10.1109/TIT.1985.1057071.  Google Scholar

[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.  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-278.  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 "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes'' (eds. L. Huguet and A. Poli), Springer-Verlag, (1989), 306-320.  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-626. 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., Lexington, MA, 1968.  Google Scholar

[18]

M. J. Mossinghoff, Wieferich pairs and Barker sequences, Des. Codes Cryptogr., 53 (2009), 149-163. 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-106. 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-156. 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, Springer, Berlin, 1997.  Google Scholar

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

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, 2020  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 & 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 & Continuous Dynamical Systems - B, 2012, 17 (4) : 1289-1307. doi: 10.3934/dcdsb.2012.17.1289
[11]

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, 2020, 16 (5) : 2253-2266. doi: 10.3934/jimo.2019052
[12]

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
[13]

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.

[14]

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
[15]

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
[16]

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
[17]

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
[18]

Zhenghong Qiu, Jianhui Huang, Tinghan Xie. Linear-Quadratic-Gaussian mean-field controls of social optima. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021047
[19]

Denis Danilov, Britta Nestler. Phase-field modelling of nonequilibrium partitioning during rapid solidification in a non-dilute binary alloy. Discrete & Continuous Dynamical Systems, 2006, 15 (4) : 1035-1047. doi: 10.3934/dcds.2006.15.1035
[20]

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

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy