第九章 差錯(cuò)控制編碼2012

1、2008.81第第 九九 章章差錯(cuò)控制編碼差錯(cuò)控制編碼2008.82引言引言1糾錯(cuò)編碼的基本原理糾錯(cuò)編碼的基本原理2常用的簡(jiǎn)單編碼常用的簡(jiǎn)單編碼3線性分組碼線性分組碼4循環(huán)碼循環(huán)碼5第第9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼67卷積碼卷積碼網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制2008.839.1 引言信道信道解調(diào)解調(diào)信源信源編碼編碼加密加密調(diào)制調(diào)制解密解密譯碼譯碼信宿信宿噪聲噪聲同步系統(tǒng)同步系統(tǒng)信源編碼信源編碼 信道編碼信道編碼 差錯(cuò)控制差錯(cuò)控制ASKFSKPSKDPSK數(shù)字通信的組成數(shù)字通信的組成A/DA/D數(shù)據(jù)壓縮數(shù)據(jù)壓縮2008.84數(shù)字通信中的編碼分為數(shù)字通信中的編碼分為：信道編碼：信道編碼：信源編碼：

2、信源編碼：為提高信號(hào)傳輸?shù)臑樘岣咝盘?hào)傳輸?shù)挠行杂行远扇〉拇胧?。采取的措施。為提高信?hào)傳輸?shù)臑樘岣咝盘?hào)傳輸?shù)目煽啃钥煽啃远扇〉拇胧Ｒ喾Q(chēng)差錯(cuò)控制采取的措施。亦稱(chēng)差錯(cuò)控制編碼。編碼。2008.85 在通信過(guò)程中，會(huì)受到各種外來(lái)在通信過(guò)程中，會(huì)受到各種外來(lái)干干擾，如脈沖干擾，隨機(jī)噪聲干擾擾，如脈沖干擾，隨機(jī)噪聲干擾，人，人為干擾及通信線路傳輸性能的限制都為干擾及通信線路傳輸性能的限制都將使信號(hào)失真。由于以上原因，引起將使信號(hào)失真。由于以上原因，引起數(shù)據(jù)信息序列產(chǎn)生錯(cuò)誤，稱(chēng)之為數(shù)據(jù)信息序列產(chǎn)生錯(cuò)誤，稱(chēng)之為差錯(cuò)。差錯(cuò)。 2008.86差錯(cuò)的兩大類(lèi)型：差錯(cuò)的兩大類(lèi)型： 隨機(jī)性錯(cuò)誤隨機(jī)性錯(cuò)誤：前

3、后出錯(cuò)位之間無(wú)一定關(guān)：前后出錯(cuò)位之間無(wú)一定關(guān)系，隨機(jī)、離散出現(xiàn)。系，隨機(jī)、離散出現(xiàn)。 突發(fā)性錯(cuò)誤突發(fā)性錯(cuò)誤：差錯(cuò)成串出現(xiàn)，且有一定：差錯(cuò)成串出現(xiàn)，且有一定相關(guān)性。相關(guān)性。 實(shí)際信道中，上述兩種錯(cuò)誤常同時(shí)存實(shí)際信道中，上述兩種錯(cuò)誤常同時(shí)存在。在。 2008.87v合理的設(shè)計(jì)基帶信號(hào)合理的設(shè)計(jì)基帶信號(hào)v時(shí)域時(shí)域/ /頻域均衡頻域均衡 v發(fā)射功率的提高發(fā)射功率的提高v采用信道編碼采用信道編碼都能有效的提高傳輸可靠性。2008.88差錯(cuò)控制 在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中增加一些監(jiān)督信息，使不帶規(guī)律性或規(guī)律性增加一些監(jiān)督信息，使不帶規(guī)律性或規(guī)律性不強(qiáng)的原始數(shù)字信號(hào)

4、變?yōu)閹б?guī)律性或加強(qiáng)了不強(qiáng)的原始數(shù)字信號(hào)變?yōu)閹б?guī)律性或加強(qiáng)了規(guī)律性的數(shù)字信號(hào)，規(guī)律性的數(shù)字信號(hào)，信道譯碼器信道譯碼器則利用這些則利用這些規(guī)律性來(lái)鑒別是否發(fā)生錯(cuò)誤，或進(jìn)行錯(cuò)誤糾規(guī)律性來(lái)鑒別是否發(fā)生錯(cuò)誤，或進(jìn)行錯(cuò)誤糾正正。2008.89 1、差錯(cuò)控制方法（1）前向糾錯(cuò)法）前向糾錯(cuò)法FEC 所發(fā)碼具有糾錯(cuò)能力，收端接收后自動(dòng)糾所發(fā)碼具有糾錯(cuò)能力，收端接收后自動(dòng)糾錯(cuò)，無(wú)需反向信道。實(shí)時(shí)性好，但譯碼設(shè)備錯(cuò)，無(wú)需反向信道。實(shí)時(shí)性好，但譯碼設(shè)備復(fù)雜，復(fù)雜，傳輸效率傳輸效率 。信源信源FEC編碼編碼信道信道FEC譯碼譯碼信宿信宿（2）信息反饋法）信息反饋法IF信息信號(hào)信息信號(hào)信息信號(hào)信息信號(hào)發(fā)端收端收端 方法和

5、設(shè)備簡(jiǎn)單，無(wú)需糾檢錯(cuò)編譯系統(tǒng)。方法和設(shè)備簡(jiǎn)單，無(wú)需糾檢錯(cuò)編譯系統(tǒng)。但需要雙向信道，但需要雙向信道，傳輸效率傳輸效率、實(shí)時(shí)性差、實(shí)時(shí)性差 。2008.810 (3)檢錯(cuò)重發(fā)法ARQ 所發(fā)碼具有檢錯(cuò)能力，收端接收后判決是所發(fā)碼具有檢錯(cuò)能力，收端接收后判決是否出錯(cuò)，通過(guò)反向信道發(fā)送判決結(jié)果，發(fā)端否出錯(cuò)，通過(guò)反向信道發(fā)送判決結(jié)果，發(fā)端據(jù)此決定是否重發(fā)。據(jù)此決定是否重發(fā)。 譯碼設(shè)備簡(jiǎn)單，對(duì)突發(fā)錯(cuò)誤有效，要求有反饋信道。譯碼設(shè)備簡(jiǎn)單，對(duì)突發(fā)錯(cuò)誤有效，要求有反饋信道。信源信源編碼器編碼器正向信道正向信道譯碼器譯碼器信宿信宿緩存器緩存器重發(fā)控制器重發(fā)控制器反向信道反向信道重發(fā)判決器重發(fā)判決器工作過(guò)程：發(fā)送工作

6、過(guò)程：發(fā)送檢測(cè)檢測(cè)回復(fù)回復(fù)重發(fā)或發(fā)送新的數(shù)據(jù)重發(fā)或發(fā)送新的數(shù)據(jù)2008.811停止等待方式停止等待方式 3221221發(fā)送端發(fā)送端接收端接收端 ARQ的三種實(shí)現(xiàn)方式： 特點(diǎn)：半雙工工作，簡(jiǎn)單，要求的緩存量小，但等待時(shí)間較長(zhǎng)，特點(diǎn)：半雙工工作，簡(jiǎn)單，要求的緩存量小，但等待時(shí)間較長(zhǎng)，傳輸效率傳輸效率 2008.812 連續(xù)重發(fā)方式 6543254321065432543210退退N N步方式：從出錯(cuò)幀開(kāi)始重發(fā)步方式：從出錯(cuò)幀開(kāi)始重發(fā)優(yōu)缺點(diǎn)：傳輸效率優(yōu)缺點(diǎn)：傳輸效率，但重發(fā)的，但重發(fā)的N N幀中，大部分幀中，大部分為正確，所以仍有浪費(fèi)。發(fā)端緩存必須可存為正確，所以仍有浪費(fèi)。發(fā)端緩存必須可存N N幀。

