信息論與編碼第八章糾錯編碼

信息論與編碼第八章糾錯編碼第一頁，共一百四十一頁，2022年，8月28日內(nèi)容提要一、糾錯碼的基本概念二、糾錯編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼第二頁，共一百四十一頁，2022年，8月28日內(nèi)容提要一、糾錯碼的基本概念二、糾錯編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼第三頁，共一百四十一頁，2022年，8月28日1.信道糾錯編碼一、糾錯碼的基本概念第四頁，共一百四十一頁，2022年，8月28日2.差錯控制系統(tǒng)模型及分類一、糾錯碼的基本概念第五頁，共一百四十一頁，2022年，8月28日2.差錯控制系統(tǒng)模型及分類一、糾錯碼的基本概念第六頁，共一百四十一頁，2022年，8月28日2.差錯控制系統(tǒng)模型及分類一、糾錯碼的基本概念第七頁，共一百四十一頁，2022年，8月28日2.差錯控制系統(tǒng)模型及分類一、糾錯碼的基本概念第八頁，共一百四十一頁，2022年，8月28日2.差錯控制系統(tǒng)模型及分類一、糾錯碼的基本概念第九頁，共一百四十一頁，2022年，8月28日3.差錯類型一、糾錯碼的基本概念第十頁，共一百四十一頁，2022年，8月28日3.差錯類型一、糾錯碼的基本概念第十一頁，共一百四十一頁，2022年，8月28日4.糾錯碼的分類一、糾錯碼的基本概念第十二頁，共一百四十一頁，2022年，8月28日4.糾錯碼的分類一、糾錯碼的基本概念第十三頁，共一百四十一頁，2022年，8月28日內(nèi)容提要一、糾錯碼的基本概念二、糾錯編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼第十四頁，共一百四十一頁，2022年，8月28日近世代數(shù)簡介近世代數(shù)又稱抽象代數(shù)，其研究對象是定義在某些運算下的集合，運算對象可以是數(shù)、多項式、矢量、矩陣、線性空間等。編碼理論是建立在碼的代數(shù)結(jié)構(gòu)基礎(chǔ)上的，為便于初學(xué)者理解，我們將簡單介紹抽象代數(shù)中與編碼直接相關(guān)的基礎(chǔ)知識，主要涉及整數(shù)及多項式的一些基本概念及群、環(huán)、域的基本知識。二、糾錯編碼的代數(shù)基礎(chǔ)第十五頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)整數(shù)的相關(guān)概念第十六頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)第十七頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)群的定義第十八頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)在實數(shù)加法下整數(shù)集是一個交換群。在這種情況下，整數(shù)0是單位元，整數(shù)-i是整數(shù)i的逆元。除去0的有理數(shù)集合在實數(shù)乘法下是交換群。整數(shù)1是關(guān)于實數(shù)乘法的單位元，有理數(shù)b/a是a/b的乘法逆元。第十九頁，共一百四十一頁，2022年，8月28日1.群這樣的二元運算稱為模2(modulo-2)加法。集合G={0,1}在模2加法下是一個群。由模2加法的定義，G在下是封閉的，同時滿足交換律、結(jié)合律。元素0是單位元，0的逆元是它本身，1的逆元也是它本身。這樣，定義了的G是一個交換群。二、糾錯編碼的代數(shù)基礎(chǔ)模2加第二十頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)第二十一頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)第二十二頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)第二十三頁，共一百四十一頁，2022年，8月28日1.群令p為一個素數(shù)(例如p=2,3,5,7,11,…)二、糾錯編碼的代數(shù)基礎(chǔ)模p乘易驗證模p乘法滿足交換律和結(jié)合律，其單位元是1。G中任何元素i關(guān)于模p乘法都有逆元。群G={1,2,3,…,p-1}在模p乘法下稱為乘群(multiplicationgroup)第二十四頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)模p乘第二十五頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)群的同構(gòu)第二十六頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)群的同構(gòu)第二十七頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)子群第二十八頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)子群第二十九頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)群的陪集第三十頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)群的陪集分解第三十一頁，共一百四十一頁，2022年，8月28日1.群二、糾錯編碼的代數(shù)基礎(chǔ)群的陪集分解第三十二頁，共一百四十一頁，2022年，8月28日2.域二、糾錯編碼的代數(shù)基礎(chǔ)域的定義第三十三頁，共一百四十一頁，2022年，8月28日2.域二、糾錯編碼的代數(shù)基礎(chǔ)群和域的區(qū)別需要指出群(G)與域(F)的區(qū)別：一個群只有規(guī)定的一種代數(shù)運算(加法或乘法)，而域是有兩種代數(shù)運算(加法和乘法)的代數(shù)系統(tǒng)。第三十四頁，共一百四十一頁，2022年，8月28日2.域二、糾錯編碼的代數(shù)基礎(chǔ)群和域的區(qū)別第三十五頁，共一百四十一頁，2022年，8月28日2.域二、糾錯編碼的代數(shù)基礎(chǔ)素數(shù)域G(p)第三十六頁，共一百四十一頁，2022年，8月28日2.域二、糾錯編碼的代數(shù)基礎(chǔ)素數(shù)域G(p)第三十七頁，共一百四十一頁，2022年，8月28日3.環(huán)二、糾錯編碼的代數(shù)基礎(chǔ)多項式的相關(guān)概念第三十八頁，共一百四十一頁，2022年，8月28日3.環(huán)二、糾錯編碼的代數(shù)基礎(chǔ)多項式的相關(guān)概念第三十九頁，共一百四十一頁，2022年，8月28日3.環(huán)二、糾錯編碼的代數(shù)基礎(chǔ)環(huán)的定義第四十頁，共一百四十一頁，2022年，8月28日3.環(huán)二、糾錯編碼的代數(shù)基礎(chǔ)整數(shù)剩余類環(huán)第四十一頁，共一百四十一頁，2022年，8月28日3.環(huán)二、糾錯編碼的代數(shù)基礎(chǔ)多項式剩余類環(huán)第四十二頁，共一百四十一頁，2022年，8月28日3.環(huán)二、糾錯編碼的代數(shù)基礎(chǔ)第四十三頁，共一百四十一頁，2022年，8月28日內(nèi)容提要一、糾錯碼的基本概念二、糾錯編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼第四十四頁，共一百四十一頁，2022年，8月28日1.分組碼相關(guān)定義三、線性分組碼假設(shè)信源信息是二進(jìn)制數(shù)字序列，將信道編碼器的輸出序列構(gòu)成長度為n的段，記為CC=[c1,c2,…,cn]

