有趣的线性反馈移位寄存器(LFSR)

2021-12-14 14:19:07 网络

最近一直在研究信道编码，发现在信道编码里面有一个电路比较重要也比较有趣，那就是线性反馈移位寄存器LFSR，相信大家对 LFSR电路也不陌生了，在通信领域lfsr有着很广泛的应用，比如说M序列，扰码，信道编码，密码学这方面都有很广泛的应用，LFRS的结构一般如下图：

其中他需要一个生成多项式为：

这个多项式是一个本原多项式，然后知道这个电路有一些有意思的性质，下面我以m = 3 来做个例子具体的电路图如下所示：

假设开始的时候(D2，D1，D0 ) = (0，0，1)，那么每过一个时钟周期会进行跳变一次，

可以看到具体的跳变如下所示：

然后我们可以看到这个计数器循环起来了，很好玩吧，无论进入那样一个状态除了0之外，都可以循环着回来，其实这里就相当于了一个3bit的伪随机数，很有意思，不是所有的多项式都有这个特性，我们现在在从数学上面来看看这个问题，其实最上面的电路是可以看成是一个除法电路，在Galois域的一个除法电路。现在假设的是R(x)是寄存器中剩余的数据，M(x)是输入的码字多项式，然后数学公式可以表示成：

然后我分别计算出了M(x)的各种情况，

然后我们单独进行一下7次方的运算

发现7次方的运算和0次的时候的余数是一样的

然后我们发现其实在上面的电路中对多项式的除法也是可以循环起来的，可以验证的是

把这个记成

上面的式子是可以循环的，然后我又想到了CRC的计算，CRC的计算也可以通过一个除法电路来实现，

假设码子多项式为

生成多项式为

那么CRC的码字为

这样我们同样可以用LFSR电路来进行实现

首先对M(x)乘以一个x的r次方，然后去去除G(x)，在电路上的表现就是

所以在输入码字以后还需要多输入r拍的0这样才能使最后的CRC码字数据。