1、第第9 9章章差錯控制編碼差錯控制編碼南京航空航天大學信息科學與技術學院南京航空航天大學信息科學與技術學院 通信原理教研組通信原理教研組copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組2引言引言1糾錯編碼的基本原理糾錯編碼的基本原理2常用的簡單編碼常用的簡單編碼3線性分組碼線性分組碼4循環碼循環碼5第第9章章 差錯控制編碼差錯控制編碼67卷積碼卷積碼網格編碼調制網格編碼調制copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組39.1 引言引言信道信道解調解調信源信源編碼編碼加密加密調制調制解密解密譯碼譯碼信宿信宿噪聲噪聲同步系

2、統同步系統信源編碼信源編碼 信道編碼信道編碼 差錯控制差錯控制ASKFSKPSKDPSK數字通信的組成數字通信的組成A/DA/D數據壓縮數據壓縮copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組4采用信道編碼采用信道編碼 在通信過程中，會受到各種外來干擾，如脈沖干擾，隨在通信過程中，會受到各種外來干擾，如脈沖干擾，隨機噪聲干擾，人為干擾及通信線路傳輸性能的限制都將使信機噪聲干擾，人為干擾及通信線路傳輸性能的限制都將使信號失真。由于以上原因，引起數據信息序列產生錯誤，稱之號失真。由于以上原因，引起數據信息序列產生錯誤，稱之為為差錯差錯。 隨機性錯誤：前后出錯位之

3、間無一定關系，隨機、離散出現。隨機性錯誤：前后出錯位之間無一定關系，隨機、離散出現。突發性錯誤：差錯成串出現，且有一定相關性。突發性錯誤：差錯成串出現，且有一定相關性。差錯的兩大類型：差錯的兩大類型： 合理的設計基帶信號合理的設計基帶信號時域時域/頻域均衡頻域均衡 都能有效的提高傳輸可靠性。都能有效的提高傳輸可靠性。發射功率的提高發射功率的提高copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組5數字通信中的編碼數字通信中的編碼信道編碼：信道編碼：信源編碼：信源編碼： 為為提高信號傳輸的有效性提高信號傳輸的有效性而采取的措施。而采取的措施。為為提高信號傳輸的可靠

4、性提高信號傳輸的可靠性而采取的措施而采取的措施, ,亦稱亦稱差錯控制編碼。差錯控制編碼。 在發送端利用信道編碼器在數據信息中增在發送端利用信道編碼器在數據信息中增加一些監督信息，使不帶規律性或規律性不加一些監督信息，使不帶規律性或規律性不強的原始數字信號變為帶規律性或加強了規強的原始數字信號變為帶規律性或加強了規律性的數字信號，律性的數字信號，信道譯碼器信道譯碼器則利用這些規則利用這些規律性來鑒別是否發生錯誤，或進行錯誤糾正。律性來鑒別是否發生錯誤，或進行錯誤糾正。差錯控制差錯控制copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組6 1、差錯控制方法、差錯控制

5、方法（1）前向糾錯法）前向糾錯法FEC 所發碼具有糾錯能力，收端接收后自動糾所發碼具有糾錯能力，收端接收后自動糾錯，無需反向信道。實時性好，但譯碼設備錯，無需反向信道。實時性好，但譯碼設備復雜，復雜，傳輸效率傳輸效率 。信源信源FEC編碼編碼信道信道FEC譯碼譯碼信宿信宿copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組7（2）信息反饋法）信息反饋法IF信息信號信息信號信息信號信息信號發端收端收端 方法和設備簡單，無需糾檢錯編譯系統。方法和設備簡單，無需糾檢錯編譯系統。但需要但需要雙向信道雙向信道，傳輸效率傳輸效率、實時性差、實時性差 。copyright 信

6、息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組8(3)檢錯重發法檢錯重發法ARQ 所發碼具有檢錯能力，收端接收后判決是否出錯，通所發碼具有檢錯能力，收端接收后判決是否出錯，通過反向信道發送判決結果，發端據此決定是否重發。過反向信道發送判決結果，發端據此決定是否重發。 譯碼設備簡單，對突發錯誤有效，要求有反饋信道。譯碼設備簡單，對突發錯誤有效，要求有反饋信道。信源信源編碼器編碼器正向信道正向信道譯碼器譯碼器信宿信宿緩存器緩存器重發控制器重發控制器反向信道反向信道重發判決器重發判決器工作過程：發送工作過程：發送檢測檢測回復回復重發或發送新的數據重發或發送新的數據copyright

