第六章 循環(huán)碼的譯碼

1、第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 6.1 6.1 循環(huán)碼譯碼的一般原理循環(huán)碼譯碼的一般原理 6.2 6.2 捕錯譯碼捕錯譯碼 6.3 6.3 大數邏輯譯碼原理大數邏輯譯碼原理 6.4 大數邏輯可譯碼的構造 6.5 軟判決譯碼的基本原理 6.6 碼字錯誤概率最小的軟判決譯碼 習題習題 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 6.1 循環(huán)碼譯碼的一般原理循環(huán)碼譯碼的一般原理 設發(fā)送的碼字是設發(fā)送的碼字是C(x)=(cn-1x n-1+c1x+c0)(今后不再今后不再嚴格區(qū)分碼字與碼多項式嚴格區(qū)分碼字與碼多項式)， 通過通過q進制輸入和輸出的信進制輸入和輸出的

2、信道后，道后， 譯碼器輸入端得到的是譯碼器輸入端得到的是 R(x)=C(x)+E(x)=(r n-1 x n-1+r1x+r0) ri=ci+ei 式中，式中， E(x)=(en-1xn-1+e1x+e0)是信道產生的錯誤圖樣，是信道產生的錯誤圖樣， 應當指出，應當指出， 上述這些式中的上述這些式中的ci、 ri、 ei均是均是GF(q)中的元中的元素，素， 也就也就是我們這里僅討論硬判決時的譯碼方法。是我們這里僅討論硬判決時的譯碼方法。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 譯碼器的主要任務就是如何從譯碼器的主要任務就是如何從R(x)中得到正確的中得到正確的估計錯誤圖樣估計錯誤圖樣 (x)=

3、E(x)， 然后得到然后得到C(x)， 并由此得到并由此得到信息組信息組m(x)。 如同所有線性分組碼的譯碼一樣，如同所有線性分組碼的譯碼一樣， 循環(huán)碼的譯碼循環(huán)碼的譯碼也分為以下也分為以下3步：步： (1) 計算計算R(x)的伴隨式的伴隨式S(x)； (2) 根據伴隨式根據伴隨式S(x)找出估計錯誤圖樣找出估計錯誤圖樣 (x)； 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (3) R(x)- (x)= ， 得到譯碼器輸出的估值碼得到譯碼器輸出的估值碼字字 ， 并送出譯碼器給用戶。并送出譯碼器給用戶。 若若 =C， 則譯碼正則譯碼正確，確， 否則譯碼錯誤。否則譯碼錯誤。 如果是非系統(tǒng)碼，如果是非系統(tǒng)

4、碼， 則還必須由則還必須由 中得到估值信中得到估值信息組息組 ； 如果是系統(tǒng)碼，如果是系統(tǒng)碼， 這一步可省略。這一步可省略。 由于循環(huán)碼的循環(huán)特性，由于循環(huán)碼的循環(huán)特性， 在上述各步運算中，在上述各步運算中， 往往往比非循環(huán)碼的計算要簡單。往比非循環(huán)碼的計算要簡單。 CCCCm 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 一、一、 伴隨式計算和錯誤的檢測伴隨式計算和錯誤的檢測 設發(fā)送的碼字設發(fā)送的碼字C=(c n-1， c n-2， ， c 1， c 0)， 信道信道產生的錯誤圖樣為產生的錯誤圖樣為E=(e n-1， e n-2， ， e 1， e 0)， 譯譯碼器收到的碼器收到的n重重 R=C+E

5、=(c n-1+e n-1， c n-2+e n-2， ， c 1+e 1， c 0+e 0) =(r n-1， r n-2， ， r 1， r 0) r i=c i+e i第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 由伴隨式定義可知，由伴隨式定義可知， 相應的伴隨式是相應的伴隨式是 S=RHT=(C+E)HT=EHT 可知伴隨式可知伴隨式S僅與錯誤圖樣有關，僅與錯誤圖樣有關， 而與發(fā)送的碼字而與發(fā)送的碼字無關，無關， 由它可計算出錯誤圖樣由它可計算出錯誤圖樣E。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 設設n， k循環(huán)碼的生成多項式為循環(huán)碼的生成多項式為g(x)， 且且 xn-1=g(x)h(x)，