設(shè)有m個不同的信息序列，每個不同的序列由k(k<n)位相繼的信息數(shù)字組成。由于每個信息序列組成k位二進(jìn)制數(shù)字，則有2k個可能不同的信息序列，即m=2k，這2k個碼字的集合稱為(n,k)分組碼。(n,k)分組碼定義第四十五頁，共一百四十一頁，2022年，8月28日1.分組碼相關(guān)定義對于2k個n長碼字全體構(gòu)成的分組碼，其碼字中的k位稱為信息位，n-k位稱為校驗位或監(jiān)督位。例如，當(dāng)k=3，n=7時，可能的消息序列數(shù)m=2k=8個，可能的長為n=7的預(yù)選序列有27=128個。具體如表：對于所選定的n長序列稱為允許使用序列，即碼字；而其他序列則是不允許使用的，即禁用序列。該例中，信息位為3，碼長為7，監(jiān)督位為4，如果用R=k/n表示碼字中信息位所占比重，稱為編碼效率。表明了信道的利用率。三、線性分組碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100校驗位和信息位第四十六頁，共一百四十一頁，2022年，8月28日1.分組碼相關(guān)定義若(n,k)分組碼中k個信息位同原始k個信息位相同，且位于n長碼字的前(或后)k位，而校驗位位于其后(或前)，則稱該分組碼為系統(tǒng)碼，否則為非系統(tǒng)碼。右表所示為系統(tǒng)碼。三、線性分組碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100系統(tǒng)碼與非系統(tǒng)碼第四十七頁，共一百四十一頁，2022年，8月28日定義：[n,k]線性分組碼是GF(q)上的n維線性空間中的一個k維子空間。2k2n2.線性分組碼定義三、線性分組碼第四十八頁，共一百四十一頁，2022年，8月28日2.線性分組碼定義三、線性分組碼也可以這樣理解：n長碼字C=[c1,c2,…,cn]中每一位同原始的k個信息位d=[d1,d2,…dk]之間滿足一定的函數(shù)關(guān)系ci=f(d1,d2,…dk),(n=1,2,…,n)