7、信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組9停止等待方式停止等待方式 3221221發送端發送端接收端接收端 ARQARQ的三種實現方式：的三種實現方式： 特點：半雙工工作，簡單，要求的緩存量小，但等待時間較長，特點：半雙工工作，簡單，要求的緩存量小，但等待時間較長，傳輸效率傳輸效率 copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組10 連續重發方式 6543254321065432543210退退N N步方式：從出錯幀開始重發步方式：從出錯幀開始重發優缺點：傳輸效率優缺點：傳輸效率，但重發的，但重發的N N幀中，大部分幀中，大部分為正

8、確，所以仍有浪費。發端緩存必須可存為正確，所以仍有浪費。發端緩存必須可存N N幀。幀。 copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組112987654321029876543210 只對出錯信息重發，因此傳輸效率大大提只對出錯信息重發，因此傳輸效率大大提高高 。但收發兩端都要有足夠的存儲空間。但收發兩端都要有足夠的存儲空間。 選擇重發方式 copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組12反饋信道反饋信道ARQFEC編碼器編碼器正向信道正向信道FEC譯碼器譯碼器ARQ 編碼既有糾錯能力也有檢錯能力，收端收到編碼既有糾

9、錯能力也有檢錯能力，收端收到信息碼組后在收端進行檢測。在糾錯范圍內：信息碼組后在收端進行檢測。在糾錯范圍內：糾正；超出范圍：通過糾正；超出范圍：通過ARQARQ方式進行重發。方式進行重發。 (4) 混合方式copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組13（1）根據各碼組信息碼和監督碼的關系分：根據各碼組信息碼和監督碼的關系分： 線性碼，非線性碼線性碼，非線性碼根據監督碼元是否僅與本組信息元有關根據監督碼元是否僅與本組信息元有關 分組碼，卷積碼分組碼，卷積碼（2）根據糾錯碼組中信息元是否隱蔽分：根據糾錯碼組中信息元是否隱蔽分： 系統碼，非系統碼系統碼，非系

10、統碼（3）糾錯碼的分類糾錯碼的分類copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組14根據碼的用途分：根據碼的用途分： 檢錯碼檢錯碼 ，糾錯碼，糾錯碼（4）根據根據碼元的取值碼元的取值： 二進制碼，多進制碼二進制碼，多進制碼（5）根據根據構造編碼的數學方法構造編碼的數學方法： 代數碼，幾何碼，算術碼代數碼，幾何碼，算術碼（6）本課程主要討論糾隨機錯誤的二進制線性分組碼。本課程主要討論糾隨機錯誤的二進制線性分組碼。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組15糾錯碼的發展概況糾錯碼的發展概況n 通信的數學理論，通信的數

11、學理論，Shannon(1948)Shannon(1948)n 漢明碼，漢明碼，Hamming (1950)Hamming (1950)n 級連碼，級連碼，Forney(1966)Forney(1966)n 卷積碼及有效譯碼，卷積碼及有效譯碼，(60(60年代年代) )n RS RS碼及有效譯碼，碼及有效譯碼，(60(60年代年代) )n TCM TCM，Ungerboeck(1982),Forney(1984)Ungerboeck(1982),Forney(1984)n Turbo Turbo碼，碼，Berrou(1993) Berrou(1993) n LDPC LDPC 碼，碼，Gall

12、ager(1963),Macky(1996)Gallager(1963),Macky(1996)n 空時編碼空時編碼,Tarokh(2000),Tarokh(2000)copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組169.2 糾錯編碼的基本原理糾錯編碼的基本原理1、 幾個術語幾個術語碼長：碼長：碼組中碼元的數目，常用碼組中碼元的數目，常用n n表示；表示；碼距：碼距：兩等長碼字兩等長碼字C C1 1、C C2 2對應位上取值不同的對應位上取值不同的數目，又稱為漢明數目，又稱為漢明(Hamming)(Hamming)距離，記為距離，記為d(cd(c1 1,c

13、,c2 2) )。碼重碼重：碼組中非零碼元的數目，記為：碼組中非零碼元的數目，記為W W；copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組17n=3時，碼距的幾何說明：時，碼距的幾何說明：（ a2 a1 a0 ）a2a1a0（ 110） （ 011 ）d=2110011（ 111） （ 000 ）d=3000111最小碼距最小碼距：在分組碼：在分組碼(n,k)(n,k)中，任意兩個碼字之中，任意兩個碼字之間漢明距離的最小值，記為間漢明距離的最小值，記為d dminmin。最小碼距的大小關系到編碼的檢最小碼距的大小關系到編碼的檢糾糾錯能力錯能力。0101011