7、幀。 2008.8132987654321029876543210 只對(duì)出錯(cuò)信息重發(fā)，因此傳輸效率大大提只對(duì)出錯(cuò)信息重發(fā)，因此傳輸效率大大提高高 。但收發(fā)兩端都要有足夠的存儲(chǔ)空間。但收發(fā)兩端都要有足夠的存儲(chǔ)空間。 選擇重發(fā)方式 2008.814反饋信道反饋信道ARQFEC編碼器編碼器正向信道正向信道FEC譯碼器譯碼器ARQ 編碼既有糾錯(cuò)能力也有檢錯(cuò)能力，收端收到編碼既有糾錯(cuò)能力也有檢錯(cuò)能力，收端收到信息碼組后在收端進(jìn)行檢測(cè)。在糾錯(cuò)范圍內(nèi)：信息碼組后在收端進(jìn)行檢測(cè)。在糾錯(cuò)范圍內(nèi)：糾正；超出范圍：通過(guò)糾正；超出范圍：通過(guò)ARQARQ方式進(jìn)行重發(fā)。方式進(jìn)行重發(fā)。 (4) 混合方式 2008.815（

8、1）根據(jù)各碼組信息碼和監(jiān)督碼的關(guān)系分：根據(jù)各碼組信息碼和監(jiān)督碼的關(guān)系分： 線性碼，非線性碼線性碼，非線性碼根據(jù)監(jiān)督碼元是否僅與本組信息元有關(guān)根據(jù)監(jiān)督碼元是否僅與本組信息元有關(guān) 分組碼，卷積碼分組碼，卷積碼（2）根據(jù)糾錯(cuò)碼組中信息元是否隱蔽分：根據(jù)糾錯(cuò)碼組中信息元是否隱蔽分： 系統(tǒng)碼，非系統(tǒng)碼系統(tǒng)碼，非系統(tǒng)碼（3）糾錯(cuò)碼的分類(lèi)2008.816根據(jù)碼的用途分：根據(jù)碼的用途分： 檢錯(cuò)碼檢錯(cuò)碼 ，糾錯(cuò)碼，糾錯(cuò)碼（4）根據(jù)根據(jù)碼元的取值碼元的取值： 二進(jìn)制碼，多進(jìn)制碼二進(jìn)制碼，多進(jìn)制碼（5）根據(jù)根據(jù)構(gòu)造編碼的數(shù)學(xué)方法構(gòu)造編碼的數(shù)學(xué)方法： 代數(shù)碼，幾何碼，算術(shù)碼代數(shù)碼，幾何碼，算術(shù)碼（6）本課程主要討論糾

9、隨機(jī)錯(cuò)誤的二進(jìn)制線性分組碼。本課程主要討論糾隨機(jī)錯(cuò)誤的二進(jìn)制線性分組碼。2008.8179、2 糾錯(cuò)編碼的基本原理1、 幾個(gè)術(shù)語(yǔ)幾個(gè)術(shù)語(yǔ)碼長(zhǎng)：碼長(zhǎng)：碼組中碼元的數(shù)目，常用碼組中碼元的數(shù)目，常用n n 表示；表示；碼距：碼距：兩等長(zhǎng)碼字兩等長(zhǎng)碼字C C1 1、C C2 2對(duì)應(yīng)位上取值不同的對(duì)應(yīng)位上取值不同的數(shù)目，又稱(chēng)為漢明數(shù)目，又稱(chēng)為漢明(Hamming)(Hamming)距離，記為距離，記為d(cd(c1 1,c,c2 2) )。碼重碼重：碼組中非零碼元的數(shù)目，記為：碼組中非零碼元的數(shù)目，記為W W；最小碼距最小碼距：在分組碼：在分組碼(n,k)(n,k)中，任意兩個(gè)碼字之中，任意兩個(gè)碼字之間

10、漢明距離的最小值，記為間漢明距離的最小值，記為d dminmin。碼距的大小關(guān)系到編碼的檢碼距的大小關(guān)系到編碼的檢糾糾錯(cuò)能力錯(cuò)能力。2008.818n=3時(shí)，碼距的幾何說(shuō)明：時(shí)，碼距的幾何說(shuō)明：（ a2 a1 a0 ）a2a1a0（ 110） （ 011 ）d=2110011（ 111） （ 000 ）d=30001112008.819A A、B B兩消息，可用一位二進(jìn)制數(shù)表示，兩消息，可用一位二進(jìn)制數(shù)表示，A=1A=1、B=0B=0出錯(cuò)時(shí)無(wú)法判定出錯(cuò)時(shí)無(wú)法判定 。例例 增加一個(gè)監(jiān)督位，取增加一個(gè)監(jiān)督位，取11A11A、00B,00B,若收到若收到0101或或1010時(shí)，時(shí)， 可知發(fā)生了錯(cuò)誤，

11、但不能糾正錯(cuò)誤?？芍l(fā)生了錯(cuò)誤，但不能糾正錯(cuò)誤。 再增加一個(gè)監(jiān)督位，取再增加一個(gè)監(jiān)督位，取111A111A、000B,000B,如一位錯(cuò)：如一位錯(cuò)： B001 A110B001 A110；若兩位錯(cuò)若兩位錯(cuò)011,110011,110則只能發(fā)現(xiàn)不能糾錯(cuò)則只能發(fā)現(xiàn)不能糾錯(cuò) 因此因此這種（這種（3.13.1）碼，能糾正一個(gè)錯(cuò)，發(fā)現(xiàn)兩個(gè)錯(cuò)。）碼，能糾正一個(gè)錯(cuò)，發(fā)現(xiàn)兩個(gè)錯(cuò)。 但是但是 (3.1)(3.1)碼中，數(shù)據(jù)位僅為碼中，數(shù)據(jù)位僅為1 1位，監(jiān)督位為兩位，位，監(jiān)督位為兩位，傳輸效率傳輸效率 可以看出：差錯(cuò)控制是以犧牲傳輸效率為代價(jià)而可以看出：差錯(cuò)控制是以犧牲傳輸效率為代價(jià)而換取了傳輸質(zhì)量的提高的。糾

12、檢錯(cuò)能力與加入的監(jiān)督換取了傳輸質(zhì)量的提高的。糾檢錯(cuò)能力與加入的監(jiān)督元數(shù)目成正比。元數(shù)目成正比。 2、 糾錯(cuò)或檢錯(cuò)的原理2008.820分組碼的三個(gè)參數(shù)分組碼的三個(gè)參數(shù)碼長(zhǎng)碼長(zhǎng) n，信息位信息位 k，最小距離最小距離 d0 ， 用符號(hào)用符號(hào) (n,k,d0) 表示表示k個(gè)信息元個(gè)信息元an-1 an-2 ar ar-1 a0 r個(gè)監(jiān)督元個(gè)監(jiān)督元碼長(zhǎng)：碼長(zhǎng)：n = k+rR=k/n為為編碼效率編碼效率，d0一定一定(糾錯(cuò)能力一定糾錯(cuò)能力一定)時(shí)，時(shí)，k/n大，效率高。大，效率高。 對(duì)被傳輸?shù)男畔⑿蛄蟹纸M，每組為對(duì)被傳輸?shù)男畔⑿蛄蟹纸M，每組為k k個(gè)信息元，對(duì)個(gè)信息元，對(duì)每組按某種關(guān)系附加每組按某種

13、關(guān)系附加(n-k) (n-k) 個(gè)監(jiān)督碼元個(gè)監(jiān)督碼元 ( (校驗(yàn)校驗(yàn)) )，形成，形成為為n n位的碼字。這種方法構(gòu)成的碼組稱(chēng)為位的碼字。這種方法構(gòu)成的碼組稱(chēng)為分組碼分組碼。2008.821 3、分組碼的糾(檢)錯(cuò)能力與最小碼距d0的關(guān)系 任一任一（ n n，k k）分組碼，若要在碼字內(nèi)能：分組碼，若要在碼字內(nèi)能： 1/ 1/ 檢測(cè)檢測(cè)e e個(gè)隨機(jī)錯(cuò)誤，則要求：個(gè)隨機(jī)錯(cuò)誤，則要求： d d0 e+1e+1 2/ 2/ 糾正糾正t t個(gè)隨機(jī)錯(cuò)誤，則要求：個(gè)隨機(jī)錯(cuò)誤，則要求： d d0 0 2 2t+1t+1 3/ 3/ 糾正糾正t t個(gè)同時(shí)檢測(cè)個(gè)同時(shí)檢測(cè)e e(et)(et)個(gè)隨機(jī)錯(cuò)誤，個(gè)隨機(jī)錯(cuò)

