-第11章-差錯控制編碼

1、1第11章 差錯控制編碼11.1 概述11.2 糾錯編碼的基本原理11.3 常用的簡單編碼11.4 線性分組碼11.5 循環(huán)碼11.6 卷積碼211.1 概述一、差錯控制編碼 在發(fā)送端被傳輸?shù)男畔⑿蛄猩细郊右恍┍O(jiān)督碼元,這些多余碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)(約束),接收端按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼元之間的關(guān)系.3二、差錯控制方法1、檢錯重發(fā)2、前向糾錯發(fā)收檢錯碼應答信號發(fā)收糾錯碼43、混合糾錯發(fā)收糾檢錯應答信號*常用檢錯重發(fā)系統(tǒng): 停發(fā)等候重發(fā),返回重發(fā)和選擇重發(fā)5（1）停發(fā)等候重發(fā)12331TI23發(fā)接收ACKNAK發(fā)現(xiàn)錯誤這是一種半雙工的通信方式,原理簡單,效率低.6

2、（2）返回重發(fā)1 2 3 4 5 6 2 3 4 5 6 7 8 91 2 3 4 5 6 2 3 4 5 6 7 8 9發(fā)接收發(fā)現(xiàn)錯誤NAK從碼組2開始重發(fā) (傳輸效率最高,需復雜的控制,收、發(fā)數(shù)據(jù)緩存)選擇重發(fā)7 8 9 10 11 12重發(fā)碼組2711.2 糾錯編碼的基本原理一、分類 1、按差錯控制編碼的功能功能：檢錯碼、糾錯碼、糾刪碼。 2、按信息碼元和附加的監(jiān)督碼元之間的檢驗關(guān)系：檢驗關(guān)系：線性碼、非線性碼。 3、按信息碼元和監(jiān)督碼元之間的約束方約束方式：式：分組碼、卷積碼。8二、編碼原理：二、編碼原理：例：3位二進制數(shù)構(gòu)成的碼組表示天氣全用用4種 用2種全用用4種 用2種000晴晴

3、晴100雪001云101霜陰010陰110霧雨011雨云111雹雨91、組成：信息位+監(jiān)督位。2、分組碼： 將信息碼分組，為每組信碼附加若干監(jiān)督碼的編碼，稱為分組碼。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組的中的信息碼元。 分組碼用（n，k）表示，n碼組長度， k 信息位數(shù)，n k = r 監(jiān)督位數(shù)。3、兩個概念：（1）碼重“1”的數(shù)目稱為碼組的重量（2）碼距兩個碼組對應位上數(shù)字不同的位數(shù)稱為碼組距離（漢明距離）。 各碼組間距離的最小值為最小碼距 d0 104、檢、糾錯能力。(1)為檢測 e 個錯碼，要求 d0 e + 1(2)為糾正 t 個錯碼，要求 d0 2 t + 1(3)為糾正 t 個錯碼，同