14、00001copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組18發送序列發送序列C: (1111011000)接收序列接收序列R: (0110010110)比較比較C和和R，可寫出另一個序列，可寫出另一個序列E：1001001110R = C + E 序列序列E定義為錯誤圖樣定義為錯誤圖樣(Error Pattern)錯誤圖樣：錯誤圖樣：copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組19A A、B B兩消息，可用一位二進制數表示，兩消息，可用一位二進制數表示，A=1A=1、B=0B=0出錯時出錯時無法判定無法判定 增加一個

15、監督位，取增加一個監督位，取11A11A、00B00B 再增加一個監督位，取再增加一個監督位，取111A111A、000B000B許用碼組：許用碼組：00，11禁用碼組：禁用碼組：01，10若收到若收到0101或或1010時，時，可知發生了錯誤，但不能糾正錯誤可知發生了錯誤，但不能糾正錯誤。許用碼組：000，111禁用碼組：001, 010, 100, 011, 101, 110如一位錯如一位錯能夠糾正錯誤能夠糾正錯誤；若兩位錯，；若兩位錯，則只能發現不能糾錯則只能發現不能糾錯2、糾錯或檢錯的原理、糾錯或檢錯的原理copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教

16、研組20因此因此這種（這種（3,13,1）碼，能糾正一個錯，發現兩個錯。）碼，能糾正一個錯，發現兩個錯。 但是但是 (3,1)(3,1)碼中，數據位僅為碼中，數據位僅為1 1位，監督位為位，監督位為兩位，傳輸效率兩位，傳輸效率 可以看出：差錯控制是以可以看出：差錯控制是以犧牲傳輸效率犧牲傳輸效率為代價而為代價而換取了傳輸質量的提高的。糾檢錯能力與加入的監督換取了傳輸質量的提高的。糾檢錯能力與加入的監督元方式和數目有關。元方式和數目有關。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組21分組碼的三個參數分組碼的三個參數碼長碼長 n，信息位，信息位 k，最小距

17、離，最小距離 d0 ， 用符號用符號 (n,k,d0) 表示表示k個信息元個信息元an-1 an-2 ar ar-1 a0 r個監督元個監督元碼長：碼長：n = k+rR=k/n為為編碼效率編碼效率，d0一定一定(糾錯能力一定糾錯能力一定)時，時，k/n大，效率高。大，效率高。 對被傳輸的信息序列分組，每組為對被傳輸的信息序列分組，每組為k k個信息元，對個信息元，對每組按某種關系附加每組按某種關系附加(n-k) (n-k) 個監督碼元個監督碼元 ( (校驗校驗) )，形成，形成為為n n位的碼字。這種方法構成的碼組稱為位的碼字。這種方法構成的碼組稱為分組碼分組碼。3、分組碼、分組碼copyr

18、ight 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組224、分組碼的糾分組碼的糾( (檢檢) )錯能力與最小碼距錯能力與最小碼距d d0 0的關系的關系 任一任一（n n，k k）分組碼，若要在碼字內能：分組碼，若要在碼字內能： 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)個隨機錯誤，個隨機錯誤，則要求：則要求： d d0 0 e+t+1 e+t+1 cop

19、yright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組231 A1 d0eA2（a）A1 A2 d0et（c） A1 d0tA2（b） A2t11copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組24例例9-1一個碼集，只有兩個許用碼：一個碼集，只有兩個許用碼：00000000、11111111，試求其糾、檢錯能力和編碼效率。試求其糾、檢錯能力和編碼效率。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組25解：解：根據碼距的定義，則該碼集根據碼距的定義，則該碼集d0 = 4， 1/ 用于檢錯，用于檢錯

20、，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） 取：取：e=2，t=1，則可滿足上式，即可檢，則可滿足上式，即可檢2個錯誤個錯誤 同時糾一個錯；同時糾一個錯；R=k/n=1/4copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組26copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組275. 差錯控制編碼的效用差錯控