若函數(shù)關(guān)系是線性的，則稱該分組碼為線性分組碼，否則為非線性分組碼。第四十九頁，共一百四十一頁，2022年，8月28日2.線性分組碼定義三、線性分組碼第五十頁，共一百四十一頁，2022年，8月28日2.線性分組碼定義三、線性分組碼第五十一頁，共一百四十一頁，2022年，8月28日2.線性分組碼定義三、線性分組碼第五十二頁，共一百四十一頁，2022年，8月28日容易驗證C是線性的。假設(shè)消息序列與碼字序列的映射關(guān)系為如下兩種：第一種：映射關(guān)系為：第二種：映射關(guān)系與第一種截然不同。第五十三頁，共一百四十一頁，2022年，8月28日三、線性分組碼2.線性分組碼定義第五十四頁，共一百四十一頁，2022年，8月28日三、線性分組碼3.線性分組碼編碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100第五十五頁，共一百四十一頁，2022年，8月28日三、線性分組碼3.線性分組碼編碼由校驗方程，可將n=7，k=3的線性分組碼寫成令則因此，C=mG且G=[IkPk*(n-k)]第五十六頁，共一百四十一頁，2022年，8月28日三、線性分組碼3.線性分組碼編碼令則因此，C=mG第五十七頁，共一百四十一頁，2022年，8月28日三、線性分組碼3.線性分組碼編碼第五十八頁，共一百四十一頁，2022年，8月28日三、線性分組碼3.線性分組碼編碼第五十九頁，共一百四十一頁，2022年，8月28日三、線性分組碼3.線性分組碼編碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100第六十頁，共一百四十一頁，2022年，8月28日三、線性分組碼3.線性分組碼編碼生成矩陣和校驗矩陣關(guān)系第六十一頁，共一百四十一頁，2022年，8月28日例題已知生成矩陣為求其校驗矩陣H，如果將H作為生成矩陣，則所生成的碼字是什么？由于G=[IkPk*(n-k)]則有又因為第六十二頁，共一百四十一頁，2022年，8月28日由生成矩陣生成的(7,3)碼為：mC00000000000010011101010010011101101110101001001110101101001111011010011111110100第六十三頁，共一百四十一頁，2022年，8月28日把校驗矩陣當(dāng)作生成矩陣，mC00000000000000100010110010001011000110011101010001001110101010110001100110001011101110101000100010110011001110101010100111011101100011001100010110111010011110111010011111111111產(chǎn)生(7,4)碼為：第六十四頁，共一百四十一頁，2022年，8月28日第六十五頁，共一百四十一頁，2022年，8月28日（n，k）線性分組碼編碼電路第六十六頁，共一百四十一頁，2022年，8月28日第六十七頁，共一百四十一頁，2022年，8月28日4.伴隨式與譯碼第六十八頁，共一百四十一頁，2022年，8月28日4.伴隨式與譯碼第六十九頁，共一百四十一頁，2022年，8月28日4.伴隨式與譯碼證明：根據(jù)線性分組碼的封閉性可知，任意兩個碼字的和應(yīng)為一個碼字。根據(jù)碼字之間距離的定義可知，兩個碼字和的非零個數(shù)則與其距離相等，且又為新碼字的重量。所以，不難理解，線性分組碼的最小距離必定等于非零碼字的最小重量。第七十頁，共一百四十一頁，2022年，8月28日4.伴隨式與譯碼第七十一頁，共一百四十一頁，2022年，8月28日線性分組碼的檢、糾錯能力與H矩陣的關(guān)系第七十二頁，共一百四十一頁，2022年，8月28日線性分組碼的檢、糾錯能力與H矩陣的關(guān)系

設(shè)C是線性分組碼，H是它的校驗矩陣，那么碼C的最小重量就等于H中線性相關(guān)的最小列數(shù)。因此，如果H中的2t個和小于2t個列的任一子集都線性無關(guān)，而H中有2t+1個列線性相關(guān)，那么碼C就是糾正t個錯誤的糾錯碼，或能檢出2t個錯誤的檢錯碼?！纠浚?，4）線性分組碼

H的前3列相加等于0，因此H線性相關(guān)的最小列數(shù)為3

