LFSR

這就是最後的project的大致內容：

LFSR（LinearFeedbackShiftingRegister），是流密碼中常用技術之一。問題是有一個F_2域（{0,1}）上的l維線性空間（記為F_2^l）裡面的常向量a（已知）。給定初始狀態x為F_2^l上未知值，記為x=(x_1,x_2,...,x_l)，用如下的方程生成餘下的位（對一個F_2上向量空間每一個維數上的坐標可以看作一個bit）：

x_{l+i}=a_1x_{i}+a_2x_{i+1}+...+a_lx_{i+l-1}i=1,2,...,N-l

於是我們把x延拓到了F_2^N上。這個過程可以看作是一個[N,k]-線性碼的生成過程。原因是，利用上式迭代，可以計算出

x_i=h_{i,1}x_1+h_{i,2}x_2+...h_{i,l}x_l

那麼如果記由h_{i,j}生成的矩陣為

G=(h_{i,j})i=1,...,N;j=1,...,l

我們產生的延拓后的向量為y，F_2^N的向量，則

y=Gx

所以G稱為生成矩陣，由它生成了一個[N,k]-線性碼，因為可以讓x遍歷F_2^l所有值，由於G的列滿秩，y實際在F_2^N生成了一個k維的線性子空間。現在的問題是，不知道x將y在一個BSC（BinarySymmetricChannel，二元對稱通道，錯誤率為p<.5）上傳輸，得到了z，也是F_2^N的向量。如果想獲得整個原序列y，其實只需要算出來x，但是我們觀察到的為z。怎麼由z計算出y，就相當於一個[N,k]-線性碼解碼問題了。

通常情況下，這個解碼的情況是p不大，但是現在p是接進.5的，我們處理的具體問題中p=.3。因此解碼會變得困難。

能正確解碼的重要特點是對於一個F_2^N的向量z它和某一個碼字y的Hamming距離最近（ML解碼，MaximumLikelihood），則用y代表z的解碼結果。那麼，如果z的確是由y生成，則它到其他碼字的Hamming距離大於到y的Hamming距離。那麼如果這個[N,k]-線性碼的最小碼距為d，則z到y的Hamming距離應不超過\lfloord/2\rfloor。

那麼，首先我們應該從G計算出該線性碼的碼距。

線性反饋移位寄存器(LFSR)是內測試電路中最基本的標準模塊結構，既用作偽隨機測試碼產生器，也作為壓縮測試結果數據的特徵分析器。

LFSR由一系列D觸發器及少量異或元件組成。標準LFSR模塊如圖7.32所示。它在控制端C1,C2的控制下以四種不同的方式工作。

它和約翰遜計數器十分相似，不同之處在於其最後一級不是直接反饋回第一級，並且它的抽頭可以可以循環使用。這種計數器的下一個狀態邏輯是非常簡單的，是一些異或門或者同或門（注意：使用同或門或者異或門都可以達到2N-1個計數狀態（二進位為2N個），但是，使用同或門時全“1”狀態是不可恢復狀態，使用異或門時全“0”是不可恢復狀態）。由於其反饋邏輯很簡單，因而它的執行速度比二進位計數器快。同時應該注意的是，它的輸出是偽隨機序列，周而復始地循環。

可以通過查表得到各種長度LFSR計數器的使用抽頭，這些抽頭通過異或門或者同或門之後回到第一個觸發器。這種形式有時稱作“多對一”，這主要是對它的反饋方式而言的。還有一種形式就是將異或邏輯分解為多個雙輸入門，使它們分佈於寄存器陣列中。這種形式叫做“一對多”。

例如：對於4bits的LFSR計數器，能夠使用的抽頭為[3,0]，使用“多對一”形式時：reg[0]=reg[0]^reg[3]或者reg[0]=reg[0]~^reg[3]。使用“一對多”形式時：reg[0]<=reg[3],reg[1]<=reg[0]^reg[3],reg[3:2]<=reg[2:1]