21、制編碼的效用 假設在隨機信道中，發送假設在隨機信道中，發送“0 0”和和“1 1”的錯的錯誤概率相等，都等于誤概率相等，都等于p p，且，且p p1 1，在碼長為，在碼長為n n的碼組中，發生的碼組中，發生r r個錯誤的概率為：個錯誤的概率為：!( )(1)!()!rrn rrnnnP rC pppr nrcopyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組28!( )(1)!()!rrn rrnnnP rC pppr nr例如：當例如：當n=7，p=10-時，則有：時，則有：371077) 1 (pP5227101 . 221)!27( ! 2! 7)2(pp

22、P8337105 . 335)!37( ! 3! 7) 3(ppP 由此可見，即使僅能糾正由此可見，即使僅能糾正1-21-2個錯誤，也可使誤碼個錯誤，也可使誤碼率下降幾個數量級。所以差錯控制編碼具有較大的實率下降幾個數量級。所以差錯控制編碼具有較大的實際應用價值。際應用價值。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組296. 6. 有擾信道編碼定理（有擾信道編碼定理（ShannonShannon第二定理）第二定理） 對于給定的有擾信道，若信道容量為對于給定的有擾信道，若信道容量為C C，只，只要發送端以低于要發送端以低于C C的信息速率的信息速率R R

23、b b發送信息，則發送信息，則一定存在一種編碼方法一定存在一種編碼方法，使得譯碼錯誤概率，使得譯碼錯誤概率P P隨著碼長隨著碼長n n的增加，按指數下降至任意小的值，的增加，按指數下降至任意小的值，表示為表示為 P P e e-nE(Rb)-nE(Rb)E(RE(Rb b) )為誤差指數，為誤差指數，R Rb bC0)0。 Rbmax=C=Blog2(1+S/N) （bit/s）copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組30 1.碼長碼長n和信息速率和信息速率Rb一定時，隨一定時，隨C誤差指數誤差指數E(Rb) P隨指數下降。隨指數下降。 其中其中 C

24、=Blog2(1+S/N)（bit/s） 2.在在C和和Rb一定時一定時(Rb C)，隨碼長，隨碼長n P 隨指數下降隨指數下降(P0)。 數字傳輸系統中，無誤碼傳輸的最高信息速率數字傳輸系統中，無誤碼傳輸的最高信息速率 Rbmax=C=Blog2(1+S/N) （bit/s） 兩個結論：兩個結論：copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組31編碼性能舉例 未采用糾錯編碼時，若接收信噪比等于7dB，編碼前誤碼率約為810-4，圖中A點，在采用糾錯編碼后，誤碼率降至約410-5，圖中B點。這樣，增大發送功率,就能降低誤碼率約一個半數量級。10-610-5

25、10-410-310-210-1編碼后PeAB信噪比 (dB)copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組32 由圖還可以看出，若保持由圖還可以看出，若保持誤碼率在誤碼率在1010-5-5，圖中，圖中C C點，點，未采用編碼時，約需要信未采用編碼時，約需要信噪比噪比E Eb b / n / n0 0 = 9.5 dB = 9.5 dB。在采用這種編碼時，約需在采用這種編碼時，約需要信噪比要信噪比7.5 dB7.5 dB，圖中，圖中D D點。可以節省功率點。可以節省功率2 dB2 dB。通常稱這通常稱這2 dB2 dB為為編碼增益編碼增益。 上面兩種情況付

26、出的代上面兩種情況付出的代價是帶寬增大。價是帶寬增大。10-610-510-410-310-210-1PeCD信噪比 (dB)編碼后copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組33 傳輸速率和傳輸速率和E Eb b/n/n0 0的關系的關系對于給定的傳輸系統式對于給定的傳輸系統式中，中，R RB B為碼元速率。為碼元速率。若希望提高傳輸速率，若希望提高傳輸速率，由上式看出勢必使信噪由上式看出勢必使信噪比下降，誤碼率增大。比下降，誤碼率增大。假設系統原來工作在圖假設系統原來工作在圖中中C C點，提高速率后由點，提高速率后由C C點升到點升到E E點。但加用

27、糾點。但加用糾錯編碼后，仍可將誤碼錯編碼后，仍可將誤碼率降到率降到D D點。這時付出點。這時付出的代價仍是帶寬增大。的代價仍是帶寬增大。10-610-510-410-310-210-1編碼后PeCDE信噪比 (dB)copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組349-3 9-3 常用的簡單編碼常用的簡單編碼1 1、奇偶監督碼：、奇偶監督碼： k=n-1,r=1k=n-1,r=1的線性碼。的線性碼。特點：特點： 碼組中的碼組中的1 1個數是奇數（奇監督碼）個數是奇數（奇監督碼） 或偶數（偶監督碼）。或偶數（偶監督碼）。0021aaann偶監督時，要滿足：偶

28、監督時，要滿足：1021aaann奇監督時，要滿足：奇監督時，要滿足：兩者的校驗能力相同，均只能檢測出奇數個錯誤。兩者的校驗能力相同，均只能檢測出奇數個錯誤。R=k/n=n-1/n=1-1/n編碼效率：編碼效率：copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組35 碼長碼長5 5的偶監督碼的偶監督碼序序 碼碼 字字 序序 碼碼 字字號號 信息碼元信息碼元 監督元監督元 號號 信息碼元信息碼元 監督元監督元 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

