第9章-差錯控制編碼

1、2021/3/261 第9章 差錯控制編碼 9.1 引言 9.2 糾錯編碼的基本原理 9.3 常用的簡單編碼 9.4 線性分組碼 9.5 循環(huán)碼 9.6 卷積碼 2021/3/262 9.1 引言 差錯控制編碼的基本方法 在發(fā)送端被傳輸?shù)男畔⑿蛄猩细郊右恍?監(jiān)督碼元,這些多余碼元與信息碼元之間 以某種確定的規(guī)則相互關(guān)聯(lián)(約束),接收端 按照既定的規(guī)則檢驗信息碼元與監(jiān)督碼 元之間的關(guān)系. 2021/3/263 常用差錯控制方法 檢錯重發(fā) 前向糾錯 發(fā)收 檢錯碼 應(yīng)答信號 發(fā)收 糾錯碼 2021/3/264 混合糾錯 發(fā)收 糾檢錯 應(yīng)答信號 常用檢錯重發(fā)系統(tǒng): 停發(fā)等候重發(fā),返回 重發(fā)和選擇重發(fā)

2、2021/3/265 停發(fā)等候重發(fā) 1233 1 TI 23 發(fā) 接收 ACK NAK 發(fā)現(xiàn)錯誤 這是一種半雙工的通信方式,原理簡單, 效率低. 2021/3/266 返回重發(fā) 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 發(fā) 接收 發(fā)現(xiàn)錯誤 NAK 從碼組2開始重發(fā) (傳輸效率最高,需復(fù)雜的控制,收、發(fā)數(shù)據(jù)緩存)選擇重發(fā) 7 8 9 10 11 12 重發(fā)碼組2 2021/3/267 9.2 糾錯編碼的基本原理 分類 按差錯控制編碼的功能功能:檢錯碼、糾錯碼、 糾刪碼。 按信息碼元和附加的監(jiān)督碼元之間的檢檢 驗關(guān)系驗關(guān)系:線性

3、碼、非線性碼。 按信息碼元和監(jiān)督碼元之間的約束方式：約束方式： 分組碼、卷積碼。 2021/3/268 例:3位二進(jìn)制數(shù)構(gòu)成的碼組表 示天氣 全用用4種 用2種全用用4種 用2種 000晴晴晴100雪 001云101霜陰 010陰110霧雨 011雨云111雹雨 2021/3/269 如不要檢（糾）錯,傳輸4種不同的信 息,用兩位碼組就夠了，這兩位碼代表 所傳信息，稱為信息位，多增加的稱 為監(jiān)督位。 將信息碼分組,為每組信碼附加若干監(jiān)督碼的編 碼,稱為分組碼。在分組碼中，監(jiān)督碼元僅監(jiān)督 本碼組的中的信息碼元。 分組碼用（n，k）表示，n碼組長度， k 信 息位數(shù)，n k = r 監(jiān)督位數(shù)。 1

4、的數(shù)目稱為碼組的重量，兩個碼組對應(yīng)位上 數(shù)字不同的位數(shù)稱為碼組距離（漢明距離）。 各碼組間距離的最小值為最小碼距 d0 2021/3/2610 d0的大小直接關(guān)系著編碼的檢,糾錯能 力。 為檢測 e 個錯碼,要求 d0 e + 1 為糾正 t 個錯碼,要求 d0 2 t + 1 為糾正 t 個錯碼，同時檢測 e 個錯碼，要求 d0 e + t +1 B d0 B A 12 B A 12 B B 34 5 d0 2021/3/2611 A B1 t e 若隨機(jī)信道中,發(fā)送“0”和發(fā)送“1”時的 錯誤概率相等,為P，且P1,則碼長為 n 的碼組恰好發(fā)生r個錯碼的概率為: rrnrr nn P rn

