信息論與編碼第八章 糾錯(cuò)編碼

第八章糾錯(cuò)編碼白慧慧辦公地址：9號(hào)教學(xué)樓北605Email:hhbai@手機(jī)容提要一、糾錯(cuò)碼的基本概念二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼內(nèi)容提要一、糾錯(cuò)碼的基本概念二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼1.信道糾錯(cuò)編碼一、糾錯(cuò)碼的基本概念2.差錯(cuò)控制系統(tǒng)模型及分類一、糾錯(cuò)碼的基本概念2.差錯(cuò)控制系統(tǒng)模型及分類一、糾錯(cuò)碼的基本概念2.差錯(cuò)控制系統(tǒng)模型及分類一、糾錯(cuò)碼的基本概念2.差錯(cuò)控制系統(tǒng)模型及分類一、糾錯(cuò)碼的基本概念2.差錯(cuò)控制系統(tǒng)模型及分類一、糾錯(cuò)碼的基本概念3.差錯(cuò)類型一、糾錯(cuò)碼的基本概念3.差錯(cuò)類型一、糾錯(cuò)碼的基本概念4.糾錯(cuò)碼的分類一、糾錯(cuò)碼的基本概念4.糾錯(cuò)碼的分類一、糾錯(cuò)碼的基本概念內(nèi)容提要一、糾錯(cuò)碼的基本概念二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼近世代數(shù)簡(jiǎn)介近世代數(shù)又稱抽象代數(shù)，其研究對(duì)象是定義在某些運(yùn)算下的集合，運(yùn)算對(duì)象可以是數(shù)、多項(xiàng)式、矢量、矩陣、線性空間等。編碼理論是建立在碼的代數(shù)結(jié)構(gòu)基礎(chǔ)上的，為便于初學(xué)者理解，我們將簡(jiǎn)單介紹抽象代數(shù)中與編碼直接相關(guān)的基礎(chǔ)知識(shí)，主要涉及整數(shù)及多項(xiàng)式的一些基本概念及群、環(huán)、域的基本知識(shí)。二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)整數(shù)的相關(guān)概念1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的定義1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)在實(shí)數(shù)加法下整數(shù)集是一個(gè)交換群。在這種情況下，整數(shù)0是單位元，整數(shù)-i是整數(shù)i的逆元。除去0的有理數(shù)集合在實(shí)數(shù)乘法下是交換群。整數(shù)1是關(guān)于實(shí)數(shù)乘法的單位元，有理數(shù)b/a是a/b的乘法逆元。1.群這樣的二元運(yùn)算稱為模2(modulo-2)加法。集合G={0,1}在模2加法下是一個(gè)群。由模2加法的定義，G在下是封閉的，同時(shí)滿足交換律、結(jié)合律。元素0是單位元，0的逆元是它本身，1的逆元也是它本身。這樣，定義了的G是一個(gè)交換群。二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)模2加1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)1.群令p為一個(gè)素?cái)?shù)(例如p=2,3,5,7,11,…)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)模p乘易驗(yàn)證模p乘法滿足交換律和結(jié)合律，其單位元是1。G中任何元素i關(guān)于模p乘法都有逆元。群G={1,2,3,…,p-1}在模p乘法下稱為乘群(multiplicationgroup)1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)模p乘1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的同構(gòu)1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的同構(gòu)1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)子群1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)子群1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的陪集1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的陪集分解1.群二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群的陪集分解2.域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)域的定義2.域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群和域的區(qū)別需要指出群(G)與域(F)的區(qū)別：一個(gè)群只有規(guī)定的一種代數(shù)運(yùn)算(加法或乘法)，而域是有兩種代數(shù)運(yùn)算(加法和乘法)的代數(shù)系統(tǒng)。2.域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)群和域的區(qū)別2.域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)素?cái)?shù)域G(p)2.域二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)素?cái)?shù)域G(p)3.環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)多項(xiàng)式的相關(guān)概念3.環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)多項(xiàng)式的相關(guān)概念3.環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)環(huán)的定義3.環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)整數(shù)剩余類環(huán)3.環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)多項(xiàng)式剩余類環(huán)3.環(huán)二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)內(nèi)容提要一、糾錯(cuò)碼的基本概念二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼1.分組碼相關(guān)定義三、線性分組碼假設(shè)信源信息是二進(jìn)制數(shù)字序列，將信道編碼器的輸出序列構(gòu)成長(zhǎng)度為n的段，記為CC=[c1,c2,…,cn]設(shè)有m個(gè)不同的信息序列，每個(gè)不同的序列由k(k<n)位相繼的信息數(shù)字組成。由于每個(gè)信息序列組成k位二進(jìn)制數(shù)字，則有2k個(gè)可能不同的信息序列，即m=2k，這2k個(gè)碼字的集合稱為(n,k)分組碼。(n,k)分組碼定義1.分組碼相關(guān)定義對(duì)于2k個(gè)n長(zhǎng)碼字全體構(gòu)成的分組碼，其碼字中的k位稱為信息位，n-k位稱為校驗(yàn)位或監(jiān)督位。例如，當(dāng)k=3，n=7時(shí)，可能的消息序列數(shù)m=2k=8個(gè)，可能的長(zhǎng)為n=7的預(yù)選序列有27=128個(gè)。具體如表：對(duì)于所選定的n長(zhǎng)序列稱為允許使用序列，即碼字；而其他序列則是不允許使用的，即禁用序列。該例中，信息位為3，碼長(zhǎng)為7，監(jiān)督位為4，如果用R=k/n表示碼字中信息位所占比重，稱為編碼效率。表明了信道的利用率。三、線性分組碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100校驗(yàn)位和信息位1.分組碼相關(guān)定義若(n,k)分組碼中k個(gè)信息位同原始k個(gè)信息位相同，且位于n長(zhǎng)碼字的前(或后)k位，而校驗(yàn)位位于其后(或前)，則稱該分組碼為系統(tǒng)碼，否則為非系統(tǒng)碼。右表所示為系統(tǒng)碼。三、線性分組碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100系統(tǒng)碼與非系統(tǒng)碼定義：[n,k]線性分組碼是GF(q)上的n維線性空間中的一個(gè)k維子空間。2k2n2.線性分組碼定義三、線性分組碼2.線性分組碼定義三、線性分組碼也可以這樣理解：n長(zhǎng)碼字C=[c1,c2,…,cn]中每一位同原始的k個(gè)信息位d=[d1,d2,…dk]之間滿足一定的函數(shù)關(guān)系ci=f(d1,d2,…dk),(n=1,2,…,n)若函數(shù)關(guān)系是線性的，則稱該分組碼為線性分組碼，否則為非線性分組碼。2.線性分組碼定義三、線性分組碼2.線性分組碼定義三、線性分組碼2.線性分組碼定義三、線性分組碼容易驗(yàn)證C是線性的。假設(shè)消息序列與碼字序列的映射關(guān)系為如下兩種：第一種：映射關(guān)系為：第二種：映射關(guān)系與第一種截然不同。三、線性分組碼2.線性分組碼定義三、線性分組碼3.線性分組碼編碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100三、線性分組碼3.線性分組碼編碼由校驗(yàn)方程，可將n=7，k=3的線性分組碼寫成令則因此，C=mG且G=[IkPk*(n-k)]三、線性分組碼3.線性分組碼編碼令則因此，C=mG三、線性分組碼3.線性分組碼編碼三、線性分組碼3.線性分組碼編碼三、線性分組碼3.線性分組碼編碼消息序列碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100三、線性分組碼3.線性分組碼編碼生成矩陣和校驗(yàn)矩陣關(guān)系例題已知生成矩陣為求其校驗(yàn)矩陣H，如果將H作為生成矩陣，則所生成的碼字是什么？由于G=[IkPk*(n-k)]則有又因?yàn)橛缮删仃嚿傻?7,3)碼為：mC00000000000010011101010010011101101110101001001110101101001111011010011111110100把校驗(yàn)矩陣當(dāng)作生成矩陣，mC00000000000000100010110010001011000110011101010001001110101010110001100110001011101110101000100010110011001110101010100111011101100011001100010110111010011110111010011111111111產(chǎn)生(7,4)碼為：（n，k）線性分組碼編碼電路4.伴隨式與譯碼4.伴隨式與譯碼4.伴隨式與譯碼證明：根據(jù)線性分組碼的封閉性可知，任意兩個(gè)碼字的和應(yīng)為一個(gè)碼字。根據(jù)碼字之間距離的定義可知，兩個(gè)碼字和的非零個(gè)數(shù)則與其距離相等，且又為新碼字的重量。所以，不難理解，線性分組碼的最小距離必定等于非零碼字的最小重量。4.伴隨式與譯碼線性分組碼的檢、糾錯(cuò)能力與H矩陣的關(guān)系線性分組碼的檢、糾錯(cuò)能力與H矩陣的關(guān)系設(shè)C是線性分組碼，H是它的校驗(yàn)矩陣，那么碼C的最小重量就等于H中線性相關(guān)的最小列數(shù)。因此，如果H中的2t個(gè)和小于2t個(gè)列的任一子集都線性無關(guān)，而H中有2t+1個(gè)列線性相關(guān)，那么碼C就是糾正t個(gè)錯(cuò)誤的糾錯(cuò)碼，或能檢出2t個(gè)錯(cuò)誤的檢錯(cuò)碼?！纠浚?，4）線性分組碼

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

