通信原理第12講-差錯(cuò)控制編碼課件

第十二章差錯(cuò)控制編碼

在信源編碼的基礎(chǔ)上，為了提高傳輸系統(tǒng)的抗干擾能力，需要在數(shù)字調(diào)制之前對(duì)數(shù)字基帶信號(hào)進(jìn)行某種前向糾錯(cuò)編碼，也就是信道編碼。信道編碼的目的是提高通信系統(tǒng)糾錯(cuò)能力，因而也稱(chēng)為差錯(cuò)控制編碼。

為了在接收端獲得應(yīng)用的高質(zhì)量圖像和聲音，信道編碼需對(duì)信源編碼后的數(shù)據(jù)流添加一些符合特定邏輯關(guān)系的附加數(shù)據(jù)，這必將使傳輸碼率增加。第十二章差錯(cuò)控制編碼在信源編碼的基礎(chǔ)1信道編碼一般有下列要求：(1)增加盡可能少的數(shù)據(jù)率而可獲得較強(qiáng)的檢錯(cuò)和糾錯(cuò)能力，即編碼效率高，抗干擾能力強(qiáng)；(2)對(duì)數(shù)字信號(hào)有良好的透明性，也即傳輸通道對(duì)于傳輸?shù)臄?shù)字信號(hào)內(nèi)容沒(méi)有任何限制；(3)傳輸信號(hào)的頻譜特性與傳輸信道的通頻帶有最佳的匹配性；(4)編碼信號(hào)內(nèi)包含有正確的數(shù)據(jù)定時(shí)信息和幀同步信息，以便接收端準(zhǔn)確地解碼；(5)編碼的數(shù)字信號(hào)具有適當(dāng)?shù)碾娖椒秶?6)發(fā)生誤碼時(shí)，誤碼的擴(kuò)散蔓延小。信道編碼一般有下列要求：2其中，最主要的可概括為兩點(diǎn)：其一，附加一些數(shù)據(jù)信息以實(shí)現(xiàn)最大的檢錯(cuò)糾錯(cuò)能力，這就涉及到差錯(cuò)控制編碼原理和特性。其二，數(shù)據(jù)流的頻譜特性適應(yīng)傳輸通道的通頻帶特性，以求信號(hào)能量經(jīng)由通道傳輸時(shí)損失最小，因此有利于載波噪聲比(載噪比，C/N)高，發(fā)生誤碼的可能性小。

其中，最主要的可概括為兩點(diǎn)：3解決誤碼從兩個(gè)方面著手1、通過(guò)合理選擇碼型，盡量減少傳輸信道發(fā)生誤碼的可能2、進(jìn)行誤碼控制，既增強(qiáng)信道的糾錯(cuò)能力解決誤碼從兩個(gè)方面著手1、通過(guò)合理選擇碼型，盡量減少傳輸信道4差錯(cuò)控制編碼原理

為了能判斷發(fā)送的信息是否有誤，可以在發(fā)送時(shí)增加必要的附加數(shù)據(jù)。又為了能糾正一定程度的錯(cuò)誤，這需要增加更多的附加數(shù)據(jù)。這些附加數(shù)據(jù)在不發(fā)生誤碼的情況下，是完全多余的，但若發(fā)生誤碼，便可利用信息數(shù)據(jù)與附加數(shù)據(jù)之間特定的關(guān)系實(shí)現(xiàn)誤碼檢知和誤碼糾正。換言之，為使信源代碼具有檢錯(cuò)糾錯(cuò)能力，應(yīng)按一事實(shí)上規(guī)則在信源編碼所產(chǎn)生數(shù)據(jù)的基礎(chǔ)上增加一些冗余碼元（又稱(chēng)監(jiān)督碼或檢驗(yàn)碼），使監(jiān)督碼元和信息碼元之間建立一種確定的關(guān)系，發(fā)送端完成這項(xiàng)任務(wù)的過(guò)程就稱(chēng)為差錯(cuò)控制編碼。差錯(cuò)控制編碼原理為了能判斷發(fā)送的信息5注意：無(wú)論檢錯(cuò)還是糾錯(cuò)，都有一定的差錯(cuò)識(shí)別范圍，誤碼嚴(yán)重而超過(guò)識(shí)別范圍時(shí)，將不能實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)，甚至越糾越錯(cuò)。注意：6差錯(cuò)控制編碼的方式1.反饋重發(fā)(ARQ，自動(dòng)重發(fā)請(qǐng)求)方式這種方式中，接收端發(fā)現(xiàn)誤碼后通過(guò)反饋信道請(qǐng)求發(fā)送端重發(fā)數(shù)據(jù)。因此，接收端需要有誤碼檢測(cè)和反饋信道。

優(yōu)點(diǎn)：系統(tǒng)的編解碼設(shè)備比較簡(jiǎn)單、糾錯(cuò)能力強(qiáng)，適合于干擾不嚴(yán)重的點(diǎn)對(duì)點(diǎn)通信中應(yīng)用。

缺點(diǎn)：當(dāng)信道質(zhì)量較差而干擾頻繁發(fā)生時(shí)，經(jīng)常處于重發(fā)信息狀態(tài)，使信息的連續(xù)性和實(shí)時(shí)性很差。差錯(cuò)控制編碼的方式1.反饋重發(fā)(ARQ，自動(dòng)重發(fā)請(qǐng)求)方式7DATA0DATA0ABNAKACKDATA0DATA1ABACKACK出錯(cuò)DATA0DATA0ABACK丟失tDATA0DATA0ABACKtACK丟失DATA0DATA0ABNAKACKDATA0DATA1AB82.前向糾錯(cuò)(FEC)方式這種方式中，發(fā)送端發(fā)送的數(shù)據(jù)內(nèi)包括信息碼元以及供接收端自動(dòng)發(fā)現(xiàn)錯(cuò)誤和糾正誤碼的監(jiān)督碼元。優(yōu)點(diǎn)：它不需要反饋信道，能進(jìn)行單點(diǎn)對(duì)多點(diǎn)的同步通信，譯碼實(shí)時(shí)性較好。缺點(diǎn)：編譯碼電路稍微復(fù)雜些，由于添加的監(jiān)督碼元較多，從而使編碼效率較低。2.前向糾錯(cuò)(FEC)方式這種方式中，發(fā)送端發(fā)送93.混合糾錯(cuò)(HEC)方式