14、誤，則要求：則要求： d d0 0 e+t+1 e+t+1 2008.822 A1 d 0eA2（a）A1 A2 d 0et（c） A1 d 0tA2（b）A2t2008.823例：例：一個(gè)碼集，只有兩個(gè)許用碼：一個(gè)碼集，只有兩個(gè)許用碼：00000000、11111111，試求其糾、檢錯(cuò)能力，試求其糾、檢錯(cuò)能力和編碼效率。和編碼效率。2008.8244、對(duì)糾錯(cuò)編碼的要求對(duì)糾錯(cuò)編碼的要求例：例：一個(gè)碼集，只有兩個(gè)許用碼：一個(gè)碼集，只有兩個(gè)許用碼：0000、1111，試求其糾檢錯(cuò)能力和編碼效率。試求其糾檢錯(cuò)能力和編碼效率。解：解：根據(jù)碼距的定義，則該碼集根據(jù)碼距的定義，則該碼集d 0 = 4， 1

15、/ 用于檢錯(cuò)，用于檢錯(cuò)，e d d0 0 1=3，即可檢即可檢3個(gè)錯(cuò)誤；個(gè)錯(cuò)誤；2/ 用于糾錯(cuò)，用于糾錯(cuò)，t (d d0 01)/2=3/2，取整，即可糾取整，即可糾1個(gè)錯(cuò)誤；個(gè)錯(cuò)誤；3/ 同時(shí)用于糾、檢錯(cuò)，同時(shí)用于糾、檢錯(cuò)， d d0 0 e+t+1 e+t+1 （e et t） ?。喝。篹=2，t=1，則可滿(mǎn)足上式，即可檢則可滿(mǎn)足上式，即可檢2個(gè)錯(cuò)誤個(gè)錯(cuò)誤 同時(shí)糾一個(gè)錯(cuò)；同時(shí)糾一個(gè)錯(cuò)；R=k/n=1/42008.8255. 差錯(cuò)控制編碼的效用 假設(shè)在隨機(jī)信道中，發(fā)送假設(shè)在隨機(jī)信道中，發(fā)送“0”0”和和“1”1”的錯(cuò)誤概的錯(cuò)誤概率相等，都等于率相等，都等于p p，且，且p p1 1，在碼長(zhǎng)為

16、在碼長(zhǎng)為n n的碼組中，的碼組中，發(fā)生發(fā)生r r個(gè)錯(cuò)誤的概率為：個(gè)錯(cuò)誤的概率為：!( )(1)!()!rrn rrnnnP rC pppr nr2008.826!( )(1)!()!rrn rrnnnP rC pppr nr例如：當(dāng)例如：當(dāng)n=7，p=10時(shí)，則有：時(shí)，則有：371077) 1 ( pP5227101 . 221)!27( ! 2! 7)2(ppP8337105 . 335)!37( ! 3! 7) 3(ppP 由此可見(jiàn)，即使僅能糾正由此可見(jiàn)，即使僅能糾正1-21-2個(gè)錯(cuò)誤，也可使個(gè)錯(cuò)誤，也可使誤碼率下降幾個(gè)數(shù)量級(jí)。所以差錯(cuò)控制編碼誤碼率下降幾個(gè)數(shù)量級(jí)。所以差錯(cuò)控制編碼具有較大

17、的實(shí)際應(yīng)用價(jià)值。具有較大的實(shí)際應(yīng)用價(jià)值。2008.8276. 有擾信道編碼定理（Shannon第二定理） 對(duì)于給定的有擾信道，若信道容量為對(duì)于給定的有擾信道，若信道容量為C C，只要發(fā)送端以低于只要發(fā)送端以低于C C的信息速率的信息速率R Rb b發(fā)送信息，發(fā)送信息，則則一定存在一種編碼方法一定存在一種編碼方法，使得譯碼錯(cuò)誤概，使得譯碼錯(cuò)誤概率率P P隨著碼長(zhǎng)隨著碼長(zhǎng)n n的增加，按指數(shù)下降至任意小的增加，按指數(shù)下降至任意小的值，表示為的值，表示為 P P e e-nE(Rb-nE(Rb) )E(RE(Rb b) )為誤差指數(shù)，為誤差指數(shù)，R Rb bC0)0。 Rbmax=C=Blog2(1

18、+S/N) （bit/s）2008.828 系統(tǒng)帶寬和信噪比的矛盾：系統(tǒng)帶寬和信噪比的矛盾： 由上節(jié)所述的糾錯(cuò)編碼原理可知，為了減少接收錯(cuò)誤由上節(jié)所述的糾錯(cuò)編碼原理可知，為了減少接收錯(cuò)誤碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。這樣作的結(jié)果使發(fā)送序列增長(zhǎng)，冗余度增大。若仍須這樣作的結(jié)果使發(fā)送序列增長(zhǎng)，冗余度增大。若仍須保持發(fā)送信息碼元速率不變，則傳輸速率必須增大，保持發(fā)送信息碼元速率不變，則傳輸速率必須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比的下降反

19、而又噪聲功率增大，使信噪比下降。信噪比的下降反而又使系統(tǒng)接收碼元序列中的錯(cuò)碼增多。一般說(shuō)來(lái)，采用使系統(tǒng)接收碼元序列中的錯(cuò)碼增多。一般說(shuō)來(lái)，采用糾錯(cuò)編碼后，誤碼率總是能夠得到很大改善的。改善糾錯(cuò)編碼后，誤碼率總是能夠得到很大改善的。改善的程度和所用的編碼有關(guān)。的程度和所用的編碼有關(guān)。2008.829 編碼性能舉例編碼性能舉例 未采用糾錯(cuò)編碼時(shí)，未采用糾錯(cuò)編碼時(shí)，若接收信噪比等于若接收信噪比等于7dB，編碼前誤碼率，編碼前誤碼率約為約為8 10-4，圖中，圖中A點(diǎn)，在采用糾錯(cuò)編碼點(diǎn)，在采用糾錯(cuò)編碼后，誤碼率降至約后，誤碼率降至約4 10-5，圖中，圖中B點(diǎn)。這樣，點(diǎn)。這樣，不增大發(fā)送功率不增大發(fā)送

20、功率就能就能降低誤碼率約一個(gè)半降低誤碼率約一個(gè)半數(shù)量級(jí)。數(shù)量級(jí)。10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)2008.830 由圖還可以看出，若由圖還可以看出，若保持誤碼率在保持誤碼率在10-5，圖中圖中C點(diǎn)，未采用編點(diǎn)，未采用編碼時(shí)，約需要信噪比碼時(shí)，約需要信噪比Eb / n0 = 10.5 dB。在。在采用這種編碼時(shí)，約采用這種編碼時(shí)，約需要信噪比需要信噪比7.5 dB，圖，圖中中D點(diǎn)。可以節(jié)省功率點(diǎn)。可以節(jié)省功率2 dB。通常稱(chēng)這。通常稱(chēng)這2 dB為為編碼增益編碼增益。 上面兩種情況付出的代上面兩種情況付出的代價(jià)是帶寬增大。價(jià)是帶寬增大。10-61

