1、第12章差錯控制編碼,內(nèi)容簡介：12.1引言12.2糾錯編碼的原理12.3常用的簡單編碼12.4線性分組碼12.5循環(huán)碼,主要內(nèi)容：1.基本概念：碼重,碼距,檢錯能力,糾錯能力2.常用編碼3.線性分組碼4.循環(huán)碼,回放,信道,解調(diào),信源,編碼,加密,調(diào)制,解密,譯碼,信宿,噪聲,同步系統(tǒng),信源編碼信道編碼誤差控制,ASKFSKPSKDPSK,數(shù)字通信的組成,在通信過程中，會受到各種外來干擾，如脈沖干擾，隨機噪聲干擾，人為干擾及通信線路傳輸性能的限制都將使信號失真。由于以上原因，引起數(shù)據(jù)信息序列產(chǎn)生錯誤，稱之為差錯。,實際信道中，上述兩種錯誤常同時存在。,隨機性錯誤：前后出錯位之間無一定關(guān)系，隨

2、機、離散出現(xiàn)。突發(fā)性錯誤：差錯成串出現(xiàn)，且有一定相關(guān)性。,差錯的兩大類型：,12.1引言,數(shù)字通信中的編碼分為：,信道編碼：,信源編碼：,為提高信號傳輸?shù)挠行远扇〉拇胧?為提高信號傳輸?shù)目煽啃远扇〉拇胧?。亦稱差錯控制編碼。,在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中增加一些監(jiān)督信息，使不帶規(guī)律性或規(guī)律性不強的原始數(shù)字信號變?yōu)閹б?guī)律性或加強了規(guī)律性的數(shù)字信號，信道譯碼器則利用這些規(guī)律性來鑒別是否發(fā)生錯誤，或進行錯誤糾正。,差錯控制,1、差錯控制方法,方法和設(shè)備簡單，無需糾檢錯編譯系統(tǒng)。但需要雙向信道，傳輸效率、實時性差。,(3)檢錯重發(fā)法ARQ,所發(fā)碼具有檢錯能力，收端接收后判決是否出錯，通過反

3、向信道發(fā)送判決結(jié)果，發(fā)端據(jù)此決定是否重發(fā)。,譯碼設(shè)備簡單，對突發(fā)錯誤有效，要求有反饋信道。,工作過程：發(fā)送檢測回復(fù)重發(fā)或發(fā)送新的數(shù)據(jù),停止等待方式,ARQ的三種實現(xiàn)方式：,特點：半雙工工作，簡單，要求的緩存量小，但等待時間較長，,傳輸效率,連續(xù)重發(fā)方式,退N步方式：從出錯幀開始重發(fā)例N=4,優(yōu)缺點：傳輸效率，但重發(fā)的N幀中，大部分為正確，所以仍有浪費。發(fā)端緩存必須可存N幀。,只對出錯信息重發(fā)，因此傳輸效率大大提高。但收發(fā)兩端都要有足夠的存儲空間。,選擇重發(fā)方式,反饋信道,ARQ,FEC編碼器,正向信道,FEC譯碼器,ARQ,編碼既有糾錯能力也有檢錯能力，收端收到信息碼組后在收端進行檢測。在糾錯

4、范圍內(nèi)：糾正；超出范圍：通過ARQ方式進行重發(fā)。,(4)混合方式,（1）,根據(jù)各碼組信息碼和監(jiān)督碼的關(guān)系分：線性碼，非線性碼,根據(jù)監(jiān)督碼元是否僅與本組信息元有關(guān)分組碼，卷積碼,（2）,根據(jù)糾錯碼組中信息元是否隱蔽分：系統(tǒng)碼，非系統(tǒng)碼,（3）,根據(jù)碼的用途分：檢錯碼，糾錯碼,（4）,根據(jù)碼元的取值：二進制碼，多進制碼,（5）,根據(jù)構(gòu)造編碼的數(shù)學(xué)方法：代數(shù)碼，幾何碼，算術(shù)碼,（6）,2、糾錯碼的分類,12.2糾錯編碼的基本原理,1、幾個術(shù)語,本課程主要討論糾隨機錯誤的二進制線性分組碼。,碼長：碼組中碼元的數(shù)目，常用n表示；,碼距：兩等長碼字C1、C2對應(yīng)位上取值不同的數(shù)目，又稱為漢明(Hammin

5、g)距離，記為d(c1,c2)。,碼重：碼組中非零碼元的數(shù)目，記為W；,最小碼距：在分組碼(n,k)中，任意兩個碼字之間漢明距離的最小值，記為dmin。,碼距的大小關(guān)系到編碼的糾檢錯能力。,例：10011w=301101d=4,n=3時，碼距的幾何說明：,（a2a1a0）,a2,a1,a0,（110）（011）,d=2,110,011,（111）（000）,d=3,000,111,增加一個監(jiān)督位，取11A、00B,若收到01或10時，可知發(fā)生了錯誤，但不能糾正錯誤。,再增加一個監(jiān)督位，取111A、000B,如一位錯：B001A110；若兩位錯011,110則只能發(fā)現(xiàn)不能糾錯,可以看出：差錯控制