這種方式中，發(fā)送端發(fā)出的信息內(nèi)包含有給出檢錯(cuò)糾錯(cuò)能力的監(jiān)督碼元，誤碼量少時(shí)接收端檢知后能自動(dòng)糾錯(cuò)，誤碼量超過(guò)糾錯(cuò)能力時(shí)接收端能通過(guò)反饋信道請(qǐng)求發(fā)送端重發(fā)有關(guān)信息。優(yōu)點(diǎn)：編譯碼電路的復(fù)雜性比FEC方式的簡(jiǎn)單，又可避免ARQ方式中信息連續(xù)性差的缺點(diǎn)，并且能保證較低的接收誤碼率。3.混合糾錯(cuò)(HEC)方式10糾錯(cuò)碼的分類(lèi)

對(duì)具體的糾錯(cuò)碼，可以從不同角度將其分類(lèi)，下圖所示即為糾錯(cuò)碼的分類(lèi)情況。糾錯(cuò)碼的分類(lèi)11圖5-6糾錯(cuò)碼的分類(lèi)

圖5-6糾錯(cuò)碼的分類(lèi)12檢錯(cuò)碼：只能檢知一定的誤碼而不能糾錯(cuò)。糾錯(cuò)碼：具備檢錯(cuò)能力和一定的糾錯(cuò)能力。糾刪碼：能檢錯(cuò)糾錯(cuò)，對(duì)超過(guò)其糾錯(cuò)能力的誤碼則將有關(guān)信息刪除或采取誤碼隱匿措施將誤碼加以掩蔽。

糾錯(cuò)碼按照檢錯(cuò)糾錯(cuò)功能的不同，可分為:糾錯(cuò)碼按照檢錯(cuò)糾錯(cuò)功能的不同，可分為:13差錯(cuò)控制編碼的幾個(gè)基本概念1.信息碼元和監(jiān)督碼元n=k+rkrnk為信息碼元，是發(fā)送端由信源編碼給出的信息數(shù)據(jù)比特。在二元碼情況下，總共有2k個(gè)不同的信息碼組。r為監(jiān)督碼元，組成一組總碼數(shù)為n的碼組。差錯(cuò)控制編碼的幾個(gè)基本概念krnk為信息碼元，是發(fā)送端由信源142.許用碼組和禁用碼組

信道編碼后總碼長(zhǎng)為n的不同碼組值可有2n個(gè)。其中發(fā)送的信息碼組有2k個(gè)，通常稱(chēng)之為許用碼組，其余的為禁用碼組，不允許傳送。2.許用碼組和禁用碼組

信道編碼后總碼長(zhǎng)為n的不同碼153.編碼效率通常，將每個(gè)碼組內(nèi)信息碼元數(shù)k值與總碼元數(shù)n值之比η＝k/n稱(chēng)為信道編碼的編碼效率，即

η＝k/n＝k/(k+r)

η是衡量信道編碼性能的一個(gè)重要指標(biāo)?？梢?jiàn)，監(jiān)督碼元越多，檢錯(cuò)糾錯(cuò)能力越強(qiáng)，但編碼效率相應(yīng)地降低。3.編碼效率164、碼重

碼重——碼字的重量，即一個(gè)碼字中“1”碼的個(gè)數(shù)。通常用W表示。例如：碼字10011000的碼重W=300000000的碼重W=01001111001的碼重W=64、碼重碼重——碼字的重量，即一個(gè)碼字中“1”碼的個(gè)數(shù)。通175、碼距碼距——即碼元距離就是兩個(gè)碼組中對(duì)應(yīng)碼位上碼元不同的個(gè)數(shù)（也稱(chēng)漢明距），用d表示。碼距反映的是碼組之間的差異程度,比如:00和01兩組碼的碼距為d=1；011和100的碼距為d=3;11000與10011之間的距離為d=3。最小碼距——碼集中所有碼字之間碼距的最小值即稱(chēng)為最小碼距，用表示。5、碼距碼距——即碼元距離就是兩個(gè)碼組中對(duì)應(yīng)碼位上碼元不同的18例如：若碼集包含的碼字有10010，00011，和11000，求最小碼距。各碼字兩兩之間的碼距分別如下：

10010和00011之間：d=2

10010和11000之間:d=200011和11000之間:d=4

因此該碼集的最小碼距為2。最小碼距是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。

例如：若碼集包含的碼字有10010，00011，和11000196、d0的大小直接關(guān)系著編碼的檢，糾錯(cuò)能力。為檢測(cè)e個(gè)錯(cuò)碼，要求d0≥e+1為糾正t個(gè)錯(cuò)碼，要求d0≥2t+1為糾正t個(gè)錯(cuò)碼，同時(shí)檢測(cè)e個(gè)錯(cuò)碼，要求d0≥e+t+1Bd0BA12BA12BB345d06、d0的大小直接關(guān)系著編碼的檢，糾錯(cuò)能力。為檢測(cè)e個(gè)錯(cuò)20例：1）如果A和B為1個(gè)比特：

d0=1，則無(wú)法檢錯(cuò)和糾錯(cuò)；2）如果A和B各增加1個(gè)監(jiān)督碼元，組成（2，1）碼組，便具有檢錯(cuò)能力。如將00和11作為許用碼組，01和10作為禁用碼組，

這時(shí)d0

