差錯控制編碼ppt課件.ppt

1、第八章 差錯控制編碼,1,2020年8月30日,2,8.1 差錯控制編碼的基本概念,數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。 信源編碼是為了提高數(shù)字通信的有效性，以及為了使模擬信號數(shù)字化而采取的編碼。 信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。 數(shù)字信號在傳輸?shù)倪^程中，加性噪聲、碼間串?dāng)_等都會產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。,2020年8月30日,3,差錯控制編碼的基本思想：,在發(fā)送端根據(jù)要傳輸?shù)臄?shù)字序列（信息碼元）按一定的規(guī)律加入多余碼元，使原來不相關(guān)

2、的數(shù)字序列變?yōu)橄嚓P(guān)，然后把這些多余碼元和有關(guān)的信息碼元一起傳送，接收端根據(jù)信息碼元與多余碼元之間的相關(guān)規(guī)則進(jìn)行檢驗(yàn)，從而發(fā)現(xiàn)錯誤。這時，或者通過反饋信道要求對方重發(fā)有錯的信息，以進(jìn)行糾錯；或者由接收端的譯碼器自動把錯誤糾正。 這些多余碼元稱為校驗(yàn)元或監(jiān)督元。它的加入不改變信息本身，也就是說，它不傳送新的信息，它的作用只是使信道譯碼器能夠檢測和糾正差錯，從而控制系統(tǒng)差錯概率，提高可靠性但這是以系統(tǒng)的有效性為代價的。,2020年8月30日,4,8.1.1 差錯控制方式,2020年8月30日,5,前向糾錯方式,前向糾錯方式記作FEC（Forword Error Correction） 發(fā)端編碼器將數(shù)

3、字信息按一定規(guī)則附加多余碼元，組成有糾錯能力的碼，發(fā)端發(fā)送能夠糾正錯誤的碼；收端譯碼器按預(yù)先規(guī)定的規(guī)則譯碼；若發(fā)現(xiàn)錯誤，確定其出錯位置并進(jìn)行糾正。 優(yōu)點(diǎn)： 單向傳輸，只有正向信道；適合于只能提供單向信道的場合；一點(diǎn)發(fā)送多點(diǎn)接收的同播方式；譯碼延遲固定，適用于實(shí)時傳輸系統(tǒng)。 缺點(diǎn)： 編譯碼設(shè)備復(fù)雜，為了糾正較多的錯誤，需要附加的多余碼元較多，因而傳輸效率較低。,2020年8月30日,6,檢錯重發(fā)方式,又稱自動請求重傳方式，記作ARQ（Automatic Repeat Request）。 發(fā)端編碼器將數(shù)字信息按一定規(guī)則附加多余碼元，使之具有一定的檢錯能力，收端譯碼器按一定規(guī)則對數(shù)據(jù)碼元組進(jìn)行錯誤判

4、決，并把判決結(jié)果形成應(yīng)答信號，通過反饋信道回送到發(fā)端，發(fā)端根據(jù)收到的應(yīng)答信號，把收端認(rèn)為有錯的那組數(shù)據(jù)碼元再次重傳，直到碼元組無錯為止。 優(yōu)點(diǎn)： 只需要少量的多余碼元就能獲得極低的輸出誤碼率，并且其成本和復(fù)雜性均比前向糾錯低缺點(diǎn)。 缺點(diǎn)： 必須提供反向信道；不能進(jìn)行同播（一點(diǎn)發(fā)多點(diǎn)收），收發(fā)端應(yīng)有緩沖存儲器和控制器；此外當(dāng)信道干擾較大時，整個系統(tǒng)可能處在重傳循環(huán)中，因而通信效率降低，信息傳輸連貫性差，不適于實(shí)時傳輸系統(tǒng)，主要在計(jì)算機(jī)通信中應(yīng)用。 常用的檢錯重發(fā)系統(tǒng)有三種，即停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)。,7,2020年8月30日,8,混合糾錯方式,混合糾錯方式記作HEC（Hybrid Er

