差錯控制編碼

差錯控制編碼第一頁，共四十八頁，2022年，8月28日8.1差錯控制編碼的基本概念數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字通信的有效性，以及為了使模擬信號數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。數(shù)字信號在傳輸?shù)倪^程中，加性噪聲、碼間串擾等都會產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。2023/2/42第二頁，共四十八頁，2022年，8月28日差錯控制編碼的基本思想：在發(fā)送端根據(jù)要傳輸?shù)臄?shù)字序列（信息碼元）按一定的規(guī)律加入多余碼元，使原來不相關(guān)的數(shù)字序列變?yōu)橄嚓P(guān)，然后把這些多余碼元和有關(guān)的信息碼元一起傳送，接收端根據(jù)信息碼元與多余碼元之間的相關(guān)規(guī)則進行檢驗，從而發(fā)現(xiàn)錯誤。這時，或者通過反饋信道要求對方重發(fā)有錯的信息，以進行糾錯；或者由接收端的譯碼器自動把錯誤糾正。這些多余碼元稱為校驗元或監(jiān)督元。它的加入不改變信息本身，也就是說，它不傳送新的信息，它的作用只是使信道譯碼器能夠檢測和糾正差錯，從而控制系統(tǒng)差錯概率，提高可靠性但這是以系統(tǒng)的有效性為代價的。2023/2/43第三頁，共四十八頁，2022年，8月28日8.1.1差錯控制方式2023/2/44第四頁，共四十八頁，2022年，8月28日前向糾錯方式前向糾錯方式記作FEC（ForwordErrorCorrection）發(fā)端編碼器將數(shù)字信息按一定規(guī)則附加多余碼元，組成有糾錯能力的碼，發(fā)端發(fā)送能夠糾正錯誤的碼；收端譯碼器按預先規(guī)定的規(guī)則譯碼；若發(fā)現(xiàn)錯誤，確定其出錯位置并進行糾正。優(yōu)點：單向傳輸，只有正向信道；適合于只能提供單向信道的場合；一點發(fā)送多點接收的同播方式；譯碼延遲固定，適用于實時傳輸系統(tǒng)。缺點：編譯碼設(shè)備復雜，為了糾正較多的錯誤，需要附加的多余碼元較多，因而傳輸效率較低。2023/2/45第五頁，共四十八頁，2022年，8月28日檢錯重發(fā)方式又稱自動請求重傳方式，記作ARQ（AutomaticRepeatRequest）。發(fā)端編碼器將數(shù)字信息按一定規(guī)則附加多余碼元，使之具有一定的檢錯能力，收端譯碼器按一定規(guī)則對數(shù)據(jù)碼元組進行錯誤判決，并把判決結(jié)果形成應答信號，通過反饋信道回送到發(fā)端，發(fā)端根據(jù)收到的應答信號，把收端認為有錯的那組數(shù)據(jù)碼元再次重傳，直到碼元組無錯為止。優(yōu)點：只需要少量的多余碼元就能獲得極低的輸出誤碼率，并且其成本和復雜性均比前向糾錯低缺點。缺點：必須提供反向信道；不能進行同播（一點發(fā)多點收），收發(fā)端應有緩沖存儲器和控制器；此外當信道干擾較大時，整個系統(tǒng)可能處在重傳循環(huán)中，因而通信效率降低，信息傳輸連貫性差，不適于實時傳輸系統(tǒng)，主要在計算機通信中應用。常用的檢錯重發(fā)系統(tǒng)有三種，即停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)。2023/2/46第六頁，共四十八頁，2022年，8月28日第七頁，共四十八頁，2022年，8月28日混合糾錯方式混合糾錯方式記作HEC（HybridErrorCorrection）發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點，可達到較低的誤碼率，因此，近年來得到廣泛應用。在實際通信系統(tǒng)中，選擇那種差錯控制方式，要視具體情況而定，可以根據(jù)信源的性質(zhì)，信息傳輸?shù)奶攸c信道干擾的種類和對誤碼率的要求而適當選擇差錯控制方式。2023/2/48第八頁，共四十八頁，2022年，8月28日8.1.2差錯控制編碼的分類根據(jù)信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼，否則為非線性碼。