6、 g(x)=n-k。 該碼的一致校驗矩陣該碼的一致校驗矩陣由式由式(5.1.9)可知為可知為)(mod121xgxxxHTTnTnT第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 所以 )(mod),()(mod),()(mod),(0101101012101210121xgxxeeexgxxccccxgxxxxrrrrHRSnnnnnnnnnT第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 由此式可知相應的多項式表示為由此式可知相應的多項式表示為 S(x)C(x)+E(x)R(x)E(x) (mod g(x) (6.1.1) 或或 S(x)=Rg(x)+g(x)q(x)=Eg(x)+g(x)q1(x) (6.1

7、.2) 式中，式中， Rg(x)和和Eg(x)分別是分別是R(x)和和E(x)被被g(x)除后所除后所得的余式。得的余式。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 二、二、 伴隨式計算電路性質及一般譯碼器伴隨式計算電路性質及一般譯碼器 用用g(x)除法電路計算伴隨式的電路除法電路計算伴隨式的電路(伴隨式計算電伴隨式計算電路路)有如下一個很重要的特點。有如下一個很重要的特點。 定理定理6.1.1 若若S(x)是是R(x)的伴隨式，的伴隨式， 則則R(x)的循環(huán)的循環(huán)移位移位xR(x)(在模在模xn-1運算下運算下)的伴隨式的伴隨式S1(x)， 是是S(x)在在伴隨式計算電路中無輸入時伴隨式計算電路

8、中無輸入時(自發(fā)運算自發(fā)運算)右移一位的結果，右移一位的結果， 即即 S1(x)xS(x) (mod g(x) (6.1.3) 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 證明 由伴隨式定義可知xR(x)之伴隨式為 S1(x)xR(x) (mod g(x)=xRg(x)+q1(x)g(x) (6.1.4)由式(6.1.2)可知： xS(x)=xRg(x)+xq(x)g(x)該式減去式(6.1.4)可得： xS(x)-S1(x)=g(x)(xq(x)-q1(x)0 (mod g(x)因此 S1(x)xS(x) (mod g(x) 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 推論6.1.1 xjR(x)的伴隨

9、式Sj(x)xjS(x) (mod g(x)， j=0， 1， ， n-1。 而任意多項式a(x)乘R(x)所對應的伴隨式 Sa(x)a(x)S(x) (mod g(x) (6.1.5)第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 在q進制時， 若碼要糾正t個錯誤， 則錯誤圖樣代表共有11) 1(11jnqNjtj (6.1.6) 個。 譯碼時， 只要知道此代表圖樣的伴隨式， 該類其它錯誤圖樣的伴隨式都可由此代表圖樣伴隨式在伴隨式計算電路中得到。 這樣， 就使得循環(huán)碼譯碼器的錯誤圖樣識別電路大為簡化， 由原來識別jtjqjnN) 1(12(6.1.7) 個圖樣減少到N1個。 第第6章章 循環(huán)碼的譯碼循

10、環(huán)碼的譯碼 例如二進制碼， n=63， t=4， 由式(6.1.6)和式(6.1.7)計算譯碼器所需識別的錯誤圖樣個數如表 6 - 1所示。 表 6 - 1 N1， N2比較表 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 例6.1 二進制7， 4， 3循環(huán)漢明碼， 它的g(x)=x3+x+1， 相應的校驗矩陣100101101011100010111)(mod0123456xgxxxxxxxHTTTTTTT第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 由式(6.1.6)知， 構造此譯碼器的錯誤圖樣識別電路時， 只要識別一個圖樣E6=(1000000)就夠了， 該圖樣的伴隨式就是H的第一列(101)。 可知，

11、 識別E6錯誤圖樣的識別電路就是一個檢測伴隨式是否是(101)的電路。 由此可得如圖 6 - 1所示的譯碼電路。 圖中的伴隨式計算電路就是一個g(x)=x3+x+1的除法電路， 而有3個輸入端的與門和反相器， 組成了識別(101)的伴隨式識別器。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 圖 6 - 1 7， 4， 3循環(huán)漢明碼譯碼器第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 譯碼器的譯碼過程如下： (1) 開始譯碼時門開， 移存器內容全為0。 收到的R(x)=r6x6+r 0， 以高次項系數(r 6)至低次項系數的次序， 一方面送入7級緩沖器， 一方面送入g(x)除法電路計算伴隨式。 7次移位后， R

12、(x)的系數全部存入緩存器， g(x)電路也得到了伴隨式S0(x)， 此時門關， 禁止輸入。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (2) 若S0(x)1+x2x6 (mod g(x)， 說明E(x)=x6， r 6位有錯， 伴隨式計算(g(x)除法器)電路中的D0、 D1、 D2存貯的值是(101)， 它就是S0(x)=1+x2之系數。 D1的0經反相后成了1， 與門3個輸入端全為1， 呈打開狀態(tài)。 這時譯碼器繼續(xù)移位， r 6從緩存器輸出， 與門也輸出一個信號“1”與r 6相加， 使r 6由原來的1變成0， 或由0變成1， 糾正了r 6的錯誤： r6+1=c6+e 6+1=c 6+1+1=

13、c 6， 得到了原來發(fā)送的碼元。 此時與門的糾錯信號“1”也反饋到伴隨式計算電路輸入端(圖中虛線所示)， 對伴隨式進行修正， 以消去該錯誤對伴隨式的影響。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 這由于 R(x)=r n-1 x n-1+r 1x+r 0 相應的伴隨式是S0(x)。 糾錯后R(x)成為 R1(x)=(r n-1+1)x n-1+r 1x+r 0 與R1(x)相應的伴隨式 S1(x)S0(x)+x n-1 (mod g(x) 因為糾錯是在第n+1次移位進行的， 所以R1(x)成為 R1(x)=xR1(x) r n-2 x n-1+ r 0 x+r n-1+1 (mod xn-1)第

14、第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 相應的伴隨式 S1(x)xS1(x)xS0(x)+xnxS0(x)+1 (mod g(x) 由于S1(x)是xR1(x)的伴隨式， 而xS0(x)是xR(x)的伴隨式， 也就是xE(x)的伴隨式， 因此為了得到真正的xR(x)的伴隨式， 就必須從S1(x)中消去“1”， 也就是在伴隨式計算電路輸入端加1。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (3) 若E(x)=x5， 則S0(x)x5x2+x+1 (mod g(x)， 此時與門不打開， 說明r 6正確。 這時伴隨式計算電路和緩存器各移位一次， r 6輸出， r 5移到緩存器最右一級， 伴隨式計算電路得到的

15、伴隨式是 S1(x)xS0(x)xE(x)x2+1 (mod g(x)第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 因此再移動一次， 與門輸出的糾正信號“1”正好與緩存器輸出的r 5=c 5+1相加， 得到了c 5， 從而完成了糾錯。 若r 5不錯， 則重復上述過程一直到譯完一個碼字為止。 該譯碼過程可用表 6 - 2表示， 已知R(x)=x6+x+1， E(x)=x4。 由該表知， 到第10個節(jié)拍， 與門輸出一個“1”糾正r 4， 最后譯碼器輸出碼字(1010011)。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 表 6 - 2 圖 6 - 1譯碼器譯碼過程 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 從上述譯

16、碼過程可知， 譯一組碼共需14(2n=14)個節(jié)拍， 僅當第一組的R(x)移出7級緩存器后， 才能接收第二組的R(x)。 為了使譯碼連續(xù)， 必須再加一個伴隨式計算電路， 如圖 6 - 2。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 圖 6 - 2 7， 4碼完整譯碼器 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 開始工作時， 所有移存器的存數全為0， 門1開、 門2關。 當k=4次移位后， 4級緩存器接收了前面的4個信息位(對系統(tǒng)碼而言)， 此時門1關， 并使4級緩沖器停止移位。 再移動n-k=3次后， g(x)除法電路得到了伴隨式S0(x)， 此時門2開， 把上邊g(x)除法電路中的伴隨式送到下面的伴

17、隨式計算電路中， 隨即門2關閉， 且上邊g(x)除法電路立即清洗為0。 門1再次打開， 4級緩存器一邊送出第一組的信息， 一邊接收第二組R(x)的前k位信息組。 與此同時， 上邊伴隨式計算電路計算第二組R(x)的伴隨式， 而下邊伴隨式計算電路， 對第一組R(x)中的信息元進行糾錯。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 三、 擴展?jié)h明碼的譯碼 2m， 2m-1-m， 4擴展?jié)h明碼是由2m-1， 2m-1-m， 3漢明碼加一個全校驗位得到。 它的碼字(c n-1， ， c 0， c )中前n個碼元(c n-1， ， c 0)是漢明碼的一個碼字， c 是全校驗位。 擴展?jié)h明碼的碼長是8的整數倍，

18、特別適用于計算機或微機組成的數據處理或數據傳輸系統(tǒng)中。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 擴展?jié)h明碼能糾正一個錯誤同時發(fā)現兩個錯誤， 雖然它不是循環(huán)碼， 但它譯碼電路的主要部分與循環(huán)漢明碼的譯碼器相同， 只要加上檢錯電路即可。 如8， 4， 4擴展碼， 只要在7， 4， 3循環(huán)漢明碼譯碼器中， 加一個檢錯電路即成， 如圖 6 - 4。 圖中， (a)部分的電路基本上與圖 6 - 1同， 是循環(huán)漢明碼的譯碼器， 不同的是多加了一個全校驗位檢查電路， 它由一個級移存器加一個模2加法器組成。 圖中， (b)部分電路是一個檢錯電路。 該譯碼器的譯碼過程如下： 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼

19、圖 6 - 4 8， 4， 4擴展碼譯碼器 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (1) 開始時所有寄存器中的內容為0， 門1和門2開。 移位4次后門2關， R(x)=r 6x6+r 0+r 中的前4位(r 6， r 5， r 4， r 3)存入4級緩存器中， 它就是待糾錯的4個信息元。 移動7次后門1關， R(x)的前7個碼元(r 6， r 5， r 4， r 3， r 2， r 1， r 0)， 已全部送入7， 4， 3碼所決定的伴隨式計算電路中， 得到了伴隨式(s2， s1， s0)。 第8次移位后， 在全校驗位檢查電路中得到了全校驗的結果s， 此時譯碼器不再輸入。 第第6章章 循環(huán)碼的

20、譯碼循環(huán)碼的譯碼 (2) 當s=0、 (s0， s1， s2)=(000)時， 譯碼器認為接收R(x)無誤， 把4級緩存器中的信息元輸出。 (3) 當s=1、 (s0， s1， s2)(000)時， 譯碼器認為有一個錯誤， 此時糾錯部分的譯碼電路， 按上面講的漢明碼的方法進行糾錯譯碼， 4次移位后已全部輸出已糾正過的信息元。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (4) s=0、 (s0， s1， s2)(000)， 譯碼器認為出現了偶數個錯誤， 錯誤告警電路輸出一信號給用戶， 表示檢測到錯誤。 (5) s=1、 (s0， s1， s2)全為0時， 譯碼器認為出現了一個以上的奇數個錯誤， 錯誤

21、告警電路也輸出一個信號給用戶。 當然， 為了使譯碼連續(xù)， 在圖 6 - 4的(a)部分電路中， 也必須有兩個伴隨式計算電路， 這與圖 6 - 2相同。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 2m-1， 2m-2-m， 4增余刪信漢明碼的譯碼電路與擴展?jié)h明碼的譯碼電路基本相同， 只不過全校驗位的結果s也要輸入到錯誤圖樣的識別電路與門中， 對7， 3， 4碼來說就是輸入到圖 6 - 4(a)中有3個輸入端的與門， 如虛線所示， 其它情況相同。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 四、 縮短循環(huán)碼的譯碼 縮短i個信息位的n-i， k-i縮短循環(huán)碼， 是在n， k循環(huán)碼中選前i個信息位為0的碼字組成

22、。 若n， k循環(huán)碼的碼字 C(x)=c n-1 x n-1+c n-2 x n-2+c 0 則n-i， k-i縮短循環(huán)碼的碼字 C(x)=c n-1-ix n-1-i+c 0 因此， 縮短循環(huán)碼的譯碼器必須在原n， k循環(huán)碼譯碼器基礎上作如下修正： 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (1) k級緩存器改為k-i級； (2) 為了與(1)的改動相適應， R(x)應自動乘以xi， 然后再輸入伴隨式計算電路。 如7， 4循環(huán)漢明碼縮短一位變成6， 3碼， 它的譯碼器就是把圖 6 - 2中的譯碼器作如下變動： R(x)從圖中(A)虛線所示的地方輸入， 這相當于R(x)自動乘以x， 4級緩存器變成

23、3級。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 6.2 捕捕 錯錯 譯譯 碼碼 一、一、 基本工作原理基本工作原理 設碼字設碼字C(x)是某一糾是某一糾t個錯誤的個錯誤的n， k循環(huán)碼的循環(huán)碼的碼字，碼字， 當它通過有擾信道到達接收端譯碼器時成為當它通過有擾信道到達接收端譯碼器時成為R(x)=C(x)+E(x)。 相應的伴隨式相應的伴隨式 S(x)R(x)E(x)EI(x)+Ep(x) (mod g(x) 式中式中 EI(x)=e n-1 x n-1+e n-k x n-k Ep(x)=e n-k-1 x n-k-1+e 0第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 分別是在碼字信息組分別是在碼字信息

24、組(或前或前k位位)和校驗位和校驗位(或后或后n-k位位)上的錯誤圖樣。上的錯誤圖樣。 若若E(x)=n-k-1， 即所有即所有t個錯誤集個錯誤集中在校驗元的中在校驗元的n-k位上，位上， 則則EI(x)=0， E(x)=Ep(x)。 Ep(x)的最高次數是的最高次數是n-k-1， 而而g(x)=n-k， 所以當所以當E(x)=Ep(x)被被g(x)除后的余式仍為除后的余式仍為Ep(x)， 即即 S(x)E(x)=Ep(x) (mod g(x)第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 對于糾對于糾t個錯誤的循環(huán)碼來說，個錯誤的循環(huán)碼來說， 必須使必須使t個錯誤能個錯誤能連續(xù)地出現在連續(xù)地出現在n-

25、k位以內，位以內， 這等價于要求有連續(xù)這等價于要求有連續(xù)k位碼位碼元無錯，元無錯， 或錯誤圖樣中連續(xù)或錯誤圖樣中連續(xù)k位的值為位的值為0。 由于由于t個錯個錯誤均勻分布在誤均勻分布在n位上時最難滿足連續(xù)位上時最難滿足連續(xù)k位無錯這一要求，位無錯這一要求， 因此可以用捕錯方法譯碼的因此可以用捕錯方法譯碼的n， k循環(huán)碼，循環(huán)碼， n、 k、 t之間必須滿足下列條件：之間必須滿足下列條件： knt 或或 tnk， 或或 R1t (6.2.1)第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 定理定理 6.2.1 糾正糾正t個錯誤的個錯誤的GF(q)上的上的n， k循循環(huán)碼，環(huán)碼， 捕錯譯碼過程中已把捕錯譯碼過

26、程中已把t個錯誤集中在個錯誤集中在Ri(x)的最低的最低次次n-k位以內的充要條件是此時的伴隨式重量位以內的充要條件是此時的伴隨式重量 (Si(x)t (6.2.2) 證明 若錯誤已集中在n-k位低次位碼元段以內， 則 Si(x)xiE(x)=Ei(x)=Eip(x) (mod g(x) Si(x)=Eip(x)第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 碼只能糾正t個錯誤， 若錯誤圖樣E(x)是一個可糾正的錯誤圖樣， 則w(E(x)t， 因而E(x)的循環(huán)移位i次的錯誤圖樣Ei(x)的重量也必小于等于t， 所以 w(Si(x)=w(Ei(x)t第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 反之， 若w(S

27、i(x)t， 則錯誤一定集中在n-k位低次位碼元段內。 設錯誤沒有集中在該段以內， 則Ei(x)(x)g(x)， 由此 Ei(x)=q(x)g(x)+Si(x) Ei(x)-Si(x)=q(x)g(x)=Ci(x) Ci(x)是g(x)的倍式， 由循環(huán)碼性質知它必是n， k循環(huán)碼的一個碼字。 因而 w(Ei(x)+(-Si(x)=w(C(x)d=2t+1 由三角不等式(3.1.2)式可知 w(Ei(x)+w(-Si(x)w(Ei(x)+(-Si(x) 2t+1第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 因為 w(Ei(x)t 所以 w(-Si(x)t+1t 由于w(-Si(x)=w(Si(x)， 因

28、此上式與假設w(Si(x)t相矛盾， 因而錯誤沒有集中在n-k低次位以內的反證法假設不能成立， 故錯誤集中在n-k低次位內。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 例 6.2 二進制15， 7， 5循環(huán)碼， 生成多項式g(x)=x8+x7+x6+x4+1， 能糾正兩個錯誤。 t=2157 滿足捕錯譯碼的必要條件式(6.2.1)， 可以用捕錯譯碼方法譯碼， 它的譯碼電路如圖 6 - 5。 其譯碼過程如下： 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 圖 6 - 5 15， 7， 5循環(huán)碼捕錯譯碼電路第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (1) 開始工作時， 所有移存器和緩存器清洗為 0， 門 2、 門

29、 3 開， 門 1、 門 4 和門 5 關閉。 n=15 次移位后， R(x)的 15 個碼元全部移入(8+7)=15 級緩存器， 信息元在前 7 級， 同時伴隨式計算電路也完成了伴隨式計算得到了S0(x)。 若S0(x)=0， 說明無錯， 打開門 5， 輸出緩存器中的 7 個信息元。 若S0(x)0， 則進行以下各步。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (2) 此時門 2 關， 門 1 開， 若w(S0(x)2， 檢測電路檢測到伴隨式的重量2， 打開門 4， 關閉門 3。 (3) 若wS0(x)2， 則15級緩存器和g(x)除法電路都循環(huán)移位一次， 并檢查wS1(x)的重量， 若仍大于

30、2， 則繼續(xù)循環(huán)移位。 n， k循環(huán)碼的一般捕錯譯碼器如圖 6 - 6 和圖 6 - 7， 它們分別稱為第一類和第二類捕錯譯碼器。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 圖 6 - 6 n， k循環(huán)碼的第一類捕錯譯碼器 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 圖 6 - 7 n， k循環(huán)碼的第二類捕錯譯碼器 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 第二類譯碼器與第一類的差別， 僅在于第二類譯碼器是把接收到的R(x)自動乘以xn-k后， 再進入g(x)除法電路計算伴隨式， 即R(x)從g(x)電路的最高次位送入。 所以 R(x)xn-k(r n-1 x n-1+r n-2 x n-2+r 0)x n

31、-k r n-1 x n-k-1+r n-2 x n-k-2+r k+r k-1x n-1 +r 1x n-k+1+r 0 x n-k (mod xn-1) (6.2.3)第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 二、 捕錯譯碼的修正 捕錯譯碼是假定錯誤能集中在n-k段以內的前提下進行的， 要求n， k循環(huán)碼必須滿足式(6.2.1)的必要條件。 但是， 能滿足此條件的糾隨機錯誤的循環(huán)碼很少， 只有糾正一個錯誤的循環(huán)漢明碼和15， 7， 5碼等， 而絕大部分循環(huán)碼均不滿足。 可是， 有些循環(huán)碼如15， 5， 7碼， 23， 12， 7Golay碼及17， 9， 5QR碼等， 雖不滿足式(6.2.1)

32、的條件， 但k僅比nt稍大或相等， 也就是說在譯碼過程中不能把錯誤全部集中在n-k個碼元段以內， 而有個別錯誤可能在其它碼元位上。 為了解決此問題， 必須對捕錯譯碼加以適當修正。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 譯碼過程中， 若譯碼器能把大部分錯誤捕捉到n-k個碼元段以內， 同時使個別錯誤進入某幾個預先指定的位上， 則也能確定此時的錯誤圖樣。 當然， 為了實現這種運算必須附加一些電路， 以確定錯誤是否在某幾個指定的位置。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 設n， k循環(huán)碼能糾正t個錯誤， 生成多項式是g(x)。 譯碼器收到R(x)后， 計算伴隨式 S0(x)E(x)=EI(x)+Ep

33、(x)SI(x)+Ep(x) (mod g(x) SI(x)EI(x)=e n-1 x n-1+e n-k x n-k (mod g(x) Ep(x)So(x)-SI(x) (mod g(x) (6.2.4)第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 式中， SI(x)是R(x)前k位(對系統(tǒng)碼來說就是信息位)碼段中錯誤圖樣EI(x)的伴隨式。 由上式知， 若EI(x)及其SI(x)是已知的， 則可根據式(6.2.4)得到R(x)中后n-k位內(校驗位)的錯誤圖樣Ep(x)， 從而確定出原來的錯誤圖樣E(x)=EI(x)+Ep(x)。 設Qj(x)是次數小于等于k-1次的二進制多項式集合， SIj(

34、x)x n-k Qj(x) (mod g(x) Ij=0， 1， 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 是x n-k Qj(x)的伴隨式， 即如果在前k位上錯誤圖樣EI(x)= x n-k Qj(x)， 則SIj(x)就是它的伴隨式。 因此， 如果任何一個重量t的錯誤圖樣E(x)， 或它的i次循環(huán)移位xiE(x)=Ei(x)， 在前k位碼段內與Qj(x)中的任一個相一致， 則把此時的SIj(x)與此時Ei(x)的伴隨式Si(x)相減， 由式(6.2.4)知： (6.2.5)()()(xSxSxEjiIip第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 例 6.3 23， 12， 7Golay碼， 它的生

35、成多項式g(x)=x11+x10+x6+x5+x4+x2+1。 該碼若用循環(huán)碼的其它方法譯碼比較復雜， 但用修正捕錯譯碼則比較簡單。 該碼的n、 k與t之間關系不滿足式(6.2.1)， 不能用捕錯譯碼， 必須用修正方法。 首先選擇在前k位中的覆蓋多項式集合Qj(x)， 經分析可知應選0， x5， x62。 其中， x5， x6是特定在信息位置上的錯誤(對系統(tǒng)碼而言)， 而 0 表示錯誤能全部集中在后n-k位內， 不需要在前k位上指定錯誤的情況。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 由0， x5， x6可得： x n-k Q1(x)=x110=0 x n-k Q2(x)=x11x5=x16 x

36、 n-k Q3(x)=x11x6=x17 由此得到相應的 (x)=0 (mod g(x) (x)x16x9+x8+x6+x5+x2+x (mod g(x) (x)x17x10+x9+x7+x6+x3+x2 (mod g(x)0IS1IS2IS第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 圖 6 - 8 23， 12碼修正捕錯譯碼器 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (1) 開始時所有移存器中的存數均清洗為 0， 開關K1、 K2和K5接至D=0 的位置， K3和K4接至E=0 的位置。 接收到的R(x)一方面送入23(=11+12)級緩存器中， 一方面送入伴隨式計算電路計算伴隨式。 23 次移位后

37、， 得到伴隨式 S0(x)=s10 x10+s9x9+s0 把它送至 3 個錯誤圖樣檢測電路； 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (2) 開關K1、 K2和K5接到D=1 的位置， K3 和K4 仍在E=0 的位置， 由錯誤圖樣檢測電路檢測可糾正的錯誤圖樣： 若w(S0(x)3， 認為錯誤全在后 11 位中， 且錯誤圖樣就是S0(x)， 此時T1=1 導致E=1， K3和K4接至E=1 位置， 并在移位過程中對 11 級緩存器的輸出進行糾錯。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 若w(S0(x)-SI1(x)2， 則 S0(x)-SI1(x) =(s10 x10+s9x9+s1x+s0)

38、-(x9+x8+x6+x5+x2+x) =s10 x10+s9x9+s8x8+s7x7+s6x6+s5x5 +s4x4+s3x3+s2x2+s1x+s0第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 若w(S0(x)-SI2(x)2， 則 S0(x)-SI2(x)=(s10 x10+s9x9+s1x+s0) -(x10+x9+x7+x6+x3+x2) =s10 x10+s9x9 +s8x8+s7x7+s6x6+s5x5 +s4x4+s3x3+s2x2+s1x+s0第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 若w(S0(x)3， 或w(S0(x)-SI1(x)2， 或w(S0(x)-SI2(x)2， 則進行下一

39、步； (3) 把 23 級緩存器和伴隨式計算電路同時循環(huán)移位一次， 對新得到的伴隨式S1(x)， 進行如同第(2)步的檢查； 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (4) 當緩存器和伴隨式計算電路共移位2n次后， 譯完了一個碼字。 此時K1、 K2和K5接至D=0的位置， K3 和K4 接到E=0 的位置； (5) 送入第二組R(x)， 同時第一組已糾過錯的碼元由 23 級緩存器輸出。 所以， 接收到的R(x)從輸入譯碼器直至輸出完為止， 共需移位3n(323)次。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 三、 覆蓋多項式的數目與建立 無論是對二進制還是q進制碼， 修正捕錯譯碼器的復雜性主要決定

40、于覆蓋多項式集合Qj(x)中， 覆蓋多項式數目j的多少， 若j過大， 則譯碼器太復雜而不能實用。 對于一個特定的循環(huán)碼是否一定能找到覆蓋多項式？ 若能找到， 則應如何找Qj(x)？最小的j應是多少？這些是捕錯譯碼能否實用的關鍵問題。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 對于滿足式(6.2.1)的碼， 也就是錯誤能全部集中到連續(xù)的n-k位以內， 或能保證連續(xù)k位無錯， 則覆蓋多項式必定存在， 就是Q0(x)=0， j=1； 如果碼不滿足式(6.2.1)， 但滿足以下關系式： R2t 或 2ntk (6.2.7)第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 引理 6.2.1 對于糾t個錯誤的GF(q)上

41、的n， k循環(huán)碼， 當且僅當R2t時， 覆蓋多項式集合必存在。 表 6 - 33， 4給出了某些二進制循環(huán)碼的覆蓋多項式集合及大小， 表中僅列出了Qj(x)中除 0 以外的所有單項式， 并且表中還列出了某些t3二進制循環(huán)碼的覆蓋多項式， 有關尋找這些覆蓋多項式的詳細討論， 請參閱文獻3、 4。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 表 6 - 3 某些二進制循環(huán)碼的覆蓋多項式 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 6.3 大數邏輯譯碼原理大數邏輯譯碼原理 循環(huán)碼譯碼器的復雜性主要決定于碼的代數結構。循環(huán)碼譯碼器的復雜性主要決定于碼的代數結構。 糾單個錯誤的漢明碼、糾單個錯誤的漢明碼、 糾單個突

42、發(fā)錯誤的循環(huán)碼，糾單個突發(fā)錯誤的循環(huán)碼， 以以及某些糾錯能力較低的碼，及某些糾錯能力較低的碼， 可以用以前所介紹的比較可以用以前所介紹的比較簡單的方法如捕錯譯碼。簡單的方法如捕錯譯碼。 但是，但是， 對絕大多數糾多個隨對絕大多數糾多個隨機錯誤的循環(huán)碼來說，機錯誤的循環(huán)碼來說， 卻沒有如此簡單的譯碼方法。卻沒有如此簡單的譯碼方法。 不過，不過， 有一類循環(huán)碼的子類，有一類循環(huán)碼的子類， 碼的結構比較特殊，碼的結構比較特殊， 可以用較簡單的大數邏輯方法譯碼，可以用較簡單的大數邏輯方法譯碼， 這類碼稱為大數這類碼稱為大數邏輯可譯碼。邏輯可譯碼。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 大數邏輯譯碼是大

43、數邏輯譯碼是 1954 年里德年里德(Re e d)， 在譯里德在譯里德-馬勒爾馬勒爾(Re e d-Mulle r ， RM)碼時提出的一種較簡單碼時提出的一種較簡單的譯碼方法的譯碼方法1， 2。 可是對于一般碼長而言，可是對于一般碼長而言， 能能用大數邏輯方法譯碼的大數邏輯可譯碼，用大數邏輯方法譯碼的大數邏輯可譯碼， 其糾錯能力其糾錯能力和碼率都稍次于有相同參數的其它碼如和碼率都稍次于有相同參數的其它碼如BCH碼，碼， 但由但由于它的譯碼算法和設備均比相應的于它的譯碼算法和設備均比相應的BCH碼譯碼方法要碼譯碼方法要簡單，簡單， 因此在實際中有較廣的應用。因此在實際中有較廣的應用。 第第6

44、章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 一、 大數邏輯譯碼的基本概念 通過以下例子介紹二進制循環(huán)碼的大數邏輯譯碼的基本思想。 7， 3， 4增余刪信漢明碼， 它的生成多項式g(x)=(x+1)(x3+x+1)=x4+x3+x2+1， 校驗矩陣是1000110010001100101110001101H第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 設接收的n重R=C+E， C=(c 6， c 5， ， c 0)是發(fā)送的碼字， E=(e 6， e 5， ， e 0)是錯誤圖樣。 相應的伴隨式01230561000110010001100101110001101sssseeeEHSTT第第6章章 循環(huán)碼的譯碼循環(huán)碼

45、的譯碼 對伴隨式的分量s0、 s1、 s2和s3進行線性組合， 也就是對H矩陣的行進行線性組合， 得到以下一組校驗方程： A1=s3 =e 6 +e 4+e 3 A2= s1 = e 6+e 5 +e 1 (6.3.1) A3= s2+s0= e 6+ +e 2 +e 0第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 顯然， 上述方程的系數所組成的 3 個七重數組： (1011000)， (1100010)和(1000101)是H行的線性組合， 在H的行空間中。 用A1、 A2和A3代表這 3 個七重， 則碼字C滿足： CAT1=CAT2=CAT3=0 或010100010100011000110100

46、56TCHccc(6.3.2) 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 可知: A1=c 6 +c 4+c 3 =0 A2= c 6+c 5 +c 1 =0 A3= c 6 +c 2 +c 0 =0 得到一組新的校驗方程。 它們有以下特點： c 6含在每一方程之中， c 5、 c 4、c 3、 c 2、 c 1和c 0只含在某一方程中。 有這種特點的校驗方程稱為正交于c 6(或x6、 e 6)碼元位的正交校驗方程(或正交一致校驗和式)， 由它們的系數所組成的矩陣H0， 稱為正交一致校驗矩陣。 所以， 由式(6.3.2)可得該碼的正交校驗矩陣第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 101000101

47、0001100011010H第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 定義 6.3.1 若某一特定碼元位(如xn-i)出現在H0矩陣中J行的每一行中， 而其它碼元位至多在其中一行出現， 則稱H0為正交于該碼元位(xn-i)的正交一致校驗矩陣。 7， 3， 4碼能糾正一個錯誤同時發(fā)現兩個錯誤， 由上面的H 0矩陣或式(6.3.2)可以發(fā)現： 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 (1) 發(fā)生一個錯誤， 且在正交碼元位上： e 6=1， 則可得A1=1， A2=1， A3=1。 (2) 發(fā)生一個錯誤但不在正交碼元位上： e 6=0， e i=1(i取5， 4， 3， 2， 1， 0中的某一個)， 則只

48、有一個Aj=1(j=1， 2， 3)， 其它兩個A均為0。 (3) 發(fā)生兩個錯誤， 其中一個在正交位上， 另一個在其它位(如e 5)： e 6=1， e 5=1， 則A1=1， A2=0， A3=1。 (4) 發(fā)生兩個錯誤， 都不在正交位上， 設e 5=1， e 4=1， 則A1=1， A2=1， A3=0。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 定理 6.3.1 一個循環(huán)碼若在任一位上能建立J個正交一致校驗和式， 則該碼能糾正tJ2個錯誤(式中， x表示取x的整數部分)。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 定義 6.3.2 如果某一碼元位置集合c i1， c i2， ， c il的線性組

49、合 ai1c i1+ai2c i2+ailc il 在A1， A2， ， AJ的一致校驗和式中均出現， 而其余碼元位置集合至多在其中一個校驗和式中出現， 則說A1， A2， ， AJ在集合c i1， c i2， ， c il上正交， 稱A1， A2， ， AJ是正交于該碼元位置集合的正交一致校驗和式， 上式中的aij是非0值。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 例如7， 4， 3循環(huán)漢明碼， g(x)=x3+x2+1。 它的校驗矩陣100111001001110011101H由S=EHT=(s2， s1， s0)得到： 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 A111=s2=(e 6+e 4

50、)+e 3+e 2 A112=s1=(e 6+e 4)+e 5+e 1 (6.3.4) A121=s1=(e 6+e 5)+e 4+e 1 A122=s2+s0=(e 6+e 5)+e 2+e 0 (6.3.5)第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 組成了J=2 組對(e6， e4)=E11和對(e6， e5)=E12碼元位置集合正交的正交一致校驗和式。 若碼組中僅出現一個錯誤， 則根據A111和A112中取值是 1 的個數多少， 正確譯得(e 6+e 4)=A11的值。 由A121和A122中取值是1的個數多少， 正確譯得(e6+e5)=A12的值。 然后再根據A11， A12中取值為 1

51、的個數， 譯出x6 碼元位是否錯誤。如x6碼元位發(fā)生了錯誤， e 6=1。 由式(6.3.4)和式(6.3.5)有： 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 A111=(e 6+e 4)+e 3+e 2=1 A112=(e 6+e 4)+e 5+e 1=1 A121=(e 6+e 5)+e 4+e 1=1 A122=(e 6+e 5)+e 2+e 0=1 可得： A11=(e 6+e 4)=1 A12=(e 6+e 5)=1 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 此兩方程正交于e6， 可以根據A11和A12中取1個數的多少， 決定出e 6的值。 這里A11=A12=1， 有兩個 1， 所以e 6

52、=1。 從該例看出， 為了譯出一個碼元需要進行兩次大數判決。 每次需要兩個正交校驗和式， 第一次是對碼元位置集合e 6， e 4和e 6， e 5正交， 第二次是對兩個碼元的位置集中的e6(x6)碼元位正交， 所以是兩步大數邏輯譯碼。 7， 4， 3循環(huán)漢明碼就稱為兩步大數邏輯可譯碼。 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 二、 大數邏輯譯碼器 大數邏輯譯碼器分為兩類： 型和型， 它們沒有本質上的不同。 下面先介紹一步大數邏輯譯碼器， 再介紹L步大數邏輯譯碼器。 1型大數邏輯譯碼器 以7， 3， 4碼的譯碼器為例， 說明這種類型的一步大數邏輯譯碼器的構成和工作過程。 由式(6.3.1)和式(6.3.2)可知： 第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 012345602133210101000101000110001101eeeeeeessssAAAEHT第第6章章 循環(huán)碼的譯碼循環(huán)碼的譯碼 圖 6 - 9 7， 3， 4碼型大數邏輯譯碼器 第第