4、時檢測 e 個錯碼，要求 d0 e + t +1Bd0BA12BA12BB345d011AB1te若隨機信道中，發(fā)送“0”和發(fā)送“1”時的錯誤概率相等，為P，且P1,則碼長為n 的碼組恰好發(fā)生r個錯碼的概率為: rrnrrnnPrnrnPPCrp)!( !)1 ()(12當 n=7 P=10-3時 P(1) 710-3 P(2) 2.110-5 P(3) 3.510-8 可見,采用差錯控制編碼,即使僅能糾正這種碼組中的1 2個錯誤,也可以使誤碼率下降幾個數(shù)量級.1311.3 常用的簡單編碼1、奇偶監(jiān)督碼 無論信息位有多少,監(jiān)督位只有一位,使碼組中“1”的數(shù)目為偶(或奇)數(shù)。 接收端奇數(shù)監(jiān)督碼偶

5、數(shù)監(jiān)督碼10021aaann 這種碼能夠檢測奇數(shù)個錯碼,適用檢測隨機錯誤142、二維奇偶監(jiān)督碼 把上述奇偶監(jiān)督碼的若干碼組排列成矩陣,每一碼組寫成一行,然后,再按列的方向增加第二維監(jiān)督位10111211aaaann20212221aaaannmmmnmnaaaa01210121ccccnn153、恒比碼 每個碼組均含有相同數(shù)目的“1”(和“0”).由于“1”的數(shù)目與“0”的數(shù)目之比保持恒定,故得此名.4、正反碼 是一種簡單的能夠糾正錯碼的編碼,監(jiān)督位數(shù)目與信息位數(shù)目相同,監(jiān)督位與信息位相同或相反,由信息碼中的“1”的個數(shù)而定. 1611.4 線性分組碼一、基本概念：1、定義：線性分組碼中信息碼

6、元和監(jiān)督碼元是用線性方程聯(lián)系起來的。2、主要性質(zhì) （1）任意兩許用碼組之和(模2和、異或關(guān)系)仍為一許用碼組. (封閉性) （2）碼的最小距離等于非零碼的最小重量173、特點：奇偶監(jiān)督碼是一種最簡單的線性碼,偶校驗時（1）S稱為校正子,又稱伴隨式. S=0無錯,S=1 有錯.（2）由r個監(jiān)督方程式計算得r個校正子,可以用來指示2r-1種錯誤。對于一位誤碼來說,就可以指示2r-1個誤碼位置.021aaaSnn18設(shè)分組碼(n,k)中k=4,為糾正一位錯碼,要求r3, 則 n=k+r=7S1S2S3錯碼位置S1S2S3錯碼位置001a0101a4010a1110a5100a2111a6011a30

7、00無錯19024561aaaaS013562aaaaS003463aaaaS4562aaaa3561aaaa3460aaaa碼長 n=2r 1，信息位 k= 2r 1 r，監(jiān)督位r，這種線性分組碼稱為漢明碼。二、編碼原理：二、編碼原理：1、校正子方程組、校正子方程組20編碼速率=2、監(jiān)督矩陣：nrrrnkrrr11211212000101110123456aaaaaaa001010110123456aaaaaaa010011010123456aaaaaaa表示成矩陣形式(nr階)1001101010101100101110123456aaaaaaa=000PIr21簡記為 或 H稱為監(jiān)督矩陣

8、，H確定，則編碼時監(jiān)督位和信息位的關(guān)系就完全確定了。 P為r k 階 Ir為 r r 階單位方陣 具有 P Ir 形式的H矩陣稱為典型陣。3、生成矩陣：TTHA00TAH012aaa=1101101101113456aaaa22或012aaa3456aaaa1101010111113456aaaaQQIGk生成矩陣（nk階）0123456aaaaaaa3456aaaaGA3456aaaaG23具有 形式的生成矩陣稱為典型生成矩陣。 由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)督位附加其后，這種碼稱為系統(tǒng)碼。QIGk24例：設(shè) 且有3個接收碼組 驗證3個接收碼組是否發(fā)生差錯？ 若在某碼組中有一位

9、錯碼，指出哪一位。100101010110001011H1011101B1101012B1100003B25解：1）B1無錯B2錯B3錯2） B2中，S1=a5+a4+a2=1S3=a5+a3+a0=1，相交叉判斷a5錯 B3中，S2=a4+a3+a1=1S3=a5+a3+a0=1，相交叉判斷a3錯26三、線性碼的重要性質(zhì)1、封閉性 任意許用兩個碼組之和仍為許用碼組2、兩個碼組之間的距離必是另一碼組的重量,故最小碼距即碼的最小重量(除全0碼外)2711.5 循環(huán)碼一、特點：1、循環(huán)碼是一種重要的線性分組碼,易于實現(xiàn),性能較好.2、循環(huán)碼除具有線性碼的一般性質(zhì)外,還具有循環(huán)性,即循環(huán)碼中任一碼組