根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。2023/2/49第九頁，共四十八頁，2022年，8月28日8.1.3幾種簡單的檢錯碼(1)奇偶監(jiān)督碼設(shè)碼字A=［an-1,an-2,…,a1,a0］，對偶監(jiān)督碼有：

an-1⊕

an-2⊕…⊕

a1⊕

a0=0奇監(jiān)督碼情況相似，只是碼組中“1”的數(shù)目為奇數(shù)，即滿足條件：

an-1⊕

an-2⊕…⊕

a1⊕

a0=1而檢錯能力與偶監(jiān)督碼相同。2023/2/410第十頁，共四十八頁，2022年，8月28日奇偶監(jiān)督碼編碼方法：把信息碼元分組，在每組信息碼元的后面附加一位監(jiān)督碼元，使得碼組中1的數(shù)目為奇數(shù)或偶數(shù)即可編碼規(guī)則：碼組長度n；信息位n-1

特點：是一種能發(fā)現(xiàn)奇數(shù)個差錯的分組碼；n

較大，即編碼碼組較長時，編碼效率接近于1;（n-1）/n

——

信息碼元比碼組碼元適用于檢測隨機的零星錯碼——加性白噪聲造成的2023/2/411第十一頁，共四十八頁，2022年，8月28日8.1.3幾種簡單的檢錯碼(2)二維奇偶監(jiān)督碼(6,11)行列監(jiān)督碼2023/2/412第十二頁，共四十八頁，2022年，8月28日二維奇偶監(jiān)督碼

編碼方法：把碼元排成方陣，按行列進行奇偶校驗

——分別附加一位監(jiān)督碼元特點：不僅可檢測每行（每列）中奇數(shù)個錯誤，而且可通過水平監(jiān)督和垂直監(jiān)督來確定錯碼的位置糾正僅一行（一列）出現(xiàn)的奇數(shù)個錯誤通過水平監(jiān)督和垂直監(jiān)督的關(guān)系可以發(fā)現(xiàn)單行中出現(xiàn)的偶數(shù)個錯誤；但不能發(fā)現(xiàn)構(gòu)成矩形的4個錯誤碼元適用于突發(fā)差錯——由突發(fā)干擾（突發(fā)脈沖，如：閃電，電火花等）在短時間內(nèi)錯碼成串出現(xiàn)，在某一行中出現(xiàn)多個錯碼2023/2/413第十三頁，共四十八頁，2022年，8月28日8.1.3幾種簡單的檢錯碼(3)重復碼在每位信息碼元之后，用簡單重復多次的方法編碼。例：重復兩次時，用111傳輸1碼，用000傳輸0碼

編碼方法：每位信息碼元簡單重復多次；收端譯碼采用多數(shù)表決法；例：重復2次特點：糾正1個錯，檢出2個錯2023/2/414第十四頁，共四十八頁，2022年，8月28日8.1.3幾種簡單的檢錯碼(4)恒比碼碼字中1的數(shù)目與0的數(shù)目保持恒定比例的碼稱為恒比碼。這種碼在檢測時，只要計算接收碼元中1的數(shù)目是否正確，就知道有無錯誤。

2023/2/415第十五頁，共四十八頁，2022年，8月28日恒比碼例：5中取3恒比碼——用于電報電碼每個碼組長度為5，共有25=32種不同的碼組，其中有3個1的碼組為可用碼組，共有10種——