5、ror Correction） 發(fā)端發(fā)送具有自動糾錯同時又具有檢錯能力的碼。收端收到碼后，檢查差錯情況，如果錯誤在碼的糾錯能力范圍以內(nèi)，則自動糾錯，如果超過了碼的糾錯能力但能檢測出來，則經(jīng)過反饋信道請求發(fā)端重發(fā)。 這種方式具有自動糾錯和檢錯重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼率，因此，近年來得到廣泛應(yīng)用。 在實(shí)際通信系統(tǒng)中，選擇那種差錯控制方式，要視具體情況而定，可以根據(jù)信源的性質(zhì)，信息傳輸?shù)奶攸c(diǎn)信道干擾的種類和對誤碼率的要求而適當(dāng)選擇差錯控制方式。,2020年8月30日,9,8.1.2 差錯控制編碼的分類,根據(jù)信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程

6、式，則稱為線性碼，否則為非線性碼。 根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。 根據(jù)碼的用途，可分為檢錯碼和糾錯碼。檢錯碼以檢錯為目的，不一定能糾錯；而糾錯碼以糾錯為目的，一定能檢錯。,2020年8月30日,10,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)督碼相

7、同。,2020年8月30日,11,奇偶監(jiān)督碼,編碼方法：把信息碼元分組，在每組信息碼元 的后面附加一位監(jiān)督碼元，使得 碼組中1的數(shù)目為奇數(shù)或偶數(shù)即可 編碼規(guī)則：碼組長度n；信息位n-1 特點(diǎn)：是一種能發(fā)現(xiàn)奇數(shù)個差錯的分組碼；n 較大，即編碼碼組較長時，編碼效率 接近于1;（n-1）/n 信息碼元比 碼組碼元 適用于檢測隨機(jī)的零星錯碼加性白噪聲造 成的,2020年8月30日,12,8.1.3 幾種簡單的檢錯碼(2),二維奇偶監(jiān)督碼,(6,11)行列監(jiān)督碼,2020年8月30日,13,二維奇偶監(jiān)督碼,編碼方法：把碼元排成方陣，按行列進(jìn)行奇偶校驗(yàn) 分別附加一位監(jiān)督碼元 特點(diǎn)：不僅可檢測每行（每列）中

8、奇數(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)多個錯碼,2020年8月30日,14,8.1.3 幾種簡單的檢錯碼(3),重復(fù)碼 在每位信息碼元之后，用簡單重復(fù)多次的方法編碼。 例：重復(fù)兩次時，用111傳輸1碼，用000傳輸0碼 編碼方法：每位信息碼元簡單重復(fù)多次； 收端 譯碼采用多數(shù)表決法； 例：重復(fù)2次 特點(diǎn)：糾正1個錯，檢出2個錯,2020年8月30

9、日,15,8.1.3 幾種簡單的檢錯碼(4),恒比碼,碼字中 1 的數(shù)目與 0 的數(shù)目保持恒定比例的碼稱為恒比碼。 這種碼在檢測時，只要計(jì)算接收碼元中 1 的數(shù)目是否正確， 就知道有無錯誤。,2020年8月30日,16,恒比碼,例：5中取3恒比碼用于電報(bào)電碼 每個碼組長度為5，共有25=32種不同的碼組， 其中有3個1的碼組為可用碼組，共有10種 表示10個阿拉伯?dāng)?shù)字，用它拼成漢字（每4阿拉 伯?dāng)?shù)字組成1個漢字電碼）；其余的22個為禁用 碼組。 特點(diǎn)：簡單；除了1錯為0與0錯為1成對出現(xiàn)（對換 性）差錯不能檢測外，其它任何奇數(shù)個或偶數(shù) 個錯碼都可以被檢測出來。 只適用于傳輸種類較少且有固定代碼

