自相关性和线性复杂度的关系

摘要

自相关性和线性复杂度是衡量序列伪随机性质的两个独立的指标.针对周期为2n的伪随机序列,本文首次指出了自相关性和线性复杂度之间存在的一个关系.该关系可应用于以下两个方面:(1)由序列的线性复杂度来估计/确定序列的自相关函数值;(2)通过线性复杂度来检验给定序列族的互相关性质.进一步的,针对一类周期为2n的伪随机序列,我们指出这类序列的自相关函数值和线性复杂度以及k-错线性复杂度存在着关系.