=2，碼組的檢錯(cuò)能力e=1，而糾錯(cuò)能力為0。3）如果再增加1個(gè)監(jiān)督碼元，就可實(shí)現(xiàn)糾錯(cuò)能力。例：1）如果A和B為1個(gè)比特：21線(xiàn)性分組碼1、奇偶校驗(yàn)碼：它是一種最簡(jiǎn)單的線(xiàn)性分組檢錯(cuò)碼。方法：是先將信源編碼后的信息數(shù)據(jù)流分成等長(zhǎng)碼組，然后在每一信息碼組之后加入1位監(jiān)督碼元作為奇偶校驗(yàn)位，使得碼組總碼長(zhǎng)的碼重為奇數(shù)（奇校驗(yàn)編碼）或偶數(shù)（偶校驗(yàn)編碼）。它可以檢知奇數(shù)個(gè)誤碼，而不能發(fā)現(xiàn)偶數(shù)個(gè)誤碼，而且沒(méi)有糾錯(cuò)能力。線(xiàn)性分組碼1、奇偶校驗(yàn)碼：22一般地，若有r個(gè)監(jiān)督碼元，就有r個(gè)監(jiān)督方程和r個(gè)相應(yīng)的校驗(yàn)子，可給出2r種狀態(tài)。對(duì)于一位誤碼來(lái)說(shuō)，非全0的2r-1種狀態(tài)可指明2r-1個(gè)誤碼位置。線(xiàn)性分組碼具有如下性質(zhì)：1、封閉性。任意兩個(gè)碼組的和還是許用的碼組。2、碼的最小距離等于非零碼的最小碼重。如果對(duì)于線(xiàn)性分組碼（n，k)中2r-1>=n，就有可能構(gòu)造出能糾正一位或一位以上誤碼的線(xiàn)性分組碼。一般地，若有r個(gè)監(jiān)督碼元，就有r個(gè)監(jiān)督方程和r個(gè)相應(yīng)的校驗(yàn)子232、漢明碼漢明碼(HammingCode)是由RichardHamming于1950年提出的，它屬于線(xiàn)性分組編碼方式，用以糾正單個(gè)錯(cuò)誤的線(xiàn)性分組碼，在軟件無(wú)線(xiàn)電中應(yīng)用廣泛。其基本原理是:將信息碼元與監(jiān)督碼元通過(guò)線(xiàn)性方程式聯(lián)系起來(lái)，每一個(gè)監(jiān)督位被編在傳輸碼字的特定比特位置上。系統(tǒng)對(duì)于錯(cuò)誤的數(shù)位無(wú)論是原有信息位中的，還是附加監(jiān)督位中的都能把它分離出來(lái)。

2、漢明碼漢明碼(HammingCode)是由Richar24它有以下特征：碼長(zhǎng)n=2m–1信息位數(shù)k=2m–m–1監(jiān)督碼位r=n–k=m最小距離d=3糾錯(cuò)能力t=1這里m為大于等于2的正整數(shù)，給定m后，即可構(gòu)造出具體的(n,k)漢明碼。假設(shè)k為4，要求能糾正一位誤碼，則根據(jù)條件2r-1>=n，得r=>3，現(xiàn)取3，則構(gòu)成（7，4）漢明碼。它有以下特征：25（7，4）漢明碼用a0、al、a2、a3、a4、a5、a6表示這7個(gè)碼元，用S1、S2、S3表示由三個(gè)監(jiān)督方程式計(jì)算得到的校正子，并假設(shè)三位S1、S2、S3校正子碼組與誤碼位置的對(duì)應(yīng)關(guān)系如下表所示。S1S2S3誤碼位置S1S2S3誤碼位置001a0101a4010a1110a5100a2111a6011a3000無(wú)錯(cuò)（7，4）碼校正子與誤碼位置（7，4）漢明碼用a0、al、a2、a3、a4、a5、a6表26當(dāng)誤碼位置在a2、a4、a5、a6時(shí)，校正子S1＝1；否則S1＝0。因此有:S1＝a6⊕a5⊕a4⊕a2同理有S2＝a6⊕a5⊕a3⊕a1S3＝a6⊕a4⊕a3⊕a0。由表可知：當(dāng)誤碼位置在a2、a4、a5、a6時(shí)，由表可知：27在編碼時(shí):a6、a5、a4、a3為信息碼元，a2、a1、a0為監(jiān)督碼元。則監(jiān)督碼元可由以下監(jiān)督方程唯一確定：0＝a6⊕a5⊕a4⊕a20＝a6⊕a5⊕a3⊕a10＝a6⊕a4⊕a3⊕a0

也即：a2＝a6⊕a5⊕a4a1＝a6⊕a5⊕a3a0＝a6⊕a4⊕a3在編碼時(shí):28由上面方程可得到16個(gè)許用碼組：在接收端收到每個(gè)碼組后，計(jì)算出S1、S2、S3，如果不全為0，則表示存在錯(cuò)誤，可以由下表確定錯(cuò)誤位置并予以糾正。信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111由上面方程可得到16個(gè)許用碼組：在接收端收到每個(gè)碼組后，計(jì)算29例如：收到碼組為0000011，可算出S1S2S3=011,由表可知在a3上有一誤碼。通過(guò)觀(guān)察可以看出，上述（7，4）碼的最小碼距為dmin＝3，它能糾正一個(gè)誤碼或檢測(cè)兩個(gè)誤碼。如果超出糾錯(cuò)能力則反而會(huì)因“亂糾”出現(xiàn)新的誤碼。例如：收到碼組為0000011，可算出S1S2S3=011,30監(jiān)督矩陣0＝a6⊕a5⊕a4⊕a20＝a6⊕a5⊕a3⊕a10＝a6⊕a4⊕a3⊕a0可寫(xiě)成：0＝1·a6+1·a5+1·a4+0·a3+1·a2+0·a1+0·a00＝1·a6+1·a5+0·a4+1·a3+0·a2+1·a1+0·a00＝1·a6+0·a5+1·a4+1·a3+0·a2+0·a1+1·a0用矩陣表示為：111010001101010a6a5a4a3a2a1a0T=010110010簡(jiǎn)化為：HAT=0T其中H稱(chēng)為監(jiān)督矩陣監(jiān)督矩陣0＝a6⊕a5⊕a4⊕a231H可以分成兩部分：11101001101010=[PIr]1011001其中P為信息位矩陣，Ir為rXr階的單位矩陣生成矩陣G：G=[IkPT]根據(jù)生成矩陣和已知的信息碼元可產(chǎn)生整個(gè)碼組。A=[a6a5a4a3]GH可以分成兩部分：111010032擴(kuò)展?jié)h明碼漢明碼如果再加上一位對(duì)所有碼元都進(jìn)行校驗(yàn)的監(jiān)督位，則監(jiān)督碼元由m增至m+1，信息位不變，碼長(zhǎng)由2m–1增至2m，通常把這種（2m，2m–1–m）碼稱(chēng)為擴(kuò)展?jié)h明碼。擴(kuò)展?jié)h明碼的最小碼距增加為4，能糾正l位錯(cuò)誤同時(shí)檢測(cè)2位錯(cuò)誤。簡(jiǎn)稱(chēng)糾1檢2錯(cuò)碼。其實(shí)質(zhì)上是在原漢明碼的每個(gè)碼組后面增加1位偶監(jiān)督碼元。例如(7,4)漢明碼可變成(8,4)擴(kuò)展?jié)h明碼（又稱(chēng)增余漢明碼）。