29、 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 copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組36 偶監督碼編碼器a4a3a2a1+信息組信息組a0a1a2a3a4碼字碼字12340aaaaacopyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組3701234bbbbbsb3b

30、0b1b2b4+接收碼組BS檢錯信號有錯無錯10偶監督碼的檢錯偶監督碼的檢錯電路電路copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組38 例例9-29-2：一數據序列：一數據序列： 1110011100 1011110111 0110101101 1000110001 1010110101 試對其進行（試對其進行（6 6，5 5）偶校驗編碼，寫出碼序列）偶校驗編碼，寫出碼序列并分析其抗干擾能力并分析其抗干擾能力 copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組39一數據序列一數據序列： 1110011100 1011110

31、111 0110101101 1000110001 1010110101 試對其進行（試對其進行（6 6，5 5）偶校驗編碼，寫出碼序列）偶校驗編碼，寫出碼序列并分析其抗干擾能力并分析其抗干擾能力解：解： （6 6，5 5）, ,將數據序列每將數據序列每5 5碼元分組，碼元分組，123450aaaaaa并作：并作：的運算的運算可得出編碼數據序列：可得出編碼數據序列：11100111001110111101110001101011011110001100010010101101011 1 只能檢測出奇數個錯誤，不能發現偶數個錯誤，只能檢測出奇數個錯誤，不能發現偶數個錯誤，也不能糾錯。也不能糾錯。

32、 copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組402 2、水平垂直奇偶校驗、水平垂直奇偶校驗碼：碼： 又稱行列監督碼或二維奇偶監督碼。又稱行列監督碼或二維奇偶監督碼。特點：特點：對水平方向和垂直方向的碼元同時實施奇偶監督。對水平方向和垂直方向的碼元同時實施奇偶監督。 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行行列列監監督督碼碼copyright

33、信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組41適于監測突發錯誤：q逐行傳輸時，能檢測長度b M+1的突發錯誤;q逐列傳輸時,能檢測長度bL+1的突發錯誤；q還能糾正一些僅在一行中的單個錯誤。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 0L5，M10的行列監督碼的行列監督碼其中其中M為列數，為列數，L為行數為行數copyright 信息科學與技術學院通信原理教研組信息科學

34、與技術學院通信原理教研組423 3、恒比碼：、恒比碼： 又稱等重碼或定又稱等重碼或定1 1碼。碼。特點：特點： 碼組中碼組中0 0，1 1的個數保持不變。的個數保持不變。 若碼長為若碼長為n n，碼重為，碼重為w w，則此碼的碼字個數，則此碼的碼字個數 為：為：C Cn nw w，禁用碼字個數為：，禁用碼字個數為：2 2n n - C- Cn nw w碼字的個數碼字的個數C C5 53 3 =10=10檢錯能力較強，可檢出檢錯能力較強，可檢出所有奇數所有奇數和和部分偶數部分偶數錯誤。錯誤。檢錯能力較強，可檢出所有奇數和部分偶數錯誤。檢錯能力較強，可檢出所有奇數和部分偶數錯誤。適用于傳輸電報或其

35、他鍵盤設備產生的字母或符適用于傳輸電報或其他鍵盤設備產生的字母或符號，但不適合信源發出的是二進制隨機數字序列號，但不適合信源發出的是二進制隨機數字序列的場合。的場合。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組43數字數字碼碼 字字0 01 12 23 34 45 56 67 78 89 901101011010101101011110011100110110101101101011010001110011110101101011110011100011100111010011100113:2 恒比碼恒比碼如：我國的電報，每如：我國的電報，每個漢字用四個

36、個漢字用四個1010進制進制數表示，每位數表示，每位1010進制進制數就采用數就采用 3 3：2 2 恒比恒比碼構成的碼構成的5 5位碼組來表位碼組來表示。示。碼字的個數碼字的個數C C5 53 3 =10=10copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組44作業：4 4、正反碼：、正反碼： 簡單的可糾錯編碼，信元數等于監督元數簡單的可糾錯編碼，信元數等于監督元數特點：特點： 信息位中，有奇數個信息位中，有奇數個1 1時，監督位重復信息位；時，監督位重復信息位； 信息位中，有偶數個信息位中，有偶數個1 1時，監督位取信息位的反碼；時，監督位取信息位的反碼