21、0-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)2008.831 傳輸速率和傳輸速率和Eb/n0的關(guān)系的關(guān)系對(duì)于給定的傳輸系統(tǒng)對(duì)于給定的傳輸系統(tǒng)式中，式中，RB為碼元速率。為碼元速率。若希望提高傳輸速率，若希望提高傳輸速率，由上式看出勢(shì)必使信由上式看出勢(shì)必使信噪比下降，誤碼率增噪比下降，誤碼率增大。假設(shè)系統(tǒng)原來(lái)工作大。假設(shè)系統(tǒng)原來(lái)工作在圖中在圖中C點(diǎn)，提高速率后點(diǎn)，提高速率后由由C點(diǎn)升到點(diǎn)升到E點(diǎn)。但加用點(diǎn)。但加用糾錯(cuò)編碼后，仍可將誤碼糾錯(cuò)編碼后，仍可將誤碼率降到率降到D點(diǎn)。這時(shí)付出的點(diǎn)。這時(shí)付出的代價(jià)仍是帶寬增大。代價(jià)仍是帶寬增大。BsssbRnPTnPnTPnE0

22、000)/ 1 (10-610-510-410-310-210-1編碼后PeCDEAB信噪比 (dB)2008.8329-3 常用的簡(jiǎn)單編碼1 1、奇偶監(jiān)督碼：、奇偶監(jiān)督碼： k=n-1,r=1k=n-1,r=1的線性碼。的線性碼。特點(diǎn)：特點(diǎn)： 碼組中的碼組中的1 1個(gè)數(shù)是奇數(shù)（奇監(jiān)督碼）個(gè)數(shù)是奇數(shù)（奇監(jiān)督碼） 或偶數(shù)（偶監(jiān)督碼）?；蚺紨?shù)（偶監(jiān)督碼）。0021aaann偶監(jiān)督時(shí)，要滿(mǎn)足：偶監(jiān)督時(shí)，要滿(mǎn)足：1021aaann奇監(jiān)督時(shí)，要滿(mǎn)足：奇監(jiān)督時(shí)，要滿(mǎn)足：兩者的校驗(yàn)?zāi)芰ο嗤?，均只能檢測(cè)出奇數(shù)個(gè)錯(cuò)誤。兩者的校驗(yàn)?zāi)芰ο嗤荒軝z測(cè)出奇數(shù)個(gè)錯(cuò)誤。R=k/n=n-1/n=1-1/n編碼效率：編碼效

23、率：2008.833序序 碼碼 字字 序序 碼碼 字字號(hào)號(hào) 信息碼元信息碼元 監(jiān)督元監(jiān)督元 號(hào)號(hào) 信息碼元信息碼元 監(jiān)督元監(jiān)督元 a4 a3 a2 a1 a0 a4 a3 a2 a1 a0 0 0 0 0 0 0 8 1 0 0 0 1 1 0 0 0 1 1 9 1 0 0 1 0 2 0 0 1 0 1 10 1 0 1 0 0 3 0 0 1 1 0 11 1 0 1 1 1 4 0 1 0 0 1 12 1 1 0 0 0 5 0 1 0 1 0 13 1 1 0 1 1 6 0 1 1 0 0 14 1 1 1 0 1 7 0 1 1 1 1 15 1 1 1 1 0 碼長(zhǎng)碼長(zhǎng)5 5

24、的偶監(jiān)督碼的偶監(jiān)督碼2008.834 偶監(jiān)督碼編碼器a4a3a2a1+信息組信息組a0a1a2a3a4碼字碼字12340aaaaa2008.83501234bbbbbsb3b0b1b2b4+接收碼組BS檢錯(cuò)信號(hào)有錯(cuò)無(wú)錯(cuò)10偶監(jiān)督碼的檢錯(cuò)電路偶監(jiān)督碼的檢錯(cuò)電路2008.836例：一數(shù)據(jù)序列：例：一數(shù)據(jù)序列： 1110011100 1011110111 0110101101 1000110001 1010110101 試對(duì)其進(jìn)行（試對(duì)其進(jìn)行（6 6，5 5）偶校驗(yàn)編碼，寫(xiě)出碼序列）偶校驗(yàn)編碼，寫(xiě)出碼序列并分析其抗干擾能力并分析其抗干擾能力 2008.837例：一數(shù)據(jù)序列例：一數(shù)據(jù)序列： 11100

25、11100 1011110111 0110101101 1000110001 1010110101 試對(duì)其進(jìn)行（試對(duì)其進(jìn)行（6 6，5 5）偶校驗(yàn)編碼，寫(xiě)出碼序列）偶校驗(yàn)編碼，寫(xiě)出碼序列并分析其抗干擾能力并分析其抗干擾能力解：解： （6 6，5 5）, ,將數(shù)據(jù)序列每將數(shù)據(jù)序列每5 5碼元分組，碼元分組，123450aaaaaa并作：并作：的運(yùn)算的運(yùn)算可得出編碼數(shù)據(jù)序列：可得出編碼數(shù)據(jù)序列：11100111001110111101110001101011011110001100010010101101011 1 只能檢測(cè)出奇數(shù)個(gè)錯(cuò)誤，不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤，只能檢測(cè)出奇數(shù)個(gè)錯(cuò)誤，不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤

26、，也不能糾錯(cuò)。也不能糾錯(cuò)。 2008.8382 2、水平垂直奇偶校驗(yàn)、水平垂直奇偶校驗(yàn)碼：碼： 又稱(chēng)行列監(jiān)督碼或二維奇偶監(jiān)督碼。又稱(chēng)行列監(jiān)督碼或二維奇偶監(jiān)督碼。特點(diǎn)：特點(diǎn)：對(duì)水平方向和垂直方向的碼元同時(shí)實(shí)施奇偶監(jiān)督。對(duì)水平方向和垂直方向的碼元同時(shí)實(shí)施奇偶監(jiān)督。 1 1 0 0 1 0 1 0 0 0 00 1 0 0 0 0 1 1 0 1 00 1 1 1 1 0 0 0 0 1 11 0 0 1 1 1 0 0 0 0 01 0 1 0 1 0 1 0 1 0 11 1 0 0 0 1 1 1 1 0 0行行列列監(jiān)監(jiān)督督碼碼2008.839適于監(jiān)測(cè)突發(fā)錯(cuò)誤：適于監(jiān)測(cè)突發(fā)錯(cuò)誤：q逐行傳輸時(shí)，

27、能檢測(cè)長(zhǎng)度逐行傳輸時(shí)，能檢測(cè)長(zhǎng)度b b m+ m+1 1的突發(fā)錯(cuò)誤的突發(fā)錯(cuò)誤; ;q逐列傳輸時(shí)逐列傳輸時(shí), ,能檢測(cè)長(zhǎng)度能檢測(cè)長(zhǎng)度b b L+L+1 1的突發(fā)錯(cuò)誤；的突發(fā)錯(cuò)誤；q還能糾正一些僅在一行中的單個(gè)錯(cuò)誤。還能糾正一些僅在一行中的單個(gè)錯(cuò)誤。其中其中m為行數(shù)，為行數(shù)，L為列數(shù)為列數(shù)2008.8403 3、恒比碼：、恒比碼： 又稱(chēng)等重碼或定又稱(chēng)等重碼或定1 1碼。碼。特點(diǎn)：特點(diǎn)： 碼組中碼組中0 0，1 1的個(gè)數(shù)保持不變。的個(gè)數(shù)保持不變。 若碼長(zhǎng)為若碼長(zhǎng)為n n，碼重為碼重為w w，則此碼的碼字個(gè)數(shù)則此碼的碼字個(gè)數(shù) 為：為：C Cn nw w，禁用碼字個(gè)數(shù)為：禁用碼字個(gè)數(shù)為：2 2n n -

28、 - C Cn nw w例如：我國(guó)的電報(bào)，每個(gè)漢字用四個(gè)例如：我國(guó)的電報(bào)，每個(gè)漢字用四個(gè)1010進(jìn)制數(shù)表進(jìn)制數(shù)表 示，每位示，每位1010進(jìn)制數(shù)就采用進(jìn)制數(shù)就采用 3 3：2 2 恒比碼構(gòu)恒比碼構(gòu) 成的成的5 5位碼組來(lái)表示。位碼組來(lái)表示。碼字的個(gè)數(shù)碼字的個(gè)數(shù)C C5 53 3 =10=10檢錯(cuò)能力較強(qiáng)，可檢出檢錯(cuò)能力較強(qiáng)，可檢出所有奇數(shù)所有奇數(shù)和和部分偶數(shù)部分偶數(shù)錯(cuò)誤。錯(cuò)誤。2008.841數(shù)字?jǐn)?shù)字碼碼 字字0 01 12 23 34 45 56 67 78 89 9011010110101011010111100111001101101011011010110100011100111101

