差錯(cuò)控制編碼ppt課件.ppt

1、第八章 差錯(cuò)控制編碼,1,2020年8月30日,2,8.1 差錯(cuò)控制編碼的基本概念,數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。 信源編碼是為了提高數(shù)字通信的有效性，以及為了使模擬信號(hào)數(shù)字化而采取的編碼。 信道編碼是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。 數(shù)字信號(hào)在傳輸?shù)倪^程中，加性噪聲、碼間串?dāng)_等都會(huì)產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。,2020年8月30日,3,差錯(cuò)控制編碼的基本思想：,在發(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)錯(cuò)誤。這時(shí)，或者通過反饋信道要求對(duì)方重發(fā)有錯(cuò)的信息，以進(jìn)行糾錯(cuò)；或者由接收端的譯碼器自動(dòng)把錯(cuò)誤糾正。 這些多余碼元稱為校驗(yàn)元或監(jiān)督元。它的加入不改變信息本身，也就是說，它不傳送新的信息，它的作用只是使信道譯碼器能夠檢測(cè)和糾正差錯(cuò)，從而控制系統(tǒng)差錯(cuò)概率，提高可靠性但這是以系統(tǒng)的有效性為代價(jià)的。,2020年8月30日,4,8.1.1 差錯(cuò)控制方式,2020年8月30日,5,前向糾錯(cuò)方式,前向糾錯(cuò)方式記作FEC（Forword Error Correction） 發(fā)端編碼器將數(shù)

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

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

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

6、式，則稱為線性碼，否則為非線性碼。 根據(jù)上述關(guān)系涉及的范圍，可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)，而且還與前面若干組的信息元有關(guān)。 根據(jù)碼的用途，可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼以檢錯(cuò)為目的，不一定能糾錯(cuò)；而糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。,2020年8月30日,10,8.1.3 幾種簡(jiǎn)單的檢錯(cuò)碼(1),奇偶監(jiān)督碼,設(shè)碼字A=an-1,an-2,a1,a0，對(duì)偶監(jiān)督碼有： an-1 an-2 a1 a0 = 0,奇監(jiān)督碼情況相似， 只是碼組中“1”的數(shù)目為奇數(shù)， 即 滿足條件： an-1 an-2 a1 a0 = 1,而檢錯(cuò)能力與偶監(jiān)督碼相

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

8、奇數(shù)個(gè)錯(cuò)誤，而且 可通過水平監(jiān)督和垂直監(jiān)督來確定錯(cuò)碼的位置 糾正僅一行（一列）出現(xiàn)的奇數(shù)個(gè)錯(cuò)誤 通過水平監(jiān)督和垂直監(jiān)督的關(guān)系可以發(fā)現(xiàn)單行中出現(xiàn) 的偶數(shù)個(gè)錯(cuò)誤；但不能發(fā)現(xiàn)構(gòu)成矩形的4個(gè)錯(cuò)誤碼元 適用于突發(fā)差錯(cuò)由突發(fā)干擾（突發(fā)脈沖，如： 閃電，電火花等）在短時(shí)間內(nèi)錯(cuò)碼成串出現(xiàn)，在某 一行中出現(xiàn)多個(gè)錯(cuò)碼,2020年8月30日,14,8.1.3 幾種簡(jiǎn)單的檢錯(cuò)碼(3),重復(fù)碼 在每位信息碼元之后，用簡(jiǎn)單重復(fù)多次的方法編碼。 例：重復(fù)兩次時(shí)，用111傳輸1碼，用000傳輸0碼 編碼方法：每位信息碼元簡(jiǎn)單重復(fù)多次； 收端 譯碼采用多數(shù)表決法； 例：重復(fù)2次 特點(diǎn)：糾正1個(gè)錯(cuò)，檢出2個(gè)錯(cuò),2020年8月30

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

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

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

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

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

14、k位)的序列段 共有2k個(gè)不同的序列段，在每一信息 段之后，附加m位監(jiān)督元，構(gòu)成長(zhǎng)度 n = k + m的分組碼(n ，k) 監(jiān)督元與信息碼元為線性關(guān)系,2020年8月30日,25,例,信息元長(zhǎng)度k = 3共有2k = 8個(gè)不同的信息組 每組信息組加4個(gè)監(jiān)督元，構(gòu)成一個(gè)長(zhǎng)度為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個(gè)信息組，信息組按上方程組求得每個(gè) 信息組的

15、4個(gè)監(jiān)督元，得到(7，3)碼的所有8個(gè)碼字 信息組 碼元 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個(gè)元素都是由D中的k個(gè)元素經(jīng)線性組合形成的。可用一聯(lián)立方程表示為,將碼組C寫成矩陣形式,矩陣G稱為生成矩陣，它是一個(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)檢錯(cuò)糾錯(cuò)能力，實(shí)現(xiàn) 方法盡可能簡(jiǎn)單，編碼效率又高的線性分組碼 由于線性碼具有封閉性，故任何二個(gè)碼組之間的距離必須與某一個(gè)碼組中“1”的個(gè)數(shù)相等，而碼組中非零碼元的數(shù)目“1”的個(gè)數(shù)為碼組的重量（碼重）所以線性碼任意二

17、個(gè)碼字之間的距離必須等于碼中某一個(gè)碼字的重量線性碼最小碼距正好等于非零碼的最小碼重 估算線性碼的差錯(cuò)控制能力： 求最小碼距最小碼重,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ā)碼組之差定義為錯(cuò)誤圖樣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只與錯(cuò)誤圖形有關(guān)，與發(fā)送的碼組C無關(guān) HT ：n x m 階；E：1x n 階；S：1x m 階；S = s1 s2 sm ,解得誤差矢量E，求得糾錯(cuò)后的碼組 C = R E,2020年8月30日,34,檢錯(cuò)與糾錯(cuò),檢錯(cuò)：當(dāng)碼組出現(xiàn)錯(cuò)誤S為非零矢量 糾錯(cuò)： S = RHT = CHT EHT = EHT S與E之間有著確定的線性關(guān)系由H矩陣 確定（也就是與G（P）矩陣有關(guān)） S=s1 s2 sm 共有2m種不同的形式，除全 0外，可代表2m -1種有錯(cuò)誤的圖形 信息碼組有2k個(gè)錯(cuò)誤圖形，有多種不同的形式可能有2k種解答；為了選擇正確的結(jié)果，要使用最大似然比準(zhǔn)則，選擇與R最相似的C（與R距離最小的碼