1、1,第11章 差錯控制編碼,11.1 引言 11.2 糾錯編碼的基本原理 11.3 常用的簡單編碼 11.3 線性分組碼 11.4 循環(huán)碼 11.5 卷積碼,2,11.1 引言一、編碼問題的提出,3,二、錯誤的類型 隨機(jī)性錯誤 （白噪聲引起） 特點：單個錯，錯誤之間不相關(guān)。主要出現(xiàn)在無記憶信道。 2. 突發(fā)性錯誤 (脈沖干擾引起） 特點：成串錯，錯誤之間有相關(guān)性。主要出現(xiàn)在有記憶信道。錯誤傳播。 3. 混合性錯誤,4,三、差錯控制的方式 1. 檢錯重發(fā)(ARQ),特點: 1）雙向通道 2）通信效率低 3）不適于實時通信 4）編、譯碼設(shè)備簡單 5）編碼效率高,總碼元 (n bit)= 信元 (k

2、 bit)+ 督元 (r bit )。,只檢不糾，有錯自動要求重發(fā)。,5,2. 前向糾錯 (FEC),特點： 1）只需單向信道省信道！ 2）通信效率高； 3）適于實時傳輸； 4) 譯碼設(shè)備復(fù)雜。,檢錯并糾錯,6,3. 反饋檢驗法,原理：收端將信碼原封不動地轉(zhuǎn)發(fā)回發(fā)端，并與原發(fā)送信碼相比較：發(fā)現(xiàn)錯重發(fā)；否則：PASS 特點: 需要雙向通道； 收發(fā)設(shè)備簡單； 傳輸效率低（最低）。,4. 檢錯刪除,7,9.2 糾錯編碼的基本原理一. 基本思想,信元和督元有一的函數(shù)關(guān)系，插入督元的過程就是一種編碼的過程，接收端可檢錯糾錯。顯然，傳輸效率（引入冗余碼） 例：天氣預(yù)報,三位碼元有23=8種組合，實際使用了

3、22=4種許用碼組。 其余 001，010，100，111 為禁用碼組。 檢錯能力：可檢錯奇數(shù)個錯； 糾錯能力：無。,8,例：天氣預(yù)報，可預(yù)報天晴,冗余量加大，禁用碼組比例提高。 檢錯能力：檢2； 糾錯能力：糾1。,許用碼組2個，禁用碼組6個,晴 陰,9,二. 糾錯編碼的分類 線性碼和非線性碼 分組碼、卷積碼和循環(huán)碼 系統(tǒng)碼和非系統(tǒng)碼 三. 分組碼 定義:將信息碼分組，為每信息碼附加若干個監(jiān)督碼編碼，稱為分組碼。 特點: 在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。,符號: ( n , k ) , r = n k 碼字:,結(jié)構(gòu):,k個信元,r個督元,碼長n,10,碼組的重量和碼距及糾錯能力

4、1. 重量 碼組中非0元素的個數(shù) 例: A= ( 10110 ) 碼重 = 3 2. 碼距 兩兩碼組對應(yīng)位上數(shù)值不同的個數(shù)，記為d。 最小碼距: 某種編碼中各個碼組間距離 的最小值，記做d0 d0=dmin 碼距的幾何意義: (n=3) 各頂點 沿立方體各邊行走的幾何距離。 碼元值：每一碼組的三個碼元值， 就是此立方體各頂點的座標(biāo)（a2a1a0） 最小碼距: 1,11,前例中：天氣預(yù)報,四個許用碼組之間的距離均為2。 Why? 擯棄d=1的碼禁用碼組。許用碼組最小碼距愈大，抗干擾能力愈強(qiáng)！ 確定最小碼距的目的：決定編碼的檢糾錯能力。,12,3. d0與糾檢錯能力 若要求檢測e個錯,則 d0e+