表示10個阿拉伯數(shù)字，用它拼成漢字（每4阿拉伯數(shù)字組成1個漢字電碼）；其余的22個為禁用碼組。特點：簡單；除了1錯為0與0錯為1成對出現(xiàn)（對換性）差錯不能檢測外，其它任何奇數(shù)個或偶數(shù)個錯碼都可以被檢測出來。只適用于傳輸種類較少且有固定代碼的字符，而不適用于表示由信源來的二進制隨機，數(shù)字序列。2023/2/416第十六頁，共四十八頁，2022年，8月28日8.1.3幾種簡單的檢錯碼(4)ISBN國際統(tǒng)一圖書編號例ISBN0－471－02977－72023/2/417第十七頁，共四十八頁，2022年，8月28日8.1.4檢錯和糾錯的基本原理如用三位二進制編碼來代表八個字母

000A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位發(fā)生錯誤，都會使傳輸字母錯誤如用三位字母傳四個字母000A 011 B 101 C 110 D發(fā)生一位錯誤，準用碼字將變成禁用碼字，接收端就能知道出錯，但是不能糾錯。如果進一步將許用碼組限制為兩種000A111B－檢錯和糾錯能力是用信息量的冗余度來換取的。2023/2/418第十八頁，共四十八頁，2022年，8月28日檢錯和糾錯的基本原理檢錯和糾錯能力是用信息量的冗余度換取的——與碼組之間的差別有關(guān)；不同的編碼方法和形式，檢錯和糾錯能力不同。例：

n=3，共有8種組合，都用于傳輸消息，在傳輸過程中若發(fā)生一個誤碼，則一種碼組就會錯誤地變成另一種碼組，但接收端卻不能發(fā)現(xiàn)錯誤，因為任何一個碼組都是許用碼組。2023/2/419第十九頁，共四十八頁，2022年，8月28日

在差錯控制編碼中，定義碼組中非零碼元的數(shù)目為碼字的漢明(Hamming)重量，簡稱碼重。例如，碼字10110，碼重w=3。定義兩個等長碼組之間相應位取值不同的數(shù)目為這兩個碼組的漢明(Hamming)距離，簡稱碼距。例如11000與10011之間的距離d=3。碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用dmin表示。最小碼距是碼的一個重要參數(shù)，它是衡量碼檢錯、糾錯能力的依據(jù)。第二十頁，共四十八頁，2022年，8月28日最小碼距與檢錯糾錯能力的關(guān)系

碼組內(nèi)的距離反映了碼組之間的差別，最小距離越大，說明兩個碼組間的最小差別越大，或者說其中一個碼組錯為另一個碼組的可能性就越小，那么其檢錯和糾錯能力也就越強，因此可以說最小碼距是衡量一種糾錯編碼的檢錯，糾錯能力大小的標準。2023/2/421第二十一頁，共四十八頁，2022年，8月28日

碼的最小距離直接關(guān)系著碼的檢錯和糾錯能力；任一(n,k)分組碼，若要在碼字內(nèi):(1)檢測e個隨機錯誤，則要求碼的最小距離dmin≥e+1;(2)糾正t個隨機錯誤，則要求碼的最小距離dmin≥2t+1;(3)糾正t個同時檢測e(≥t)個隨機錯誤，則要求碼的最小距離dmin≥t+e+1。t1eAB第二十二頁，共四十八頁，2022年，8月28日用差錯控制編碼提高通信系統(tǒng)的可靠性，是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性:Rc=k/n其中,k是信息元的個數(shù)，n為碼長。對糾錯碼的基本要求是:檢錯和糾錯能力盡量強；編碼效率盡量高；編碼規(guī)律盡量簡單。實際中要根據(jù)具體指標要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。編碼效率2023/2/423第二十三頁，共四十八頁，2022年，8月28日8.2線性分組碼線性分組碼的構(gòu)成將信息序列劃分為等長(k位)的序列段共有2k個不同的序列段，在每一信息段之后，附加m位監(jiān)督元，構(gòu)成長度

n=k+m的分組碼(n，k)

監(jiān)督元與信息碼元為線性關(guān)系2023/2/424第二十四頁，共四十八頁，2022年，8月28日例

信息元長度k=3共有2k=8個不同的信息組每組信息組加4個監(jiān)督元，構(gòu)成一個長度為7