故：wmin(C)=3

,能糾正1個錯誤或檢出2個錯誤第七十三頁，共一百四十一頁，2022年，8月28日第七十四頁，共一百四十一頁，2022年，8月28日第七十五頁，共一百四十一頁，2022年，8月28日第七十六頁，共一百四十一頁，2022年，8月28日第七十七頁，共一百四十一頁，2022年，8月28日第七十八頁，共一百四十一頁，2022年，8月28日例：某一個(5,2)系統(tǒng)線性碼的生成矩陣是設(shè)接收到碼字是r=(10101)，先構(gòu)造該碼的標(biāo)準(zhǔn)陣列譯碼表，然后譯出發(fā)碼的估值C。第七十九頁，共一百四十一頁，2022年，8月28日(1)信息組：m=(00),(10),(01),(11)(2)求得4個許用碼字C=mG為

C1=(00000),C2=(10111

),C3=(01101),C4=(11010)(3)求出校驗矩陣

第八十頁，共一百四十一頁，2022年，8月28日(4)求出伴隨式第八十一頁，共一百四十一頁，2022年，8月28日(5)標(biāo)準(zhǔn)陣列S1=000E1+C1=00000C2=10111C3=01101C4=11010S2=111E2=10000001111110101010S3=101E3=01000111110010110010S4=100E4=00100100110100111110S5=010E5=00010101010111111000S6=001E6=00001101100100111011S7=011E7=00011101000111011001S8=110E8=00110100010101111100選擇重量最小的n重作為陪集首S=EHT第八十二頁，共一百四十一頁，2022年，8月28日【例】（7，3）線性分組碼

能檢出3重錯誤，糾正1重錯誤。

第八十三頁，共一百四十一頁，2022年，8月28日如：（一個錯）如兩個錯：

，但無伴隨式與之對應(yīng)，不能糾正。

第八十四頁，共一百四十一頁，2022年，8月28日例已知（7，3）碼的校驗矩陣為第八十五頁，共一百四十一頁，2022年，8月28日若錯誤圖樣en=（0010000），則是H矩陣第三列！若錯誤圖樣中只有一個分量非零，則ST是H矩陣相應(yīng)的列，因而能夠糾正單個錯誤！第八十六頁，共一百四十一頁，2022年，8月28日若錯誤圖樣en=（0010100），則是H矩陣第三列與第五列之和！第八十七頁，共一百四十一頁，2022年，8月28日由定義可以求得，rn的伴隨式：是H矩陣第一列與第二列之和！若發(fā)生兩個錯誤，譯碼器只能判決傳輸有錯（en

≠0）,不能判定由哪幾位錯誤引起！第八十八頁，共一百四十一頁，2022年，8月28日一．基本概念漢明碼：一類能糾單個錯誤的糾錯碼。

二．糾單個錯誤的線性分組碼【例】（7，4）線性碼

5.漢明碼第八十九頁，共一百四十一頁，2022年，8月28日（1）H中列為非全零元素；

（2）H中任意兩列都不相同，但存在相加等于0的三個列的子集。

H中線性相關(guān)的最小列數(shù)為3，故，該碼是糾單個錯誤的碼。定理：C是一個線性分組碼，H是校驗矩陣，C是可以糾單個錯誤的糾錯碼的充要條件：（1）H中沒有元素全為0的列矢量；（2）H中任意兩個列矢量都不相同。第九十頁，共一百四十一頁，2022年，8月28日幾個結(jié)論：對于具有糾單個錯誤能力的線性分組碼。

（1）若接收矢量的伴隨式，則譯碼器認(rèn)為接收矢量沒有錯誤；

（2）如果，且等于H矩陣中的某一列，則譯碼器糾認(rèn)為接收矢量在該列對應(yīng)校驗矩陣中的位置出錯，此時只需將接收字該位置的碼元取反就能糾錯；（3）若，但不等于H中的任一列，則錯誤不能糾正?！纠?/p>

（1）第九十一頁，共一百四十一頁，2022年，8月28日伴隨式對應(yīng)于H中的第五列，故：