故：wmin(C)=3

,能糾正1個(gè)錯(cuò)誤或檢出2個(gè)錯(cuò)誤例：某一個(gè)(5,2)系統(tǒng)線性碼的生成矩陣是設(shè)接收到碼字是r=(10101)，先構(gòu)造該碼的標(biāo)準(zhǔn)陣列譯碼表，然后譯出發(fā)碼的估值C。(1)信息組：m=(00),(10),(01),(11)(2)求得4個(gè)許用碼字C=mG為C1=(00000),C2=(10111

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

(4)求出伴隨式(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【例】（7，3）線性分組碼

能檢出3重錯(cuò)誤，糾正1重錯(cuò)誤。

如：（一個(gè)錯(cuò)）如兩個(gè)錯(cuò)：

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

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

≠0）,不能判定由哪幾位錯(cuò)誤引起！一．基本概念漢明碼：一類能糾單個(gè)錯(cuò)誤的糾錯(cuò)碼。

二．糾單個(gè)錯(cuò)誤的線性分組碼【例】（7，4）線性碼

5.漢明碼（1）H中列為非全零元素；

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

H中線性相關(guān)的最小列數(shù)為3，故，該碼是糾單個(gè)錯(cuò)誤的碼。定理：C是一個(gè)線性分組碼，H是校驗(yàn)矩陣，C是可以糾單個(gè)錯(cuò)誤的糾錯(cuò)碼的充要條件：（1）H中沒有元素全為0的列矢量；（2）H中任意兩個(gè)列矢量都不相同。幾個(gè)結(jié)論：對(duì)于具有糾單個(gè)錯(cuò)誤能力的線性分組碼。

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

（2）如果，且等于H矩陣中的某一列，則譯碼器糾認(rèn)為接收矢量在該列對(duì)應(yīng)校驗(yàn)矩陣中的位置出錯(cuò)，此時(shí)只需將接收字該位置的碼元取反就能糾錯(cuò)；（3）若，但不等于H中的任一列，則錯(cuò)誤不能糾正。【例】

（1）伴隨式對(duì)應(yīng)于H中的第五列，故：

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

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

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

設(shè)消息或數(shù)據(jù)以二進(jìn)制形式表示，并以F2={0,1}表示這個(gè)二元集。如：

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

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

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

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

四.漢明碼的編譯碼電路框圖編碼器設(shè)計(jì)例(7,4)漢明碼

由，2.譯碼器設(shè)計(jì)令接收字為

伴隨式為

由校驗(yàn)矩陣H，

令1101000000011010000011100100001010001000100000010001000000100010000001

漢明碼的譯碼電路框圖

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

2.碼字的多項(xiàng)式描述對(duì)于任意個(gè)長(zhǎng)度為n的碼字，可用下列多項(xiàng)式來描述：這里，把各碼元當(dāng)作多項(xiàng)式的系數(shù)；x及其冪次數(shù)僅是碼元位置的標(biāo)記，我們并不關(guān)心它的取值；稱系數(shù)不為零的x的最高次數(shù)為多項(xiàng)式A(x)的次數(shù)，或稱為多項(xiàng)式的階數(shù)。多項(xiàng)式的模運(yùn)算示例如果A＝（an-1an-2

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

(1)(x)＝an-2xn-1＋…＋a1x2＋a0x＋an-1都是（n，k）循環(huán)碼的碼字多項(xiàng)式。循環(huán)多項(xiàng)式的模運(yù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

循環(huán)多項(xiàng)式的模運(yùn)算定理：對(duì)于(n,k)循環(huán)碼，若A(x)對(duì)應(yīng)碼字，對(duì)應(yīng)A(x)的i次左循環(huán)移位，則等于除以后的余式，即：

例題：設(shè)循環(huán)碼(7,4)中一個(gè)碼字為[00001101]，則該循環(huán)碼的所有碼字及其碼多項(xiàng)式如表所示。序號(hào)循環(huán)碼左移位數(shù)i000110100011010101101002110100031010001401000115100011063.生成多項(xiàng)式和生成矩陣生成多項(xiàng)式記為g(x),所有循環(huán)碼(n,k)的碼多項(xiàng)式A(x)可由g(x)生成，即A(x)=m(x)g(x),式中，m(x)為消息多項(xiàng)式，它與消息位對(duì)應(yīng)。生成多項(xiàng)式g(x)性質(zhì)：循環(huán)碼(n,k)的生成多項(xiàng)式是xn+1的一個(gè)因子，且最高次數(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)的生成多項(xiàng)式g(x)解：將x7+1分解得x7+1=(x+1)(x3+x+1)(x3+x2+1)，因?yàn)間(x)最高次數(shù)為n-k=3，所以，其生成多項(xiàng)式有兩種可能，即：x3+x+1或x3+x2+1由生成多項(xiàng)式g(x)容易得到生成矩陣。生成矩陣的每一行必定為線性無關(guān)的，且每行都是一個(gè)碼字。g(x)為n-k階多項(xiàng)式，則g(x),xg(x),x2g(x),…,xk-1g(x)必是線性無關(guān)的，將此對(duì)應(yīng)的碼字作為矩陣的每一行，得到生成矩陣。與生成矩陣對(duì)應(yīng)的生成矩陣多項(xiàng)式G(x)可記作：3.生成多項(xiàng)式和生成矩陣?yán)}：已知循環(huán)碼(7,4)的生成多項(xiàng)式g(x)有兩種可能