擴(kuò)展?jié)h明碼漢明碼如果再加上一位對(duì)所有碼元都進(jìn)行校驗(yàn)的監(jiān)督位，33循環(huán)碼：循環(huán)碼是一種特殊的線(xiàn)性分組碼，它除了具有群碼的封閉性外，還有一個(gè)特性就是循環(huán)性。按模運(yùn)算循環(huán)碼：循環(huán)碼是一種特殊的線(xiàn)性分組碼，它除了具有群碼的封閉性34為了用代數(shù)理論研究循環(huán)碼，可將碼組用多項(xiàng)式來(lái)表示，稱(chēng)為碼多項(xiàng)式。設(shè)許用碼組C=（cn–1

cn–2…clc0）對(duì)應(yīng)的碼多項(xiàng)式可表示為

C（x）=cn–1

xn–1+cn–2

xn–2+…+clx+c0其中多項(xiàng)式的系數(shù)就是碼字各分量的值，x為一個(gè)任意實(shí)變量，其冪次i代表該分量所在位置。為了用代數(shù)理論研究循環(huán)碼，可將碼組用多項(xiàng)式來(lái)表示，稱(chēng)為碼多項(xiàng)35循環(huán)碼中的幾個(gè)定理1、若C(x)是n長(zhǎng)循環(huán)碼中的一個(gè)碼多項(xiàng)式，則xiC(x)按模（xn+1）運(yùn)算的余式必為循環(huán)碼中另一碼多項(xiàng)式。2、一個(gè)二進(jìn)制中（n，k）循環(huán)碼中有惟一的r=n-k次多項(xiàng)式g(x)，且其常數(shù)項(xiàng)為l。如果一個(gè)碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱(chēng)g(x)生成該碼，且稱(chēng)g(x)為該碼的生成多項(xiàng)式，所對(duì)應(yīng)的碼字成為生成子或生成子序列。

3、設(shè)g(x)是（n，k）循環(huán)碼[C(x)]中的一個(gè)次數(shù)最低的多項(xiàng)式（g(x)≠0），則該循環(huán)碼由g(x)生成，并且g(x)是（xn+1）的一個(gè)因式。

循環(huán)碼中的幾個(gè)定理1、若C(x)是n長(zhǎng)循環(huán)碼中的一個(gè)碼多項(xiàng)式36從以上討論中，可得到幾個(gè)重要結(jié)論：

①在二元或GF(2)上找一個(gè)(n,k)循環(huán)碼，就是找一個(gè)能除盡xn+1的n-k次首1多項(xiàng)式g(x)，為了尋找生成多項(xiàng)式，必須對(duì)xn+1進(jìn)行因式分解，這可用計(jì)算機(jī)來(lái)完成。對(duì)于某些n值，xn+1只有很少的幾個(gè)因式，因而碼長(zhǎng)為n的循環(huán)碼也不多。僅對(duì)于很少的幾個(gè)n值，才有較多的因式。②如果C(x)是(n,k)碼的一個(gè)碼多項(xiàng)式，則g(x)一定除盡C(x)。反之，若g(x)|C(x)，則次數(shù)小于等于n-1的C(x)必是碼的碼多項(xiàng)式。也就是說(shuō)若C(x)是碼多項(xiàng)式，則

C(x)≡0modg(x)從以上討論中，可得到幾個(gè)重要結(jié)論：

①在二元或GF(2)上找37例：多項(xiàng)式x7+1=（x+1）（x

3+x+1）（x

3+x2+1），構(gòu)造一個(gè)(7,3)循環(huán)碼要構(gòu)造一個(gè)(7,3)循環(huán)碼，就是在x7+1中找一個(gè)n–k=4次的因式g(x)，作為碼的生成多項(xiàng)式，由它的一切倍式就組成了(7,3)循環(huán)碼。若選g(x)=（x

3+x+1）（x+1）=x4+x3+x2+1，該碼的八個(gè)碼字可由g(x)，x

g(x)，x2

g(x)的線(xiàn)性組合產(chǎn)生出來(lái)，而且這三個(gè)碼多項(xiàng)式是線(xiàn)性無(wú)關(guān)的，它們構(gòu)成一組基底。所以生成的循環(huán)子空間（循環(huán)碼）是一個(gè)三維子空間V7，3，對(duì)應(yīng)于一個(gè)(7,3)循環(huán)碼。若選g(x)=（x+1）（x3+x2+1）=x4

+x2+x+l，則生成另一個(gè)循環(huán)碼。由此可知，只要知道了xn

+l的因式分解式，用它的各個(gè)因式的乘積，便能得到很多個(gè)不同的循環(huán)碼。例：多項(xiàng)式x7+1=（x+1）（x3+x38循環(huán)碼的編碼方法

1、首先根據(jù)給定的(n,k)值選定生成多項(xiàng)式g(x)

。

