Family complexity and cross-correlation measure for families of binary sequences

Winterhof A., Yayla O.

RAMANUJAN JOURNAL, vol.39, no.3, pp.639-645, 2016 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 39 Issue: 3
  • Publication Date: 2016
  • Doi Number: 10.1007/s11139-014-9649-5
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.639-645
  • Middle East Technical University Affiliated: No


We study the relationship between two measures of pseudorandomness for families of binary sequences: family complexity and cross-correlation measure introduced by Ahlswede et al. in 2003 and recently by Gyarmati et al., respectively. More precisely, we estimate the family complexity of a family (e(i, 1,...,) e(i, N)) is an element of {-1,+1}(N), i = 1, ..., F, of binary sequences of length N in terms of the cross-correlation measure of its dual family (e(1, n,...,) e(F, n)) is an element of {-1,+ 1}(F), n = 1,..., N. We apply this result to the family of sequences of Legendre symbols with irreducible quadratic polynomials modulo p with middle coefficient 0, that is, e(i, n) = (n(2)-bi(2))(n=1)((p-1)/2) for i = 1,..., (p - 1)/2, where b is a quadratic nonresidue modulo p, showing that this family as well as its dual family has both a large family complexity and a small cross-correlation measure up to a rather large order.