（2）H中無對應(yīng)列與之對應(yīng)，不能正確譯碼。第九十二頁，共一百四十一頁，2022年，8月28日結(jié)論：為了得到具有糾一個錯誤的二元（n，n-m）線性碼，（其中n-m=k，m為校驗位的個數(shù)），只需從定義在F2上的m維非零列矢量中選取彼此不同的n個列矢量并依任意次序把它們排成一個m×n的矩陣：那么以H為校驗矩陣的二元（n，n-m）線性碼C就是一個可以糾正所有單個錯誤的的碼。

三．漢明碼：1．定義：設(shè)Vm(F2)是定義在F2上的一個m維的矢量空間

令H是二元m×（2m-1）矩陣，這個矩陣的列是Vm（F2）中按某種次序排列的2m-1個非零矢量，那么定義在F2上的n=2m-1，k=2m-1-m的線性分組碼（校驗矩陣為H）就稱為長2m-1的漢明碼。

設(shè)消息或數(shù)據(jù)以二進(jìn)制形式表示，并以F2={0,1}表示這個二元集。第九十三頁，共一百四十一頁，2022年，8月28日如：

的（7，4）線性分組碼就是漢明碼

m=3，n=23-1=7，k=7-3=4

2．定理：二元（2m-1，2m-1-m）漢明碼是能夠糾單個錯誤的線性碼，而且是校驗位數(shù)為m的所有二元線性碼種編碼效率最高的碼，其最小重量：wmin（C）=3。

3．完備碼：設(shè)C是（n，k）線性分組碼，其糾錯能力為t，如果用且只用小于等于t個錯誤的全部錯誤圖樣作為陪集首就能做成標(biāo)準(zhǔn)陣列，那么稱這個碼為完備碼。

第九十四頁，共一百四十一頁，2022年，8月28日四.漢明碼的編譯碼電路框圖編碼器設(shè)計例(7,4)漢明碼

由，第九十五頁，共一百四十一頁，2022年，8月28日2.譯碼器設(shè)計令接收字為

伴隨式為

由校驗矩陣H，

令1101000000011010000011100100001010001000100000010001000000100010000001

第九十六頁，共一百四十一頁，2022年，8月28日漢明碼的譯碼電路框圖

第九十七頁，共一百四十一頁，2022年，8月28日內(nèi)容提要一、糾錯碼的基本概念二、糾錯編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼第九十八頁，共一百四十一頁，2022年，8月28日1.循環(huán)碼的定義定義一一個(n,k)線性分組碼，如果每個碼字經(jīng)任意循環(huán)移位之后仍然在碼字的集合中，那么就稱此碼是一個循環(huán)碼。定義二設(shè)是某(n,k)線性分組碼的碼字集合，如果對于任何，它的循環(huán)移位，則稱該碼為循環(huán)碼。這種循環(huán)性可以推廣到任意次循環(huán)移位，記作：第九十九頁，共一百四十一頁，2022年，8月28日【例】（7，3）線性分組碼由：得由兩組碼字循環(huán)構(gòu)成的循環(huán)碼。

第一百頁，共一百四十一頁，2022年，8月28日2.碼字的多項式描述對于任意個長度為n的碼字，可用下列多項式來描述：這里，把各碼元當(dāng)作多項式的系數(shù)；x及其冪次數(shù)僅是碼元位置的標(biāo)記，我們并不關(guān)心它的取值；稱系數(shù)不為零的x的最高次數(shù)為多項式A(x)的次數(shù)，或稱為多項式的階數(shù)。第一百零一頁，共一百四十一頁，2022年，8月28日第一百零二頁，共一百四十一頁，2022年，8月28日多項式的模運算示例第一百零三頁，共一百四十一頁，2022年，8月28日

如果A＝（an-1an-2

…a1a0）是（n，k）循環(huán)碼的一個碼字，則A(1)＝（an-2…a1a0an-1）也是該循環(huán)碼的一個碼字。這就是說A(x)＝an-1xn-1＋an-2xn-2＋…＋a1x＋a0

和A

(1)(x)＝an-2xn-1＋…＋a1x2＋a0x＋an-1都是（n，k）循環(huán)碼的碼字多項式。循環(huán)多項式的模運算比較A(x)和A(1)(x)后可得

A

(1)(x)＝xA(x),modxn+1以及A(i)(x)＝xiA(x)（i＝1,2,…,n－1）,modxn+1