1）g(x)是一個(gè)（n－k）次多項(xiàng)式2）g(x)的常數(shù)項(xiàng)不為03）g(x)是xn＋1的一個(gè)因子循環(huán)碼的編碼方法1、首先根據(jù)給定的(n,k)值選定生成392、冗余碼的計(jì)算1)把信息碼元多項(xiàng)式m(x)乘xn-k，得T(x)；2)用g(x)除T(x)，得到余式r(x)；3)余式r(x)即為循環(huán)冗余碼，它作為監(jiān)督碼元加于信息碼元后面。4）寫(xiě)出碼多項(xiàng)式C(x)=T(x)＋r(x)

即，在m(x)后面添加n個(gè)02、冗余碼的計(jì)算1)把信息碼元多項(xiàng)式m(x)乘xn-k，得40監(jiān)督位信息位例(7,3)循環(huán)碼m(x)=x2+x,g(x)=x4+x2+

x+1解r(x)例(7,3)循環(huán)碼m(x)=x2+x,g(x)=x441在接收端的檢錯(cuò)設(shè)接收端接收到的數(shù)據(jù)為R(x)那么，進(jìn)行R(x)/g(x)運(yùn)算如果：1、余數(shù)為零

2、余數(shù)不為零沒(méi)有出錯(cuò)，或出錯(cuò)概率很低有錯(cuò)在接收端的檢錯(cuò)設(shè)接收端接收到的數(shù)據(jù)為R(x)沒(méi)有出錯(cuò)，或出錯(cuò)42循環(huán)碼的生成矩陣

一個(gè)[n,k]線(xiàn)性分組碼是n維線(xiàn)性空間中的一個(gè)k維子空間，同樣，一個(gè)[n,k]循環(huán)碼也是n維線(xiàn)性空間中的一個(gè)k維子空間。因此，只要找出k個(gè)線(xiàn)性無(wú)關(guān)的碼多項(xiàng)式，就可通過(guò)線(xiàn)性組合得到所有碼多項(xiàng)式。由于碼的生成多項(xiàng)式g(x)是n-k次的，所以g(x)，xg(x)，x2g(x)，…，xk-1g(x)都是線(xiàn)性無(wú)關(guān)的，可得碼的生成矩陣：G=xk-1g(x)

…xg(x)g(x)循環(huán)碼的生成矩陣一個(gè)[n,k]線(xiàn)性分43第十二章差錯(cuò)控制編碼

在信源編碼的基礎(chǔ)上，為了提高傳輸系統(tǒng)的抗干擾能力，需要在數(shù)字調(diào)制之前對(duì)數(shù)字基帶信號(hào)進(jìn)行某種前向糾錯(cuò)編碼，也就是信道編碼。信道編碼的目的是提高通信系統(tǒng)糾錯(cuò)能力，因而也稱(chēng)為差錯(cuò)控制編碼。

為了在接收端獲得應(yīng)用的高質(zhì)量圖像和聲音，信道編碼需對(duì)信源編碼后的數(shù)據(jù)流添加一些符合特定邏輯關(guān)系的附加數(shù)據(jù)，這必將使傳輸碼率增加。第十二章差錯(cuò)控制編碼在信源編碼的基礎(chǔ)44信道編碼一般有下列要求：(1)增加盡可能少的數(shù)據(jù)率而可獲得較強(qiáng)的檢錯(cuò)和糾錯(cuò)能力，即編碼效率高，抗干擾能力強(qiáng)；(2)對(duì)數(shù)字信號(hào)有良好的透明性，也即傳輸通道對(duì)于傳輸?shù)臄?shù)字信號(hào)內(nèi)容沒(méi)有任何限制；(3)傳輸信號(hào)的頻譜特性與傳輸信道的通頻帶有最佳的匹配性；(4)編碼信號(hào)內(nèi)包含有正確的數(shù)據(jù)定時(shí)信息和幀同步信息，以便接收端準(zhǔn)確地解碼；(5)編碼的數(shù)字信號(hào)具有適當(dāng)?shù)碾娖椒秶?6)發(fā)生誤碼時(shí)，誤碼的擴(kuò)散蔓延小。信道編碼一般有下列要求：45其中，最主要的可概括為兩點(diǎn)：其一，附加一些數(shù)據(jù)信息以實(shí)現(xiàn)最大的檢錯(cuò)糾錯(cuò)能力，這就涉及到差錯(cuò)控制編碼原理和特性。其二，數(shù)據(jù)流的頻譜特性適應(yīng)傳輸通道的通頻帶特性，以求信號(hào)能量經(jīng)由通道傳輸時(shí)損失最小，因此有利于載波噪聲比(載噪比，C/N)高，發(fā)生誤碼的可能性小。

其中，最主要的可概括為兩點(diǎn)：46解決誤碼從兩個(gè)方面著手1、通過(guò)合理選擇碼型，盡量減少傳輸信道發(fā)生誤碼的可能2、進(jìn)行誤碼控制，既增強(qiáng)信道的糾錯(cuò)能力解決誤碼從兩個(gè)方面著手1、通過(guò)合理選擇碼型，盡量減少傳輸信道47差錯(cuò)控制編碼原理

