通信原理第十二章 差錯控制xin

1、第第12章章差錯控制編碼差錯控制編碼第12章 差錯控制編碼內(nèi)容簡介：12.1 引言12.2 糾錯編碼的原理12.3 常用的簡單編碼12.4 線性分組碼 12.5 循環(huán)碼第12章 差錯控制編碼主要內(nèi)容：1.基本概念：碼重,碼距,檢錯能力,糾錯能力2.常用編碼3.線性分組碼 4.循環(huán)碼第12章 差錯控制編碼回放信道信道解調解調信源信源編碼編碼加密加密調制調制解密解密譯碼譯碼信宿信宿噪聲噪聲同步系統(tǒng)同步系統(tǒng)信源編碼信源編碼 信道編碼信道編碼 誤差控制誤差控制ASKFSKPSKDPSK數(shù)字通信的組成數(shù)字通信的組成A/DA/D數(shù)據(jù)壓縮數(shù)據(jù)壓縮第12章 差錯控制編碼 在通信過程中，會受到各種外來干擾，如脈

2、沖干擾，隨機噪聲干擾，人為干擾及通信線路傳輸性能的限制都將使信號失真。由于以上原因，引起數(shù)據(jù)信息序列產(chǎn)生錯誤，稱之為差錯。 實際信道中，上述兩種錯誤常同時存在。 隨機性錯誤：前后出錯位之間無一定關系，隨機、離散出現(xiàn)。突發(fā)性錯誤：差錯成串出現(xiàn)，且有一定相關性。差錯的兩大類型：差錯的兩大類型： 合理的設計基帶信號合理的設計基帶信號時域時域/頻域均衡頻域均衡 都能有效的提高傳輸可靠性。都能有效的提高傳輸可靠性。發(fā)射功率的提高發(fā)射功率的提高第12章 差錯控制編碼12.1 12.1 引言引言數(shù)字通信中的編碼分為：數(shù)字通信中的編碼分為：信道編碼：信道編碼：信源編碼：信源編碼： 為提高信號傳輸?shù)挠行远扇?/p>

3、的措施。為提高信號傳輸?shù)挠行远扇〉拇胧樘岣咝盘杺鬏數(shù)目煽啃远扇樘岣咝盘杺鬏數(shù)目煽啃远扇?的措施。亦稱差錯控制編碼。的措施。亦稱差錯控制編碼。 在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中增加一些在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中增加一些監(jiān)督信息，使不帶規(guī)律性或規(guī)律性不強的原始數(shù)字監(jiān)督信息，使不帶規(guī)律性或規(guī)律性不強的原始數(shù)字信號變?yōu)閹б?guī)律性或加強了規(guī)律性的數(shù)字信號，信道信號變?yōu)閹б?guī)律性或加強了規(guī)律性的數(shù)字信號，信道譯碼器則利用這些規(guī)律性來鑒別是否發(fā)生錯誤，或進譯碼器則利用這些規(guī)律性來鑒別是否發(fā)生錯誤，或進行錯誤糾正。行錯誤糾正。差錯控制差錯控制第12章 差錯控制編碼 1、差錯控制方法（1）前

4、向糾錯法）前向糾錯法FEC 所發(fā)碼具有糾錯能力，收端接收后自動糾錯，無需反向所發(fā)碼具有糾錯能力，收端接收后自動糾錯，無需反向信道。實時性好，但譯碼設備復雜，信道。實時性好，但譯碼設備復雜，傳輸效率傳輸效率 。信源FEC編碼信道FEC譯碼信宿（2）信息反饋法）信息反饋法IF信息信號信息信號信息信號信息信號發(fā)端發(fā)端收端收端 方法和設備簡單，無需糾檢錯編譯系統(tǒng)。但需要雙向方法和設備簡單，無需糾檢錯編譯系統(tǒng)。但需要雙向信道，信道，傳輸效率傳輸效率、實時性差、實時性差 。第12章 差錯控制編碼 (3)檢錯重發(fā)法ARQ 所發(fā)碼具有檢錯能力，收端接收后判決是否出錯，通過所發(fā)碼具有檢錯能力，收端接收后判決是否

5、出錯，通過反向信道發(fā)送判決結果，發(fā)端據(jù)此決定是否重發(fā)。反向信道發(fā)送判決結果，發(fā)端據(jù)此決定是否重發(fā)。 譯碼設備簡單，對突發(fā)錯誤有效，要求有反饋信道。譯碼設備簡單，對突發(fā)錯誤有效，要求有反饋信道。信源信源編碼器編碼器正向信道正向信道譯碼器譯碼器信宿信宿緩存器緩存器重發(fā)控制器重發(fā)控制器反向信道反向信道重發(fā)判決器重發(fā)判決器工作過程：發(fā)送工作過程：發(fā)送檢測檢測回復回復重發(fā)或發(fā)送新的數(shù)據(jù)重發(fā)或發(fā)送新的數(shù)據(jù)第12章 差錯控制編碼停止等待方式停止等待方式 3221221發(fā)送端發(fā)送端接收端接收端ARQ的三種實現(xiàn)方式： 特點：半雙工工作，簡單，要求的緩存量小，但等待時間較長，特點：半雙工工作，簡單，要求的緩存量小