6、是以犧牲傳輸效率為代價而換取了傳輸質(zhì)量的提高的。糾檢錯能力與加入的監(jiān)督元數(shù)目成正比。,2、糾錯或檢錯的原理,分組碼的三個參數(shù)碼長n，信息位k，最小距離d0，用符號(n,k,d0)表示,R=k/n為編碼效率，d0一定(糾錯能力一定)時，k/n大，效率高。,對被傳輸?shù)男畔⑿蛄蟹纸M，每組為k個信息元，對每組按某種關(guān)系附加(n-k)個監(jiān)督碼元(校驗)，形成為n位的碼字。這種方法構(gòu)成的碼組稱為分組碼。,分組碼的表示：符號（n，k）,n碼組的總位數(shù),k碼組中信息碼元的數(shù)目,r=n-k監(jiān)督碼元的數(shù)目,編碼效率,R越大，信息位比重大，有效性越高。,3、分組碼的糾(檢)錯能力與最小碼距d0的關(guān)系,任一（n，k）

7、分組碼，若要在碼字內(nèi)能：1/檢測e個隨機錯誤，則要求：d0e+12/糾正t個隨機錯誤，則要求：d02t+13/糾正t個同時檢測e(et)個隨機錯誤，則要求：d0e+t+1,糾（檢）錯能力的幾何解釋,e檢錯能力t糾錯能力,（1）,時能檢出e個或e個以下錯碼。,（2）,（3）,時能糾正t個或t個以下錯碼。,時能檢出t個或e個以下錯碼。,4、對糾錯編碼的要求,糾、檢錯能力強，編碼效率高，碼長短，編碼規(guī)律簡單。,例：,一個碼集，只有兩個許用碼：0000、1111，試求其糾檢錯能力和編碼效率。,解：,根據(jù)碼距的定義，則該碼集d0=4，,1/用于檢錯，ed01=3，即可檢3個錯誤；,2/用于糾錯，t(d0

8、1)/2=3/2，取整，即可糾1個錯誤；,3/同時用于糾、檢錯，d0e+t+1（et）?。篹=2，t=1，則可滿足上式，即可檢2個錯誤同時糾一個錯；,R=k/n=1/4,編碼效率：,5.差錯控制編碼的效用：,假設(shè)在隨機信道中，發(fā)送“0”和“1”的錯誤概率相等，都等于p，且p1，在碼長為n的碼組中，發(fā)生r個錯誤的概率為：,例如：當n=7，p=10時，則有：,由此可見，即使僅能糾正1-2個錯誤，也可使誤碼率下降幾個數(shù)量級。所以差錯控制編碼具有較大的實際應(yīng)用價值。,例12-1已知8個碼組為：（O00000），（001110），（010101），（011011），（100011），（1O1101），（

9、110110），（111000），（1）求以上碼組的最小碼距；（2）若此8個碼組用于檢錯，可檢出幾位錯？（3）若用于糾錯碼，能糾幾位？（4）若同時用于糾錯和檢錯，糾錯、檢錯性能如何？,（1）,（2）,（3）,（4）,例12-2已知兩碼組（0000）和（1111），若該碼組用于檢錯，能檢出幾位錯碼？若用于糾錯，能糾正幾位錯碼？若同時用于糾錯和檢錯，問各能糾、檢幾位錯碼？,（1）,（2）,（3）,一.奇偶監(jiān)督碼,在信息為后加一位校驗位,12.3常用的簡單編碼,奇監(jiān)督碼,偶監(jiān)督碼,特點：只能檢測出奇數(shù)個錯碼，不能檢測出偶數(shù),奇偶監(jiān)督碼：k=n-1,r=1的線性碼。特點：碼組中的1個數(shù)是奇數(shù)（奇監(jiān)督碼

