有趣的線(xiàn)性反饋移位寄存器(LFSR)

最近一直在研究信道編碼，發(fā)現在信道編碼里面有一個(gè)電路比較重要也比較有趣，那就是線(xiàn)性反饋移位寄存器 LFSR ，相信大家對 LFSR 電路也不陌生了，在通信領(lǐng)域lfsr有著(zhù)很廣泛的應用，比如說(shuō)M序列，擾碼，信道編碼，密碼學(xué)這方面都有很廣泛的應用，LFRS的結構一般如下圖：

其中他需要一個(gè)生成多項式為：

這個(gè)多項式是一個(gè)本原多項式，然后知道這個(gè)電路有一些有意思的性質(zhì)，下面我以m = 3 來(lái)做個(gè)例子具體的電路圖如下所示：

假設開(kāi)始的時(shí)候(D2，D1，D0 ) = (0，0，1)，那么每過(guò)一個(gè)時(shí)鐘周期會(huì )進(jìn)行跳變一次，

可以看到具體的跳變如下所示：

然后我們可以看到這個(gè)計數器循環(huán)起來(lái)了，很好玩吧，無(wú)論進(jìn)入那樣一個(gè)狀態(tài)除了0之外，都可以循環(huán)著(zhù)回來(lái)，其實(shí)這里就相當于了一個(gè)3bit的偽隨機數，很有意思，不是所有的多項式都有這個(gè)特性，我們現在在從數學(xué)上面來(lái)看看這個(gè)問(wèn)題，其實(shí)最上面的電路是可以看成是一個(gè)除法電路，在Galois域的一個(gè)除法電路?，F在假設的是R(x)是寄存器中剩余的數據，M(x)是輸入的碼字多項式，然后數學(xué)公式可以表示成：

然后我分別計算出了M(x)的各種情況，

然后我們單獨進(jìn)行一下7次方的運算

發(fā)現7次方的運算和0次的時(shí)候的余數是一樣的

然后我們發(fā)現其實(shí)在上面的電路中對多項式的除法也是可以循環(huán)起來(lái)的，可以驗證的是

把這個(gè)記成

上面的式子是可以循環(huán)的，然后我又想到了CRC的計算，CRC的計算也可以通過(guò)一個(gè)除法電路來(lái)實(shí)現，

假設碼子多項式為

生成多項式為

那么CRC的碼字為

這樣我們同樣可以用LFSR電路來(lái)進(jìn)行實(shí)現

首先對M(x)乘以一個(gè)x的r次方，然后去去除G(x)，在電路上的表現就是

所以在輸入碼字以后還需要多輸入r拍的0這樣才能使最后的CRC碼字數據。

同理這個(gè)電路也可以進(jìn)行CRC校驗，把生成的數據全部都依次輸入進(jìn)這個(gè)。