6、，但等待時間較長，傳輸效率傳輸效率 第12章 差錯控制編碼 連續(xù)重發(fā)方式 6543254321065432543210退退N N步方式：從出錯幀開始重發(fā)步方式：從出錯幀開始重發(fā) 例例N=4N=4 優(yōu)缺點：傳輸效率優(yōu)缺點：傳輸效率，但重發(fā)的，但重發(fā)的N N幀中，大部分為正確，所以幀中，大部分為正確，所以 仍有浪費。發(fā)端緩存必須可存仍有浪費。發(fā)端緩存必須可存N N幀。幀。 第12章 差錯控制編碼2987654321029876543210 只對出錯信息重發(fā)，因此傳輸效率大大提高只對出錯信息重發(fā)，因此傳輸效率大大提高 。但收發(fā)。但收發(fā)兩端都要有足夠的存儲空間。兩端都要有足夠的存儲空間。 選擇重發(fā)方式

7、 第12章 差錯控制編碼反饋信道反饋信道ARQFEC編碼器編碼器正向信道正向信道FEC譯碼器譯碼器ARQ 編碼既有糾錯能力也有檢錯能力，收端收到信息碼組后編碼既有糾錯能力也有檢錯能力，收端收到信息碼組后在收端進行檢測。在糾錯范圍內(nèi)：糾正；超出范圍：通過在收端進行檢測。在糾錯范圍內(nèi)：糾正；超出范圍：通過ARQARQ方式進行重發(fā)。方式進行重發(fā)。 (4) 混合方式 第12章 差錯控制編碼（1）根據(jù)各碼組信息碼和監(jiān)督碼的關系分：根據(jù)各碼組信息碼和監(jiān)督碼的關系分： 線性碼，非線性碼線性碼，非線性碼根據(jù)監(jiān)督碼元是否僅與本組信息元有關根據(jù)監(jiān)督碼元是否僅與本組信息元有關 分組碼，卷積碼分組碼，卷積碼（2）根據(jù)

8、糾錯碼組中信息元是否隱蔽分：根據(jù)糾錯碼組中信息元是否隱蔽分： 系統(tǒng)碼，非系統(tǒng)碼系統(tǒng)碼，非系統(tǒng)碼（3）根據(jù)碼的用途分：根據(jù)碼的用途分： 檢錯碼檢錯碼 ，糾錯碼，糾錯碼（4）根據(jù)根據(jù)碼元的取值碼元的取值： 二進制碼，多進制碼二進制碼，多進制碼（5）根據(jù)根據(jù)構造編碼的數(shù)學方法構造編碼的數(shù)學方法： 代數(shù)碼，幾何碼，算術碼代數(shù)碼，幾何碼，算術碼（6） 2、 糾錯碼的分類第12章 差錯控制編碼12.2 糾錯編碼的基本原理1、 幾個術語幾個術語本課程主要討論糾隨機錯誤的二進制線性分組碼。本課程主要討論糾隨機錯誤的二進制線性分組碼。碼長：碼組中碼元的數(shù)目，常用碼長：碼組中碼元的數(shù)目，常用n 表示；表示；碼距：

9、兩等長碼字碼距：兩等長碼字C1、C2對應位上取值不同的數(shù)目，又稱對應位上取值不同的數(shù)目，又稱 為漢明為漢明(Hamming)距離，記為距離，記為d(c1,c2)。碼重：碼組中非零碼元的數(shù)目，記為碼重：碼組中非零碼元的數(shù)目，記為W；最小碼距：在分組碼最小碼距：在分組碼(n,k)中，任意兩個碼字之間漢明距離的最中，任意兩個碼字之間漢明距離的最 小值，記為小值，記為dmin。碼距的大小關系到編碼的糾檢錯能力。碼距的大小關系到編碼的糾檢錯能力。例：例：10011 w=3 01101 d=4第12章 差錯控制編碼n=3時，碼距的幾何說明：時，碼距的幾何說明：（ a2 a1 a0 ）a2a1a0（ 110

10、） （ 011 ）d=2110011（ 111） （ 000 ）d=3000111第12章 差錯控制編碼A A、B B兩消息，可用一位二進制數(shù)表示，兩消息，可用一位二進制數(shù)表示，A=1A=1、B=0B=0出錯時無法判定出錯時無法判定 。例例 增加一個監(jiān)督位，取增加一個監(jiān)督位，取11A11A、00B,00B,若收到若收到0101或或1010時，時， 可知發(fā)生了錯誤，但不能糾正錯誤?？芍l(fā)生了錯誤，但不能糾正錯誤。 再增加一個監(jiān)督位，取再增加一個監(jiān)督位，取111A111A、000B,000B,如一位錯：如一位錯： B001 A110B001 A110；若兩位錯若兩位錯011,110011,110則

11、只能發(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)督位為兩位，傳輸效率傳輸效率 可以看出：差錯控制是以犧牲傳輸效率為代可以看出：差錯控制是以犧牲傳輸效率為代價而換取了傳輸質量的提高的。糾檢錯能力與加價而換取了傳輸質量的提高的。糾檢錯能力與加入的監(jiān)督元數(shù)目成正比。入的監(jiān)督元數(shù)目成正比。 2、 糾錯或檢錯的原理第12章 差錯控制編碼分組碼的三個參數(shù)分組碼的三個參數(shù)碼長碼長 n，信息位，信息位 k，最小距離，最小距離 d0 ，