的(7，3)線性分組碼。設(shè)：每組信息元為C1C2C3監(jiān)督元為C4C5C6C7

根據(jù)下列線性方程組求監(jiān)督元

C4=C1+C3C5=C1+C2+C3C6=C1+C2C7=C2+C32023/2/425第二十五頁，共四十八頁，2022年，8月28日例

(7，3)碼有8個信息組，信息組按上方程組求得每個信息組的4個監(jiān)督元，得到(7，3)碼的所有8個碼字信息組碼元

00000000000010011101010010011101101110101001001110101101001111011010011111110100重要特性，線性碼有封閉性

2023/2/426第二十六頁，共四十八頁，2022年，8月28日8.2線性分組碼設(shè)分組碼由n位碼組構(gòu)成，記為c1，c2，…，cn，信息碼組由k位碼組成，記為d1，d2，…，dk。則該分組碼記為（n，k）碼。碼組和信息碼組可用行矩陣C和D表示若為線性分組碼，C中的n個元素都是由D中的k個元素經(jīng)線性組合形成的?？捎靡宦?lián)立方程表示為2023/2/427第二十七頁，共四十八頁，2022年，8月28日將碼組C寫成矩陣形式矩陣G稱為生成矩陣，它是一個k×n的矩陣第二十八頁，共四十八頁，2022年，8月28日生成矩陣G2023/2/429第二十九頁，共四十八頁，2022年，8月28日生成矩陣GIk

單位矩陣，k行k列(kxk階)P矩陣，k行m列(kxm階)編碼前k位，編碼后有n位，2n>2k；選擇P矩陣，可得到有較強檢錯糾錯能力，實現(xiàn)方法盡可能簡單，編碼效率又高的線性分組碼由于線性碼具有封閉性，故任何二個碼組之間的距離必須與某一個碼組中“1”的個數(shù)相等，而碼組中非零碼元的數(shù)目“1”的個數(shù)為碼組的重量（碼重）所以線性碼任意二個碼字之間的距離必須等于碼中某一個碼字的重量——線性碼最小碼距正好等于非零碼的最小碼重估算線性碼的差錯控制能力：求最小碼距——最小碼重2023/2/430第三十頁，共四十八頁，2022年，8月28日例

已知（6，3）碼的生成距陣，求：編碼碼組2023/2/431第三十一頁，共四十八頁，2022年，8月28日監(jiān)督矩陣H校驗矩陣或監(jiān)督矩陣H：mxn階PT:m行k列

k+m=n列2023/2/432第三十二頁，共四十八頁，2022年，8月28日伴隨式（校正子）S

設(shè)發(fā)送碼組C=［cn-1,cn-2,…,c1,c0］，在傳輸過程中可能發(fā)生誤碼。接收碼組R=［rn-1,rn-2,…,r1,r0］，則收發(fā)碼組之差定義為錯誤圖樣E，也稱為誤差矢量，即E=R–C=［en-1,en-2,…,e1,e0］，且

當ri=ci

當ri≠ci

令S=RHT，稱為伴隨式或校正子

S=RHT=CHT⊕

EHT=EHT

S只與錯誤圖形有關(guān)，與發(fā)送的碼組C無關(guān)

HT

：nxm階；E：1xn階；S：1xm階；S=[s1s2

……sm]

解得誤差矢量E，求得糾錯后的碼組C=R⊕E2023/2/433第三十三頁，共四十八頁，2022年，8月28日檢錯與糾錯檢錯：當碼組出現(xiàn)錯誤S為非零矢量糾錯：

S=RHT=CHT⊕EHT=EHT

S與E之間有著確定的線性關(guān)系——由H矩陣確定（也就是與G（P）矩陣有關(guān)）

S=[s1s2

……sm]共有2m種不同的形式，除全

