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

第十二章差錯控制編碼

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

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

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

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

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

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

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

對具體的糾錯碼，可以從不同角度將其分類，下圖所示即為糾錯碼的分類情況。糾錯碼的分類11圖5-6糾錯碼的分類

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

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

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

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

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

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

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

10010和00011之間：d=2

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

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

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

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

這時d0

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

2、漢明碼漢明碼(HammingCode)是由Richar24它有以下特征：碼長n=2m–1信息位數(shù)k=2m–m–1監(jiān)督碼位r=n–k=m最小距離d=3糾錯能力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個碼元，用S1、S2、S3表示由三個監(jiān)督方程式計算得到的校正子，并假設(shè)三位S1、S2、S3校正子碼組與誤碼位置的對應(yīng)關(guān)系如下表所示。S1S2S3誤碼位置S1S2S3誤碼位置001a0101a4010a1110a5100a2111a6011a3000無錯（7，4）碼校正子與誤碼位置（7，4）漢明碼用a0、al、a2、a3、a4、a5、a6表26當(dāng)誤碼位置在a2、a4、a5、a6時，校正子S1＝1；否則S1＝0。因此有:S1＝a6⊕a5⊕a4⊕a2同理有S2＝a6⊕a5⊕a3⊕a1S3＝a6⊕a4⊕a3⊕a0。由表可知：當(dāng)誤碼位置在a2、a4、a5、a6時，由表可知：27在編碼時: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在編碼時:28由上面方程可得到16個許用碼組：在接收端收到每個碼組后，計算出S1、S2、S3，如果不全為0，則表示存在錯誤，可以由下表確定錯誤位置并予以糾正。信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111由上面方程可得到16個許用碼組：在接收端收到每個碼組后，計算29例如：收到碼組為0000011，可算出S1S2S3=011,由表可知在a3上有一誤碼。通過觀察可以看出，上述（7，4）碼的最小碼距為dmin＝3，它能糾正一個誤碼或檢測兩個誤碼。如果超出糾錯能力則反而會因“亂糾”出現(xiàn)新的誤碼。例如：收到碼組為0000011，可算出S1S2S3=011,30監(jiān)督矩陣0＝a6⊕a5⊕a4⊕a20＝a6⊕a5⊕a3⊕a10＝a6⊕a4⊕a3⊕a0可寫成：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簡化為：HAT=0T其中H稱為監(jiān)督矩陣監(jiān)督矩陣0＝a6⊕a5⊕a4⊕a231H可以分成兩部分：11101001101010=[PIr]1011001其中P為信息位矩陣，Ir為rXr階的單位矩陣生成矩陣G：G=[IkPT]根據(jù)生成矩陣和已知的信息碼元可產(chǎn)生整個碼組。A=[a6a5a4a3]GH可以分成兩部分：111010032擴(kuò)展?jié)h明碼漢明碼如果再加上一位對所有碼元都進(jìn)行校驗(yàn)的監(jiān)督位，則監(jiān)督碼元由m增至m+1，信息位不變，碼長由2m–1增至2m，通常把這種（2m，2m–1–m）碼稱為擴(kuò)展?jié)h明碼。擴(kuò)展?jié)h明碼的最小碼距增加為4，能糾正l位錯誤同時檢測2位錯誤。簡稱糾1檢2錯碼。其實(shí)質(zhì)上是在原漢明碼的每個碼組后面增加1位偶監(jiān)督碼元。例如(7,4)漢明碼可變成(8,4)擴(kuò)展?jié)h明碼（又稱增余漢明碼）。

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

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

C（x）=cn–1

xn–1+cn–2

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

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

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

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

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

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

3+x+1）（x

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

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

g(x)，x2

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

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

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

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

。

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

即，在m(x)后面添加n個02、冗余碼的計算1)把信息碼元多項式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在接收端的檢錯設(shè)接收端接收到的數(shù)據(jù)為R(x)那么，進(jìn)行R(x)/g(x)運(yùn)算如果：1、余數(shù)為零

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

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

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

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

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

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

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

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

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

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

對具體的糾錯碼，可以從不同角度將其分類，下圖所示即為糾錯碼的分類情況。糾錯碼的分類54圖5-6糾錯碼的分類

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

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

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

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

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

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

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

10010和00011之間：d=2

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

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

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

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

這時d0

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

2、漢明碼漢明碼(HammingCode)是由Richar67它有以下特征：碼長n=2m–1信息位數(shù)k=2m–m–1監(jiān)督碼位r=n–k=m最小距離d=3糾錯能力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個碼元，用S1、S2、S3表示由三個監(jiān)督方程式計算得到的校正子，并假設(shè)三位S1、S2、S3校正子碼組與誤碼位置的對應(yīng)關(guān)系如下表所示。S1S2S3誤碼位置S1S2S3誤碼位置001a0101a4010a1110a5100a2111a6011a3000無錯（7，4）碼校正子與誤碼位置（7，4）漢明碼用a0、al、a2、a3、a4、a5、a6表69當(dāng)誤碼位置在a2、a4、a5、a6時，校正子S1＝1；否則S1＝0。因此有:S1＝a6⊕a5⊕a4⊕a2同理有S2＝a6⊕a5⊕a3⊕a1S3＝a6⊕a4⊕a3⊕a0。由表可知：當(dāng)誤碼位置在a2、a4、a5、a6時，由表可知：70在編碼時: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在編碼時:71由上面方程可得到16個許用碼組：在接收端收到每個碼組后，計算出S1、S2、S3，如果不全為0，則表示存在錯誤，可以由下表確定錯誤位置并予以糾正。信息位監(jiān)督位信息位監(jiān)督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100100011010001010110011100001110111011010101100010001001101010111100110111101111111100010001001010100111由上面方程可得到16個許用碼組：在接收端收到每個碼組后，計算72例如：收到碼組為0000011，可算出S1S2S3=011,由表可知在a3上有一誤碼。通過觀察可以看出，上述（7，4）碼的最小碼距為dmin＝3，它能糾正一個誤碼或檢測兩個誤碼。如果超出糾錯能力則反而會因“亂糾”出現(xiàn)新的誤碼。例如：收到碼組為0000011，可算出S1S2S3=011,73監(jiān)督矩陣0＝a6⊕a5⊕a4⊕a20＝a6⊕a5⊕a3⊕a10＝a6⊕a4⊕a3⊕a0可寫成：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簡化為：HAT=0T其中H稱為監(jiān)督矩陣監(jiān)督矩陣0＝a6⊕a5⊕a4⊕a274H可以分成兩部分：11101001101010=[PIr]1011001其中P為信息位矩陣，Ir為rXr階的單位矩陣生成矩陣G：G=[IkPT]根據(jù)生成矩陣和已知的信息碼元可產(chǎn)生整個碼組。A=[a6a5a4a3]GH可以分成兩部分：111010075擴(kuò)展?jié)h明碼漢明碼如果再加上一位對所有碼元都進(jìn)行校驗(yàn)的監(jiān)督位，則監(jiān)督碼元由m增至m+1，信息位不變，碼長由2m–1增至2m，通常把這種（2m，2m–1–m）碼稱為擴(kuò)展?jié)h明碼。擴(kuò)展?jié)h明碼的最小碼距增加為4，能糾正l位錯誤同時檢測2位錯誤。簡稱糾1檢2錯碼。其實(shí)質(zhì)上是在原漢明碼的每個碼組后面增加1位偶監(jiān)督碼元。例如(7,4)漢明碼可變成(8,4)擴(kuò)展?jié)h明碼（又稱增余漢明碼）。

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

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

C（x）=cn–1

xn–1+cn–2

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

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

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

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