37、；可糾一位、檢測所有兩位錯和部分兩位以上的錯誤。可糾一位、檢測所有兩位錯和部分兩位以上的錯誤。例：例：11001 1100111001 11001110011100110001 1000110001 100010111001110(n,k) (n,k) 其中其中k=n/2 k=n/2 編碼效率：編碼效率： R=k/n=1/2R=k/n=1/2copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組459.4 線性分組碼9.4.1 9.4.1 基本概念基本概念 可用可用線性方程組線性方程組表述碼的規律性的分表述碼的規律性的分組碼稱為線性分組碼。線性碼建立在代數組碼稱為

38、線性分組碼。線性碼建立在代數學群論基礎上，線性碼各許用碼的集合構學群論基礎上，線性碼各許用碼的集合構成代數學中的群，因此，又稱為群碼。成代數學中的群，因此，又稱為群碼。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組46 1. 1. 含有全零碼字。含有全零碼字。 2.2.任意兩個許用碼字之和仍是一個許用碼字。任意兩個許用碼字之和仍是一個許用碼字。（封閉性封閉性） 3.3.最小碼距最小碼距d d0 0等于非零碼字的最小重量即等于非零碼字的最小重量即d d0 0=W=Wminmin （由此性質可以方便的確定出線性分組碼的最（由此性質可以方便的確定出線性分組碼的最

39、小碼距，進而明確其糾錯能力。）小碼距，進而明確其糾錯能力。） 在群中只有一種運算，就是模在群中只有一種運算，就是模2 2 和。和。線性分組碼的性質線性分組碼的性質：copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組47 奇偶監督碼是一種最簡單的線性碼，我們曾經作了奇偶監督碼是一種最簡單的線性碼，我們曾經作了偶校驗的例子。偶校驗的例子。0021aaann稱為稱為監督監督方程方程。接收時，為了檢測傳輸時是否有錯，還要做同樣的計接收時，為了檢測傳輸時是否有錯，還要做同樣的計算：算：01234bbbbbs有錯無錯10s這里這里S S稱為稱為校正子，校正子，上式也稱上式

40、也稱伴隨式伴隨式。奇偶監督碼中只有一位監督碼，因此只能表示有否錯誤。奇偶監督碼中只有一位監督碼，因此只能表示有否錯誤。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組48當監督位增加，則監督方程增加，校正子增加。當監督位增加，則監督方程增加，校正子增加。r r位監督碼除了用全位監督碼除了用全“0 0”表示無錯外，可表示表示無錯外，可表示r21種錯誤圖樣。種錯誤圖樣。(n,k)碼可糾錯的錯誤圖樣數為：碼可糾錯的錯誤圖樣數為： 我們把接收碼組我們把接收碼組R R與發射碼組與發射碼組C C的差稱為的差稱為錯誤圖樣錯誤圖樣，用用E E表示：表示：E=C-RE=C-R

41、，或者，或者 C=R+EC=R+E (n,k)中，信息碼為中，信息碼為k位，可傳輸位，可傳輸M=2k種信息，當種信息，當增加增加r位的監督位后，有位的監督位后，有2n種狀態，但只取種狀態，但只取2k 種為許種為許用狀態，其他為禁用，用狀態，其他為禁用，(n,k)碼可檢測的錯誤圖樣數為碼可檢測的錯誤圖樣數為 2n-2k2n-k -1=2r-1不可檢測的錯誤圖樣數為不可檢測的錯誤圖樣數為2k-1copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組491nc2nctnctiinc12 n-k-1 + + =對于能糾正對于能糾正 t 個錯誤的線性分組碼個錯誤的線性分組碼

42、(n,k)應滿足：應滿足：inc是錯是錯 i 位的個數。位的個數。如果滿足如果滿足 ，則有可能構造出糾正一位或一位，則有可能構造出糾正一位或一位以上的線性碼以上的線性碼。i=1時，時，1nnc 即對于碼組長度為即對于碼組長度為n n，信息碼元，信息碼元k k位，監督元位，監督元r r，nr12copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組50 思考：思考： 例例9-39-3設設(n(n，k)k)中，中，k=4k=4，要求能糾一位錯，取，要求能糾一位錯，取r=r=？copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組51 解：

43、解： (n(n，k)k)線性分組碼，線性分組碼，k=4k=4，要求能糾一位錯，要求能糾一位錯，現取現取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 C3 3為信息碼元，為信息碼元，C C2 2C C1 1C C0 0為監督元為監督元由由r=3r=3，可有三個監督方程和校正子，設為，可有三個監督方程和校正子，設為s s1 1s s2 2s s3 321rn 恰好滿足恰好滿足

