Families of sequences with good family complexity and cross-correlation measure

Doğan K., ŞAHİN M., YAYLA O.

AIMS Mathematics, vol.10, no.1, pp.38-55, 2025 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 10 Issue: 1
  • Publication Date: 2025
  • Doi Number: 10.3934/math.2025003
  • Journal Name: AIMS Mathematics
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Directory of Open Access Journals
  • Page Numbers: pp.38-55
  • Keywords: binary sequences, cross-correlation measure, family complexity, k-symbols sequences, pseudorandomness
  • Middle East Technical University Affiliated: Yes

Abstract

In this paper, we examine the pseudorandomness of a family of sequences with respect to two key measures: family complexity (f-complexity) and cross-correlation measure of order ℓ. Our study encompasses sequences over both binary and k-symbol (k-ary) alphabets. We first extend known methods for constructing families of binary pseudorandom sequences and establish a bound on the f-complexity of a large family of binary sequences generated from the Legendre symbols of certain irreducible polynomials. We demonstrate that this family, as well as its dual, exhibits both high family complexity and low cross-correlation measure up to a relatively high order. Additionally, we present a second family of binary sequences with similarly high f-complexity and low cross-correlation measure. Finally, we generalize our results to families of sequences over the k-symbol alphabets.