第九章 差錯控制編碼2012

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

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

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

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

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

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

7、幀。 2008.8132987654321029876543210 只對出錯信息重發(fā)，因此傳輸效率大大提只對出錯信息重發(fā)，因此傳輸效率大大提高高 。但收發(fā)兩端都要有足夠的存儲空間。但收發(fā)兩端都要有足夠的存儲空間。 選擇重發(fā)方式 2008.814反饋信道反饋信道ARQFEC編碼器編碼器正向信道正向信道FEC譯碼器譯碼器ARQ 編碼既有糾錯能力也有檢錯能力，收端收到編碼既有糾錯能力也有檢錯能力，收端收到信息碼組后在收端進行檢測。在糾錯范圍內(nèi)：信息碼組后在收端進行檢測。在糾錯范圍內(nèi)：糾正；超出范圍：通過糾正；超出范圍：通過ARQARQ方式進行重發(fā)。方式進行重發(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ù)糾錯碼組中信息元是否隱蔽分：根據(jù)糾錯碼組中信息元是否隱蔽分： 系統(tǒng)碼，非系統(tǒng)碼系統(tǒng)碼，非系統(tǒng)碼（3）糾錯碼的分類2008.816根據(jù)碼的用途分：根據(jù)碼的用途分： 檢錯碼檢錯碼 ，糾錯碼，糾錯碼（4）根據(jù)根據(jù)碼元的取值碼元的取值： 二進制碼，多進制碼二進制碼，多進制碼（5）根據(jù)根據(jù)構(gòu)造編碼的數(shù)學(xué)方法構(gòu)造編碼的數(shù)學(xué)方法： 代數(shù)碼，幾何碼，算術(shù)碼代數(shù)碼，幾何碼，算術(shù)碼（6）本課程主要討論糾

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

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

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

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

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

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例：例：一個碼集，只有兩個許用碼：一個碼集，只有兩個許用碼：00000000、11111111，試求其糾、檢錯能力，試求其糾、檢錯能力和編碼效率。和編碼效率。2008.8244、對糾錯編碼的要求對糾錯編碼的要求例：例：一個碼集，只有兩個許用碼：一個碼集，只有兩個許用碼：0000、1111，試求其糾檢錯能力和編碼效率。試求其糾檢錯能力和編碼效率。解：解：根據(jù)碼距的定義，則該碼集根據(jù)碼距的定義，則該碼集d 0 = 4， 1

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

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

17、的實際應(yīng)用價值。具有較大的實際應(yīng)用價值。2008.8276. 有擾信道編碼定理（Shannon第二定理） 對于給定的有擾信道，若信道容量為對于給定的有擾信道，若信道容量為C C，只要發(fā)送端以低于只要發(fā)送端以低于C C的信息速率的信息速率R Rb b發(fā)送信息，發(fā)送信息，則則一定存在一種編碼方法一定存在一種編碼方法，使得譯碼錯誤概，使得譯碼錯誤概率率P P隨著碼長隨著碼長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é)所述的糾錯編碼原理可知，為了減少接收錯誤由上節(jié)所述的糾錯編碼原理可知，為了減少接收錯誤碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。碼元數(shù)量，需要在發(fā)送信息碼元序列中加入監(jiān)督碼元。這樣作的結(jié)果使發(fā)送序列增長，冗余度增大。若仍須這樣作的結(jié)果使發(fā)送序列增長，冗余度增大。若仍須保持發(fā)送信息碼元速率不變，則傳輸速率必須增大，保持發(fā)送信息碼元速率不變，則傳輸速率必須增大，因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中因而增大了系統(tǒng)帶寬。系統(tǒng)帶寬的增大將引起系統(tǒng)中噪聲功率增大，使信噪比下降。信噪比的下降反

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

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

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

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

23、率：2008.833序序 碼碼 字字 序序 碼碼 字字號號 信息碼元信息碼元 監(jiān)督元監(jiān)督元 號號 信息碼元信息碼元 監(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 碼長碼長5 5

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

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

26、，也不能糾錯。也不能糾錯。 2008.8382 2、水平垂直奇偶校驗、水平垂直奇偶校驗碼：碼： 又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。特點：特點：對水平方向和垂直方向的碼元同時實施奇偶監(jiān)督。對水平方向和垂直方向的碼元同時實施奇偶監(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)測突發(fā)錯誤：適于監(jiān)測突發(fā)錯誤：q逐行傳輸時，

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

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

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

30、有偶數(shù)個1 1時，監(jiān)督位取信息位的反碼；時，監(jiān)督位取信息位的反碼；可糾一位、檢測所有兩位錯和部分兩位以上的錯誤?？杉m一位、檢測所有兩位錯和部分兩位以上的錯誤。例：例：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ī)律性的分組碼稱為線性分組碼。線性碼建立在代組碼稱為線性分組碼

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

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