為了能判斷發(fā)送的信息是否有誤，可以在發(fā)送時(shí)增加必要的附加數(shù)據(jù)。又為了能糾正一定程度的錯(cuò)誤，這需要增加更多的附加數(shù)據(jù)。這些附加數(shù)據(jù)在不發(fā)生誤碼的情況下，是完全多余的，但若發(fā)生誤碼，便可利用信息數(shù)據(jù)與附加數(shù)據(jù)之間特定的關(guān)系實(shí)現(xiàn)誤碼檢知和誤碼糾正。換言之，為使信源代碼具有檢錯(cuò)糾錯(cuò)能力，應(yīng)按一事實(shí)上規(guī)則在信源編碼所產(chǎn)生數(shù)據(jù)的基礎(chǔ)上增加一些冗余碼元（又稱(chēng)監(jiān)督碼或檢驗(yàn)碼），使監(jiān)督碼元和信息碼元之間建立一種確定的關(guān)系，發(fā)送端完成這項(xiàng)任務(wù)的過(guò)程就稱(chēng)為差錯(cuò)控制編碼。差錯(cuò)控制編碼原理為了能判斷發(fā)送的信息48注意：無(wú)論檢錯(cuò)還是糾錯(cuò)，都有一定的差錯(cuò)識(shí)別范圍，誤碼嚴(yán)重而超過(guò)識(shí)別范圍時(shí)，將不能實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò)，甚至越糾越錯(cuò)。注意：49差錯(cuò)控制編碼的方式1.反饋重發(fā)(ARQ，自動(dòng)重發(fā)請(qǐng)求)方式這種方式中，接收端發(fā)現(xiàn)誤碼后通過(guò)反饋信道請(qǐng)求發(fā)送端重發(fā)數(shù)據(jù)。因此，接收端需要有誤碼檢測(cè)和反饋信道。

優(yōu)點(diǎn)：系統(tǒng)的編解碼設(shè)備比較簡(jiǎn)單、糾錯(cuò)能力強(qiáng)，適合于干擾不嚴(yán)重的點(diǎn)對(duì)點(diǎn)通信中應(yīng)用。

缺點(diǎn)：當(dāng)信道質(zhì)量較差而干擾頻繁發(fā)生時(shí)，經(jīng)常處于重發(fā)信息狀態(tài)，使信息的連續(xù)性和實(shí)時(shí)性很差。差錯(cuò)控制編碼的方式1.反饋重發(fā)(ARQ，自動(dòng)重發(fā)請(qǐng)求)方式50DATA0DATA0ABNAKACKDATA0DATA1ABACKACK出錯(cuò)DATA0DATA0ABACK丟失tDATA0DATA0ABACKtACK丟失DATA0DATA0ABNAKACKDATA0DATA1AB512.前向糾錯(cuò)(FEC)方式這種方式中，發(fā)送端發(fā)送的數(shù)據(jù)內(nèi)包括信息碼元以及供接收端自動(dòng)發(fā)現(xiàn)錯(cuò)誤和糾正誤碼的監(jiān)督碼元。優(yōu)點(diǎn)：它不需要反饋信道，能進(jìn)行單點(diǎn)對(duì)多點(diǎn)的同步通信，譯碼實(shí)時(shí)性較好。缺點(diǎn)：編譯碼電路稍微復(fù)雜些，由于添加的監(jiān)督碼元較多，從而使編碼效率較低。2.前向糾錯(cuò)(FEC)方式這種方式中，發(fā)送端發(fā)送523.混合糾錯(cuò)(HEC)方式

這種方式中，發(fā)送端發(fā)出的信息內(nèi)包含有給出檢錯(cuò)糾錯(cuò)能力的監(jiān)督碼元，誤碼量少時(shí)接收端檢知后能自動(dòng)糾錯(cuò)，誤碼量超過(guò)糾錯(cuò)能力時(shí)接收端能通過(guò)反饋信道請(qǐng)求發(fā)送端重發(fā)有關(guān)信息。優(yōu)點(diǎn)：編譯碼電路的復(fù)雜性比FEC方式的簡(jiǎn)單，又可避免ARQ方式中信息連續(xù)性差的缺點(diǎn)，并且能保證較低的接收誤碼率。3.混合糾錯(cuò)(HEC)方式53糾錯(cuò)碼的分類(lèi)

對(duì)具體的糾錯(cuò)碼，可以從不同角度將其分類(lèi)，下圖所示即為糾錯(cuò)碼的分類(lèi)情況。糾錯(cuò)碼的分類(lèi)54圖5-6糾錯(cuò)碼的分類(lèi)

圖5-6糾錯(cuò)碼的分類(lèi)55檢錯(cuò)碼：只能檢知一定的誤碼而不能糾錯(cuò)。糾錯(cuò)碼：具備檢錯(cuò)能力和一定的糾錯(cuò)能力。糾刪碼：能檢錯(cuò)糾錯(cuò)，對(duì)超過(guò)其糾錯(cuò)能力的誤碼則將有關(guān)信息刪除或采取誤碼隱匿措施將誤碼加以掩蔽。

糾錯(cuò)碼按照檢錯(cuò)糾錯(cuò)功能的不同，可分為:糾錯(cuò)碼按照檢錯(cuò)糾錯(cuò)功能的不同，可分為:56差錯(cuò)控制編碼的幾個(gè)基本概念1.信息碼元和監(jiān)督碼元n=k+rkrnk為信息碼元，是發(fā)送端由信源編碼給出的信息數(shù)據(jù)比特。在二元碼情況下，總共有2k個(gè)不同的信息碼組。r為監(jiān)督碼元，組成一組總碼數(shù)為n的碼組。差錯(cuò)控制編碼的幾個(gè)基本概念krnk為信息碼元，是發(fā)送端由信源572.許用碼組和禁用碼組

信道編碼后總碼長(zhǎng)為n的不同碼組值可有2n個(gè)。其中發(fā)送的信息碼組有2k個(gè)，通常稱(chēng)之為許用碼組，其余的為禁用碼組，不允許傳送。2.許用碼組和禁用碼組

信道編碼后總碼長(zhǎng)為n的不同碼583.編碼效率通常，將每個(gè)碼組內(nèi)信息碼元數(shù)k值與總碼元數(shù)n值之比η＝k/n稱(chēng)為信道編碼的編碼效率，即

η＝k/n＝k/(k+r)

η是衡量信道編碼性能的一個(gè)重要指標(biāo)。可見(jiàn)，監(jiān)督碼元越多，檢錯(cuò)糾錯(cuò)能力越強(qiáng)，但編碼效率相應(yīng)地降低。3.編碼效率594、碼重