29、01101011110011100011100111010011100113:2 恒比碼恒比碼如：我國(guó)的電報(bào)，每如：我國(guó)的電報(bào)，每個(gè)漢字用四個(gè)個(gè)漢字用四個(gè)1010進(jìn)制進(jìn)制數(shù)表示，每位數(shù)表示，每位1010進(jìn)制進(jìn)制數(shù)就采用數(shù)就采用 3 3：2 2 恒比恒比碼構(gòu)成的碼構(gòu)成的5 5位碼組來(lái)表位碼組來(lái)表示。示。碼字的個(gè)數(shù)碼字的個(gè)數(shù)C C5 53 3 =10=102008.8424 4、正反碼：、正反碼： 簡(jiǎn)單的可糾錯(cuò)編碼，信元數(shù)等于監(jiān)督元數(shù)簡(jiǎn)單的可糾錯(cuò)編碼，信元數(shù)等于監(jiān)督元數(shù)特點(diǎn)：特點(diǎn)： 信息位中，有奇數(shù)個(gè)信息位中，有奇數(shù)個(gè)1 1時(shí)，監(jiān)督位重復(fù)信息位；時(shí)，監(jiān)督位重復(fù)信息位； 信息位中，有偶數(shù)個(gè)信息位中，

30、有偶數(shù)個(gè)1 1時(shí)，監(jiān)督位取信息位的反碼；時(shí)，監(jiān)督位取信息位的反碼；可糾一位、檢測(cè)所有兩位錯(cuò)和部分兩位以上的錯(cuò)誤?？杉m一位、檢測(cè)所有兩位錯(cuò)和部分兩位以上的錯(cuò)誤。例：例：11001 1100111001 11001110011100110001 1000110001 100010111001110(n,k) (n,k) 其中其中k=n/2 k=n/2 編碼效率：編碼效率： R=k/n=1/2R=k/n=1/22008.8439.4 線性分組碼9.4.1 9.4.1 基本概念基本概念 可用線性方程組表述碼的規(guī)律性的分可用線性方程組表述碼的規(guī)律性的分組碼稱(chēng)為線性分組碼。線性碼建立在代組碼稱(chēng)為線性分組碼

31、。線性碼建立在代數(shù)學(xué)群論基礎(chǔ)上，線性碼各許用碼的集數(shù)學(xué)群論基礎(chǔ)上，線性碼各許用碼的集合構(gòu)成代數(shù)學(xué)中的群，因此，又稱(chēng)為群合構(gòu)成代數(shù)學(xué)中的群，因此，又稱(chēng)為群碼。碼。2008.844 1. 1. 含有全零碼字。含有全零碼字。 2.2.任意兩個(gè)許用碼字之和仍是一個(gè)許用碼字。任意兩個(gè)許用碼字之和仍是一個(gè)許用碼字。（封閉性封閉性） 3.3.最小碼距最小碼距d d0 0等于非零碼字的最小重量即等于非零碼字的最小重量即d d0 0= =w wminmin （由此性質(zhì)可以方便的確定出線性分組碼的最（由此性質(zhì)可以方便的確定出線性分組碼的最小碼距，進(jìn)而明確其糾錯(cuò)能力。）小碼距，進(jìn)而明確其糾錯(cuò)能力。） 在群中只有一種

32、運(yùn)算，就是模在群中只有一種運(yùn)算，就是模2 2 和。和。線性分組碼的性質(zhì)線性分組碼的性質(zhì)：2008.845 奇偶監(jiān)督碼是一種最簡(jiǎn)單的線性碼，我們?cè)?jīng)作了奇偶監(jiān)督碼是一種最簡(jiǎn)單的線性碼，我們?cè)?jīng)作了偶校驗(yàn)的例子。偶校驗(yàn)的例子。0021aaann稱(chēng)為監(jiān)督稱(chēng)為監(jiān)督方程方程。接收時(shí)，為了檢測(cè)傳輸時(shí)是否有錯(cuò)，還要做同樣的計(jì)接收時(shí)，為了檢測(cè)傳輸時(shí)是否有錯(cuò)，還要做同樣的計(jì)算：算：01234bbbbbs有錯(cuò)無(wú)錯(cuò)10s這里這里S S稱(chēng)為稱(chēng)為校正子，校正子，上式也稱(chēng)上式也稱(chēng)伴隨式伴隨式。奇偶監(jiān)督碼中只有一位監(jiān)督碼，因此只能表示有否錯(cuò)誤。奇偶監(jiān)督碼中只有一位監(jiān)督碼，因此只能表示有否錯(cuò)誤。2008.846當(dāng)監(jiān)督位增加，

33、則監(jiān)督方程增加，校正子增加。當(dāng)監(jiān)督位增加，則監(jiān)督方程增加，校正子增加。r r位監(jiān)督碼除了用全位監(jiān)督碼除了用全“0”0”表示無(wú)錯(cuò)外，可表示表示無(wú)錯(cuò)外，可表示r21種錯(cuò)誤圖樣。種錯(cuò)誤圖樣。(n,k)碼可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為：碼可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為： 我們把接收碼組我們把接收碼組R R與發(fā)射碼組與發(fā)射碼組C C的差稱(chēng)為的差稱(chēng)為錯(cuò)誤圖樣錯(cuò)誤圖樣，用用E E表示：表示：E=C-RE=C-R，或者，或者 C=R+EC=R+E (n,k)中，信息碼為中，信息碼為k位，可傳輸位，可傳輸M=2k種信息，當(dāng)種信息，當(dāng)增加增加r位的監(jiān)督位后，有位的監(jiān)督位后，有2n種狀態(tài)，但只取種狀態(tài)，但只取2k 種為許種為許用狀態(tài)，

34、其他為禁用，用狀態(tài)，其他為禁用，(n,k)碼可檢測(cè)的錯(cuò)誤圖樣數(shù)為碼可檢測(cè)的錯(cuò)誤圖樣數(shù)為 2n-2k2 n-k -1=2 r-1不可檢測(cè)的錯(cuò)誤圖樣數(shù)為不可檢測(cè)的錯(cuò)誤圖樣數(shù)為2k-12008.8471nc2nctnctiinc12 n-k-1 + + =對(duì)于能糾正對(duì)于能糾正 t 個(gè)錯(cuò)誤的線性分組碼個(gè)錯(cuò)誤的線性分組碼(n,k)應(yīng)滿(mǎn)足：應(yīng)滿(mǎn)足：inc是錯(cuò)是錯(cuò) i 位的個(gè)數(shù)。位的個(gè)數(shù)。如果滿(mǎn)足如果滿(mǎn)足 ，則有可能構(gòu)造出糾正一位或一，則有可能構(gòu)造出糾正一位或一位以上的線性碼位以上的線性碼。i=1時(shí)，時(shí)，1nnc 即對(duì)于碼組長(zhǎng)度為即對(duì)于碼組長(zhǎng)度為n n，信息碼元信息碼元k k位，監(jiān)督元位，監(jiān)督元r r，nr

35、122008.848下面我們通過(guò)例子來(lái)說(shuō)明如何構(gòu)造線性碼。下面我們通過(guò)例子來(lái)說(shuō)明如何構(gòu)造線性碼。 思考：思考： 設(shè)設(shè)(n(n，k)k)中，中，k=4k=4，要求能糾一位錯(cuò)，取要求能糾一位錯(cuò)，取 r=r=？2008.849 解：解： (n(n，k)k)線性分組碼，線性分組碼，k=4k=4，要求能糾一位錯(cuò)，現(xiàn)取要求能糾一位錯(cuò)，現(xiàn)取 r=3r=3，可指示可指示2 23 3-1=7-1=7種錯(cuò)誤，種錯(cuò)誤， 碼長(zhǎng)碼長(zhǎng)n=4+3=7n=4+3=7，表示為：表示為： C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 其中其中C C6 6C C5 5C C4 4C C