33、則監(jiān)督方程增加，校正子增加。當(dāng)監(jiān)督位增加，則監(jiān)督方程增加，校正子增加。r r位監(jiān)督碼除了用全位監(jiān)督碼除了用全“0”0”表示無錯外，可表示表示無錯外，可表示r21種錯誤圖樣。種錯誤圖樣。(n,k)碼可糾錯的錯誤圖樣數(shù)為：碼可糾錯的錯誤圖樣數(shù)為： 我們把接收碼組我們把接收碼組R R與發(fā)射碼組與發(fā)射碼組C C的差稱為的差稱為錯誤圖樣錯誤圖樣，用用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)碼可檢測的錯誤圖樣數(shù)為碼可檢測的錯誤圖樣數(shù)為 2n-2k2 n-k -1=2 r-1不可檢測的錯誤圖樣數(shù)為不可檢測的錯誤圖樣數(shù)為2k-12008.8471nc2nctnctiinc12 n-k-1 + + =對于能糾正對于能糾正 t 個錯誤的線性分組碼個錯誤的線性分組碼(n,k)應(yīng)滿足：應(yīng)滿足：inc是錯是錯 i 位的個數(shù)。位的個數(shù)。如果滿足如果滿足 ，則有可能構(gòu)造出糾正一位或一，則有可能構(gòu)造出糾正一位或一位以上的線性碼位以上的線性碼。i=1時，時，1nnc 即對于碼組長度為即對于碼組長度為n n，信息碼元信息碼元k k位，監(jiān)督元位，監(jiān)督元r r，nr

35、122008.848下面我們通過例子來說明如何構(gòu)造線性碼。下面我們通過例子來說明如何構(gòu)造線性碼。 思考：思考： 設(shè)設(shè)(n(n，k)k)中，中，k=4k=4，要求能糾一位錯，取要求能糾一位錯，取 r=r=？2008.849 解：解： (n(n，k)k)線性分組碼，線性分組碼，k=4k=4，要求能糾一位錯，現(xiàn)取要求能糾一位錯，現(xiàn)取 r=3r=3，可指示可指示2 23 3-1=7-1=7種錯誤，種錯誤， 碼長碼長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，可有三個監(jiān)督方程和校正子，設(shè)為可有三個監(jiān)督方程和校正子，設(shè)為s s1 1s s2 2s s3 321rn 恰好滿足恰好滿足 , ,故可糾一位錯。故可糾一位錯。2008.850設(shè)設(shè)s s1 1s s2 2s s3 3三位校正三位校正子與誤碼位置的對子與誤碼位置的對應(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誤碼位置誤碼位置無錯無錯 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)線性分組碼如下：線性分組碼如下： 序序 碼碼 字字 號號 信息元信息元 監(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 序序 碼碼 字字 號號 信息元信息元 監(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)督方程改寫成矩陣的形式，將前面的監(jiān)督方程改寫成矩陣的形式， 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)督矩陣 不滿足以上關(guān)系的為非典型矩陣，典型矩陣和不滿足以上關(guān)系的為非典型矩陣，典型矩陣和非典型矩陣之間可以轉(zhuǎn)換。非典型矩陣之間可以轉(zhuǎn)換。2/ 2/ H H矩陣各行是線性無關(guān)的。矩陣各

41、行是線性無關(guān)的。行數(shù)行數(shù)-監(jiān)督元的個數(shù)監(jiān)督元的個數(shù)r r列數(shù)列數(shù)-碼組長度碼組長度 n nI Ir r為為r r階單位陣階單位陣1/ 1/ 當(dāng)有當(dāng)有H=P H=P IrIr 時稱為典型矩陣，時稱為典型矩陣，2008.854利用監(jiān)督方程，我們可以對線性碼的利用監(jiān)督方程，我們可以對線性碼的封閉性加以證明封閉性加以證明 即H陣與編碼碼字的轉(zhuǎn)置乘積為0，可用來作為判斷接收碼組是否錯的依據(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)給出信息組后，如何方便迅速地求出整個當(dāng)給出信息組后，如何方便迅速地求出整個編碼碼組，即如何生成編碼矢量編碼碼組，即如何生成編碼矢量？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或者可以寫成：或者可以寫成