碼重——碼字的重量，即一個(gè)碼字中“1”碼的個(gè)數(shù)。通常用W表示。例如：碼字10011000的碼重W=300000000的碼重W=01001111001的碼重W=64、碼重碼重——碼字的重量，即一個(gè)碼字中“1”碼的個(gè)數(shù)。通605、碼距碼距——即碼元距離就是兩個(gè)碼組中對(duì)應(yīng)碼位上碼元不同的個(gè)數(shù)（也稱(chēng)漢明距），用d表示。碼距反映的是碼組之間的差異程度,比如:00和01兩組碼的碼距為d=1；011和100的碼距為d=3;11000與10011之間的距離為d=3。最小碼距——碼集中所有碼字之間碼距的最小值即稱(chēng)為最小碼距，用表示。5、碼距碼距——即碼元距離就是兩個(gè)碼組中對(duì)應(yīng)碼位上碼元不同的61例如：若碼集包含的碼字有10010，00011，和11000，求最小碼距。各碼字兩兩之間的碼距分別如下：

10010和00011之間：d=2

10010和11000之間:d=200011和11000之間:d=4

因此該碼集的最小碼距為2。最小碼距是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。

例如：若碼集包含的碼字有10010，00011，和11000626、d0的大小直接關(guān)系著編碼的檢，糾錯(cuò)能力。為檢測(cè)e個(gè)錯(cuò)碼，要求d0≥e+1為糾正t個(gè)錯(cuò)碼，要求d0≥2t+1為糾正t個(gè)錯(cuò)碼，同時(shí)檢測(cè)e個(gè)錯(cuò)碼，要求d0≥e+t+1Bd0BA12BA12BB345d06、d0的大小直接關(guān)系著編碼的檢，糾錯(cuò)能力。為檢測(cè)e個(gè)錯(cuò)63例：1）如果A和B為1個(gè)比特：

d0=1，則無(wú)法檢錯(cuò)和糾錯(cuò)；2）如果A和B各增加1個(gè)監(jiān)督碼元，組成（2，1）碼組，便具有檢錯(cuò)能力。如將00和11作為許用碼組，01和10作為禁用碼組，

這時(shí)d0

=2，碼組的檢錯(cuò)能力e=1，而糾錯(cuò)能力為0。3）如果再增加1個(gè)監(jiān)督碼元，就可實(shí)現(xiàn)糾錯(cuò)能力。例：1）如果A和B為1個(gè)比特：64線(xiàn)性分組碼1、奇偶校驗(yàn)碼：它是一種最簡(jiǎn)單的線(xiàn)性分組檢錯(cuò)碼。方法：是先將信源編碼后的信息數(shù)據(jù)流分成等長(zhǎng)碼組，然后在每一信息碼組之后加入1位監(jiān)督碼元作為奇偶校驗(yàn)位，使得碼組總碼長(zhǎng)的碼重為奇數(shù)（奇校驗(yàn)編碼）或偶數(shù)（偶校驗(yàn)編碼）。它可以檢知奇數(shù)個(gè)誤碼，而不能發(fā)現(xiàn)偶數(shù)個(gè)誤碼，而且沒(méi)有糾錯(cuò)能力。線(xiàn)性分組碼1、奇偶校驗(yàn)碼：65一般地，若有r個(gè)監(jiān)督碼元，就有r個(gè)監(jiān)督方程和r個(gè)相應(yīng)的校驗(yàn)子，可給出2r種狀態(tài)。對(duì)于一位誤碼來(lái)說(shuō)，非全0的2r-1種狀態(tài)可指明2r-1個(gè)誤碼位置。線(xiàn)性分組碼具有如下性質(zhì)：1、封閉性。任意兩個(gè)碼組的和還是許用的碼組。2、碼的最小距離等于非零碼的最小碼重。如果對(duì)于線(xiàn)性分組碼（n，k)中2r-1>=n，就有可能構(gòu)造出能糾正一位或一位以上誤碼的線(xiàn)性分組碼。一般地，若有r個(gè)監(jiān)督碼元，就有r個(gè)監(jiān)督方程和r個(gè)相應(yīng)的校驗(yàn)子662、漢明碼漢明碼(HammingCode)是由RichardHamming于1950年提出的，它屬于線(xiàn)性分組編碼方式，用以糾正單個(gè)錯(cuò)誤的線(xiàn)性分組碼，在軟件無(wú)線(xiàn)電中應(yīng)用廣泛。其基本原理是:將信息碼元與監(jiān)督碼元通過(guò)線(xiàn)性方程式聯(lián)系起來(lái)，每一個(gè)監(jiān)督位被編在傳輸碼字的特定比特位置上。系統(tǒng)對(duì)于錯(cuò)誤的數(shù)位無(wú)論是原有信息位中的，還是附加監(jiān)督位中的都能把它分離出來(lái)。

2、漢明碼漢明碼(HammingCode)是由Richar67它有以下特征：碼長(zhǎng)n=2m–1信息位數(shù)k=2m–m–1監(jiān)督碼位r=n–k=m最小距離d=3糾錯(cuò)能力t=1這里m為大于等于2的正整數(shù)，給定m后，即可構(gòu)造出具體的(n,k)漢明碼。假設(shè)k為4，要求能糾正一位誤碼，則根據(jù)條件2r-1>=n，得r=>3，現(xiàn)取3，則構(gòu)成（7，4）漢明碼。它有以下特征：68（7，4）漢明碼用a0、al、a2、a3、a4、a5、a6表示這7個(gè)碼元，用S1、S2、S3表示由三個(gè)監(jiān)督方程式計(jì)算得到的校正子，并假設(shè)三位S1、S2、S3校正子碼組與誤碼位置的對(duì)應(yīng)關(guān)系如下表所示。S1S2S3誤碼位置S1S2S3誤碼位置001a0101a4010a1110a5100a2111a6011a3000無(wú)錯(cuò)（7，4）碼校正子與誤碼位置（7，4）漢明碼用a0、al、a2、a3、a4、a5、a6表69當(dāng)誤碼位置在a2、a4、a5、a6時(shí)，校正子S1＝1；否則S1＝0。因此有:S1＝a6⊕a5⊕a4⊕a2同理有S2＝a6⊕a5⊕a3⊕a1S3＝a6⊕a4⊕a3⊕a0。由表可知：當(dāng)誤碼位置在a2、a4、a5、a6時(shí)，由表可知：70在編碼時(shí):a6、a5、a4、a3為信息碼元，a2、a1、a0為監(jiān)督碼元。則監(jiān)督碼元可由以下監(jiān)督方程唯一確定：0＝a6⊕a5⊕a4⊕a20＝a6⊕a5⊕a3⊕a10＝a6⊕a4⊕a3⊕a0

