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

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

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

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

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ù)項(xiàng)（或最高項(xiàng)）非零的可糾錯(cuò)誤圖案E(x)組成一個(gè)集合，計(jì)算它們的伴隨式，構(gòu)成一張表。譯碼時(shí)，先計(jì)算出S(x)，然后對(duì)其做0, 1, , n-1次模g(x)移位，得到Sj(x)。比較Sj(x)是否在可譯表中，若在，則得到循環(huán)移位j次后的錯(cuò)誤圖案。9運(yùn)算量分析糾t個(gè)錯(cuò)的(n,k)線(xiàn)性分組碼譯碼所需錯(cuò)誤圖案表大小為 ，而糾t個(gè)錯(cuò)的(n,k)循環(huán)碼譯碼所需

5、錯(cuò)誤圖案表大小為 ，10循環(huán)碼伴隨式譯碼舉例糾一個(gè)錯(cuò)的循環(huán)碼：漢明碼共有n種可糾的錯(cuò)誤圖案，而它們都是000001（伴隨式為S0(x)）的循環(huán)移位。因此它們可以歸為一類(lèi)，即對(duì)計(jì)算出的S(x)做0n-1次模g(x)移位，直到出現(xiàn)S0(x)為止，將R(x)做相應(yīng)次移位后最后一位反轉(zhuǎn)，再做剩余的移位，即得到正確的譯碼結(jié)果。可見(jiàn)伴隨式表可以大大縮小。11循環(huán)碼的捕錯(cuò)譯碼依據(jù)：能糾t個(gè)錯(cuò)的GF(q)上的(n,k)循環(huán)碼，不多于t個(gè)錯(cuò)誤全在最低的n-k位中的充要條件是w(S(x) t。證明：若這些錯(cuò)不全落在低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捕錯(cuò)譯碼算法與條件算法：根據(jù)上面的分析，可實(shí)現(xiàn)捕錯(cuò)譯碼。即S(x)做j次模g(x)移位后，如果重量不大于t則此時(shí)的Sj(x)就是R(x)循環(huán)移位j次的錯(cuò)誤圖案。條件：t個(gè)錯(cuò)誤均勻分布時(shí)仍要保證其空隙長(zhǎng)度不小于k。因此有kn/t，即編碼效率R=k/n1/t。捕錯(cuò)譯碼的修正：略，見(jiàn)參考書(shū)。13大數(shù)邏輯譯碼正交一致校驗(yàn)矩陣：若某一特定碼元位（如xn-1）出現(xiàn)在H0矩陣中J行的每一行中，而其它碼元位至多在其中一行出現(xiàn)，則稱(chēng)H0為正交于該碼元位(xn-1)的正交一致校驗(yàn)矩陣。正交一致校驗(yàn)和式：正交一臻校驗(yàn)矩陣中的各校驗(yàn)方程。14糾錯(cuò)能力與正交一致校驗(yàn)矩

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