最近一直在研究信道編碼，發(fā)現(xiàn)在信道編碼里面有一個電路比較重要也比較有趣，那就是線性反饋移位寄存器 LFSR ，相信大家對 LFSR 電路也不陌生了，在通信領(lǐng)域lfsr有著很廣泛的應(yīng)用，比如說M序列，擾碼，信道編碼，密碼學(xué)這方面都有很廣泛的應(yīng)用，LFRS的結(jié)構(gòu)一般如下圖：
其中他需要一個生成多項式為：
這個多項式是一個本原多項式，然后知道這個電路有一些有意思的性質(zhì)，下面我以m = 3 來做個例子具體的電路圖如下所示：
假設(shè)開始的時候(D2，D1，D0 ) = (0，0，1)，那么每過一個時鐘周期會進行跳變一次，
可以看到具體的跳變?nèi)缦滤荆?/p>
然后我們可以看到這個計數(shù)器循環(huán)起來了，很好玩吧，無論進入那樣一個狀態(tài)除了0之外，都可以循環(huán)著回來，其實這里就相當于了一個3bit的偽隨機數(shù)，很有意思，不是所有的多項式都有這個特性，我們現(xiàn)在在從數(shù)學(xué)上面來看看這個問題，其實最上面的電路是可以看成是一個除法電路，在Galois域的一個除法電路?，F(xiàn)在假設(shè)的是R(x)是寄存器中剩余的數(shù)據(jù)，M(x)是輸入的碼字多項式，然后數(shù)學(xué)公式可以表示成：
然后我分別計算出了M(x)的各種情況，
然后我們單獨進行一下7次方的運算
發(fā)現(xiàn)7次方的運算和0次的時候的余數(shù)是一樣的
然后我們發(fā)現(xiàn)其實在上面的電路中對多項式的除法也是可以循環(huán)起來的，可以驗證的是
把這個記成
上面的式子是可以循環(huán)的，然后我又想到了CRC的計算，CRC的計算也可以通過一個除法電路來實現(xiàn)，
假設(shè)碼子多項式為
生成多項式為
那么CRC的碼字為
這樣我們同樣可以用LFSR電路來進行實現(xiàn)
首先對M(x)乘以一個x的r次方，然后去去除G(x)，在電路上的表現(xiàn)就是
所以在輸入碼字以后還需要多輸入r拍的0這樣才能使最后的CRC碼字數(shù)據(jù)。
同理這個電路也可以進行CRC校驗，把生成的數(shù)據(jù)全部都依次輸入進這個。
下載文檔
