线性的通过移位来持续生成的一个随机数生成器,通过一组寄存器实现,所以叫$线性移位寄存器$。

下面看图:
线性移位寄存器原.png

下面我画下每个元素的原理:
线性移位寄存器标注.png

这里默认每个开关都关上了,所以最终的结果是$a_1⊕a_2⊕…⊕a_n$

但如果开关电路的开关不一定是闭合的呢?

于是我们得到一般形式:

$$ a_k = \sum^n_{i=1}{c_i\times a_{k-i}} (k>n) $$

这个式子的另一个形式是:

$$ \sum^n_{i=1}{c_i a_{k-i}} - a_k = 0 (k>n) $$

在这里我们注意这是在模2的有限域下的运算,所以以下两个事实:

  1. 开关开启关闭用0/1表示,最终的结果表示为开关C与输入值之乘积。因为关闭的话结果为0,所以也相当于未参加运算。所以在上面第一个算式里我特意将 $c_i a_{k-i}$ 写成了 $c_i\times a_{k-i}$。
  2. 模2有限域下的加法,电路上的实现就是异或,非常有意思的结论。

接下来,我们看个例题:

线性移位寄存器例题.png

方便起见我就直接截图解析:

线性移位寄存器例题解析.png

一个线性反馈移位寄存器中,有N级反馈的存在,但是如果开关电路全部置于关,或是起始部分不置于开启状态,那么就会有部分不参加反馈,它的形式如下:
请输入图片描述

如此一来,我们很容易看出。n 级线性反馈移位寄存器最多有 $2^n$ 个不同的状态。因此 n 级线性反馈移位寄存器的状态周期小于等于 $2^{n-1}$。其输出序列的周期与状态周期相等,也小于等于 $2^{n-1}$。只要选择合适的反馈函数便可使序列的周期达到最大值 $2^{n-1}$,周期达到最大值的序列称为 m-序列

Last modification:November 12th, 2018 at 09:34 pm
If you think my article is useful to you, please feel free to appreciate