The merit factor of binary arrays derived from the quadratic character

Kai-Uwe Schmidt

doi:10.3934/amc.2011.5.589

Article Contents

2011, Volume 5, Issue 4: 589-607. Doi: 10.3934/amc.2011.5.589

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

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

Received: June 30, 2010

Revised: June 30, 2011

Published: October 2011

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.