10、的字符，而不適用于表示由信源來的二進(jìn)制隨機(jī)，數(shù)字序列。,2020年8月30日,17,8.1.3 幾種簡單的檢錯碼(4),ISBN國際統(tǒng)一圖書編號 例 ISBN 0471029777,2020年8月30日,18,8.1.4 檢錯和糾錯的基本原理,如用三位二進(jìn)制編碼來代表八個字母 000 A100E 001 B101F 010C110G 011D111H 不管哪一位發(fā)生錯誤，都會使傳輸字母錯誤 如用三位字母傳四個字母 000 A011B101 C110D 發(fā)生一位錯誤，準(zhǔn)用碼字將變成禁用碼字，接收端就能知道出錯，但是不能糾錯。 如果進(jìn)一步將許用碼組限制為兩種 000 A 111 B,檢錯和糾錯能力

11、是用信息量的冗余度來換取的。,2020年8月30日,19,檢錯和糾錯的基本原理,檢錯和糾錯能力是用信息量的冗余度換取的與碼組之間的差別有關(guān)；不同的編碼方法和形式，檢錯和糾錯能力不同。 例： n = 3，共有8種組合，都用于傳輸消息，在傳輸過程中若發(fā)生一個誤碼，則一種碼組就會錯誤地變成另一種碼組，但接收端卻不能發(fā)現(xiàn)錯誤，因?yàn)槿魏我粋€碼組都是許用碼組。,在差錯控制編碼中，定義碼組中非零碼元的數(shù)目為碼字的漢明(Hamming)重量， 簡稱碼重。例如，碼字 10110，碼重w=3。 定義兩個等長碼組之間相應(yīng)位取值不同的數(shù)目為這兩個碼組的漢明(Hamming)距離， 簡稱碼距。例如 11000 與 10

12、011之間的距離d=3。 碼組集中任意兩個碼字之間距離的最小值稱為碼的最小距離，用dmin表示。最小碼距是碼的一個重要參數(shù)， 它是衡量碼檢錯、糾錯能力的依據(jù)。,20,2020年8月30日,21,最小碼距與檢錯糾錯能力的關(guān)系,碼組內(nèi)的距離反映了碼組之間的差別，最小距離越大，說明兩個碼組間的最小差別越大，或者說其中一個碼組錯為另一個碼組的可能性就越小，那么其檢錯和糾錯能力也就越強(qiáng)，因此可以說最小碼距是衡量一種糾錯編碼的檢錯，糾錯能力大小的標(biāo)準(zhǔn)。,碼的最小距離直接關(guān)系著碼的檢錯和糾錯能力；任一(n,k)分組碼，若要在碼字內(nèi): (1) 檢測e個隨機(jī)錯誤，則要求碼的最小距離dmine+1; (2) 糾正

13、t個隨機(jī)錯誤， 則要求碼的最小距離dmin2t+1; (3) 糾正t個同時檢測e(t)個隨機(jī)錯誤，則要求碼的最小距離dmint+e+1。,t,1,e,A,B,22,2020年8月30日,23,用差錯控制編碼提高通信系統(tǒng)的可靠性， 是以降低有效性為代價換來的。我們定義編碼效率R來衡量有效性: Rc=k/n 其中, k是信息元的個數(shù)，n為碼長。 對糾錯碼的基本要求是: 檢錯和糾錯能力盡量強(qiáng)； 編碼效率盡量高；編碼規(guī)律盡量簡單。實(shí)際中要根據(jù)具體指標(biāo)要求，保證有一定糾、檢錯能力和編碼效率，并且易于實(shí)現(xiàn)。,編碼效率,2020年8月30日,24,8.2 線性分組碼,線性分組碼的構(gòu)成 將信息序列劃分為等長(

14、k位)的序列段 共有2k個不同的序列段，在每一信息 段之后，附加m位監(jiān)督元，構(gòu)成長度 n = k + m的分組碼(n ，k) 監(jiān)督元與信息碼元為線性關(guān)系,2020年8月30日,25,例,信息元長度k = 3共有2k = 8個不同的信息組 每組信息組加4個監(jiān)督元，構(gòu)成一個長度為7 的(7，3)線性分組碼。 設(shè)： 每組信息元為C1C2C3監(jiān)督元為C4 C5 C6C7 根據(jù)下列線性方程組求監(jiān)督元 C4 = C1 + C3 C5 = C1 + C2 + C3 C6 = C1 + C2 C7 = C2 + C3,2020年8月30日,26,例,(7，3)碼有8個信息組，信息組按上方程組求得每個 信息組的