0外，可代表2m-1種有錯誤的圖形信息碼組有2k個錯誤圖形，有多種不同的形式可能有2k種解答；為了選擇正確的結(jié)果，要使用最大似然比準則，選擇與R最相似的C（與R距離最小的碼組——E是1碼最小的矢量）。2023/2/434第三十四頁，共四十八頁，2022年，8月28日例：（6，3）碼2023/2/435第三十五頁，共四十八頁，2022年，8月28日S與E對照表ES000000000100000101010000011001000110000100100000010010000001001100010111

（6，3）碼具有糾1位錯的能力發(fā)生1個錯誤的情況：

S是HT的第i行，說明R中第i位產(chǎn)生了錯誤，可以把它糾正發(fā)生2個錯誤的情況：除S=111對應第1，5位有錯其它的雙錯不能得到糾正

例：

接收碼組R[111011]

2023/2/436第三十六頁，共四十八頁，2022年，8月28日查表法譯碼器的原理S=RHT=CHT⊕EHT=EHT算出伴隨式S與最小碼重的差錯矢量E的對照表，提供譯碼使用2023/2/437第三十七頁，共四十八頁，2022年，8月28日漢明碼按上述方法構(gòu)造的能糾正單個錯誤的線性分組碼稱為漢明碼。對于線性分組碼，為了指示所有單錯位置和無錯的情況，必須滿足不等式漢明碼具有以下特點：漢明碼的編碼效率2023/2/438第三十八頁，共四十八頁，2022年，8月28日漢明界如果碼組有糾t個差錯的能力，則應能指出無錯、單錯到t個差錯所有可能的情況，校驗位數(shù)m應滿足不等式：－漢明界，是糾正t個差錯的一個必要條件2023/2/439第三十九頁，共四十八頁，2022年，8月28日8.3循環(huán)碼特點線性分組碼循環(huán)性——任一許用碼字經(jīng)過循環(huán)移位后，得到的碼組仍為一個許用碼組如是循環(huán)碼的一許用碼組則也是一許用碼組移位i次得到也是許用碼組2023/2/440第四十頁，共四十八頁，2022年，8月28日8.3.1循環(huán)碼的特點及表達碼多項式表示以此類推，碼組C移位i次，相應的碼多項式c(i)(x)是xi·c(x)除以（xn+1)后的余式。在模（xn+1)意義下，若c(x)是碼多項式，則xic(x)都是碼多項式。2023/2/441第四十一頁，共四十八頁，2022年，8月28日循環(huán)碼的編碼過程一個k位的信息碼組可用信息多項式表示假設(shè)碼組多項式可表示為如果(χn+1)是g(χ)的倍式

C（1）(χ)=χd(χ)g(χ)+aC1g(χ)=[χd(χ)+aC1]g(χ)=d1(χ)g(χ)d1(χ)對應某個信息碼組2023/2/442第四十二頁，共四十八頁，2022年，8月28日生成多項式g(χ)

(χn+1)是g(χ)的倍式，且g(χ)為n-k次多項式，所以對(χn+1)進行因式分解，便可得到相應的g(χ)。對(χn+1)進行因式分解可由計算機完成，有表格給出。由信息多項式求解碼多項式

C(χ)=d(χ)g(χ)

n-1次k-1次n-k次2023/2/443第四十三頁，共四十八頁，2022年，8月28日例(7，4)——n=7

k=4m=n-k=3g(χ)應為(χ7+1)的3次因式χ７

+1=(χ+1)(χ３+

χ+1)(χ３+

χ２

+1)g1(χ)=(χ３+

χ+1)g2(χ)=(χ３+

χ２

+1)D=[1010]——d(χ)=(χ３+

χ)C1(χ)=d(χ)g1(χ)=(χ３+

χ)(χ３+

χ+1)

=χ６+

χ３

+

χ２+

χ

——

C1=[1001110]C2(χ)=d(χ)g2(χ)=(χ３+

χ)(χ３+

χ２

+1)

=χ６+χ５

+χ４+χ——

C２

=[1110010]注：

1.不同的生成多項式得到不同的碼組

2.由此編碼法得到的不是系統(tǒng)碼（前4位不是D=[1010]）2023/2/444