第一百零四頁，共一百四十一頁，2022年，8月28日循環(huán)多項式的模運算定理：對于(n,k)循環(huán)碼，若A(x)對應(yīng)碼字，對應(yīng)A(x)的i次左循環(huán)移位，則等于除以后的余式，即：

第一百零五頁，共一百四十一頁，2022年，8月28日例題：設(shè)循環(huán)碼(7,4)中一個碼字為[00001101]，則該循環(huán)碼的所有碼字及其碼多項式如表所示。序號循環(huán)碼左移位數(shù)i00011010001101010110100211010003101000140100011510001106第一百零六頁，共一百四十一頁，2022年，8月28日3.生成多項式和生成矩陣生成多項式記為g(x),所有循環(huán)碼(n,k)的碼多項式A(x)可由g(x)生成，即A(x)=m(x)g(x),

式中，m(x)為消息多項式，它與消息位對應(yīng)。生成多項式g(x)性質(zhì)：循環(huán)碼(n,k)的生成多項式是xn+1的一個因子，且最高次數(shù)為n-k。證明：由于A(x)=m(x)g(x),而m(x)最高次數(shù)為k-1，A(x)最高次數(shù)為n-1，所以g(x)最高次數(shù)為(n-1)-(k-1)=n-k。例：求循環(huán)碼(7,4)的生成多項式g(x)解：將x7+1分解得

x7+1=(x+1)(x3+x+1)(x3+x2+1)，因為g(x)最高次數(shù)為n-k=3，所以，其生成多項式有兩種可能，即：x3+x+1或x3+x2+1第一百零七頁，共一百四十一頁，2022年，8月28日由生成多項式g(x)容易得到生成矩陣。生成矩陣的每一行必定為線性無關(guān)的，且每行都是一個碼字。g(x)為n-k階多項式，則g(x),xg(x),x2g(x),…,xk-1g(x)必是線性無關(guān)的，將此對應(yīng)的碼字作為矩陣的每一行，得到生成矩陣。與生成矩陣對應(yīng)的生成矩陣多項式G(x)可記作：3.生成多項式和生成矩陣第一百零八頁，共一百四十一頁，2022年，8月28日例題：已知循環(huán)碼(7,4)的生成多項式g(x)有兩種可能

x3+x+1或x3+x2+1，分別求其生成矩陣解：若生成多項式g(x)=x3+x+1,則生成矩陣多項式為：所對應(yīng)的生成矩陣為：第一百零九頁，共一百四十一頁，2022年，8月28日例題：已知循環(huán)碼(7,4)的生成多項式g(x)有兩種可能

x3+x+1或x3+x2+1，分別求其生成矩陣解：若生成多項式g(x)=x3+x2+1,則生成矩陣多項式為：所對應(yīng)的生成矩陣為：第一百一十頁，共一百四十一頁，2022年，8月28日例題：如果循環(huán)碼(7,4)的生成多項式g(x)=x3+x+1求對應(yīng)的所有碼字解：可得生成矩陣為第一百一十一頁，共一百四十一頁，2022年，8月28日16個碼字構(gòu)成4個循環(huán)組，前兩組分別7個碼字，后兩組為自循環(huán)的單獨碼字。可見，循環(huán)碼并不是只由一個碼字循環(huán)就可以得到全部碼字。第一百一十二頁，共一百四十一頁，2022年，8月28日將生成矩陣通過矩陣初等變換轉(zhuǎn)換成[IkPk*r]的形式，即可得到系統(tǒng)生成矩陣。3.生成多項式和生成矩陣生成多項式g(x)生成矩陣多項式G(x)生成矩陣G系統(tǒng)生成矩陣G’第一百一十三頁，共一百四十一頁，2022年，8月28日解：可以先得到兩個生成矩陣，后經(jīng)過矩陣初等變換得到系統(tǒng)生成矩陣?yán)}：已知循環(huán)碼(7,4)的生成多項式g(x)有兩種可能

