停走生成器输出序列的概率特性和马氏链分析

"一类‘停走’生成器输出序列的若干概率性质 (2002年)" 是一篇关于钟控序列生成器，特别是“停走”生成器的文章，作者为唐加山，发表于2002年《南京邮电学院学报（自然科学版）》。文章探讨了在更一般假设下的“停走”生成器的输出序列概率性质，扩展了已有的研究成果。 正文: “停走”生成器是一种特殊的钟控序列生成器，它由两个线性反馈移位寄存器（LFSR）构成。这种生成器的输出序列受两个LFSR的输出序列a∞和b∞的影响，其中a∞和b∞是独立的随机变量序列，它们分别取值为0和1，并满足一定的概率分布条件。文章假设每个ai和bi独立同分布，且有固定的概率p和q取0或1，0<p,q<1。 生成器的输出序列un由公式(1)给出，即un是b∞的值与a∞的累加值的乘积。这个序列可以看作是在b0的基础上，逐项加上a∞的前n个值。因此，un的值取决于b0以及a∞的前n个元素。 该文的研究重点在于在LFSR输出序列的非特殊假设下，分析“停走”生成器输出序列un的统计特性。这包括但不限于序列的分布、独立性以及与马尔科夫链和平稳过程相关的特性。在已有的文献中，这些性质通常在更严格的假设下被研究，如LFSR输出序列是二进制循环移位序列。唐加山在更一般的情况下讨论了这些问题，得出了新的结论。 文章指出，通过分析“停走”生成器的输出序列，可以验证它是否满足强平稳马尔科夫链的条件。马尔科夫链是一种随机过程，其未来状态只依赖于当前状态，而不依赖于过去的详细历史。在密码学和其他相关领域，这种性质对于生成器的随机性和安全性至关重要。 此外，由于“停走”生成器在密码学等领域的广泛应用，了解其输出序列的随机性和统计特性对于评估其作为伪随机数生成器的性能具有重要意义。通过深入研究这些概率性质，可以为设计更安全、更高效的密码系统提供理论支持。 这篇文章深化了我们对“停走”生成器的理解，尤其是在更广泛的情况下的概率特性，为后续的相关研究提供了理论基础。同时，它也为实际应用中的序列生成器设计和优化提供了理论依据。