5、1 若要求糾正t個錯,則 d02t+1 若要檢測e糾正t 個錯(同時),則 d0e+t+1, 且et 碼距與檢錯和糾錯能力的關(guān)系如圖：,t 1 t,e,13,0 1 2 3 A,d0,(a),0 1 2 3 4 5 A B,t t,d0,(b),A B,t 1 t,e,(c),圖9-4,14,例題 已知三個碼組為（001010），（101101）和（010001）。 若用于檢錯，能檢出幾位錯碼？若用于糾錯，能糾正幾位錯碼？若糾錯檢錯結(jié)合，各能糾錯、檢錯幾位錯碼？,15,11.3 常用的簡單編碼屬于分組碼一類。簡單、實用。一. 奇偶監(jiān)督碼滿足:,偶監(jiān)督碼：碼組中1的個數(shù)為偶數(shù)； 奇監(jiān)督碼：碼組中

6、1的個數(shù)為奇數(shù)。 檢錯能力: 所有奇數(shù)個錯。一半！應(yīng)用非常多。 編碼效率:,16,二維奇偶監(jiān)督碼 進(jìn)行橫、縱向監(jiān)督 例:,橫 向 監(jiān) 督,縱 向 監(jiān) 督,糾檢錯能力: 仍可檢錯奇數(shù)個錯 還可檢錯偶數(shù)個錯 可糾正一些錯碼 適于檢測突發(fā)性錯誤,17,恒比碼(等重碼) 例: 碼重為3,1 . 0 1 0 1 1 1 1 0 0 1 1 0 1 1 0,許用碼組: C35 = 10 禁用碼組: 25-10 = 22,檢錯能力: 可檢測所有奇數(shù)個碼元的錯和部分偶數(shù)個碼元的錯,但 不能檢測碼組中“1”變?yōu)椤?” 與“0”變?yōu)椤?”的錯碼數(shù)目相同的那些偶數(shù)錯碼 編碼效率:,18,例： n=10 , 則 k=

7、5, 接受端的檢測,四、 正反碼 編碼規(guī)則: 信息位(n/2)中有奇數(shù)個“1”,則監(jiān)督位與信息位相同 信息位(n/2)中有偶數(shù)個“1”,則監(jiān)督位是信息位的反碼,19,校驗碼組和錯碼的關(guān)系 若發(fā)送碼組為1100111001: 無錯碼 1位出錯：接收碼組變成10001 11001,校驗碼取合成碼的反碼 2位出錯：接收碼組變成10011 11001,校驗碼即合成碼,20,若傳輸中產(chǎn)生了差錯，使接收碼組變成1000111001，則合成碼組為100011100101000。由于接收碼組中信息位有偶數(shù)個“1”，所以校驗碼組應(yīng)取合成碼組的反碼，即10111。由于其中有4個“1”和1個“0”，按上表判斷信息位

8、中左邊第2位為錯碼。 若接收碼組錯成1100101001，則合成碼組變成110010100110000。由于接收碼組中信息位有奇數(shù)個“1”，故校驗碼組就是10000，按上表判斷，監(jiān)督位中第1位為錯碼。 最后，若接收碼組為1001111001，則合成碼組為100111100101010，校驗碼組與其相同，按上表判斷，這時錯碼多于1個。 上述長度為10的正反碼具有糾正1位錯碼的能力，并能檢測全部2位以下的錯碼和大部分2位以上的錯碼。,21,11.4 線性分組碼 定義：若分組碼（n,k）,督元與信元的關(guān)系可用一線性方程組來描述，則該分組碼（n,k）稱為線性分組碼。 一、漢明碼 能糾一位錯的線性分組碼

9、。 最小碼距：d0=3 1. 構(gòu)造原理 考察：定義一個監(jiān)督方程（監(jiān)督關(guān)系式、偶監(jiān)督）：,由于一位校正子只有兩種取值，故只能表示有錯或無錯，不能指出錯碼的位置。,22,推想:如果監(jiān)督位增加一位（即變成兩位），則可增加一個類似于上式的監(jiān)督關(guān)系，即可獲得兩個校正子，于是可有,23,再推廣:,S1 S2 Sr 0 0 . 0 0 0 . 1 1 1 .1 1,顯然：要求 2r-1n（n=k+r），則可指示（僅一位錯時）任一錯碼的位置包括信元、督元。 或： 2rk+r+1,可指示一個錯碼可能出現(xiàn)的2r-1個位置。,24,2. 例: 構(gòu)造k=4 的漢明碼 （1）確定 r 由 2r k+r+1 得 r =

