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

2014/08/21 by Arne Winterhof, Winterhof, Arne, Oğuz Yayla +1
Computer Science · Mathematics · Engineering · #Coding theory and cryptography #Analytic Number Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1408.4980

Abstract

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)∈ \-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)∈ \-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²-bi²)/(p))_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 have both a large family complexity and a small cross-correlation measure up to a rather large order.

Related

• Families of sequences with good family complexity and cross-correlation measure
• The cross-correlation measure of families of finite binary sequences:\n limiting distributions and minimal values
• Correlation, Linear Complexity, Maximum order Complexity on Families of binary Sequences
• Improved lower bound on the family complexity of Legendre sequences
• Pseudorandom binary sequences: quality measures and number-theoretic constructions