10、循環(huán)一位以后,仍為該碼中的一個碼組.3、長為n的碼組可表示成碼多項式012211)(axaxaxaxTnnnn284、碼多項式的模運算 若F(x) = N(x) Q(x) + R(x) 則：F(x) R(x)（模等） ( 模 N(x)、商Q(x) 、余數(shù)R(x) ) 例： )1(113224xxxxx模xxxx11243xx 412xx295、結(jié)論：在循環(huán)碼中,若 T(x)是一個長為n的許用碼組,則xi T(x)在按模xn +1運算下,也是一個許用碼組。 即 若 則 T(x)也是一個許用碼組) 1()()(nixxTxTx模30二、生成多項式：二、生成多項式：在循環(huán)碼中，一個（n，k）碼有2k

11、個不同碼組1、（n，k）循環(huán)碼的生成多項式g（x）是一個常數(shù)項為1的r=n-k次多項式2、g（x）是循環(huán)碼中次數(shù)最低的多項式（全0碼除外）3、 g（x）為xn+1的一個r次因子（可以有多個）4、 g（x）可以整除xn+1及任何一個碼組5、 g（x）的碼重就是碼組的最小碼距012211)(axaxaxaxTnnnn31三、生成矩陣三、生成矩陣G假如輸入信息碼元mk-1 mk-2 m0 則)()()()()(21xgxxgxgxxgxxGkk)()()(021xGmmmxTkkG生成矩陣不一定是典型的，但根據(jù)矩陣性質(zhì)將其線性變換，可以化成典型矩陣形式G=Ik.Q32四、生成多項式g(X)的確定 T

12、(x) = h(x) g(x) 又 g(x)為一個碼組, 故xkg(x)在模xn+1運算下也為一碼組, 故可寫成1)()(1)(nnkxxTxQxxgx33 故故 g(x) 是是 xn+1的一個的一個n k次因式次因式。 例： )(1)(xTxxgxnk)()()()()(1xhxxgxgxhxgxxkkn) 1)(1)(1(13237xxxxxx都可作為(7,3)循環(huán)碼的生成多項式34五、編、解碼方法1、編碼步驟：*根據(jù)給定的（n,k)選定生成多項式g(x)即從xn+1的因子中選一n-k次多項式作為g(x).*所有碼多項式T(x)都可被g(x)整除,據(jù)此對給定的信息位m(x)進行編碼.1.

13、信息碼后附加n-k個02. 3. )( xmxkn )()()()()(xgxrxQxgxmxkn)()()(xrxmxxTkn35監(jiān)督位信息位例 (7,3)循環(huán)碼 m(x)=x2+x, g(x)= x4 +x2+ x+1 解 5637)(xxxmx1)()(2456xxxxxxgxmxkn1112422xxxxxxr(x)11001011)(256xxxxT362、解碼 將接收碼組R(x)用g(x)去除,若未發(fā)生錯誤, R(x)能被g(x)整除, 發(fā)生錯誤則有余項.3711.6 卷積碼(n,k,N) 監(jiān)督位不僅與當前段的k個信息位有關(guān),而且與前N-1段的信息有關(guān), N稱為卷積碼的約束長度。一

14、、編碼原理：以（3,1,3）碼為例1、編碼器模型圖： M3 M2 M1+輸入序列 mjy1y2y338 每輸入一個比特信息，編碼器輸出三個比特信息，編碼效率Rc=1/3。2、生成碼多項式： g1=1 g2=1+x2 g3=1+x+x23、編碼輸出序列： 假設(shè)輸入信息碼為10110，則其延時多項式為m(x)=1+x2+x339那么：y1=m.g1=1+x2+x3，對應碼序列10110 y2=m.g2=(1+x2+x3)(1+x2)=1+x2+x3+x2+x4+x5 =1+x3+x4+x5，對應碼序列100111(溢出) y3=m.g3=(1+x2+x3)(1+x+x2)=1+x2+x3+x+x3

15、+x4+x2 +x4+x5=1+x+x5，對應碼序列110001(溢出)則：總的輸出碼序列為 111 001 100 110 01040二、卷積碼的圖解表示法： （3，1，3）卷積碼編碼器 a 狀態(tài)m1m2為00， b 狀態(tài)m1m2為01， c 狀態(tài)m1m2為10， d 狀態(tài)m1m2為11。 M3 M2 M1+輸入序列 mjy1y2Y3411、（、（3，1，3）卷積碼的樹狀圖）卷積碼的樹狀圖000000111000111001110000111001110011100010101aababcdabcdabcd1110011100111000101010001110011100111000101

16、01bcdabcdabcdabcda向上表示輸入向上表示輸入0；向下表示輸入向下表示輸入1橫線上數(shù)碼表示一個碼組的三位422、（3，1，3）卷積碼的網(wǎng)格圖abcd000000000000000111111111111111011011011001001001001110110110110010010010101101101100實線表示輸入0，虛線表示輸入1433、（3，1，3）卷積碼的狀態(tài)圖aabbccda111110101000011100001010abcd11100011010110000101101044例：例：在前述編碼器中，若起始狀態(tài)為a，輸入序列為11010，求輸出序列和狀態(tài)變化路徑abcd0000000000000001111