10、3，則 n= k+r=7 ( 7,4 ) 分組碼,25,（2）寫出校正子的編碼表 r = 3 共有3個校正子,（3） 由校正子編碼表得監(jiān)督方程組校正子和哪些碼元構(gòu)成偶監(jiān)督關(guān)系,若 S1S2S3 = 000 時, 即無錯得校驗方程:,偶監(jiān)督關(guān)系,26,得校驗方程:,即實際上確定了督元和信元之間的關(guān)系:,校驗方程,督信關(guān)系,有了校正子編碼表，督元不是隨便選的！,（4） 給定了信元a6a5a4a3,可由“督信關(guān)系”確定督元全部( 7,4 ) 碼組。,移項,27,（4） 給定了信元a6a5a4a3,可確定督元全部( 7,4 ) 碼組,28,二. 線性分組碼 1. 線性方程組和監(jiān)督方程,寫成矩陣式:,2

11、9,可見：H一旦確定，督元和信元之間的關(guān)系也就確定了。 若:,則稱H為典型陣，一般，H總可以化為典型陣。,30,2. 生成矩陣,矩陣形式:,從督信方程入手 由,31,寫成行陣形式:,其中 Q = PT 上式表明：信息位給定后，就產(chǎn)生了監(jiān)督位！,進(jìn)一步，令生成矩陣 G = Ik Q 則，碼組行陣 A = a6a5a4a3 G,32,例：生成矩陣,討論： 具有 Ik Q 形式的生成矩陣稱為典型生成矩陣。 由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)督位附加其后這種碼稱為系統(tǒng)碼。,碼組行陣：,33,一般形式: A = an-1an-2ar G,3. G 和 H 的關(guān)系 由 Q = PT 或 P =

12、QT 則 : H = P Ir G = Ik Q 綜上：線性分組碼的編碼，就是根據(jù)其監(jiān)督陣H或生成陣G將長為k的信息碼編成長為n的碼組。,34,4. 線性分組碼的糾錯譯碼過程 怎樣由含有錯誤的接收碼組中的接收碼組中恢復(fù)正確。 （1）錯誤圖樣 設(shè)：發(fā)碼組為A , 接受碼組為B 則 B A = E ( 模 2 )錯誤行陣或錯誤圖樣： E= en-1en-2e0 ,例: A = 1 1 1 1 1 1 1 B = 1 0 0 1 1 0 1 則 E = 0 1 1 0 0 1 0 ,35,（2）校正子（或稱譯碼伴隨式）,B = A+E 代入上式，得,結(jié)論：校正子S 僅于錯誤圖案有關(guān)，與發(fā)送碼組無關(guān)。

13、,36,由收到的碼組B，按式：BHT=SS 由 S=EHT E 按B+E=A A 由A 原始信息,（3）糾錯譯碼過程,37,(7,4) Hamming code 發(fā)送碼組A=0001011 接收碼組B=0000011,例,監(jiān)督矩陣：H=,38,5. 線性分組碼的重要性質(zhì) （1）封閉性 設(shè)： A1、A2 分別為一線性分組碼的任意兩個許用碼組。 則：A1+A2 仍為該線性分組碼的許用碼組。 （2）線性分組碼的最小碼距即為該碼的最小重量: d0=Wmin（除全0碼組）,39,例題,線性碼的生成矩陣為：,（1）確定(n,k)碼中的n,k （2） 求典型監(jiān)督矩陣H （3）寫出監(jiān)督方程 （4）列出所有碼組

14、，并求最小碼距d0,40,11.5 循環(huán)碼(cyclic code) 仍屬于線性分組碼 特點: 編譯碼設(shè)備簡單，檢糾錯能力強(qiáng)。11.5.1 循環(huán)碼的原理具有線性分組碼的所有性質(zhì)之外，還具有循環(huán)性：循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。,41,碼多項式 T(x) （1）定義 為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項式來表示，這個多項式被稱為碼多項式。 設(shè)：許用循環(huán)碼A=(an-1 an-2 a1 a0)， 則：它的碼多項式表示為：,其中：x僅是碼元位置的標(biāo)記。,42,例: 設(shè) ( 7,3 ) 循環(huán)碼組為 ( 0 1 1 1 0 0 1 ) 則相應(yīng)碼多項式為：,反