x3+x+1或x3+x2+1，分別求其系統(tǒng)生成矩陣矩陣初等變換矩陣初等變換第一百一十四頁，共一百四十一頁，2022年，8月28日通過比較，可以發(fā)現(xiàn)，對于生成矩陣G1及系統(tǒng)生成矩陣G1’,最后所生成的碼字相同，唯一不同的是消息位與碼字的對應(yīng)關(guān)系不同。第一百一十五頁，共一百四十一頁，2022年，8月28日由生成多項式g(x)直接產(chǎn)生系統(tǒng)循環(huán)碼步驟：(1)將消息多項式m(x)乘以xn-k；(2)將xn-km(x)除以g(x)得到余式r(x)；(3)將r(x)加進(jìn)xn-km(x)，得到系統(tǒng)碼。第一百一十六頁，共一百四十一頁，2022年，8月28日解:(1)消息碼為[1101]，所以消息多項式為m(x)=x3+x2+1，則

xn-km(x)=x3m(x)=x6+x5+x3

(2)求余式

(3)求系統(tǒng)碼多項式

C(x)=xn-km(x)+r(x)=x6+x5+x3+1所以對應(yīng)的系統(tǒng)循環(huán)碼為[1101001]例題：如果循環(huán)碼(7,4)的生成多項式g(x)=x3+x+1，消息碼為[1101]，求對應(yīng)的系統(tǒng)循環(huán)碼第一百一十七頁，共一百四十一頁，2022年，8月28日4.校驗多項式和校驗矩陣第一百一十八頁，共一百四十一頁，2022年，8月28日4.校驗多項式和校驗矩陣第一百一十九頁，共一百四十一頁，2022年，8月28日4.校驗多項式和校驗矩陣第一百二十頁，共一百四十一頁，2022年，8月28日5.伴隨多項式和伴隨矩陣伴隨多項式S(x)與收到的碼多項式R(x)同余伴隨多項式S(x)與差錯圖樣多項式E(x)之間也存在一一對應(yīng)關(guān)系第一百二十一頁，共一百四十一頁，2022年，8月28日5.伴隨多項式和伴隨矩陣循環(huán)碼譯碼步驟(1)利用，建立差錯圖樣多項式E(x)和伴隨多項式S(x)之間的映射表；(2)收到R(x)后，利用得到某個S(x)，然后利用步驟(1)中建立的映射表，即可查到所對應(yīng)的差錯多項式E(x);(3)將差錯多項式E(x)與R(x)相加，即可得到經(jīng)過糾錯的C(x)。第一百二十二頁，共一百四十一頁，2022年，8月28日解，由得到例題：如果循環(huán)碼(7,4)的生成多項式g(x)=x3+x+1，確定差錯圖樣多項式與伴隨多項式的映射表差錯圖樣多項式E(x)伴隨多項式S(x)0011xxx2x2x3x+1x4x2+xx5x2+x+1x6x2+1第一百二十三頁，共一百四十一頁，2022年，8月28日若已知伴隨多項式S(x)，可以容易求得對應(yīng)的伴隨矩陣S。例如，S(x)=x2+x+1,則伴隨矩陣S=[111]當(dāng)然，由于循環(huán)碼是線性分組碼的子類，所以，伴隨矩陣仍可以由S=RHT求得。5.伴隨多項式和伴隨矩陣第一百二十四頁，共一百四十一頁，2022年，8月28日6.BCH碼和RS碼BCH碼是循環(huán)碼中的一個大類，分為二進(jìn)制BCH碼和非二進(jìn)制BCH碼(例如RS碼)。二進(jìn)制BCH碼可記為(2m-1,k)，其中m為正整數(shù)且，即碼長n=2m-1，且(t為可糾正的差錯數(shù))，t由最小碼距決定，即二進(jìn)制BCH碼的優(yōu)點是，具有糾正多個隨機(jī)差錯的能力。具有嚴(yán)謹(jǐn)?shù)拇鷶?shù)結(jié)構(gòu)，可以按照碼長n和糾錯能力t直接將BCH碼構(gòu)造出來。該特點優(yōu)于一般線性分組碼，一般線性分組碼在設(shè)計出來之后，需要計算最小距離dmin，才能知道糾錯能力。若不符合要求，還要重復(fù)設(shè)計過程。第一百二十五頁，共一百四十一頁，2022年，8月28日6.BCH碼和RS碼確定BCH碼的生成多項式g(x)，取決于兩方面：(1)g(x)是xn+1因式中最高階為n-k的多項式，這是任何循環(huán)碼都必須滿足的條件。由于BCH碼的碼長n=2m-1，，所以其碼長的取值只能是7,15,31,63,127,255,…當(dāng)n較大時，xn+1的因式分解就只能用計算機(jī)來計算。(2)g(x)必須滿足對糾錯能力t的要求，即對最小碼距的要求。實際應(yīng)用中，將滿足上述兩個條件的系數(shù)整理成“BCH碼生成多項式系數(shù)”表，以便查用。第一百二十六頁，共一百四十一頁，2022年，8月28日例題：求碼長為15且能糾正3個差錯的BCH碼解：碼長n=2m-1=15，所以m=4；糾錯能力t=3；將x15+1因式分解后，得x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)