44、, ,故可糾一位錯。故可糾一位錯。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組52設設s1s2s3三位校正子與誤三位校正子與誤碼位置的對應關系為：碼位置的對應關系為：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 C2 2 C C3 3 C C4 4 C C5 5 C C6 6S S1 1 S S2 2 S S3 3 于是監督碼元于是監督碼元C C2 2C C1 1C C0 0應應由以下

45、由以下監督方程監督方程決定。決定。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監督元與信息元之間的線性方程組監督元與信息元之間的線性方程組s1=C2+C6+C5+C4=0s2=C1+C6+C5+C3=0s3=C0+C6+C4+C3=0copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組53于是得到于是得到(7(7，4)4)線性分組碼如下：線性分組碼如下： 序序 碼碼 字字 號號 信息元信息元 監督元監督元 8 1 0 0 0 1 1 18 1 0

46、 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 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 序序 碼碼 字字 號號 信息元信息元 監督元監督元 0 0 0 0 0 0 0 00 0 0 0 0 0

47、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 0 0 1 1 7 0 1 1 1 0 0 0 7 0 1 1 1 0 0 0copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組549.4.2 監督矩陣0001001101010101100

48、101110123456CCCCCCC 將前面的監督方程改寫成矩陣的形式，將前面的監督方程改寫成矩陣的形式， C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 可看成為編碼矢量，于是有：可看成為編碼矢量，于是有：記做：記做：TTHC00TCH監督方程監督方程copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組55H - H - 監督矩陣監督矩陣110110110111P 不滿足以上關系的為非典型矩陣，典型矩陣和不滿足以上關系的為非典型矩陣，典型矩陣和非典型矩陣之間可以轉換。非典型矩陣之間可以轉換。2/ 2/ H H矩陣各

49、行是線性無關的。矩陣各行是線性無關的。行數行數-監督元的個數監督元的個數r r列數列數-碼組長度碼組長度 n nI Ir r為為r r階單位陣階單位陣1/ 1/ 當有當有H=P IrH=P Ir時稱為典型矩陣，時稱為典型矩陣，100I010001copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組56利用監督方程，我們可以對線性碼的利用監督方程，我們可以對線性碼的封閉性加以證明封閉性加以證明 即H陣與編碼碼字的轉置乘積為0，可用來作為判斷接收碼組是否錯的依據。,/3TTOCHcopyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組57

50、 設監督方程設監督方程A A1 1、A A2 2均為線性碼集合中的許用碼均為線性碼集合中的許用碼組，因此有組，因此有 令兩許用碼組相加令兩許用碼組相加 A A1 1+A+A2 2帶入監督方程，有：帶入監督方程，有：02THA01THA因此，因此， A A1 1+A+A2 2亦為許用碼組。亦為許用碼組。0)(2121TTTHAHAHAAcopyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組589.4.3 生成矩陣 當給出信息組后，如何方便迅速地求出整個當給出信息組后，如何方便迅速地求出整個編碼碼組，即如何生成編碼矢量編碼碼組，即如何生成編碼矢量？C C2 2=C=C

51、6 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由監督元與信息元之間的關系：由監督元與信息元之間的關系：3456012110110110111CCCCCCCTPCCCCCCC3456012或者可以寫成：或者可以寫成：copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組59QCCCCCCC3456012令令QPT則有：則有：給給Q Q的左邊，加一個的左邊，加一個k kk k階的單位矩陣，則構成：階的單位矩陣，則構成：G=IG=Ik k Q Q稱為稱為生成矩陣生成矩陣，且為

52、典型形式。典型，且為典型形式。典型G G矩陣矩陣行數行數- - 信息元的個數信息元的個數k k列數列數- - 碼組長度碼組長度 n n每行本身就是一個許用碼組每行本身就是一個許用碼組TTHG00TGH于是有：于是有：矩陣和非典型矩陣之間可以轉換。矩陣和非典型矩陣之間可以轉換。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組60碼字的前面碼字的前面 k k 位為信息位，后面位為信息位，后面 位為位為監督位監督位一般情況，定義線性分組碼的碼字有如下形式：一般情況，定義線性分組碼的碼字有如下形式：信息碼元信息碼元監督位監督位信息信息位位編碼編碼 碼字碼字kkn k

53、n系統形式的線性分組碼系統形式的線性分組碼1210()nnn kn kCccccc 120()kkMmmm02121mmmccckkknnnkn 0M G編碼編碼 kkn copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組61設信息組1000111010011000101010001011G生成矩陣生成矩陣編碼碼組編碼碼組CM G6543Mcccccopyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組62. )2階矩陣，各行線性無關為nkG1）由G和信息組即可產生全部碼字.111110 101011TQP通過典型生成矩陣產生的一定

