AUTOCORRELATION AND DISTINCTNESS OF DECIMATIONS OF l-SEQUENCES BASED ON PRIMES

作者：Tian Tian^*; Qi Wen Feng

来源：SIAM Journal on Discrete Mathematics, 2009, 23(2): 805-821.

DOI：10.1137/080721200

• feedback with carry shift registers
• l-sequences
• decimations
• autocorrelations
• cyclically distinct

It has long been open whether all pairs of proper decimations of l-sequences based on primes are cyclically distinct. By determining the nontrivial maximal autocorrelation of l-sequences, this paper presents a partial proof of the distinctness problem. Since the proof idea is completely different from former ones, the set of decimations that are known to be cyclically distinct is further enlarged. On the basis of convincing experimental data, the proof seems to ensure that more than 79% of l-sequences based on different primes satisfy the fact that every pair of proper decimations is cyclically distinct. In particular, a complete proof is provided for l-sequences based on primes of the form 2 . r + 1, where r is an odd prime number.

• 出版日期2009
• 单位中国科学技术信息研究所