36、3 3為信息碼元，為信息碼元，C C2 2C C1 1C C0 0為監(jiān)督元為監(jiān)督元由由r=3r=3，可有三個(gè)監(jiān)督方程和校正子，設(shè)為可有三個(gè)監(jiān)督方程和校正子，設(shè)為s s1 1s s2 2s s3 321rn 恰好滿(mǎn)足恰好滿(mǎn)足 , ,故可糾一位錯(cuò)。故可糾一位錯(cuò)。2008.850設(shè)設(shè)s s1 1s s2 2s s3 3三位校正三位校正子與誤碼位置的對(duì)子與誤碼位置的對(duì)應(yīng)關(guān)系為：應(yīng)關(guān)系為：0 0 00 0 00 0 10 0 10 1 00 1 01 0 01 0 00 1 10 1 11 0 11 0 11 1 01 1 01 1 11 1 1誤碼位置誤碼位置無(wú)錯(cuò)無(wú)錯(cuò) C C0 0 C C1 1 C

37、C2 2 C C3 3 C C4 4 C C5 5 C C6 6S S1 1 S S2 2 S S3 3 于是監(jiān)督碼元于是監(jiān)督碼元C C2 2C C1 1C C0 0應(yīng)應(yīng)由以下由以下監(jiān)督方程監(jiān)督方程決定。決定。C C2 2=C=C6 6+C+C5 5+C+C4 4C C1 1=C=C6 6+C+C5 5+C+C3 3C C0 0=C=C6 6+C+C4 4+C+C3 3監(jiān)督元與信息元之間的線性方程組監(jiān)督元與信息元之間的線性方程組s s1 1=C=C2 2+C+C6 6+C+C5 5+C+C4 4=0s s2 2=C=C1 1+C+C6 6+C+C5 5+C+C3 3=0s s3 3=C=C0

38、0+C+C6 6+C+C4 4+C+C3 3=02008.851于是得到于是得到(7(7，4)4)線性分組碼如下：線性分組碼如下： 序序 碼碼 字字 號(hào)號(hào) 信息元信息元 監(jiān)督元監(jiān)督元 8 1 0 0 0 1 1 18 1 0 0 0 1 1 1 9 1 0 0 1 1 0 0 9 1 0 0 1 1 0 0 10 1 0 1 0 0 1 0 10 1 0 1 0 0 1 0 11 1 0 1 1 0 0 1 11 1 0 1 1 0 0 1 12 1 1 0 0 0 0 1 12 1 1 0 0 0 0 1 13 1 1 0 1 0 1 0 13 1 1 0 1 0 1 0 14 1 1 1

39、0 1 0 0 14 1 1 1 0 1 0 0 15 1 1 1 1 1 1 1 15 1 1 1 1 1 1 1 序序 碼碼 字字 號(hào)號(hào) 信息元信息元 監(jiān)督元監(jiān)督元 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 2 0 0 1 0 1 0 1 2 0 0 1 0 1 0 1 3 0 0 1 1 1 1 0 3 0 0 1 1 1 1 0 4 0 1 0 0 1 1 0 4 0 1 0 0 1 1 0 5 0 1 0 1 1 0 1 5 0 1 0 1 1 0 1 6 0 1 1 0 0 1 1 6 0 1 1

40、0 0 1 1 7 0 1 1 1 0 0 0 7 0 1 1 1 0 0 02008.8529.4.2 監(jiān)督矩陣 將前面的監(jiān)督方程改寫(xiě)成矩陣的形式，將前面的監(jiān)督方程改寫(xiě)成矩陣的形式， C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 可看成為編碼矢量，于是有：可看成為編碼矢量，于是有：記做：記做：TTHC00TCH監(jiān)督方程監(jiān)督方程2008.853H - H - 監(jiān)督矩陣監(jiān)督矩陣 不滿(mǎn)足以上關(guān)系的為非典型矩陣，典型矩陣和不滿(mǎn)足以上關(guān)系的為非典型矩陣，典型矩陣和非典型矩陣之間可以轉(zhuǎn)換。非典型矩陣之間可以轉(zhuǎn)換。2/ 2/ H H矩陣各行是線性無(wú)關(guān)的。矩陣各

41、行是線性無(wú)關(guān)的。行數(shù)行數(shù)-監(jiān)督元的個(gè)數(shù)監(jiān)督元的個(gè)數(shù)r r列數(shù)列數(shù)-碼組長(zhǎng)度碼組長(zhǎng)度 n nI Ir r為為r r階單位陣階單位陣1/ 1/ 當(dāng)有當(dāng)有H=P H=P IrIr 時(shí)稱(chēng)為典型矩陣，時(shí)稱(chēng)為典型矩陣，2008.854利用監(jiān)督方程，我們可以對(duì)線性碼的利用監(jiān)督方程，我們可以對(duì)線性碼的封閉性加以證明封閉性加以證明 即H陣與編碼碼字的轉(zhuǎn)置乘積為0，可用來(lái)作為判斷接收碼組是否錯(cuò)的依據(jù)。,/3TTOCH2008.855 設(shè)監(jiān)督方程設(shè)監(jiān)督方程A A1 1、A A2 2均為均為線性碼集合中的許用碼線性碼集合中的許用碼組，因此有組，因此有 令兩許用碼組相加令兩許用碼組相加 A A1 1+A+A2 2帶入監(jiān)

42、督方程，有：帶入監(jiān)督方程，有：02THA01THA因此，因此， A A1 1+A+A2 2亦為許用碼組。亦為許用碼組。0)(2121TTTHAHAHAA2008.8569.4.3 生成矩陣 當(dāng)給出信息組后，如何方便迅速地求出整個(gè)當(dāng)給出信息組后，如何方便迅速地求出整個(gè)編碼碼組，即如何生成編碼矢量編碼碼組，即如何生成編碼矢量？C C2 2=C=C6 6+C+C5 5+C+C4 4C C1 1=C=C6 6+C+C5 5+C+C3 3C C0 0=C=C6 6+C+C4 4+C+C3 3由監(jiān)督元與信息元之間的關(guān)系：由監(jiān)督元與信息元之間的關(guān)系：TPCCCCCCC3456012或者可以寫(xiě)成：或者可以寫(xiě)成

43、：2008.857QCCCCCCC3456012令令QPT則有：則有：給給Q Q的左邊，加一個(gè)的左邊，加一個(gè)k kk k階的單位矩陣，則構(gòu)成：階的單位矩陣，則構(gòu)成：G=G=I Ik k Q Q稱(chēng)為稱(chēng)為生成矩陣生成矩陣，且為典型形式。典型，且為典型形式。典型G G矩陣矩陣行數(shù)行數(shù)- - 信息元的個(gè)數(shù)信息元的個(gè)數(shù)k k列數(shù)列數(shù)- - 碼組長(zhǎng)度碼組長(zhǎng)度 n n每行本身就是一個(gè)許用碼組每行本身就是一個(gè)許用碼組TTHG00TGH于是有：于是有：矩陣和非典型矩陣之間可以轉(zhuǎn)換。矩陣和非典型矩陣之間可以轉(zhuǎn)換。2008.858碼字的前面碼字的前面 k k 位為信息位，后面位為信息位，后面 位為位為監(jiān)督位監(jiān)督位一

44、般情況，定義線性分組碼的碼字有如下形式：一般情況，定義線性分組碼的碼字有如下形式：信息碼元信息碼元監(jiān)督位監(jiān)督位信息信息位位編碼編碼 碼字碼字kkn kn系統(tǒng)形式的線性分組碼系統(tǒng)形式的線性分組碼1210()nnn kn kCccccc 120()kkMmmm02121mmmccckkknnnkn 0M G編碼編碼 kkn 2008.859設(shè)信息組生成矩陣生成矩陣編碼碼組編碼碼組CM G6543Mcccc2008.860. )2階矩陣，各行線性無(wú)關(guān)為nkG1）由G和信息組即可產(chǎn)生全部碼字.通過(guò)典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。通過(guò)典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。G稱(chēng)為典型生成矩陣。3) kGI Q2