54、是系統碼。通過典型生成矩陣產生的一定是系統碼。k10000100I00100001G稱為典型生成矩陣。3) kGI Qcopyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組63011010101001110100G （1）試確定試確定(n,k)(n,k)，并求，并求H H ； (2) (2) 寫出監督元與信息元的關系式及寫出監督元與信息元的關系式及 該（該（n,kn,k）碼的全部碼字；）碼的全部碼字； (3) (3) 確定最小碼距及檢錯能力。確定最小碼距及檢錯能力。例9-4設已知設已知copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教

55、研組64110100011010101001解：求H，需確定P，QPT應將已知的那個G轉換成典型形式，求出Q，再利用 求出G。011010101001110100G011010110100101001H=P Ir=100101010110001011rTIQcopyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組65 (2) 0THC5432101101000110100101001cccccc設C= 012345cccccc于是有：110100011010101001345cccGMC監督元與信息元的關系式監督元與信息元的關系式copyright 信息科學與技術學

56、院通信原理教研組信息科學與技術學院通信原理教研組66用三位二進制數的所有用三位二進制數的所有8種狀態帶入，可得到所有碼字如右表種狀態帶入，可得到所有碼字如右表。 序號 碼 字 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) 確定最小碼距及確定最小碼距及 檢錯能力檢錯能力所以有：所以有：d d0 0=3=3可用于檢兩位錯或可用于檢兩位錯或糾一位錯。糾一位錯。利用性質知：最小利用性質知：最小碼距碼距d0 0等于非零碼等

57、于非零碼字的最小重量即字的最小重量即d0 0=wminmincopyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組679.4.4 校正子S 發送端經過編碼后給出：發送端經過編碼后給出：0121cccccnn接收端收到的碼組為：接收端收到的碼組為：0121rrrrRnn兩者的差記為：兩者的差記為：0121eeeeCREnniiiiicrcre10表示第表示第 i 位無錯位無錯表示第表示第 i 位有錯位有錯E稱為錯誤圖樣。共有稱為錯誤圖樣。共有2n個錯誤圖樣。個錯誤圖樣。當當 E為全零錯誤圖樣時，為全零錯誤圖樣時，R=C 沒有傳輸錯誤沒有傳輸錯誤;copyright

58、信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組68TTHR0可利用可利用E檢出或糾正錯誤；檢出或糾正錯誤；TTHR0傳輸中的錯誤超出了可糾錯的范圍。傳輸中的錯誤超出了可糾錯的范圍。可能有可能有兩種兩種情況：情況：(n,k)可檢測的錯誤圖樣數為可檢測的錯誤圖樣數為 2n - 2k(n,k)可糾錯的錯誤圖樣數為可糾錯的錯誤圖樣數為 2n-k - 1這時的錯誤圖樣稱為不可檢測的錯誤圖樣這時的錯誤圖樣稱為不可檢測的錯誤圖樣一般來講，一般來講，E=0， 則則R=C，可滿足監督方程，可滿足監督方程E0，則，則RC，不滿足監督方程，不滿足監督方程檢錯：當檢錯：當S=0時，認為時，認為E=0

59、，當，當S 0時，認為時，認為E 0,校正子校正子 S 的計算的計算TTTTTEHEHCHHECRHS)(即校正子只與錯誤圖樣即校正子只與錯誤圖樣E有關。有關。copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組69標準陣列表標準陣列表kknknknknkkkkCECECEECECECEECECECEECCCCDDDD2232222233323322322222321232101E排列方法排列方法第一個元素。排在零碼字個碼字排在第一行，全碼的）（02),(11Cknk陪陪集集陪陪集集首首copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原

60、理教研組70kknknknknkkkkCECECEECECECEECECECEECCCCDDDD2232222233323322322222321232101E陪陪集集陪陪集集首首下面構成第二行。放在下面，并將放在重作為錯誤圖樣重中選擇重量較小的個剩下的）（iiknCCECEnn212222且希望重量盡可能小。重是前面未出現過的，每行第一個重。有繼續以上過程，用完所）（nn3copyright 信息科學與技術學院通信原理教研組信息科學與技術學院通信原理教研組71構造標準陣列的一般方法如下：構造標準陣列的一般方法如下：1）用概率譯碼確定各伴隨式）用概率譯碼確定各伴隨式S對應的差錯圖案對應的差錯圖