15、之，由碼多項式易得出碼組：( 0 1 1 1 0 0 1 ),可由碼組直接寫出。,43,（2）碼多項式的按模運(yùn)算 1）整數(shù)的按模運(yùn)算 若一個整數(shù)m可以表示為:,則在模n運(yùn)算下，有mp（模n）。 例：,同樣對于多項式而言，也有類似按模運(yùn)算。,44,其中：商Q(x)為多項式，余數(shù)R(x)的冪次低于N(x)的冪次。 例: 求 x4+x2+1 按模 x3+1 運(yùn)算的余式 R(x),2）碼多項式的按模運(yùn)算 若,則,45,3）循環(huán)性 在循環(huán)碼中，若T(x) 是一個長為n的許用碼組，則xiT(x) 在按模xn+1運(yùn)算下，亦是一個許用碼組。即 設(shè)： T(x) 是長為n的許用碼組多項式,則： T(x)仍為該碼組

16、中的一個碼多項式。,例: （7，3）碼T(x) = x6+x5+x2+1 ( 1 1 0 0 1 0 1),前碼組循環(huán)左移3位！,46,由此類推,可見：一個長為n的循環(huán)碼，必為按模（xn+1）運(yùn)算的一個余式。,47,2. 生成多項式g(x) （1）存在性 ( n，k ) 循環(huán)碼中有且僅有一個g(x) g(x)=xn-k+1 特點: 最高的次數(shù): n-k=r； 最高次項和常數(shù)項系數(shù)必為1 。,在循環(huán)碼中，除了全0碼組外，再也沒有連續(xù)k位均為0的碼組。即連0長度最多為k-1位！,這唯一的n-k次多項式稱為生成多項式，記為g(x),48,（2） g(x) 與生成矩陣 G(x) 的關(guān)系,A = an-

17、1ar G G = Ik Q ,生成矩陣G的每一行都是一個碼組；G是k行n列矩陣， 只要找到k個已知碼組，就能構(gòu)成生成矩陣G！,生成多項式確定后，則g(x)、x g(x)、 xk-1 g(x)都是碼組，且這k個碼組信息無關(guān)，因此可以用來構(gòu)成生成矩陣。,g(x)確定了G(x)也就確定了整個碼組即確定！,49,若信息位是0001，則G矩陣的第一行就是該信息位對應(yīng)的碼組；同理：G矩陣的第2行是0100對應(yīng)的碼組 即: 生成矩陣G的各行是k個線性無關(guān)的碼組,50,(7, 3) 循環(huán)碼的全部碼組,51,例: ( 7，3 )循環(huán)碼， g(x) = x4+x2+x+1 求 典型生成矩陣,解:,典型陣:,可方

18、便地直接寫成碼組形式,52,（3） g(x) 與 T(x) 的關(guān)系（7，3）,表明：所有T(x)都可以被g(x)整除，而且任一次數(shù)不大于(k-1)的多項式乘以g(x)都是碼多項式。,53,依據(jù): g(x)是xn+1的一個(n-k)次的因子，且常數(shù)項不為零。 證：任一循環(huán)多項式T(x)都是g(x)的倍式，即,而生成多項式g(x)本身也是一個碼組，即有,由于碼組T(x)為一（n-k）次多項式，故xkT(x)為一n次多項式。由,知，xkT(x)在模（xn+1）的運(yùn)算下，亦為一碼組，故可寫成,（4） 如何尋找 g(x),54,上式左端分子和分母都是n次多項式，故商Q(x)1，因此上式可化成即,將T(x

19、)=h(x)g(x)、 T(x)=g(x)代入，并化簡，得,表明: g(x)應(yīng)該是xn+1的一個因式！,結(jié)論: g(x)是xn+1的一個(n-k)次的因子，且常數(shù)項不為零。,55,依據(jù): g(x)是xn+1的一個(n-k)次的因子，且常數(shù)項不為零。 如 (x7+1) = (x+1)(x3+x2+1)(x3+x+1) n=7 （7，4）： x3+x2+1、x3+x+1 （7，3）： (x+1)(x3+x2+1) 、(x+1)(x3+x+1) （7，6）： x+1,（4） 如何尋找 g(x),56,例: （7，3）循環(huán)碼有多項式如下，找出（7，3）碼的生成多項式g(x)。 （1） x4+x3+x