10、）或偶數(shù)（偶監(jiān)督碼）。,序碼字序碼字號信息碼元監(jiān)督元號信息碼元監(jiān)督元a4a3a2a1a0a4a3a2a1a0000000810001100011910010200101101010030011011101114010011211000501010131101160110014111017011111511110,碼長5的偶監(jiān)督碼,偶監(jiān)督碼編碼器,偶監(jiān)督碼的檢錯電路,例：一數(shù)據(jù)序列：1110010111011011000110101,試對其進行（6，5）偶校驗編碼，寫出碼序列并分析其抗干擾能力,解：,（6，5）,將數(shù)據(jù)序列每5碼元分組，,并作：,的運算,可得出編碼數(shù)據(jù)序列：,1110011011

11、10011011100010101011,只能檢測出奇數(shù)個錯誤，不能發(fā)現(xiàn)偶數(shù)個錯誤，也不能糾錯。,二.二維奇偶監(jiān)督碼,行監(jiān)督位,列監(jiān)督位,水平垂直奇偶校驗碼：又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。特點：對水平方向和垂直方向的碼元同時實施奇偶監(jiān)督。,110010100000100001101001111000011100111000001010101010111000111100,行列監(jiān)督碼,特點：,（1）能檢測出每一行（列）中的奇數(shù)個或偶數(shù)個錯碼，但不能檢測出行列同時成偶數(shù)個出現(xiàn)的錯碼。,（2）能檢測突發(fā)性錯誤（成串錯碼）。,（3）能糾正錯碼。,恒比碼：又稱等重碼或定1碼。特點：碼組中0，1的個數(shù)保

12、持不變。若碼長為n，碼重為w，則此碼的碼字個數(shù)為：Cnw，禁用碼字個數(shù)為：2n-Cnw,例如：我國的電報，每個漢字用四個10進制數(shù)表示，每位10進制數(shù)就采用3：2恒比碼構(gòu)成的5位碼組來表示。,碼字的個數(shù)C53=10,檢錯能力較強，可檢出所奇數(shù)和部分偶數(shù)錯誤。,作業(yè)：,正反碼：簡單的可糾錯編碼，信元數(shù)等于監(jiān)督元數(shù)特點：信息位中，有奇數(shù)個1時，監(jiān)督位重復(fù)信息位；信息位中，有偶數(shù)個1時，監(jiān)督位取信息位的反碼；,可糾一位、檢測所有兩位錯和部分兩位以上的錯誤。,例：,110011100111001,100011000101110,(n,k)其中k=n/2編碼效率：R=k/n=1/2,四.正反碼,例：信息

13、位：11001監(jiān)督位：11001信息位：10001監(jiān)督位：01110,1.編碼規(guī)則：,（1）當信息位中有奇數(shù)個1時，監(jiān)督位是信息位的簡單重復(fù)。,（2）當信息位中有偶數(shù)個1時，監(jiān)督位是信息位的反碼。,例：1100111001=000001000101110=11111,2.譯碼方法,（1）將碼組中的信息碼與監(jiān)督碼進行模2加得合成碼組。,（2）若信息碼中有奇數(shù)個1，則合成碼組即為檢驗碼組。若信息碼中有偶數(shù)個1，則合成碼組的反碼即為檢驗碼組。,（3）觀察檢驗碼組中1的個數(shù)，按p278進行檢錯和糾錯。,12.4線性分組碼,一.以（7，4）分組碼為例,碼字：A=（）,其中信息位：,監(jiān)督位：,若分組碼可用

14、下列線性方程組表示：,（“+”為模2加）,則：該分組碼為（7，4）線性分組碼（共有16個碼字）,性質(zhì)：,（1）封閉性：任意2個許用碼組之和（模2加）仍為一個許用碼組。,（2）有零元：,（3）有負元：,（4）結(jié)合律成立：,（任一碼字即為本身的負元）,二.監(jiān)督矩陣H,將上例中的式子改寫為：,用矩陣表示為：,并記為：,H陣可表示為：,（階）,（階單位陣）,矩陣H稱為（7，4）線性分組碼得監(jiān)督矩陣。上式也稱為典型監(jiān)督矩陣。若不是典型監(jiān)督矩陣要用初等變換化成典型矩陣。,三.生成矩陣G,若信息碼元已知，通過監(jiān)督矩陣可以求出監(jiān)督碼元。,用矩陣表示：,或,將上式擴展可以由已知信息碼元求得整個碼組。,令：,G稱