5、r n PPCrp )!( ! ! )1 ()( 2021/3/2612 當(dāng) n=7 P=10-3時 P(1) 710-3 P(2) 2.110-5 P(3) 3.510-8 可見,采用差錯控制編碼,即使僅能糾 正這種碼組中的1 2個錯誤,也可以使 誤碼率下降幾個數(shù)量級. 2021/3/2613 9.3 常用的簡單編碼 奇偶監(jiān)督碼 無論信息位有多少,監(jiān)督位只有一位,使碼 組中“1”的數(shù)目為偶(或奇)數(shù). 接收端 奇數(shù)監(jiān)督碼 偶數(shù)監(jiān)督碼 1 0 021 aaa nn 這種碼能夠檢測奇數(shù)個錯碼,適用 檢測隨機(jī)錯誤 2021/3/2614 二維奇偶監(jiān)督碼 把上述奇偶監(jiān)督碼的若干碼組排列成矩 陣,每一

6、碼組寫成一行,然后,再按列的方向 增加第二維監(jiān)督位 1 0 1 1 1 2 1 1 aaaa nn 2 0 2 1 2 2 2 1 aaaa nn mmm n m n aaaa 0121 0121 cccc nn 2021/3/2615 恒比碼 每個碼組均含有相同數(shù)目的“1”(和“0”).由 于“1”的數(shù)目與“0”的數(shù)目之比保持恒定,故 得此名. 正反碼 是一種簡單的能夠糾正錯碼的編碼,監(jiān)督位數(shù) 目與信息位數(shù)目相同,監(jiān)督位與信息位相同或相 反,由信息碼中的“1”的個數(shù)而定. 2021/3/2616 9.4 線性分組碼 線性分組碼中信息碼元和監(jiān)督碼元是用線性方 程聯(lián)系起來的.線性碼建立在代數(shù)學(xué)群

7、論基礎(chǔ)上, 線性碼各許用碼組的集合構(gòu)成代數(shù)學(xué)中的群,因 此,又稱群碼. 主要性質(zhì) 任意兩許用碼組之和(模2和)仍為一許用碼組. (封閉性) 碼的最小距離等于非零碼的最小重量 2021/3/2617 奇偶監(jiān)督碼是一種最簡單的線性碼,偶 校驗時 S稱為校正子,又稱伴隨式. S=0無錯,S=1 有 錯. 一般, 由r個監(jiān)督方程式計算得r個校正子, 可以用來指示2r-1種錯誤,對于一位誤碼來 說,就可以指示2r-1個誤碼位置.對于(n,k)碼, 如果滿足2r-1n 則可能構(gòu)造出糾正一位或 一位以上錯誤的線性碼. 021 aaaS nn 2021/3/2618 設(shè)分組碼(n,k)中k=4,為糾正一位錯碼

8、, 要求r3, 則 n=k+r=7 S1S2S3錯碼位置S1S2S3錯碼位置 001a0101a4 010a1110a5 100a2111a6 011a3000無錯 2021/3/2619 0 24561 aaaaS 0 13562 aaaaS 0 03463 aaaaS 4562 aaaa 3561 aaaa 3460 aaaa 計算監(jiān)督 位 判斷 錯碼 位置 按上述方法構(gòu)造的糾正單個錯誤的線性 分組碼稱為漢明碼。 碼長 n=2r 1 信息位 k= 2r 1 r 監(jiān)督位r （1） （2） 2021/3/2620 編碼速率= （1）改寫為 n rrr n k rr r 1 12 1 12 12

9、 00010111 0123456 aaaaaaa 00101011 0123456 aaaaaaa 01001101 0123456 aaaaaaa 表示成矩陣形式 1001101 0101011 0010111 0 1 2 3 4 5 6 a a a a a a a = 0 0 0 PIr 2021/3/2621 簡記為 或 H稱為監(jiān)督矩陣,H確定,則編碼時監(jiān)督位和 信息位的關(guān)系就完全確定了。 P為r k 階 Ir為 r r 階單位方陣 具有 P Ir 形式的H矩陣稱為典型陣。 （2）改寫為: TT HA00 T AH 0 1 2 a a a = 1101 1011 0111 3 4 5

10、6 a a a a 2021/3/2622 或 012 aaa 3456 aaaa 110 101 011 111 3456 aaaaQ 階rkPQ T QIG k 生成矩陣 0123456 aaaaaaa 3456 aaaaG A 3456 aaaaG 2021/3/2623 具有 形式的生成矩陣稱 為典型生成矩陣。 由典型生成矩陣得出的碼組A中, 信息位不變,監(jiān)督位附加其后，這 種碼稱為系統(tǒng)碼。 QIG k 2021/3/2624 發(fā)送碼組A在傳輸過程中可能發(fā)生誤碼, 設(shè)接收到的碼組為B=bn-1 bn-2 b0 則 B A = E E= en-1 en-2 e0 錯誤圖樣 也可寫作 B=

11、A+E ii ii i ab ab e 當(dāng) 當(dāng) 1 0 2021/3/2625 接收端計算校正子為 錯誤圖樣與校正子之間有確定的關(guān)系 TTT TT EHEHAH HEABHS ）（ 2021/3/2626 例 設(shè) 且有3 個接收碼組 驗證3個接收碼組是否發(fā)生差錯? 若在某碼組中有錯碼,錯碼的校正子是什么？ 然后再指出發(fā)生錯碼的碼字中,哪位有錯？ 100101 010110 001011 H 101110 1 B 110101 2 B110000 3 B 2021/3/2627 解:1）若無錯,則錯誤圖樣為0,S為0 000 11 T HBS B1無錯 101 22 T HBS B2錯 110

12、33 T HBSB3錯 2） S2=H 第1 列 E=1 0 0 0 0 0 第1位 錯 同理 S3=H 第3列 E=0 0 1 0 0 0 第3位 錯 T EHS 2021/3/2628 線性碼的重要性質(zhì) 封閉性 任意許用兩個碼組之和仍為許用碼組 兩個碼組之間的距離必是另一碼組的重 量,故最小碼距即碼的最小重量(除全0碼 外) 2021/3/2629 9.5 循環(huán)碼 9.5.1 循環(huán)碼原理 循環(huán)碼是一種重要的線性分組碼,易于實 現(xiàn),性能較好. 循環(huán)碼除具有線性碼的一般性質(zhì)外,還具 有循環(huán)性,即循環(huán)碼中任一碼組循環(huán)一位 以后,仍為該碼中的一個碼組. 一長為n的碼組可表示成碼多項式 01 2 2

13、 1 1 )(axaxaxaxT n n n n 2021/3/2630 碼多項式的按模運算 若F(x) = N(x) Q(x) + R(x) 則 F(x) R(x) ( 模 N(x) ) 例 )1(11 3224 xxxxx模 x xxx11 243 xx 4 1 2 xx 2021/3/2631 在循環(huán)碼中,若 T(x)是一個長為n 的許用碼組,則xi T(x)在按模xn +1 運算下,也是一個許用碼組. 即 若 則 T(x)也是一個許用碼組 ) 1()()( ni xxTxTx模 2021/3/2632 在循環(huán)碼中,一個（n,k）碼有2k個不同 碼組 假設(shè)用g（x）表示一個前k-1位皆為

14、0（第 k位不為0）的碼組 則 在循環(huán)碼中,除全0碼外,再沒有連續(xù)k位均 為“0”的碼組，即連“0”的長度最多 只能k-1位。因此g（x）必須是一個常數(shù) 項不為“0”的n-k次多項式 01 2 2 1 1 )(axaxaxaxT n n n n 0 1 1 )(axaxaxg kn kn kn kn 生成多項 式 2021/3/2633 g(x),xg(x),x2g(x), xk-1g(x)都是碼組,且線性 無關(guān),故循環(huán)碼的生成矩陣G可寫成 假如輸入信息碼元mk-1 mk-2 m0 則 )( )( )( )( )( 2 1 xg xxg xgx xgx xG k k )()()( 021 xG

15、mmmxT kk )()( 0 2 2 1 1 xgmxmxm k k k k 2021/3/2634 所有碼多項式T(x)都可被g(x)整除,而且, 任一次數(shù)不大于k-1的多項式乘g(x)都 是碼多項式. 生成多項式g(X)的確定 T(x) = h(x) g(x) 又 g(x)為一個碼組, 故xkg(x)在模xn+1運算下 也為一碼組, 故可寫成 1 )( )( 1 )( nn k x xT xQ x xgx =1 2021/3/2635 故 g(x) 是 xn+1的一個n k次因式, 此即尋 找 g(x) 的方法. 例 )(1)(xTxxgx nk )()()()()(1xhxxgxgxh

16、xgxx kkn ) 1)(1)(1(1 3237 xxxxxx 都可作為(7,3)循環(huán)碼的生成多項式 2021/3/2636 9.5.2 循環(huán)碼的編、解碼方法 編碼步驟 根據(jù)給定的（n,k)選定生成多項式g(x),即 從xn+1的因子中選一n-k次多項式作為 g(x). 所有碼多項式T(x)都可被g(x)整除,據(jù)此 對給定的信息位m(x)進(jìn)行編碼. 1. 信息碼后附加n-k個0 2. 3. )( xmx kn )( )( )( )( )( xg xr xQ xg xmx kn )()()(xrxmxxT kn 2021/3/2637 監(jiān)督位 信息位 例 (7,3)循環(huán)碼 m(x)=x2+x,

17、 g(x)= x4 +x2+ x+1 解 5637 )(xxxmx 1)( )( 24 56 xxx xx xg xmx kn 1 1 1 24 2 2 xxx x xx r(x) 11001011)( 256 xxxxT 2021/3/2638 a+b+cd+ 輸入m 輸出f e S （7,3）碼編碼器 m a b c d e f 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 f=m f=e 2021/3/2639

18、循環(huán)碼的解碼 將接收碼組R(x)用g(x)去除,若未發(fā)生錯誤, R(x)能被g(x)整除, 發(fā)生錯誤則有余項. 2021/3/2640 9.6 卷積碼 在編碼器復(fù)雜性相同的情況下,卷積 碼的性能優(yōu)于分組碼. 卷積碼把k個信息位編n位,k和n通常很小, 特別適宜于串行形式傳輸,延時小. n 個碼元與當(dāng)前段的k個信息位有關(guān),而且 與前N-1段的信息有關(guān),編碼過程相互關(guān)聯(lián) 的碼元為Nn個. N或nN稱為卷積碼的約束長度, 常把卷積碼記作(n,k,N) 2021/3/2641 6 5 4 3 2 1 + 輸入bi ci 輸出 bici 卷積碼編碼器 k=1, n=2, N=6 2021/3/2642

19、b6 b5 b4 b3 b2 b1 + 一級 移存 + S6 S5 S4 S3 S2 S1 + 門限電路 (2,1,6)卷積碼門限譯碼器 輸入 bi ci 重算ci 輸出 校正子 “1”的個數(shù)3? 2021/3/2643 假定b1以前各碼元均未發(fā)生錯誤,則 )()( 111 cEbES )()( 222 cEbES )()( 333 cEbES )()()( 1444 bEcEbES )()()()( 21555 bEbEcEbES )()()()()( 321666 bEbEbEcEbES 錯 無錯 b b bE 1 0 )( 錯 無錯 c c cE 1 0 )( (1) 2021/3/26

20、44 (1)式經(jīng)線性變換 這是一組正交于E(b1)的正交校驗方程,在 所考察的12個碼元(b1b6,c1c6)中錯誤不多 于2個的條件下,僅當(dāng)E(b1)=1, (2)式才有可 能有3個或3個以上方程等于1. 門限電路門 限設(shè)為3,此時,門限電路輸出“1”,糾正b1 錯誤,同時送到受E(b1)影響的各級校正子 移存器糾正其中錯誤. )()( 111 cEbES )()()( 1444 bEcEbES )()()()( 21555 bEbEcEbES )()()()()( 6263162 cEcEbEbEbESS (2) 2021/3/2645 監(jiān)督矩陣H 假定b1進(jìn)入編碼器之前,各級移存器處 于

21、“0”狀態(tài) 則 即 11 bc 22 bc 33 bc 414 bbc 5215 bbbc 63216 bbbbc 74327 bbbbc 0 11 bc 0 22 bc 0 33 bc 0 5215 bbbc 0 414 bbc 0 63216 bbbbc 0 74327 bbbbc 2021/3/2646 H1 用矩陣表示為 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 1 1 6 6 5 5 4 4 3 3 2 2 1

22、1 c b c b c b c b c b c b 0 Nkn)( n n-k 2021/3/2647 H1:截短監(jiān)督矩陣 自第7行起,每行結(jié)構(gòu)相同,只是每行的 起始比上一行多兩個“0”。 一般,卷積碼的截短監(jiān)督矩陣形式為: knNNN kn kn kn Ipppp Ippp Ipp Ip H 121 123 12 1 1 000 00 0 2021/3/2648 In-k n-k階單位方陣 Pi （n-k）k矩陣 0 n-k 階全零方陣 基本監(jiān)督矩陣 h= PN 0 PN-1 0 PN-2 0 P1 In-k 只要給定h,H1隨之確定。 2021/3/2649 生成矩陣G 基本生成矩陣g g= IK Q1 0 Q2 0 Q3 0 QN 截短生成矩陣 1 G 1 21 121 321 0 00 000 QI QQI QQQI QQQQI k Nk NK Nk Ik k階單位方陣 Qi =PiT k （n-k）矩陣 0 k 階全零方陣 2021/3/2650 卷積碼的圖解表示 （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 + + 輸入序列 mj mj y1,j Y2,j 2021/