20、（2） x3+x2+1 （3） x+1 （4） x4+x2+x+1 （5） x4+x+1,57,11.5.2 循環(huán)碼的編碼方法 1. ( n，k ) 循環(huán)碼的編碼步驟 設(shè): 已選好g(x)，給定信息碼組m(x):,（1）作xn-km(x)實際上是把信息碼后附加上（n-k）個“0”。 （2）作,（3）編碼輸出系統(tǒng)循環(huán)碼多項式T(x)為：,得到了r(x)。,由于循環(huán)碼多項式T(x)都可被g(x)整除，也就是：,58,例: ( 7，3 ) 循環(huán)碼，選 g(x) = x4+x2+x+1 設(shè) m(x) = x2+x+1 ( 1 1 1 ) 求系統(tǒng)碼多項式T(x)。 解:,59,11.7. 卷積碼,卷積碼

21、屬線性非分組碼。 卷積碼表示為（n，k，N），通常n，k都很小。 其中的參量定義為： n：子碼長（子碼位數(shù)）。 k：子碼中信息段長（信息段位數(shù)）。 N：以子碼為單位的卷積碼約束度。 卷積編碼器把k比特信息段編成n比特的子碼，所編n比特的子碼不僅與當(dāng)前信息段有關(guān)，而且還與前(N1)個信息段有關(guān)聯(lián)。約束長度為Nn比特。編碼效率為k/n。,60,編碼器原理方框圖,61,例： (n, k, N) = (3, 1, 3)卷積碼編碼器 方框圖 設(shè)輸入信息比特序列是bi-2 bi-1 bi bi+1，則當(dāng)輸入bi時，此編碼器輸出3比特ci di ei，輸入和輸出的關(guān)系如下：,62,左式可以改寫為,63,卷積

22、碼的監(jiān)督矩陣H是一個有頭無尾的半無窮矩陣。,64,碼的截短監(jiān)督矩陣可以寫成： 式中 2階單位方陣； Pi 2 1階矩陣，i = 1, 2, 3； O2 2階全零方陣。,65,一般，卷積碼的截短監(jiān)督矩陣具有如下形式： 式中 In-k (n k)階單位方陣； Pi (n k) k階矩陣； On-k (n k)階全零方陣。 H1的末行稱為基本監(jiān)督矩陣h h = PN On-k PN-1 On-k PN-2 On-k P1 In-k,66,生成矩陣G 上例中的輸出碼元序列可以寫成 b1 d1 e1 b2 d2 e2 b3 d3 e3 b4 d4 e4 = b1 b1 b1 b2 b2 (b2 + b1

23、) b3 (b3 + b1) (b3 + b2 + b1) b4 (b4 + b2) (b4 + b3 + b2) ,67,此碼的生成矩陣G即為上式最右矩陣： 半無窮矩陣，其特點是每一行的結(jié)構(gòu)相同，只是比上一行向右退后3列（因現(xiàn)在n = 3）。,68,截短生成矩陣：類似地，也有截短生成矩陣 式中I1 一階單位方陣； Qi 1 2階矩陣。 與H1矩陣比較可見，Qi是矩陣PiT的轉(zhuǎn)置： Qi = PiT (i = 1, 2, ),69,Ik k階單位方陣； Qi k (n k)階矩陣； Ok k階全零方陣。 并將上式中矩陣第一行稱為基本生成矩陣 g Ik Q1 Ok Q2 Ok Q3Ok QN,截短生成矩陣 G1 具有如下形式：,70,11.7.3 卷積碼的解碼 分類： 代數(shù)解碼：大數(shù)邏輯解碼，又稱門限解碼 概率解碼(最大似然解碼)：序貫解碼、維特比算法,大數(shù)邏輯解碼原理,71,例：(2, 1, 6)卷積碼 編碼器方框圖 當(dāng)輸入序列為b1 b2 b3 b4 時，監(jiān)督位為 c1 = b1 c2 = b2 c3 = b3 c4 = b1 + b4 c5 = b1 + b2