45、008.861011010101001110100G （1）試確定試確定(n,k)，并求，并求H ； (2) 寫(xiě)出監(jiān)督元與信息元的關(guān)系式及寫(xiě)出監(jiān)督元與信息元的關(guān)系式及 該（該（n,k）碼的全部碼字；碼的全部碼字； (3) 確定最小碼距及檢錯(cuò)能力。確定最小碼距及檢錯(cuò)能力。例：設(shè)已知設(shè)已知2008.862110100011010101001解：求H，需確定P，TQPQPT應(yīng)將已知的那個(gè)G轉(zhuǎn)換成典型形式，求出Q，再利用 求出G。011010101001110100G011010110100101001H=P Ir=100101010110001011rTIQ2008.863 (2) 0THC0000

46、101010110001011012345cccccc設(shè)C= 012345cccccc于是有：110100011010101001345cccGMC監(jiān)督元與信息元的關(guān)系式2008.864用三位二進(jìn)制數(shù)的所有用三位二進(jìn)制數(shù)的所有8種狀態(tài)帶入，可得到所有碼字如右表種狀態(tài)帶入，可得到所有碼字如右表。 序號(hào) 碼 字 0 0 0 0 0 0 0 1 0 0 1 0 1 1 2 0 1 0 1 1 0 3 0 1 1 1 0 1 4 1 0 0 1 0 1 5 1 0 1 1 1 0 6 1 1 0 0 1 1 7 1 1 1 0 0 0(3) 確定最小碼距及確定最小碼距及 檢錯(cuò)能力檢錯(cuò)能力所以有：所以有

47、：d d0 0=3=3可用于檢兩位錯(cuò)或糾一位錯(cuò)。利用性質(zhì)知：最小利用性質(zhì)知：最小碼距碼距d0 0等于非零碼等于非零碼字的最小重量即字的最小重量即d0 0=wminmin2008.8659.4.4 校正子S 發(fā)送端經(jīng)過(guò)編碼后給出：發(fā)送端經(jīng)過(guò)編碼后給出：0121cccccnn接收端收到的碼組為：接收端收到的碼組為：0121rrrrRnn兩者的差記為：兩者的差記為：0121eeeeCREnniiiiicrcre10表示第表示第 i 位無(wú)錯(cuò)位無(wú)錯(cuò)表示第表示第 i 位有錯(cuò)位有錯(cuò)E稱(chēng)為錯(cuò)誤圖樣。共有稱(chēng)為錯(cuò)誤圖樣。共有2n個(gè)錯(cuò)誤圖樣。個(gè)錯(cuò)誤圖樣。當(dāng)當(dāng) E為全零錯(cuò)誤圖樣時(shí)，為全零錯(cuò)誤圖樣時(shí)，R=C 沒(méi)有傳輸錯(cuò)

48、誤沒(méi)有傳輸錯(cuò)誤;2008.866TTHR0可可利用利用E檢出或糾正錯(cuò)誤；檢出或糾正錯(cuò)誤；TTHR0傳輸中的錯(cuò)誤超出了可糾錯(cuò)的范圍。傳輸中的錯(cuò)誤超出了可糾錯(cuò)的范圍。但可能有但可能有兩種兩種情況：情況：(n,k)可檢測(cè)的錯(cuò)誤圖樣數(shù)為可檢測(cè)的錯(cuò)誤圖樣數(shù)為 2n - 2k(n,k)可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為 2n-k - 1這時(shí)的錯(cuò)誤圖樣稱(chēng)為不可檢測(cè)的錯(cuò)誤圖樣這時(shí)的錯(cuò)誤圖樣稱(chēng)為不可檢測(cè)的錯(cuò)誤圖樣一般來(lái)講，一般來(lái)講，E=0， 則則R=C，可滿(mǎn)足監(jiān)督方程可滿(mǎn)足監(jiān)督方程E0，則，則RC，不滿(mǎn)足監(jiān)督方程不滿(mǎn)足監(jiān)督方程檢錯(cuò)：當(dāng)檢錯(cuò)：當(dāng)S=0時(shí)，認(rèn)為時(shí)，認(rèn)為E=0，當(dāng)，當(dāng)S 0時(shí)，認(rèn)為時(shí)，認(rèn)為E 0

49、,校正子校正子 S 的計(jì)算的計(jì)算TTTTTEHEHCHHECRHS)(即校正子只與錯(cuò)誤圖樣即校正子只與錯(cuò)誤圖樣E有關(guān)。有關(guān)。2008.867構(gòu)造標(biāo)準(zhǔn)陣列的一般方法如下：構(gòu)造標(biāo)準(zhǔn)陣列的一般方法如下：1）用概率譯碼確定各伴隨式）用概率譯碼確定各伴隨式S對(duì)應(yīng)的差錯(cuò)圖案對(duì)應(yīng)的差錯(cuò)圖案E，共，共 對(duì)對(duì)；2）表格為）表格為 列，列， 行，先確定第一行和第一列，第一行為行，先確定第一行和第一列，第一行為 個(gè)個(gè)碼字碼字 ，第一列為，第一列為 ；3）各列對(duì)應(yīng)的元素為第一列的）各列對(duì)應(yīng)的元素為第一列的 和該列的和該列的 之和；之和；2n2k2n k2kiEjciEjC0C1C21kC00SE000EC011ECC

50、02121kkECC11SE101ECE11EC121kEC2121n kn kSE02121n kn kECE121n kEC2121n kkEC陪集首 譯碼時(shí)，計(jì)算伴隨式譯碼時(shí)，計(jì)算伴隨式S，查表獲得錯(cuò)誤圖樣，查表獲得錯(cuò)誤圖樣E，最后恢復(fù)出，最后恢復(fù)出發(fā)送碼字發(fā)送碼字CER。2008.868例：例：已知監(jiān)督矩陣：已知監(jiān)督矩陣： 若接收為：若接收為： R= 0 0 0 0 0 1 1 ，試確定是否錯(cuò)誤，試確定是否錯(cuò)誤，若接收錯(cuò)誤，試進(jìn)行糾錯(cuò)。若接收錯(cuò)誤，試進(jìn)行糾錯(cuò)。2008.869TTEHRHS 110100010001110101011111 1100000R= 0 0 0 0 0 1 1

51、 ，解：計(jì)算校正子解：計(jì)算校正子2008.8700 0 00 0 00 0 10 0 10 1 00 1 01 0 01 0 00 1 10 1 11 0 11 0 11 1 01 1 01 1 11 1 1誤碼位置誤碼位置無(wú)錯(cuò)無(wú)錯(cuò) C C0 0 C C1 1 C C2 2 C C3 3 C C4 4 C C5 5 C C6 6S S1 1 S S2 2 S S3 3錯(cuò)誤圖樣：錯(cuò)誤圖樣： E= 0 0 0 1 0 0 0 對(duì)照校正子與誤碼位置，確定錯(cuò)誤圖樣：對(duì)照校正子與誤碼位置，確定錯(cuò)誤圖樣：011TEH2008.871于是：于是：R=R+E = 0 0 0 0 0 1 1 + 0 0 0 1

52、 0 0 0 由于由于 ，當(dāng)只發(fā)生一位錯(cuò)碼時(shí)，矩陣，當(dāng)只發(fā)生一位錯(cuò)碼時(shí)，矩陣E E中中只有一個(gè)非零元素，與只有一個(gè)非零元素，與H H的轉(zhuǎn)置相乘的結(jié)果是選的轉(zhuǎn)置相乘的結(jié)果是選出其中的一列，即校正子與出其中的一列，即校正子與H H矩陣的哪一列相同，矩陣的哪一列相同，則該列即為碼元發(fā)生錯(cuò)誤的位置。則該列即為碼元發(fā)生錯(cuò)誤的位置。 TEHS = 0 0 0 1 0 1 1 2008.872(n，k)線性分組碼編、譯碼過(guò)程小結(jié)： 編碼過(guò)程：編碼過(guò)程： 設(shè)線性分組碼為設(shè)線性分組碼為(n，k)，0121mmmmMkk信息碼為：信息碼為：1) 根據(jù)生成矩陣或監(jiān)督矩陣，根據(jù)生成矩陣或監(jiān)督矩陣，2) 由由C=MG0

