Correlation, Linear Complexity, Maximum order Complexity on Families of binary Sequences

2021/07/25 by Zhixiong Chen, Chen, Zhixiong, Ana I. Gómez +5
Computer Science · Engineering · #Cellular Automata and Applications #Coding theory and cryptography #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2107.11840

openalex publication_date 2021/07/25 · openalex created_date 2021/08/02 · openalex updated_date 2026/07/28

Abstract

Correlation measure of order k is an important measure of randomness in binary sequences. This measure tries to look for dependence between several shifted version of a sequence. We study the relation between the correlation measure of order k and another two pseudorandom measures: the Nth linear complexity and the Nth maximum order complexity. We simplify and improve several state-of-the-art lower bounds for these two measures using the Hamming bound as well as weaker bounds derived from it.

Related

• Maximum-order Complexity and Correlation Measures
• Family complexity and cross-correlation measure for families of binary sequences
• Families of sequences with good family complexity and cross-correlation measure
• The correlation measures of finite sequences: limiting distributions and\n minimum values
• The cross-correlation measure of families of finite binary sequences:\n limiting distributions and minimal values