x3+x+1或x3+x2+1，分別求其生成矩陣解：若生成多項(xiàng)式g(x)=x3+x+1,則生成矩陣多項(xiàng)式為：所對(duì)應(yīng)的生成矩陣為：例題：已知循環(huán)碼(7,4)的生成多項(xiàng)式g(x)有兩種可能

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

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

(2)求余式

(3)求系統(tǒng)碼多項(xiàng)式C(x)=xn-km(x)+r(x)=x6+x5+x3+1所以對(duì)應(yīng)的系統(tǒng)循環(huán)碼為[1101001]例題：如果循環(huán)碼(7,4)的生成多項(xiàng)式g(x)=x3+x+1，消息碼為[1101]，求對(duì)應(yīng)的系統(tǒng)循環(huán)碼4.校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣4.校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣4.校驗(yàn)多項(xiàng)式和校驗(yàn)矩陣5.伴隨多項(xiàng)式和伴隨矩陣伴隨多項(xiàng)式S(x)與收到的碼多項(xiàng)式R(x)同余伴隨多項(xiàng)式S(x)與差錯(cuò)圖樣多項(xiàng)式E(x)之間也存在一一對(duì)應(yīng)關(guān)系5.伴隨多項(xiàng)式和伴隨矩陣循環(huán)碼譯碼步驟(1)利用，建立差錯(cuò)圖樣多項(xiàng)式E(x)和伴隨多項(xiàng)式S(x)之間的映射表；(2)收到R(x)后，利用得到某個(gè)S(x)，然后利用步驟(1)中建立的映射表，即可查到所對(duì)應(yīng)的差錯(cuò)多項(xiàng)式E(x);(3)將差錯(cuò)多項(xiàng)式E(x)與R(x)相加，即可得到經(jīng)過糾錯(cuò)的C(x)。解，由得到例題：如果循環(huán)碼(7,4)的生成多項(xiàng)式g(x)=x3+x+1，確定差錯(cuò)圖樣多項(xiàng)式與伴隨多項(xiàng)式的映射表差錯(cuò)圖樣多項(xiàng)式E(x)伴隨多項(xiàng)式S(x)0011xxx2x2x3x+1x4x2+xx5x2+x+1x6x2+1若已知伴隨多項(xiàng)式S(x)，可以容易求得對(duì)應(yīng)的伴隨矩陣S。例如，S(x)=x2+x+1,則伴隨矩陣S=[111]當(dāng)然，由于循環(huán)碼是線性分組碼的子類，所以，伴隨矩陣仍可以由S=RHT求得。5.伴隨多項(xiàng)式和伴隨矩陣6.BCH碼和RS碼BCH碼是循環(huán)碼中的一個(gè)大類，分為二進(jìn)制BCH碼和非二進(jìn)制BCH碼(例如RS碼)。二進(jìn)制BCH碼可記為(2m-1,k)，其中m為正整數(shù)且，即碼長(zhǎng)n=2m-1，且(t為可糾正的差錯(cuò)數(shù))，t由最小碼距決定，即二進(jìn)制BCH碼的優(yōu)點(diǎn)是，具有糾正多個(gè)隨機(jī)差錯(cuò)的能力。具有嚴(yán)謹(jǐn)?shù)拇鷶?shù)結(jié)構(gòu)，可以按照碼長(zhǎng)n和糾錯(cuò)能力t直接將BCH碼構(gòu)造出來。該特點(diǎn)優(yōu)于一般線性分組碼，一般線性分組碼在設(shè)計(jì)出來之后，需要計(jì)算最小距離dmin，才能知道糾錯(cuò)能力。若不符合要求，還要重復(fù)設(shè)計(jì)過程。6.BCH碼和RS碼確定BCH碼的生成多項(xiàng)式g(x)，取決于兩方面：(1)g(x)是xn+1因式中最高階為n-k的多項(xiàng)式，這是任何循環(huán)碼都必須滿足的條件。由于BCH碼的碼長(zhǎng)n=2m-1，，所以其碼長(zhǎng)的取值只能是7,15,31,63,127,255,…當(dāng)n較大時(shí)，xn+1的因式分解就只能用計(jì)算機(jī)來計(jì)算。(2)g(x)必須滿足對(duì)糾錯(cuò)能力t的要求，即對(duì)最小碼距的要求。實(shí)際應(yīng)用中，將滿足上述兩個(gè)條件的系數(shù)整理成“BCH碼生成多項(xiàng)式系數(shù)”表，以便查用。例題：求碼長(zhǎng)為15且能糾正3個(gè)差錯(cuò)的BCH碼解：碼長(zhǎng)n=2m-1=15，所以m=4；糾錯(cuò)能力t=3；將x15+1因式分解后，得x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)查前述的“BCH碼生成多項(xiàng)式系數(shù)”表，可得滿足條件的BCH碼為(15,5)，其相應(yīng)的生成多項(xiàng)式的最高階為n-k=10，則生成多項(xiàng)式為g(x)=(x2+x+1)(x4+x+1)(x4+x3+x2+x+1)=x10+x8+x5+x4+x2+x+16.BCH碼和RS碼RS(Reed-Solomn)碼是一種非二進(jìn)制BCH碼。RS碼是極大最小距離碼(MDC碼)。若某個(gè)碼的最小距離dmin=n-k+1，則稱線性分組碼(n,k)為極大最小距離碼。在(n,k)線性分組碼中，極大最小距離碼具有最大的檢錯(cuò)、糾錯(cuò)能力。由于RS碼是多進(jìn)制，所以很容易與M進(jìn)制調(diào)制技術(shù)相匹配；RS碼特別適合糾正突發(fā)錯(cuò)誤。內(nèi)容提要一、糾錯(cuò)碼的基本概念二、糾錯(cuò)編碼的代數(shù)基礎(chǔ)三、線性分組碼四、循環(huán)碼五、卷積碼卷積碼與線性分組碼的比較卷積碼線性分組碼表示符號(hào)(n,k,K)，K為約束長(zhǎng)度(n,k)記憶性有記憶，輸出的n個(gè)比特不僅與當(dāng)前輸入的k比特有關(guān)，而且與以前輸入的K個(gè)k比特有關(guān)無記憶，輸出的n個(gè)比特僅與當(dāng)前輸入的k個(gè)比特有關(guān)(可視為K=0時(shí)的無記憶卷積碼)代數(shù)結(jié)構(gòu)無嚴(yán)格的代數(shù)結(jié)構(gòu)，目前多采用計(jì)算機(jī)來搜索好碼，缺乏有效的數(shù)學(xué)分析工具有嚴(yán)格的代數(shù)結(jié)構(gòu)，借用數(shù)學(xué)工具研究較為透徹編碼效率kk…kn…輸入k位當(dāng)前時(shí)間以前K個(gè)時(shí)間輸入n位kn輸入k位輸入n位卷積碼線性分組碼1.卷積碼的組織結(jié)構(gòu)卷積碼(n,k,K)與線性分組碼(n,k)的重要區(qū)別在于，卷積碼是有記憶的，并用約束長(zhǎng)度表示記憶長(zhǎng)度，記為K。輸出的n位比特不僅與當(dāng)前時(shí)間輸入的k比特有關(guān)，還與以前時(shí)間輸入的多個(gè)k比特有關(guān)，到底與以前多長(zhǎng)時(shí)間有關(guān)，就由約束長(zhǎng)度K來度量。卷積碼可以視為多個(gè)線性分組碼的線性疊加，只不過多個(gè)線性分組碼是來源于同一個(gè)輸入源的多個(gè)不同時(shí)間段(包括當(dāng)前時(shí)間段和K個(gè)以前時(shí)間段)。顯然，當(dāng)K=0時(shí)，卷積碼就退化為線性分組碼。例題：設(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的目的是說明該時(shí)刻已完成“結(jié)尾清空處理”，即在該時(shí)刻可以輸入新的消息。由上例中看到，當(dāng)輸入[1011]時(shí)，輸出為110110100001，因此，該卷積碼的編碼效率為：對(duì)L段輸入消息碼進(jìn)行編碼，每段消息碼長(zhǎng)度為k比特，因此有效消息共Lk比特。經(jīng)過編碼后，產(chǎn)生了Ln個(gè)比特，但由于“結(jié)尾清空處理”額外輸入的K段全“0”數(shù)據(jù)，因此總共產(chǎn)生的數(shù)據(jù)為(L+K)n比特。當(dāng)K=0時(shí)，卷積碼的編碼效率為：與線性分組碼一致。

2.卷積碼的解析表示法(1)生成矩陣表示法(2)生成多項(xiàng)式表示法(3)沖激響應(yīng)表示法(1)生成矩陣表示法卷積碼為線性碼，可通過