53、 求出所有碼字，且為系統(tǒng)碼。求出所有碼字，且為系統(tǒng)碼。H0=P IrG0=Ik QQPT求出典型生成矩陣；求出典型生成矩陣；2008.873譯碼過(guò)程：譯碼過(guò)程：1） 由收到的碼組由收到的碼組R計(jì)算校正子計(jì)算校正子S；TRHS TTHRS或2） 由由S判決是否有錯(cuò)并通過(guò)判決是否有錯(cuò)并通過(guò) 找出錯(cuò)誤圖樣；找出錯(cuò)誤圖樣；TEHS 3） 按照按照 R+E=C 計(jì)算并還原計(jì)算并還原 C；4）將碼組）將碼組C還原成原信息組還原成原信息組M。2008.8749.4.5 漢明碼漢明碼是用于糾一位錯(cuò)誤的線性分組碼。漢明碼是用于糾一位錯(cuò)誤的線性分組碼。特點(diǎn)：特點(diǎn)：12 rn最小碼距：最小碼距： 30d糾錯(cuò)能力：糾

54、錯(cuò)能力：1t編碼效率編碼效率 ：R1knrrnnn Rn當(dāng) 很大時(shí)，2008.875例n=15的漢明碼，其監(jiān)督位為多少？編碼的漢明碼，其監(jiān)督位為多少？編碼效率為多少？效率為多少？2008.876解：解：4161212rnnrr，可知：由于是其信息位有于是其信息位有 15-4=11 位位此漢明碼為（此漢明碼為（15，11）碼）碼編碼效率：編碼效率：R/11/1573%k n其監(jiān)督位有其監(jiān)督位有 15-11=4 位位2008.877 漢明碼是線性分組碼，因此其監(jiān)督矩陣同樣漢明碼是線性分組碼，因此其監(jiān)督矩陣同樣有有n n列、列、r r行，當(dāng)監(jiān)督位數(shù)給定后，即可構(gòu)造出行，當(dāng)監(jiān)督位數(shù)給定后，即可構(gòu)造出漢

55、明碼。漢明碼。例，例，r=3 H H矩陣的矩陣的n n列由除了全零以外的列由除了全零以外的 個(gè)個(gè)r r位碼位碼構(gòu)成，每碼組出現(xiàn)一次且全部出現(xiàn)。（構(gòu)成，每碼組出現(xiàn)一次且全部出現(xiàn)。（H H不唯一）不唯一）21r0001011001010101001101000111G101100111010101110100H構(gòu)造構(gòu)造2008.878得到的漢明碼如下所示：得到的漢明碼如下所示：信息位監(jiān)督位信息位監(jiān)督位a6a5a4a300000001001000110100010101100111a2a1a0000011101110110101011000a6a5a4a31000100110101010110011

56、0111101111a2a1a01111000100010010101001112008.879（7，4）漢明碼編碼器）漢明碼編碼器a6a5a4a3信息組信息組a0a1a2a3a4碼字碼字+a5a6+2008.880完備碼 糾正單個(gè)錯(cuò)誤的漢明碼中，糾正單個(gè)錯(cuò)誤的漢明碼中，r r 位校正子碼組與位校正子碼組與誤碼圖樣一一對(duì)應(yīng)，最充分地利用了監(jiān)督位所能誤碼圖樣一一對(duì)應(yīng)，最充分地利用了監(jiān)督位所能提供的信息。提供的信息。 在一般情況下，對(duì)于能糾正在一般情況下，對(duì)于能糾正t t個(gè)錯(cuò)誤的線性分個(gè)錯(cuò)誤的線性分組碼組碼(n(n，k)k)，應(yīng)滿(mǎn)足以下不等式：應(yīng)滿(mǎn)足以下不等式： 因此，漢明碼也是糾一位錯(cuò)的線性分組

57、碼中，因此，漢明碼也是糾一位錯(cuò)的線性分組碼中，編碼效率最高的編碼效率最高的。tiintnnnknrCCCC12112122008.881tiintnnnknrCCCC1211212 上式取等號(hào)時(shí)，校正子與誤碼不超過(guò)上式取等號(hào)時(shí)，校正子與誤碼不超過(guò)t t個(gè)的所個(gè)的所有圖樣一一對(duì)應(yīng)，監(jiān)督碼元得到最充分的利用，有圖樣一一對(duì)應(yīng)，監(jiān)督碼元得到最充分的利用，這種線性分組碼即完備碼。這種線性分組碼即完備碼。 除漢明碼外，迄今為止，找到的唯一能糾除漢明碼外，迄今為止，找到的唯一能糾正多個(gè)錯(cuò)誤的完備碼為正多個(gè)錯(cuò)誤的完備碼為(23(23，12)12)戈雷碼。戈雷碼。 t=3t=3漢明碼就是一種完備碼。漢明碼就是一

58、種完備碼。 該式亦稱(chēng)為漢明界，它給出已知該式亦稱(chēng)為漢明界，它給出已知k k和和t t時(shí)，時(shí)，所需要的監(jiān)督位數(shù)。所需要的監(jiān)督位數(shù)。2008.882列陣的個(gè)來(lái)構(gòu)成時(shí)，可任選其中nHnrn12 但此時(shí)構(gòu)成的則非漢明碼。但此時(shí)構(gòu)成的則非漢明碼。 通常選擇碼重最小的矢量?jī)?yōu)先。通常選擇碼重最小的矢量?jī)?yōu)先。例試構(gòu)造一個(gè)試構(gòu)造一個(gè)k=5的可糾一個(gè)錯(cuò)的線性分組碼的可糾一個(gè)錯(cuò)的線性分組碼1/ 計(jì)算最短的碼長(zhǎng)；計(jì)算最短的碼長(zhǎng)；2/ 構(gòu)造構(gòu)造H；3/ 求生成矩陣求生成矩陣G；4/ 求信息組為求信息組為(10101)的編碼碼字的編碼碼字C。2008.883解：解： 1/ 因?yàn)橐驗(yàn)閠 等于等于1, 且要求且要求k=5,

59、可用試探法確定可用試探法確定n設(shè)：設(shè)：n-k=3，則則 不滿(mǎn)足糾錯(cuò)要求；不滿(mǎn)足糾錯(cuò)要求； 853712123nkn設(shè)：設(shè)：n-k=4，則則 滿(mǎn)足糾錯(cuò)要求；滿(mǎn)足糾錯(cuò)要求； 9541512124nkn于是取于是取n=9，此時(shí)此時(shí)r = n-k = 4，(9, 5)線性分組碼線性分組碼2008.8842/ r=4，四位碼共有四位碼共有 種狀態(tài)，除全零外種狀態(tài)，除全零外 都可用于構(gòu)造都可用于構(gòu)造H矩陣。矩陣。1624 為了構(gòu)造典型矩陣，選為了構(gòu)造典型矩陣，選1000，0100，0010，0001四碼組，然后從其余的四碼組，然后從其余的11個(gè)碼組中，再選出個(gè)碼組中，再選出5個(gè)，通常個(gè)，通常按照碼重從小到

60、大選擇。按照碼重從小到大選擇。100010100010011010001001001000100111HPIr實(shí)際只需實(shí)際只需9個(gè)個(gè)2008.885110010000011001000100100100010100010001100001 QIGk4/ M=1 0 1 0 1C=MG=1 0 1 0 1 0 1 1 0Q3/ 求生成矩陣求生成矩陣 已知已知 TPQ Ik于是有：于是有：2008.8869.5 循環(huán)碼9.5.1 9.5.1 循環(huán)碼原理循環(huán)碼原理 循環(huán)碼是線性分組碼的一個(gè)重要子類(lèi)，也是循環(huán)碼是線性分組碼的一個(gè)重要子類(lèi)，也是目前研究最成熟的一類(lèi)碼。它不僅有封閉性，且還目前研究最成熟的