43、：2008.857QCCCCCCC3456012令令QPT則有：則有：給給Q Q的左邊，加一個的左邊，加一個k kk k階的單位矩陣，則構(gòu)成：階的單位矩陣，則構(gòu)成：G=G=I Ik k Q Q稱為稱為生成矩陣生成矩陣，且為典型形式。典型，且為典型形式。典型G G矩陣矩陣行數(shù)行數(shù)- - 信息元的個數(shù)信息元的個數(shù)k k列數(shù)列數(shù)- - 碼組長度碼組長度 n n每行本身就是一個許用碼組每行本身就是一個許用碼組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階矩陣，各行線性無關(guān)為nkG1）由G和信息組即可產(chǎn)生全部碼字.通過典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。通過典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。G稱為典型生成矩陣。3) kGI Q2

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

46、101010110001011012345cccccc設(shè)C= 012345cccccc于是有：110100011010101001345cccGMC監(jiān)督元與信息元的關(guān)系式2008.864用三位二進制數(shù)的所有用三位二進制數(shù)的所有8種狀態(tài)帶入，可得到所有碼字如右表種狀態(tài)帶入，可得到所有碼字如右表。 序號 碼 字 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) 確定最小碼距及確定最小碼距及 檢錯能力檢錯能力所以有：所以有

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

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

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

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

51、 ，解：計算校正子解：計算校正子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誤碼位置誤碼位置無錯無錯 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錯誤圖樣：錯誤圖樣： E= 0 0 0 1 0 0 0 對照校正子與誤碼位置，確定錯誤圖樣：對照校正子與誤碼位置，確定錯誤圖樣：011TEH2008.871于是：于是：R=R+E = 0 0 0 0 0 1 1 + 0 0 0 1

52、 0 0 0 由于由于 ，當(dāng)只發(fā)生一位錯碼時，矩陣，當(dāng)只發(fā)生一位錯碼時，矩陣E E中中只有一個非零元素，與只有一個非零元素，與H H的轉(zhuǎn)置相乘的結(jié)果是選的轉(zhuǎn)置相乘的結(jié)果是選出其中的一列，即校正子與出其中的一列，即校正子與H H矩陣的哪一列相同，矩陣的哪一列相同，則該列即為碼元發(fā)生錯誤的位置。則該列即為碼元發(fā)生錯誤的位置。 TEHS = 0 0 0 1 0 1 1 2008.872(n，k)線性分組碼編、譯碼過程小結(jié)： 編碼過程：編碼過程： 設(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譯碼過程：譯碼過程：1） 由收到的碼組由收到的碼組R計算校正子計算校正子S；TRHS TTHRS或2） 由由S判決是否有錯并通過判決是否有錯并通過 找出錯誤圖樣；找出錯誤圖樣；TEHS 3） 按照按照 R+E=C 計算并還原計算并還原 C；4）將碼組）將碼組C還原成原信息組還原成原信息組M。2008.8749.4.5 漢明碼漢明碼是用于糾一位錯誤的線性分組碼。漢明碼是用于糾一位錯誤的線性分組碼。特點：特點：12 rn最小碼距：最小碼距： 30d糾錯能力：糾

54、錯能力：1t編碼效率編碼效率 ：R1knrrnnn Rn當(dāng) 很大時，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列由除了全零以外的列由除了全零以外的 個個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完備碼 糾正單個錯誤的漢明碼中，糾正單個錯誤的漢明碼中，r r 位校正子碼組與位校正子碼組與誤碼圖樣一一對應(yīng)，最充分地利用了監(jiān)督位所能誤碼圖樣一一對應(yīng)，最充分地利用了監(jiān)督位所能提供的信息。提供的信息。 在一般情況下，對于能糾正在一般情況下，對于能糾正t t個錯誤的線性分個錯誤的線性分組碼組碼(n(n，k)k)，應(yīng)滿足以下不等式：應(yīng)滿足以下不等式： 因此，漢明碼也是糾一位錯的線性分組

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

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

59、可用試探法確定可用試探法確定n設(shè)：設(shè)：n-k=3，則則 不滿足糾錯要求；不滿足糾錯要求； 853712123nkn設(shè)：設(shè)：n-k=4，則則 滿足糾錯要求；滿足糾錯要求； 9541512124nkn于是取于是取n=9，此時此時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個碼組中，再選出個碼組中，再選出5個，通常個，通常按照碼重從小到

60、大選擇。按照碼重從小到大選擇。100010100010011010001001001000100111HPIr實際只需實際只需9個個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)碼是線性分組碼的一個重要子類，也是循環(huán)碼是線性分組碼的一個重要子類，也是目前研究最成熟的一類碼。它不僅有封閉性，且還目前研究最成熟的