12、 用符號用符號 (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個信息元，對每組個信息元，對每組按某種關系附加按某種關系附加(n-k) 個監(jiān)督碼元個監(jiān)督碼元 (校驗校驗)，形成為，形成為n位的碼字。位的碼字。這種方法構成的碼組稱為這種方法構成的碼組稱為分組碼分組碼。第12章 差錯控制編碼分組碼的表示：符號（分組碼的表示：符號（n，k）n 碼組

13、的總位數(shù)碼組的總位數(shù)k 碼組中信息碼元的數(shù)目碼組中信息碼元的數(shù)目r = n-k 監(jiān)督碼元的數(shù)目監(jiān)督碼元的數(shù)目編碼效率編碼效率nrnkR/1/R R越大，信息位比重大，有效性越高。越大，信息位比重大，有效性越高。第12章 差錯控制編碼 3、分組碼的糾(檢)錯能力與最小碼距d0的關系 任一任一（ 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

14、e(et)(et)個隨機錯誤，則個隨機錯誤，則 要求：要求： d d0 0 e e+t+1 +t+1 第12章 差錯控制編碼 A1 d 0eA2（a）A1 A2 d 0et（c） A1 d 0tA2（b）A2t第12章 差錯控制編碼e檢錯能力檢錯能力 t糾錯能力糾錯能力10ed（1）時能檢出時能檢出e e個或個或e e個以下錯碼。個以下錯碼。（2）（3） 120 td 時能糾正時能糾正t t個或個或t t個以下錯碼。個以下錯碼。時能檢出時能檢出t t個或個或e e個以下錯碼。個以下錯碼。)(10teted第12章 差錯控制編碼4、對糾錯編碼的要求、對糾錯編碼的要求例：例：一個碼集，只有兩個許用

15、碼：一個碼集，只有兩個許用碼：0000、1111，試求其糾檢錯能力和編碼效率。試求其糾檢錯能力和編碼效率。解：解：根據(jù)碼距的定義，則該碼集根據(jù)碼距的定義，則該碼集d 0 = 4， 1/ 用于檢錯，e d d0 1=3，即可檢3個錯誤；2/ 用于糾錯，t (d d01)/2=3/2，取整，即可糾1個錯誤；3/ 同時用于糾、檢錯， d d0 e+t+1 e+t+1 （e et t） ?。篹=2，t=1，則可滿足上式，即可檢2個錯誤 同時糾一個錯；R=k/n=1/4第12章 差錯控制編碼5. 差錯控制編碼的效用： 假設在隨機信道中，發(fā)送假設在隨機信道中，發(fā)送“0”和和“1”的錯誤概率相等，都的錯誤概

16、率相等，都等于等于p，且，且p1，在碼長為，在碼長為n的碼組中，發(fā)生的碼組中，發(fā)生r個錯誤的概率個錯誤的概率為：為：rrnrrrnnprnrnppCrP)!( !)1 ()(例如：當例如：當n=7，p=10時，則有：時，則有：371077) 1 ( pP5227101 . 221)!27( ! 2! 7)2(ppP8337105 . 335)!37( ! 3! 7) 3(ppP 由此可見，即使僅能糾正由此可見，即使僅能糾正1-2個錯誤，也可使誤碼率下降個錯誤，也可使誤碼率下降幾個數(shù)量級。所以差錯控制編碼具有較大的實際應用價值。幾個數(shù)量級。所以差錯控制編碼具有較大的實際應用價值。第12章 差錯控

17、制編碼例例12-1 12-1 已知已知8 8個碼組為：（個碼組為：（O00000O00000），（），（001110001110），），（010101010101），（），（011011011011），（），（100011100011），）， （1O11011O1101），），（110110110110），（），（111000111000），），（1 1）求以上碼組的最小碼距；（）求以上碼組的最小碼距；（2 2）若此）若此8 8個碼組用于檢錯，個碼組用于檢錯，可檢出幾位錯？（可檢出幾位錯？（3 3）若用于糾錯碼，能糾幾位？（）若用于糾錯碼，能糾幾位？（4 4）若同時用于糾錯和檢錯，糾錯、檢錯性

18、能如何？若同時用于糾錯和檢錯，糾錯、檢錯性能如何？30d10 ed13 e2e120 td123 t1t10ted （1）（2）（3）（4）第12章 差錯控制編碼例例12-2 12-2 已知兩碼組（已知兩碼組（00000000）和（）和（11111111），若該碼組），若該碼組用于檢錯，能檢出幾位錯碼？若用于糾錯，能糾用于檢錯，能檢出幾位錯碼？若用于糾錯，能糾正幾位錯碼？若同時用于糾錯和檢錯，問各能糾、正幾位錯碼？若同時用于糾錯和檢錯，問各能糾、檢幾位錯碼？檢幾位錯碼？ 40d14 e3e124 t1t14te1t2e （1）（2）（3）第12章 差錯控制編碼一一. 奇偶監(jiān)督碼奇偶監(jiān)督碼在信息

19、為后加一位校驗位在信息為后加一位校驗位12.3 12.3 常用的簡單編碼常用的簡單編碼00121aaaann 奇監(jiān)督碼奇監(jiān)督碼偶監(jiān)督碼偶監(jiān)督碼特點：只能檢測出奇數(shù)個錯碼，不能檢測出偶數(shù)特點：只能檢測出奇數(shù)個錯碼，不能檢測出偶數(shù)10121aaaann奇偶監(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)督碼）。第12章 差錯控制編碼序序 碼碼 字字 序序 碼碼 字字號號 信息碼元信息碼元 監(jiān)督元監(jiān)督元 號號 信息碼元信息碼元 監(jiān)督元監(jiān)督元 a4 a3 a2

20、 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的偶監(jiān)督碼的偶監(jiān)督碼第12章 差錯控制編碼 偶監(jiān)督碼編碼器a4a3a2a1+信息組信息組a0a1a2a3a4碼字碼字12340aaaaa第12章

21、差錯控制編碼偶監(jiān)督碼的檢錯電路01234bbbbbsb3b0b1b2b4+接收碼組BS檢錯信號有錯無錯10第12章 差錯控制編碼例：一數(shù)據(jù)序列：例：一數(shù)據(jù)序列： 1110011100 1011110111 0110101101 1000110001 1010110101 試對其進行（試對其進行（6 6，5 5）偶校驗編碼，寫出碼序列）偶校驗編碼，寫出碼序列并分析其抗干擾能力并分析其抗干擾能力解：解： （6 6，5 5）, ,將數(shù)據(jù)序列每將數(shù)據(jù)序列每5 5碼元分組，碼元分組，123450aaaaaa并作：并作：的運算的運算可得出編碼數(shù)據(jù)序列：可得出編碼數(shù)據(jù)序列：11100111001110111

22、101110001101011011110001100010010101101011 1 只能檢測出奇數(shù)個錯誤，不能發(fā)現(xiàn)偶數(shù)個錯誤，只能檢測出奇數(shù)個錯誤，不能發(fā)現(xiàn)偶數(shù)個錯誤，也不能糾錯。也不能糾錯。 第12章 差錯控制編碼二二. 二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn 行監(jiān)督位行監(jiān)督位列監(jiān)督位列監(jiān)督位第12章 差錯控制編碼水平垂直奇偶校驗水平垂直奇偶校驗碼：碼： 又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。特點：特點：對水平方向和垂直方向的碼元同時實施奇偶監(jiān)督。對水平方向和垂直方向

23、的碼元同時實施奇偶監(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)督督碼碼第12章 差錯控制編碼特點：特點：（1）能檢測出每一行（列）中的奇數(shù)個或偶數(shù)個錯碼，）能檢測出每一行（列）中的奇數(shù)個或偶數(shù)個錯碼，但不能檢測出行列同時成偶數(shù)個出現(xiàn)的錯碼。但不能檢測出行列同時成偶數(shù)個出現(xiàn)的錯碼。（2）能檢測突發(fā)性錯誤（成串錯碼）。）能檢測突發(fā)性錯誤（成串錯碼）。（3）能糾正錯碼。）能糾

24、正錯碼。第12章 差錯控制編碼恒比碼：恒比碼： 又稱等重碼或定又稱等重碼或定1 1碼。碼。特點：特點： 碼組中碼組中0 0，1 1的個數(shù)保持不變。的個數(shù)保持不變。 若碼長為若碼長為n n，碼重為，碼重為w w，則此碼的碼字個數(shù)，則此碼的碼字個數(shù) 為：為：C Cn nw w，禁用碼字個數(shù)為：，禁用碼字個數(shù)為：2 2n n - C- Cn nw w例如：我國的電報，每個漢字用四個例如：我國的電報，每個漢字用四個1010進制數(shù)表進制數(shù)表 示，每位示，每位1010進制數(shù)就采用進制數(shù)就采用 3 3：2 2 恒比碼構恒比碼構 成的成的5 5位碼組來表示。位碼組來表示。碼字的個數(shù)碼字的個數(shù)C C5 53 3

25、 =10=10檢錯能力較強，可檢出所奇數(shù)和部分偶數(shù)錯誤。檢錯能力較強，可檢出所奇數(shù)和部分偶數(shù)錯誤。第12章 差錯控制編碼作業(yè)：正反碼：正反碼： 簡單的可糾錯編碼，信元數(shù)等于監(jiān)督元數(shù)簡單的可糾錯編碼，信元數(shù)等于監(jiān)督元數(shù)特點：特點： 信息位中，有奇數(shù)個信息位中，有奇數(shù)個1 1時，監(jiān)督位重復信息位；時，監(jiān)督位重復信息位； 信息位中，有偶數(shù)個信息位中，有偶數(shù)個1 1時，監(jiān)督位取信息位的反碼；時，監(jiān)督位取信息位的反碼；可糾一位、檢測所有兩位錯和部分兩位以上的錯誤?？杉m一位、檢測所有兩位錯和部分兩位以上的錯誤。例：例：11001 1100111001 11001110011100110001 100011

26、0001 100010111001110(n,k) (n,k) 其中其中k=n/2 k=n/2 編碼效率：編碼效率： R=k/n=1/2R=k/n=1/2第12章 差錯控制編碼 四四. .正反碼正反碼例：信息位：例：信息位：11001 11001 監(jiān)督位：監(jiān)督位：1100111001 信息位：信息位：10001 10001 監(jiān)督位：監(jiān)督位：01110011101.1.編碼規(guī)則：編碼規(guī)則：（1 1）當信息位中有奇數(shù)個）當信息位中有奇數(shù)個1 1時，監(jiān)督位是信息位時，監(jiān)督位是信息位的簡單重復。的簡單重復。（2 2）當信息位中有偶數(shù)個）當信息位中有偶數(shù)個1 1時，監(jiān)督位是信息位時，監(jiān)督位是信息位的反碼

27、。的反碼。第12章 差錯控制編碼例：例：11001 1100111001 11001=00000=00000 10001 01110=11111 10001 01110=111112.2.譯碼方法譯碼方法（1 1）將碼組中的信息碼與監(jiān)督碼進行模）將碼組中的信息碼與監(jiān)督碼進行模2 2加得合加得合成碼組。成碼組。（2 2）若信息碼中有奇數(shù)個）若信息碼中有奇數(shù)個1 1，則合成碼組即為，則合成碼組即為檢驗碼組。檢驗碼組。 若信息碼中有偶數(shù)個若信息碼中有偶數(shù)個1 1，則合成碼組的反，則合成碼組的反碼即為檢驗碼組。碼即為檢驗碼組。（3 3）觀察檢驗碼組中）觀察檢驗碼組中1 1的個數(shù)，按的個數(shù)，按p278p

28、278進行檢錯進行檢錯和糾錯。和糾錯。第12章 差錯控制編碼12.4 線性分組碼l 線性分組碼中信息碼元和監(jiān)督碼元是用線性方程聯(lián)系起來的。線性碼建立在代數(shù)學群論基礎上，線性碼各許用碼組的集合構成代數(shù)學中的群，因此，又稱群碼。l主要性質 任意兩許用碼組之和(模2和)仍為一許用碼組。 (封閉性) 碼的最小距離等于非零碼的最小重量。第12章 差錯控制編碼奇偶監(jiān)督碼是一種最簡單的線性碼，偶校驗奇偶監(jiān)督碼是一種最簡單的線性碼，偶校驗時時lS稱為校正子，又稱伴隨式。S=0無錯，S=1 有錯。l一般，由r個監(jiān)督方程式計算得r個校正子，可以用來指示2r-1種錯誤，對于一位誤碼來說，就可以指示2r-1個誤碼位置

29、。l對于(n,k)碼，如果滿足2r-1n 則可能構造出糾正一位或一位以上錯誤的線性碼。021aaaSnn第12章 差錯控制編碼設分組碼設分組碼(n,k)中中k=4,為糾正一位錯碼為糾正一位錯碼,要求要求r3, 則則 n=k+r=7S1S2S3錯碼位置S1S2S3錯碼位置001a0101a4010a1110a5100a2111a6011a3000無錯一一.以（以（7，4）分組碼為例）分組碼為例第12章 差錯控制編碼024561aaaaS013562aaaaS003463aaaaS4562aaaa3561aaaa3460aaaa計算監(jiān)督位判斷錯碼位置按上述方法構造的糾正單個錯誤的線性分組碼稱為漢明

30、碼。碼長 n=2r 1 信息位 k= 2r 1 r 監(jiān)督位r（1）（2）第12章 差錯控制編碼碼字：碼字：A=A=（ ）3456aaaa012aaa其中信息位：其中信息位：監(jiān)督位監(jiān)督位 ：3456aaaa012aaa若分組碼可用下列線性方程組表示：若分組碼可用下列線性方程組表示：346035614562aaaaaaaaaaaa（“+”為模為模2加加 ）則：該分組碼為（則：該分組碼為（7 7，4 4）線性分組碼（共有）線性分組碼（共有1616個個碼字）碼字）第12章 差錯控制編碼表表 9-2 (7,4)碼的碼字表碼的碼字表 第12章 差錯控制編碼性質：性質：（1 1）封閉性：任意）封閉性：任意2

31、 2個許用碼組之和（模個許用碼組之和（模2 2加）仍加）仍為一個許用碼組。為一個許用碼組。（2 2）有零元：）有零元：（3 3）有負元：）有負元：（4 4）結合律成立：）結合律成立：iioAAAoiiAAA)()(432432AAAAAA（任一碼字即為本身的負元）（任一碼字即為本身的負元）nrrrnkrrr11211212編碼速率編碼速率=第12章 差錯控制編碼l（1）改寫為000101110123456aaaaaaa001010110123456aaaaaaa010011010123456aaaaaaa表示成矩陣形式1001101010101100101110123456aaaaaaa=00

32、0PIr二. 監(jiān)督矩陣H第12章 差錯控制編碼0001011001110101011101000123456aaaaaaa用矩陣表示為：用矩陣表示為：并記為：并記為：OHAOAHTTT或第12章 差錯控制編碼H陣可表示為：陣可表示為：rPIH100110101010110010111PkrrIrr（ 階）（ 階單位陣）矩陣矩陣H H稱為（稱為（7 7，4 4）線性分組碼得監(jiān)督矩陣。上式）線性分組碼得監(jiān)督矩陣。上式也稱為典型監(jiān)督矩陣。若不是典型監(jiān)督矩陣要用也稱為典型監(jiān)督矩陣。若不是典型監(jiān)督矩陣要用初等變換化成典型矩陣。初等變換化成典型矩陣。第12章 差錯控制編碼三三. . 生成矩陣生成矩陣G G

33、 若信息碼元已知，通過監(jiān)督矩陣可以求出監(jiān)若信息碼元已知，通過監(jiān)督矩陣可以求出監(jiān)督碼元。督碼元。346035614562aaaaaaaaaaaa345603456134562110110110111aaaaaaaaaaaaaaa34563456012110110110111aaaaaaaaPaaa用矩陣表示：用矩陣表示： 11010101111134563456012aaaaPaaaaaaaT或或第12章 差錯控制編碼 將上式擴展可以由已知信息碼元求得整個碼將上式擴展可以由已知信息碼元求得整個碼組。組。110100010101000110010111000134560123456aaaaaaaa

34、aaaTPIG41101000101010001100101110001令：令：G稱為生成矩陣第12章 差錯控制編碼典型監(jiān)督矩陣和典型生成矩陣存在以下關系式：典型監(jiān)督矩陣和典型生成矩陣存在以下關系式：rTrIQIPHTkkPIQIG),(knknr例：（例：（7，4）rIPH100110101010110010111TkPIG1101000101010001100101110001第12章 差錯控制編碼 34560123456aaaaaaaaaaa1101000101010001100101110001全部碼字為：全部碼字為：0001110110011010110100110010011110

35、01010100110100000000001111111001011101010111000011100110101001010011001111000130d10 ed2e120 td1t第12章 差錯控制編碼四四. . 伴隨式（校正子）伴隨式（校正子）S S 設發(fā)送碼字為設發(fā)送碼字為 ，接收碼字，接收碼字為為 ，由于干擾，噪聲可能引入，由于干擾，噪聲可能引入誤差，使接收碼組與發(fā)送碼組不同，因此誤差，使接收碼組與發(fā)送碼組不同，因此有有 ，其中，其中 是傳輸中產(chǎn)是傳輸中產(chǎn)生的錯誤行矩陣。對于二進制碼元有生的錯誤行矩陣。對于二進制碼元有: E矩陣中哪一位碼元為矩陣中哪一位碼元為1就表示接收碼字

36、中就表示接收碼字中對應位有錯。對應位有錯。E稱為錯誤圖樣。稱為錯誤圖樣。021aaaAnn0121bbbbBnnEAB021eeeEnnABABE模模2第12章 差錯控制編碼 在接收端用在接收端用H來檢測接收來檢測接收B中的錯碼。中的錯碼。令：令：THBS伴隨式或校正子：伴隨式或校正子：如果如果B與與A相同，則：相同，則：0TTHAHBS否則：否則：0THBS又又EABTTTTTHEHEHAHEAHBS)( 表示校正子表示校正子S僅與信道的錯誤圖樣僅與信道的錯誤圖樣E有關，而與有關，而與發(fā)送的碼字發(fā)送的碼字A無關。無關。 第12章 差錯控制編碼表表 9-3 (7,4)碼碼S與與E的對應關系的對

37、應關系 第12章 差錯控制編碼五五. . 如何利用如何利用S S完成糾錯完成糾錯對（對（7，4）線性分組碼）線性分組碼100110101010110010111H設設B中最高位有錯，錯誤圖樣中最高位有錯，錯誤圖樣0000001E1110000001TTHHES它的轉置它的轉置111TS恰好是典型恰好是典型H陣的第一列。陣的第一列。第12章 差錯控制編碼同理可求出：同理可求出：若次高位有錯若次高位有錯011S，即，即 恰好是恰好是H的第二列。的第二列。TS 因此，在接收碼組中只錯一位碼元情況下，因此，在接收碼組中只錯一位碼元情況下，計算出的校正子計算出的校正子S總是和典型監(jiān)督矩陣總是和典型監(jiān)督矩

38、陣 中的中的某一行相同。某一行相同。 TH例：例：1010000B1011010000HBHSTT與第三列相同與第三列相同第12章 差錯控制編碼0000100E正確碼組為：正確碼組為： 101010000001001010000EBA六六. . 漢明碼漢明碼 漢明碼是一種可以糾正單個隨機錯誤的線性漢明碼是一種可以糾正單個隨機錯誤的線性分組碼。它的最小碼距分組碼。它的最小碼距 ，監(jiān)督元位數(shù)，監(jiān)督元位數(shù) ，碼長，碼長 ，信息元位，信息元位數(shù)數(shù) ，編碼效率，編碼效率當當r很大時，很大時， ，因此是一種高效碼。，因此是一種高效碼。30d)2( rknr12 rnrkr121211212rrrrrnkR

39、1R第12章 差錯控制編碼 上例中的（上例中的（7，4）線性分組碼就是漢明碼，）線性分組碼就是漢明碼，并且任意調換并且任意調換H矩陣中各列的結果不會影響糾，矩陣中各列的結果不會影響糾，檢錯能力。檢錯能力。 第12章 差錯控制編碼例例 設設 且有且有3個接收碼組個接收碼組l驗證3個接收碼組是否發(fā)生差錯？l若在某碼組中有錯碼，錯碼的校正子是什么？然后再指出發(fā)生錯碼的碼字中，哪位有錯？100101010110001011H1011101B1101012B1100003B第12章 差錯控制編碼解：解：1）若無錯，則錯誤圖樣為）若無錯，則錯誤圖樣為0，S為為000011THBSB1無錯10122THBS

40、B2錯11033THBSB3錯2） S2=H 第1列 E=1 0 0 0 0 0 第1位錯同理 S3=H 第3列 E=0 0 1 0 0 0 第3位錯TEHS 第12章 差錯控制編碼12.5 循環(huán)碼循環(huán)碼 一一. . 概念概念1. 循環(huán)碼：循環(huán)碼： 線性分組碼線性分組碼 （1）封閉性）封閉性 ),(kn（2）循環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)）循環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位之后，所得到的碼組仍為一許用碼組。移位之后，所得到的碼組仍為一許用碼組。 2. 碼多項式碼多項式循環(huán)碼的一許用碼組循環(huán)碼的一許用碼組可表示為：可表示為： ),(0121aaaaAnn012211)(axaxaxa

41、xAnnnn其中：其中：x為碼元位置標記，不考慮其取值。為碼元位置標記，不考慮其取值。碼元碼元 只取只取“1”或或“0”。 ) 1, 1 , 0(niai第12章 差錯控制編碼例例: (7，3）循環(huán)碼中第二個碼組）循環(huán)碼中第二個碼組 1110100)(1234562xxxxxxxA)0010111(2A124xxx如何實現(xiàn)移位：乘一個如何實現(xiàn)移位：乘一個x相當于碼左移一位。相當于碼左移一位。 xxxxxxA2352)()0101110(A3. 按模運算按模運算若若)()()()()(xNxRxQxNxM（ 的次數(shù)小于的次數(shù)小于 ）則：則：)()()(xNxRxM模)(xR)(xN稱為稱為 按模

42、按模 運算后運算后的余式。的余式。)(xM)(xN第12章 差錯控制編碼例：例： 1 133xx模 1 113224xxxxx模4. 規(guī)律規(guī)律（1）循環(huán)碼中，將許用碼組）循環(huán)碼中，將許用碼組 左移左移一位得到的碼字記為：一位得到的碼字記為： 。其。其碼多項式為：碼多項式為：可以證明：可以證明：),(0121aaaaAnn),(1032)1(nnnaaaaA102312)1()(nnnnnaxaxaxaxA 1)()()1(nxxAxxA模 1)()()(niixxAxAx模第12章 差錯控制編碼（2）根據(jù)循環(huán)碼的定義，）根據(jù)循環(huán)碼的定義， 均為均為許用碼字。許用碼字。 因此下列結論：若因此下列

43、結論：若 是許用碼字，則是許用碼字，則 在按模在按模 運算下，也是許用碼字。運算下，也是許用碼字。)()3()2()1(,iAAAA)(xA)(xAxi1nx即：若即：若 1)()()(niixxAxAx模則則 也是許用碼字。也是許用碼字。)()(xAi例例: (7，3）循環(huán)碼）循環(huán)碼)0101110(3A則：則：1)(125xxxxA7n那么那么 1)(734534583xxxxxxxxxxAx模其碼字為其碼字為 。4A第12章 差錯控制編碼二二. . 生成多項式與生成矩陣生成多項式與生成矩陣G G1. (n，k) 循環(huán)碼碼組集合中（全循環(huán)碼碼組集合中（全“0”除外）最除外）最高階數(shù)最小的多

44、項式高階數(shù)最小的多項式（n-k）階）階稱為生成多項稱為生成多項式，記為式，記為g(x)。2. 集合中其它碼多項式都是集合中其它碼多項式都是 運算運算下的余式。下的余式。 即可以由生成多項式即可以由生成多項式g(x)產(chǎn)生循環(huán)碼的全部碼產(chǎn)生循環(huán)碼的全部碼字。字。) 1()(nixngx模第12章 差錯控制編碼3. 生成矩陣生成矩陣G循環(huán)碼的生成矩陣多項式可以寫成循環(huán)碼的生成矩陣多項式可以寫成_)()()()()(21xgxxgxgxxgxxGkk以（以（7，3）循環(huán)碼為例）循環(huán)碼為例1)(24xxxxg)()()()(2xgxxgxgxxG111010001110100011101G經(jīng)線性變換，將

45、經(jīng)線性變換，將G整理成典型生成矩陣。整理成典型生成矩陣。第12章 差錯控制編碼TkPIG111010001110101101001整個碼組可表示為：整個碼組可表示為：)()()()()(2456456xgxxgxgxaaaxGaaaxA任意一個碼多項式都能被任意一個碼多項式都能被g(x)整除。整除。)()()(4526xgaxxgaxgxa)()(4526xgaxaxa第12章 差錯控制編碼三三. . 監(jiān)督多項式、監(jiān)督矩陣監(jiān)督多項式、監(jiān)督矩陣1. 對于對于(n，k) 循環(huán)碼，循環(huán)碼， 可分解成可分解成g(x)和其和其它因式的乘積。它因式的乘積。)()(1xhxgxn1nx記為：記為：稱稱h(x

46、)為監(jiān)督多項式，其矩陣形式為：為監(jiān)督多項式，其矩陣形式為：kIPH 以（以（7，3）循環(huán)碼為例）循環(huán)碼為例111001111101TP1000101010011100101100001011H第12章 差錯控制編碼) 1)(1)(1(13237xxxxxx2. 對于（對于（7，3）循環(huán)碼，）循環(huán)碼，g(x)的最高次為的最高次為4所以，有兩種方案所以，有兩種方案) 1() 1(123347xxxxxx) 1() 1(324xxxxx第一種方案：第一種方案：1)(234xxxxg101110011100100111001101110001011100010111G1)(23xxxh第12章 差錯控

47、制編碼碼字：碼字：01011101110010101110000000000010111100101111001010111001第二種方案：第二種方案：1)(3xxxh1)(24xxxxg111010001110101101001111010001110100011101G碼字：碼字：10011100111010111010000000000100111101001100111011101001第12章 差錯控制編碼例例: 已知已知(7，4）循環(huán)碼的生成多項式為）循環(huán)碼的生成多項式為（1）求典型生成矩陣和典型監(jiān)督矩陣；）求典型生成矩陣和典型監(jiān)督矩陣；（2）輸入信息碼為）輸入信息碼為11001

48、011，求編碼后的系統(tǒng)碼；，求編碼后的系統(tǒng)碼；（3）全部碼組；）全部碼組；（4）糾、檢錯能力）糾、檢錯能力 123 xx解：解：1)(23xxxg)()()()()(23xgxxgxgxxgxxGTkPIG10110001110100110001001100011011000010110000101100001011第12章 差錯控制編碼100111001001110011101rIPH0011101)(1101)(1010011)(0011)()()(213456xGxAxGxAxGaaaaxA第12章 差錯控制編碼全部碼字為：全部碼字為：10011100010110011101011000

49、1001011001110100101100000000001111111010011100010111010011001110110001011101001011000130d10 ed2e120 td1t第12章 差錯控制編碼四四. . 編碼電路編碼電路1. 對于對于 (n，k) 循環(huán)碼中，可用多項式表示為：循環(huán)碼中，可用多項式表示為：)()()(xrxxmxAkn其中：其中：m(x)為不大于（為不大于（k-1）次的多項式，代表信息碼）次的多項式，代表信息碼元。元。 r(x)為不大于為不大于(r-1)次的多項式，代表監(jiān)督碼元。次的多項式，代表監(jiān)督碼元。 )()()(xhxgxA)()()(

50、)(xgxhxrxxmkn)()()()(xrxgxhxxmkn或：或：第12章 差錯控制編碼)()()()()(xgxrxhxgxmxkn)()()(xgxrxmxkn模該式提供了循環(huán)碼編碼的數(shù)學依據(jù)。該式提供了循環(huán)碼編碼的數(shù)學依據(jù)。2. 步驟：步驟：（1）信息多項式）信息多項式m(x)左移左移n-k位。（相當于位。（相當于 ）（2）求其模）求其模g(x)的余式的余式r(x)（3）余式的系數(shù)作監(jiān)督碼元，附加在信息碼元之后形）余式的系數(shù)作監(jiān)督碼元，附加在信息碼元之后形成循環(huán)碼。成循環(huán)碼。knxxm )(第12章 差錯控制編碼例例: 已知已知(7，3）循環(huán)碼的生成多項式為）循環(huán)碼的生成多項式為求

51、信息位為求信息位為101時的碼字。時的碼字。解：解：1)(24xxxxg1)(24xxxxg)()()()(2xgxxgxgxxG111010001110101101001111010001110100011101G0011101)(101)()()(1456xGxAxGaaaxA第12章 差錯控制編碼3. 編碼電路編碼電路1D2D3D4D門1門2輸入信息碼元輸出碼組 首先，四級移位寄存器清零，三位信息碼元到來首先，四級移位寄存器清零，三位信息碼元到來時，門時，門1 1斷開，門斷開，門2 2接通，直接輸出信息元。第接通，直接輸出信息元。第3 3次移位次移位脈沖來時將除法電路運算所得的余數(shù)存入四

52、級移位寄脈沖來時將除法電路運算所得的余數(shù)存入四級移位寄存器，第存器，第4747次移位時，門次移位時，門2 2斷開，門斷開，門1 1接通，輸出監(jiān)督接通，輸出監(jiān)督碼元（即余數(shù)）。當一個碼字輸出完畢后就將移位寄碼元（即余數(shù)）。當一個碼字輸出完畢后就將移位寄存器清零，等待下一組信息碼元輸入后重新編碼。存器清零，等待下一組信息碼元輸入后重新編碼。 1)(234xxxxg第12章 差錯控制編碼4. 解碼解碼（1）只檢錯）只檢錯設發(fā)送碼組為設發(fā)送碼組為A，接收碼組為，接收碼組為B。)()()(xgxmxAB不出錯時，有不出錯時，有B(x)=A(x)則：則： 能整除。能整除。余數(shù)不為余數(shù)不為0時，時，B有錯。有錯。)()()(xmxgxB第12章 差錯控制編碼框圖：框圖：（2）糾錯）糾錯用用B(x)除以除以g(x)得到余式得到余式按余式按余式 用查表的方法或通過某種運算得用查表的方法或通過某種運算得到到E(x)。)(xr)(xr