第六講——循環(huán)碼譯碼

1、第六講循環(huán)碼的譯碼1譯碼的基本準則最小錯誤概率min PE = min P(CC|R)最大后驗概率：max P(C=C|R)C 取maxi P(Ci|R) 的最大值時的Ci最大似然：max P(R| C=C)C 取maxi P(R|Ci) 的最大值時的Ci，當發(fā)送碼字等概時，最大后驗概率準則與最大似然準則等價P(Ci|R)=P(Ci) P(R|Ci)/P(R)。其中的P(Ci)為發(fā)送碼字Ci的先驗概率。2譯碼方法分類按處理方法分類時域譯碼，直接根據(jù)序列的前后關系進行譯碼變換域譯碼，將序列進行某些變換如FFT等再行譯碼時域處理中，又可分為代數(shù)譯碼：利用碼的代數(shù)結(jié)構(gòu)的譯碼概率譯碼：不僅利用碼的代數(shù)

2、結(jié)構(gòu)，還利用信道統(tǒng)計特性的譯碼3循環(huán)碼的代數(shù)譯碼適用情況：非時變對稱DMC，接收符號集與發(fā)送符號集相同，且各發(fā)送符號在接收符號集中有一個最大似然的對應符號，不妨令此符號即為發(fā)送符號。依據(jù)：最大似然譯碼準則4時非變對稱DMC中的最大似然準則對接收矢量R，和一個可能的許用碼矢量C，它們的相應的似然值為iP(ri|ci)，這里用到了信道的無記性，再利用非時變性和對稱性得Pcm(1-Pc)/(M-1)n，其中m為序列中ri=ci的符號個數(shù)，n為序列中rici的符號個數(shù)，M為符號集大?。淮送飧鶕?jù)最大似然準則且在信道容量不為0的情況下，有Pc (1-Pc)/(M-1)。因此有最小差錯概率的序列與R的漢明距

3、離最小。5最小漢明距離準則在非時變對稱DMC信道中，最小漢明距離準則與最大似然準則等價，此時如果再有發(fā)送碼字等概的假設，則最小漢明距離就是最小序列（或碼字）差錯概率譯碼準則注意：最小漢明距離準則的適用條件，信道特性中的離散、無記憶、非時變和對稱，發(fā)送碼字等概這幾個條件缺一不可。6循環(huán)碼的一般譯碼方法對收到的R(x)=C(x)+E(x)，找到最可能發(fā)生的錯誤圖案E(x)根據(jù)接收多項式R(x)計算伴隨式S(x)計算錯誤圖案 ，即形成伴隨式S(x)的最輕圖案 7伴隨式的循環(huán)移位令S(x)為R(x)的伴隨式，則R(x)的循環(huán)移位xR(x) mod xn-1的伴隨式S1(x)是S(x)的模g(x)移位運

4、算的結(jié)果：S1(x)=xS(x) mod g(x)因此有：xjR(x) mod xn-1 = Sj(x)=xjS(x) mod g(x)；a(x)R(x) mod xn-1 = Sa(x)=a(x)S(x) mod g(x)8循環(huán)碼的伴隨式譯碼將常數(shù)項（或最高項）非零的可糾錯誤圖案E(x)組成一個集合，計算它們的伴隨式，構(gòu)成一張表。譯碼時，先計算出S(x)，然后對其做0, 1, , n-1次模g(x)移位，得到Sj(x)。比較Sj(x)是否在可譯表中，若在，則得到循環(huán)移位j次后的錯誤圖案。9運算量分析糾t個錯的(n,k)線性分組碼譯碼所需錯誤圖案表大小為 ，而糾t個錯的(n,k)循環(huán)碼譯碼所需

5、錯誤圖案表大小為 ，10循環(huán)碼伴隨式譯碼舉例糾一個錯的循環(huán)碼：漢明碼共有n種可糾的錯誤圖案，而它們都是000001（伴隨式為S0(x)）的循環(huán)移位。因此它們可以歸為一類，即對計算出的S(x)做0n-1次模g(x)移位，直到出現(xiàn)S0(x)為止，將R(x)做相應次移位后最后一位反轉(zhuǎn)，再做剩余的移位，即得到正確的譯碼結(jié)果。可見伴隨式表可以大大縮小。11循環(huán)碼的捕錯譯碼依據(jù)：能糾t個錯的GF(q)上的(n,k)循環(huán)碼，不多于t個錯誤全在最低的n-k位中的充要條件是w(S(x) t。證明：若這些錯不全落在低n-k位中，則E(x)-S(x)0，其重量d=2t+1，則w(E(x) + w(-S(x) d，而

6、w(E(x) t，= w(S(x) t + 1。12捕錯譯碼算法與條件算法：根據(jù)上面的分析，可實現(xiàn)捕錯譯碼。即S(x)做j次模g(x)移位后，如果重量不大于t則此時的Sj(x)就是R(x)循環(huán)移位j次的錯誤圖案。條件：t個錯誤均勻分布時仍要保證其空隙長度不小于k。因此有kn/t，即編碼效率R=k/n1/t。捕錯譯碼的修正：略，見參考書。13大數(shù)邏輯譯碼正交一致校驗矩陣：若某一特定碼元位（如xn-1）出現(xiàn)在H0矩陣中J行的每一行中，而其它碼元位至多在其中一行出現(xiàn)，則稱H0為正交于該碼元位(xn-1)的正交一致校驗矩陣。正交一致校驗和式：正交一臻校驗矩陣中的各校驗方程。14糾錯能力與正交一致校驗矩

7、陣的關系一個線性分組碼若在任一位上都能建立J個正交一致校驗和式，則該碼能糾正tJ/2個錯誤。大數(shù)邏輯譯碼：當要判斷第I位碼元處是否發(fā)生錯誤時，可以根據(jù)J個該位的正交一致校驗和式為0的個數(shù)來判斷，如果為不為0的個數(shù)大于J/2時則該位有錯，否則該位正確。15大數(shù)邏輯譯碼對循環(huán)碼而言，只需要對任一特定位建立正交一致校驗和式即可，在判斷其它位是否正確時，可以通過移位的方式來實現(xiàn)。大數(shù)邏輯可譯碼：可以采用大數(shù)邏輯譯碼的碼。顯然，是否能構(gòu)成J個一致校驗和式是關鍵。一步大數(shù)邏輯可譯碼和L步大數(shù)邏輯可譯碼。16BCH碼的譯碼出發(fā)點：BCH碼是一種構(gòu)造性較好的碼，可以較容易地得到較大的n, k, 和t。在伴隨式譯碼的三步曲中，最關鍵的是第二步：即根據(jù)S(x)找錯誤圖案E(x)。當k和n-k都很大時，以上算法復雜度都很高，需要找到更有效的方法。17伴隨式譯碼的進一步分解將第二步“計算錯誤圖案”分成兩步：確定錯誤位置確定在各錯誤位置上的錯誤值對于二進制碼而言，第2步可以省略。18錯誤位置多項式在找錯誤位置時，位置可由該BCH碼的本原元（或生成元）的冪次表示，即 ，li是第i個錯誤的位置。則找到各xi即可。而各xi為方程