查前述的“BCH碼生成多項式系數(shù)”表，可得滿足條件的BCH碼為(15,5)，其相應(yīng)的生成多項式的最高階為n-k=10，則生成多項式為

g(x)=(x2+x+1)(x4+x+1)(x4+x3+x2+x+1)=x10+x8+x5+x4+x2+x+1第一百二十七頁，共一百四十一頁，2022年，8月28日6.BCH碼和RS碼RS(Reed-Solomn)碼是一種非二進(jìn)制BCH碼。RS碼是極大最小距離碼(MDC碼)。若某個碼的最小距離dmin=n-k+1，則稱線性分組碼(n,k)為極大最小距離碼。在(n,k)線性分組碼中，極大最小距離碼具有最大的檢錯、糾錯能力。由于RS碼是多進(jìn)制，所以很容易與M進(jìn)制調(diào)制技術(shù)相匹配；RS碼特別適合糾正突發(fā)錯誤。第一百二十八頁，共一百四十一頁，2022年，8月28日內(nèi)容提要一、糾錯碼的基本概念二、糾錯編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼第一百二十九頁，共一百四十一頁，2022年，8月28日卷積碼與線性分組碼的比較卷積碼線性分組碼表示符號(n,k,K)，K為約束長度(n,k)記憶性有記憶，輸出的n個比特不僅與當(dāng)前輸入的k比特有關(guān)，而且與以前輸入的K個k比特有關(guān)無記憶，輸出的n個比特僅與當(dāng)前輸入的k個比特有關(guān)(可視為K=0時的無記憶卷積碼)代數(shù)結(jié)構(gòu)無嚴(yán)格的代數(shù)結(jié)構(gòu)，目前多采用計算機(jī)來搜索好碼，缺乏有效的數(shù)學(xué)分析工具有嚴(yán)格的代數(shù)結(jié)構(gòu)，借用數(shù)學(xué)工具研究較為透徹編碼效率kk…kn…輸入k位當(dāng)前時間以前K個時間輸入n位kn輸入k位輸入n位卷積碼線性分組碼第一百三十頁，共一百四十一頁，2022年，8月28日1.卷積碼的組織結(jié)構(gòu)卷積碼(n,k,K)與線性分組碼(n,k)的重要區(qū)別在于，卷積碼是有記憶的，并用約束長度表示記憶長度，記為K。輸出的n位比特不僅與當(dāng)前時間輸入的k比特有關(guān)，還與以前時間輸入的多個k比特有關(guān)，到底與以前多長時間有關(guān)，就由約束長度K來度量。卷積碼可以視為多個線性分組碼的線性疊加，只不過多個線性分組碼是來源于同一個輸入源的多個不同時間段(包括當(dāng)前時間段和K個以前時間段)。顯然，當(dāng)K=0時，卷積碼就退化為線性分組碼。第一百三十一頁，共一百四十一頁，2022年，8月28日例題：設(shè)卷積碼(2,1,2)，其組織結(jié)構(gòu)如圖(a)所示，假設(shè)輸入序列為[1011]，通過求輸出序列，來說明卷積碼編碼的全過程10011010011011011010011000010100000(a)(b)(c)(d)(e)(f)(g)從(a)到(d)依次輸入[1011]，從(e)到(f)是為了清空K段緩存器，所以需要在輸入序列后加K段0比特，稱為“結(jié)尾清空處理”過程。另外，(g)中又輸入0的目的是說明該時刻已完成“結(jié)尾清空處理”，即在該時刻可以輸入新的消息。第一百三十二頁，共一百四十一頁，2022年，8月28日由上例中看到，當(dāng)輸入[1011]時，輸出為110110100001，因此，該卷積碼的編碼效率為：對L段輸入消息