也即：a2＝a6⊕a5⊕a4a1＝a6⊕a5⊕a3a0＝a6⊕a4⊕a3在編碼時(shí):71由上面方程可得到16個(gè)許用碼組：在接收端收到每個(gè)碼組后，計(jì)算出S1、S2、S3，如果不全為0，則表示存在錯(cuò)誤，可以由下表確定錯(cuò)誤位置并予以糾正。信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111由上面方程可得到16個(gè)許用碼組：在接收端收到每個(gè)碼組后，計(jì)算72例如：收到碼組為0000011，可算出S1S2S3=011,由表可知在a3上有一誤碼。通過(guò)觀(guān)察可以看出，上述（7，4）碼的最小碼距為dmin＝3，它能糾正一個(gè)誤碼或檢測(cè)兩個(gè)誤碼。如果超出糾錯(cuò)能力則反而會(huì)因“亂糾”出現(xiàn)新的誤碼。例如：收到碼組為0000011，可算出S1S2S3=011,73監(jiān)督矩陣0＝a6⊕a5⊕a4⊕a20＝a6⊕a5⊕a3⊕a10＝a6⊕a4⊕a3⊕a0可寫(xiě)成：0＝1·a6+1·a5+1·a4+0·a3+1·a2+0·a1+0·a00＝1·a6+1·a5+0·a4+1·a3+0·a2+1·a1+0·a00＝1·a6+0·a5+1·a4+1·a3+0·a2+0·a1+1·a0用矩陣表示為：111010001101010a6a5a4a3a2a1a0T=010110010簡(jiǎn)化為：HAT=0T其中H稱(chēng)為監(jiān)督矩陣監(jiān)督矩陣0＝a6⊕a5⊕a4⊕a274H可以分成兩部分：11101001101010=[PIr]1011001其中P為信息位矩陣，Ir為rXr階的單位矩陣生成矩陣G：G=[IkPT]根據(jù)生成矩陣和已知的信息碼元可產(chǎn)生整個(gè)碼組。A=[a6a5a4a3]GH可以分成兩部分：111010075擴(kuò)展?jié)h明碼漢明碼如果再加上一位對(duì)所有碼元都進(jìn)行校驗(yàn)的監(jiān)督位，則監(jiān)督碼元由m增至m+1，信息位不變，碼長(zhǎng)由2m–1增至2m，通常把這種（2m，2m–1–m）碼稱(chēng)為擴(kuò)展?jié)h明碼。擴(kuò)展?jié)h明碼的最小碼距增加為4，能糾正l位錯(cuò)誤同時(shí)檢測(cè)2位錯(cuò)誤。簡(jiǎn)稱(chēng)糾1檢2錯(cuò)碼。其實(shí)質(zhì)上是在原漢明碼的每個(gè)碼組后面增加1位偶監(jiān)督碼元。例如(7,4)漢明碼可變成(8,4)擴(kuò)展?jié)h明碼（又稱(chēng)增余漢明碼）。

擴(kuò)展?jié)h明碼漢明碼如果再加上一位對(duì)所有碼元都進(jìn)行校驗(yàn)的監(jiān)督位，76循環(huán)碼：循環(huán)碼是一種特殊的線(xiàn)性分組碼，它除了具有群碼的封閉性外，還有一個(gè)特性就是循環(huán)性。按模運(yùn)算循環(huán)碼：循環(huán)碼是一種特殊的線(xiàn)性分組碼，它除了具有群碼的封閉性77為了用代數(shù)理論研究循環(huán)碼，可將碼組用多項(xiàng)式來(lái)表示，稱(chēng)為碼多項(xiàng)式。設(shè)許用碼組C=（cn–1

cn–2…clc0）對(duì)應(yīng)的碼多項(xiàng)式可表示為

C（x）=cn–1

xn–1+cn–2

xn–2+…+clx+c0其中多項(xiàng)式的系數(shù)就是碼字各分量的值，x為一個(gè)任意實(shí)變量，其冪次i代表該分量所在位置。為了用代數(shù)理論研究循環(huán)碼，可將碼組用多項(xiàng)式來(lái)表示，稱(chēng)為碼多項(xiàng)78循環(huán)碼中的幾個(gè)定理1、若C(x)是n長(zhǎng)循環(huán)碼中的一個(gè)碼多項(xiàng)式，則xiC(x)按模（xn+1）運(yùn)算的余式必為循環(huán)碼中另一碼多項(xiàng)式。2、一個(gè)二進(jìn)制中（n，k）循環(huán)碼中有惟一的r=n-k次多項(xiàng)式g(x)，且其常數(shù)項(xiàng)為l。如果一個(gè)碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱(chēng)g(x)生成該碼，且稱(chēng)g(x)為該碼的生成多項(xiàng)式，所對(duì)應(yīng)的碼字成為生成子或生成子序列。

3、設(shè)g(x)是（n，k）循環(huán)碼[C(x)]中的一個(gè)次數(shù)最低的多項(xiàng)式（g(x)≠0），則該循環(huán)碼由g(x)生成，并且g(x)是（xn+1）的一個(gè)因式。

循環(huán)碼中的幾個(gè)定理1、若C(x)是n長(zhǎng)循環(huán)碼中的一個(gè)碼多項(xiàng)式79從以上討論中，可得到幾個(gè)重要結(jié)論：

①在二元或GF(2)上找一個(gè)(n,k)循環(huán)碼，就是找一個(gè)能除盡xn+1的n-k次首1多項(xiàng)式g(x)，為了尋