1、1第11章 差錯控制編碼11.1 概述11.2 糾錯編碼的基本原理11.3 常用的簡單編碼11.4 線性分組碼11.5 循環碼11.6 卷積碼211.1 概述一、差錯控制編碼 在發送端被傳輸的信息序列上附加一些監督碼元,這些多余碼元與信息碼元之間以某種確定的規則相互關聯(約束),接收端按照既定的規則檢驗信息碼元與監督碼元之間的關系.3二、差錯控制方法1、檢錯重發2、前向糾錯發收檢錯碼應答信號發收糾錯碼43、混合糾錯發收糾檢錯應答信號*常用檢錯重發系統: 停發等候重發,返回重發和選擇重發5（1）停發等候重發12331TI23發接收ACKNAK發現錯誤這是一種半雙工的通信方式,原理簡單,效率低.6

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

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

4、時檢測 e 個錯碼，要求 d0 e + t +1Bd0BA12BA12BB345d011AB1te若隨機信道中，發送“0”和發送“1”時的錯誤概率相等，為P，且P1,則碼長為n 的碼組恰好發生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個錯誤,也可以使誤碼率下降幾個數量級.1311.3 常用的簡單編碼1、奇偶監督碼 無論信息位有多少,監督位只有一位,使碼組中“1”的數目為偶(或奇)數。 接收端奇數監督碼偶

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

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

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

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

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三、線性碼的重要性質1、封閉性 任意許用兩個碼組之和仍為許用碼組2、兩個碼組之間的距離必是另一碼組的重量,故最小碼距即碼的最小重量(除全0碼外)2711.5 循環碼一、特點：1、循環碼是一種重要的線性分組碼,易于實現,性能較好.2、循環碼除具有線性碼的一般性質外,還具有循環性,即循環碼中任一碼組

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

11、個不同碼組1、（n，k）循環碼的生成多項式g（x）是一個常數項為1的r=n-k次多項式2、g（x）是循環碼中次數最低的多項式（全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生成矩陣不一定是典型的，但根據矩陣性質將其線性變換，可以化成典型矩陣形式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)循環碼的生成多項式34五、編、解碼方法1、編碼步驟：*根據給定的（n,k)選定生成多項式g(x)即從xn+1的因子中選一n-k次多項式作為g(x).*所有碼多項式T(x)都可被g(x)整除,據此對給定的信息位m(x)進行編碼. 信息

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

14、理：以（3,1,3）碼為例1、編碼器模型圖： M3 M2 M1+輸入序列 mjy1y2y338 每輸入一個比特信息，編碼器輸出三個比特信息，編碼效率Rc=1/3。2、生成碼多項式： g1=1 g2=1+x2 g3=1+x+x23、編碼輸出序列： 假設輸入信息碼為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+x4+

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

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