15、為生成矩陣,典型監(jiān)督矩陣和典型生成矩陣存在以下關(guān)系式：,例：（7，4）,全部碼字為：,四.伴隨式（校正子）S,設(shè)發(fā)送碼字為，接收碼字為，由于干擾，噪聲可能引入誤差，使接收碼組與發(fā)送碼組不同，因此有，其中是傳輸中產(chǎn)生的錯誤行矩陣。對于二進制碼元有:,E矩陣中哪一位碼元為1就表示接收碼字中對應(yīng)位有錯。E稱為錯誤圖樣。,模2,在接收端用H來檢測接收B中的錯碼。,令：,伴隨式或校正子：,如果B與A相同，則：,否則：,又,表示校正子S僅與信道的錯誤圖樣E有關(guān)，而與發(fā)送的碼字A無關(guān)。,五.如何利用S完成糾錯,對（7，4）線性分組碼,設(shè)B中最高位有錯，錯誤圖樣,它的轉(zhuǎn)置,恰好是典型H陣的第一列。,同理可求出

16、：,若次高位有錯,，即恰好是H的第二列。,因此，在接收碼組中只錯一位碼元情況下，計算出的校正子S總是和典型監(jiān)督矩陣中的某一行相同。,例：,與第三列相同,正確碼組為：,六.漢明碼,漢明碼是一種可以糾正單個隨機錯誤的線性分組碼。它的最小碼距，監(jiān)督元位數(shù)，碼長，信息元位數(shù)，編碼效率當r很大時，因此是一種高效碼。,上例中的（7，4）線性分組碼就是漢明碼，并且任意調(diào)換H矩陣中各列的結(jié)果不會影響糾，檢錯能力。,12.5循環(huán)碼,一.概念,1.循環(huán)碼：線性分組碼,（1）封閉性,（2）循環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位之后，所得到的碼組仍為一許用碼組。,2.碼多項式,循環(huán)碼的一許用碼組可表示為：,其中：x

17、為碼元位置標記，不考慮其取值。碼元只取“1”或“0”。,例:(7，3）循環(huán)碼中第二個碼組,如何實現(xiàn)移位：乘一個x相當于碼左移一位。,3.按模運算,若,（的次數(shù)小于）,則：,稱為按模運算后的余式。,例：,4.規(guī)律,（1）循環(huán)碼中，將許用碼組左移一位得到的碼字記為：。其碼多項式為：,可以證明：,（2）根據(jù)循環(huán)碼的定義，均為許用碼字。因此下列結(jié)論：若是許用碼字，則在按模運算下，也是許用碼字。,即：若,則也是許用碼字。,例:(7，3）循環(huán)碼,則：,那么,其碼字為。,二.生成多項式與生成矩陣G,1.(n，k)循環(huán)碼碼組集合中（全“0”除外）最高階數(shù)最小的多項式（n-k）階稱為生成多項式，記為g(x)。,

18、2.集合中其它碼多項式都是運算下的余式。即可以由生成多項式g(x)產(chǎn)生循環(huán)碼的全部碼字。,3.生成矩陣G,循環(huán)碼的生成矩陣多項式可以寫成,以（7，3）循環(huán)碼為例,經(jīng)線性變換，將G整理成典型生成矩陣。,整個碼組可表示為：,任意一個碼多項式都能被g(x)整除。,三.監(jiān)督多項式、監(jiān)督矩陣,1.對于(n，k)循環(huán)碼，可分解成g(x)和其它因式的乘積。,記為：,稱h(x)為監(jiān)督多項式，其矩陣形式為：,以（7，3）循環(huán)碼為例,2.,對于（7，3）循環(huán)碼，g(x)的最高次為4,所以，有兩種方案,第一種方案：,碼字：,第二種方案：,碼字：,例:已知(7，4）循環(huán)碼的生成多項式為（1）求典型生成矩陣和典型監(jiān)督矩陣；（2）輸入信息碼為11001011，求編碼后的系統(tǒng)碼；（3）全部碼組；（