15、4個監(jiān)督元，得到(7，3)碼的所有8個碼字 信息組 碼元 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 重要特性，線性碼有封閉性,2020年8月30日,27,8.2 線性分組碼,設(shè)分組碼由n位碼組構(gòu)成，記為c1，c2，cn，信息碼組由k位碼組成，記為d1，d2，dk。則該分組碼記為（n，k）碼。 碼組和信息碼組可用行矩陣C和

16、D表示 若為線性分組碼，C中的n個元素都是由D中的k個元素經(jīng)線性組合形成的?？捎靡宦?lián)立方程表示為,將碼組C寫成矩陣形式,矩陣G稱為生成矩陣，它是一個kn的矩陣,28,2020年8月30日,29,生成矩陣G,2020年8月30日,30,生成矩陣G,Ik 單位矩陣，k行k列(k x k階) P矩陣，k行m列(k x m階) 編碼前k位，編碼后有n位，2n 2k； 選擇P矩陣，可得到有較強(qiáng)檢錯糾錯能力，實(shí)現(xiàn) 方法盡可能簡單，編碼效率又高的線性分組碼 由于線性碼具有封閉性，故任何二個碼組之間的距離必須與某一個碼組中“1”的個數(shù)相等，而碼組中非零碼元的數(shù)目“1”的個數(shù)為碼組的重量（碼重）所以線性碼任意二

17、個碼字之間的距離必須等于碼中某一個碼字的重量線性碼最小碼距正好等于非零碼的最小碼重 估算線性碼的差錯控制能力： 求最小碼距最小碼重,2020年8月30日,31,例,已知（6，3）碼的生成距陣，求：編碼碼組,2020年8月30日,32,監(jiān)督矩陣H,校驗(yàn)矩陣或監(jiān)督矩陣 H： m x n 階 PT: m行k列 k + m = n列,2020年8月30日,33,伴隨式（校正子）S,設(shè)發(fā)送碼組C=cn-1,cn-2,c1,c0，在傳輸過程中可能 發(fā)生誤碼。接收碼組R =rn-1,rn-2,r1,r0，則收發(fā)碼組之差定義為錯誤圖樣E， 也稱為誤差矢量， 即,E =RC =en-1,en-2,e1,e0，且

18、,當(dāng)ri=ci,當(dāng)rici,令 S = RHT，稱為伴隨式或校正子 S = RHT = CHT EHT = EHT S只與錯誤圖形有關(guān)，與發(fā)送的碼組C無關(guān) HT ：n x m 階；E：1x n 階；S：1x m 階；S = s1 s2 sm ,解得誤差矢量E，求得糾錯后的碼組 C = R E,2020年8月30日,34,檢錯與糾錯,檢錯：當(dāng)碼組出現(xiàn)錯誤S為非零矢量 糾錯： S = RHT = CHT EHT = EHT S與E之間有著確定的線性關(guān)系由H矩陣 確定（也就是與G（P）矩陣有關(guān)） S=s1 s2 sm 共有2m種不同的形式，除全 0外，可代表2m -1種有錯誤的圖形 信息碼組有2k個錯誤圖形，有多種不同的形式可能有2k種解答；為了選擇正確的結(jié)果，要使用最大似然比準(zhǔn)則，選擇與R最相似的C（與R距離最小的碼