第6章 編碼技術(shù)

1、第6章 編碼技術(shù)6.1 概述6.2 常用的差錯控制編碼6.3 線性分組碼6.4 循環(huán)碼6.5 卷積碼6.1 概述6.1.1 信源編碼與信道編碼6.1.2 差錯控制與編碼分類6.1.3 差錯控制能力與編碼效率6.1.4 差錯控制方式6.1.1 信源編碼與信道編碼n信源編碼(有效性編碼)n去除冗余n降低傳輸速率n信道編碼(可靠性編碼)n添加冗余n降低差錯率：犧牲通信的有效性（信息傳輸速率）來提高可靠性6.1.2 差錯控制與編碼分類n差錯控制編碼n理論依據(jù)：香農(nóng)信道編碼定理n基本思想：通過對信息碼元序列作某種變換,使原來彼此相互獨立,沒有關(guān)聯(lián)的信息碼元序列,經(jīng)過這種變換后,產(chǎn)生某種規(guī)律性或相關(guān)性,使

2、在接收端可根據(jù)這種規(guī)律性來檢查,以至糾正傳輸序列中的差錯n實現(xiàn)：發(fā)送端按照某種規(guī)則在信息序列上附加監(jiān)督碼元，接收端則按照同一規(guī)則檢查兩者間關(guān)系n簡單例子對于一給定的有干擾信道，若其信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息，則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值。香農(nóng)信道編碼定理舉例說明：假如要傳送A、B兩個消息n編碼一：編碼一：n消息A-“0”；消息B-“1”n若傳輸中產(chǎn)生錯碼（“0”錯成“1”或“1”錯成“0”）收端無法發(fā)現(xiàn)，該編碼無檢錯糾錯能力。n編碼二：編碼二：n消息A-“00”；消息B-“11”n若傳輸中產(chǎn)生一位錯碼，則變成“01”或“

3、10”，收端判決為有錯（因“01”“10”為禁用碼組），但無法確定錯碼位置，不能糾正，該編碼具有檢出一位錯碼的能力。n這表明增加一位冗余碼元后碼具有檢出一位錯碼的能力n編碼三：編碼三：n消息A-“000”；消息B-“111”n傳輸中產(chǎn)生一位即使兩位錯碼，都將變成禁用碼組，收端判決傳輸有錯。該編碼具有檢出兩位錯碼的能力。n在產(chǎn)生一位錯碼情況下，收端可根據(jù)“大數(shù)”法則進行正確判決，能夠糾正這一位錯碼。該編碼具有糾正一位錯碼的能力。n這表明增加兩位冗余碼元后碼具有檢出兩位錯碼及糾正一位錯碼的能力。n可見n糾錯編碼之所以具有檢錯和糾錯能力，確實是因為在信息碼元外添加了冗余碼元（監(jiān)督碼元）n一般說來，添

4、加的冗余越多，碼的檢錯、糾錯能力越強，但信道的傳輸效率下降也越多。n涉及概念：檢錯、糾錯；許用碼組/字、禁用碼組/字；錯誤譯碼6.1.2 差錯控制與編碼分類差錯分類n隨機差錯獨立差錯n差錯的出現(xiàn)隨機，且差錯之間是統(tǒng)計獨立的n由隨機噪聲引起n存在這種差錯的信道稱為隨機信道無記憶信道n突發(fā)差錯n差錯在短時間成串出現(xiàn)，而在其間又存在較長的無差錯區(qū)間，且差錯之間相關(guān)n因脈沖噪聲，也可能是由存儲系統(tǒng)中磁帶的缺陷或讀寫頭接觸不良引起n存在這種差錯的信道稱為突發(fā)信道有記憶信道例n設發(fā)送數(shù)據(jù)序列為：00000000001111111111n接收數(shù)據(jù)序列為：01101001001111001001n則差錯序列為

5、： 01101001000000110110n差錯序列：發(fā)送數(shù)據(jù)序列與接收序列對應碼位的模和n發(fā)生了兩個長度分別為和的突發(fā)差錯，其錯誤圖樣分別為1101001和11011n突發(fā)長度：指突發(fā)差錯首位與末位之間的長度（中間可能有沒錯的碼位）n差錯序列或錯誤圖樣中的“”表示對應碼位沒錯，而“”表示有錯n實際信道很復雜，所出現(xiàn)的差錯并不是單一的，往往是隨機和突發(fā)差錯并存，只不過以某種錯誤為主6.1.2 差錯控制與編碼分類n編碼分類n按功能分n按監(jiān)督碼元與信息碼元關(guān)系分n按監(jiān)督碼元與信息碼元約束關(guān)系分n按信息碼元在碼組中的形式分：系統(tǒng)碼與非系統(tǒng)碼n按糾正差錯的類型分：糾正隨機錯誤的碼與糾正突發(fā)錯誤的碼n

6、按碼元的取值分：二進制碼與多進制碼6.1.3 差錯控制能力與編碼效率n幾個概念n碼重：碼字中非零碼元的數(shù)目定義為該碼字的重量，簡稱碼重。如“10011”碼字的碼重為3。n碼距：兩個碼字中對應碼位上具有不同二進制碼元的位數(shù)定義兩碼字的距離，稱為漢明（Hamming）距離,簡稱碼距。如兩碼字“10011”與“11010”間碼距為2。n最小碼距：在一個碼中，任意兩個碼字間距離的最小值，即碼字集合中任意兩元素間的最小距離，記為d0最小碼距與檢、糾錯能力關(guān)系n一個碼能檢測e個錯碼，則要求其最小碼距d0e+1反之，若碼的最小距離為d0，則最多能檢測d0-1個錯碼。n一個碼能糾正t個錯碼，則要求其最小碼距d

7、02t+1反之，若碼的最小距離為d0，則最多能糾正(d0-1)/2個錯碼。n一個碼能糾正t個錯碼，同時能檢測e個錯碼，則要求其最小碼距 d0e+t+1 (et) n假設隨機信道中發(fā)送“0”碼與發(fā)送“1”碼傳錯概率相等,為Pe,且Pe(j-i)n能檢出全部的奇數(shù)個錯碼：n含有奇數(shù)項錯碼的多項式必不含(x+1)因子，只要選取的g(x)含有(x+1)因子n能檢測所有長度不超過(n-k)的突發(fā)錯誤：n突發(fā)長度不大于b的突發(fā)錯誤對應的錯碼多項式為E(x)=xi(eb-1xb-1+ eb-2xb-2+e1x+1)= xi E1(x)n由于g(x)除不盡xi； g(x)為n-k次多項式，只要E1(x)的次數(shù)

8、b-1不超過(n-k-1)次， g(x)便除不盡E1(x)。也就是說，能檢測長度不超過(n-k)的突發(fā)錯誤。n在突發(fā)長度b大于(n-k)的錯誤中，若b=n-k+1，則(n，k)循環(huán)碼不能檢測概率為2-(n-k-1)；若bn-k+1，則不能檢測概率為2-(n-k）。n設錯碼多項式為E(x)= xi E1(x) ，E1(x)的次數(shù)為(b-1)，必有x0 和xb-1項，還應有b-2項xj，因此共有2b-2種不同的多項式。n只有E1(x)有g(shù)(x)的因子時，即E1(x)= g(x) Q(x)時，這種錯碼才不能檢測出來。ng(x)為(n-k)次，所以Q(x)定為b-1-(n-k)次；當b-1=n-k（即

9、b=n-k+1），則Q(x)=1，此時僅有一個E1(x)= g(x)的錯誤圖樣不可檢測，占突發(fā)錯誤圖樣總數(shù)的1/2b-2=2-(n-k-1)BCH碼n發(fā)現(xiàn)者：Hocguenghem(59)，Bose和 Chaudhuri(60)n特點：能糾正多個隨機錯誤，并有嚴密的數(shù)學結(jié)構(gòu)n循環(huán)碼中一類重要子碼：g(x)與dmin關(guān)系密切nBCH碼的碼長n與監(jiān)督位、糾錯能力t間關(guān)系：n對于任一正整數(shù)m和t(tn/2)，必定存在一個碼長n=2m-1，監(jiān)督位n-kmt，能糾正所有不大于t個隨機錯誤的BCH碼BCH碼n分兩類：n本原BCH碼：g(x)中含有最高次數(shù)為m的本原多項式，且碼長n= 2m-1n非本原BCH

10、碼： g(x)中不含這種本原多項式，且碼長n是2m-1的一個因子n本原多項式（次數(shù)為m)：不含因式的既約多項式，能除盡 ，但除不盡xr-1，r 2m-1。n例如m=3時， 2m-1=7， nx7-1=（x+1)(x3+x2+1)(x3+x+1)，此時最高次數(shù)為3的本原多項式有兩個：(x3+x2+1) 和(x3+x+1)，它們都能除得盡x7-1，但除不盡x6-1和x5-112 mxn具有循環(huán)性質(zhì)的漢明碼就是糾正單個隨機錯誤的本原BCH碼：n漢明碼是糾正單個隨機錯誤的碼，其碼長n= 2m-1，k= 2m-1-mBCH碼的構(gòu)造舉例n例1：構(gòu)造一個糾錯能力為3，碼長為15的BCH碼。n查表9-8得：n

11、=15，k=5，t=3的BCH碼，對應碼多項式標號為(2467)8=(10100110111)2，g(x)=x10+x8+x5+x4+x2+x+1BCH碼的構(gòu)造舉例n例2：試求Golay碼（23，12）（非本原BCH碼）碼的生成多項式。n查表9-9得： （23，12）非本原BCH碼對應碼多項式標號為(5343)8=(101011100011)2 ，g(x)=x11+x9+x7+x6+x5+x+1擴展BCH碼n在BCH碼上增加一奇偶校驗位，擴展后碼距增加1，同時具有檢錯、糾錯能力，但不再是循環(huán)碼了。RS碼n多進制BCH碼n具有很強的糾錯能力，特別適合于糾正突發(fā)錯誤n糾t個符號錯誤的(n,k) R

12、S碼：n碼長n=2m-1 個符號 m(2m-1 ) bitn信息段k個符號 mk bitn監(jiān)督段n-k=2t個符號 m (n-k ) bitn最小碼距dmin=2t+1個符號 m (2t+1) bit6.5 卷積碼n幾點說明：n又名連環(huán)碼，是一種非分組碼n與分組碼相比，在同等碼率和相似的糾錯能力下，卷積碼的實現(xiàn)往往更簡單n卷積碼主要應用于FEC數(shù)據(jù)通信系統(tǒng)中n基本原理：n在任何一段規(guī)定時間里編碼器產(chǎn)生的n個碼元，不僅取決于這段時間中的k個信息碼元,而且還取決于前m(m= N-1)段規(guī)定時間內(nèi)的信息碼元，編碼過程中相互關(guān)聯(lián)的碼元為Nn個。nm或N段時間內(nèi)的碼元數(shù)目Nn稱為卷積碼的約束長度。n記作

13、(n，k，N)或 (n,k,m)，編碼效率R=k/n。 卷積碼(2,1,2)編碼器 m1m2數(shù)據(jù)輸入碼字輸出S1S2S3C1C2 起始狀態(tài)，各級移位寄存器清零，即S1S2S3為000。S1等于當前輸入數(shù)據(jù)，而移位寄存器狀態(tài)S2S3存儲以前的數(shù)據(jù)，輸出碼字C由下式確定 1123213CSSSCSS=排= 表 (2,1,2)編碼器的工作過程 卷積碼的描述卷積碼的描述 1. 樹圖樹圖 (2,1,2)碼的樹圖碼的樹圖 a1100abb0110cdc0011abd1001cd0010a1101ba0011a1100abb0110cdc0011abd1001cd1101c0010db1001a1100數(shù)碼

14、起點狀態(tài)a00b01c10d11上半部下半部數(shù)碼11012. 狀態(tài)圖狀態(tài)圖 (2,1,2)碼的狀態(tài)圖 a00b01c10d11cbad01011111001000103. 格圖格圖 (2,1,2)碼的格圖 a00起點aaaaaabbbccccbbcbddddd000000000000000000100101010101010110101010111111111111101010100101卷積碼的譯碼卷積碼的譯碼 1. 維特比譯碼維特比譯碼 維特比譯碼格圖維特比譯碼格圖 圖79起點d80100(4)cba700(3)6500(3)4300(3)200(2)10 00(1)級11(1)11(3)

15、11(3)11(3)10(2)10(4)00(3)01(3)01(3)10(3)10(3)10(3)01(1)01(1)01(5)00(2)11(2)收碼01011010010001解碼11010000 2. 序列譯碼序列譯碼 當m很大時，可以采用序列譯碼法。 其過程如下： 譯碼先從碼樹的起始節(jié)點開始，把接收到的第一個子碼的n個碼元與自始節(jié)點出發(fā)的兩條分支按照最小漢明距離進行比較， 沿著差異最小的分支走向第二個節(jié)點。在第二個節(jié)點上，譯碼器仍以同樣原理到達下一個節(jié)點，以此類推，最后得到一條路徑。若接收碼組有錯，則自某節(jié)點開始，譯碼器就一直在不正確的路徑中行進，譯碼也一直錯誤。因此，譯碼器有一個門

16、限值，當接收碼元與譯碼器所走的路徑上的碼元之間的差異總數(shù)超過門限值時，譯碼器判定有錯，并且返回試走另一分支。經(jīng)數(shù)次返回找出一條正確的路徑，最后譯碼輸出。 n舉例說明：D0D1輸入mj輸出mjPj1Pj2c1c0c2c1c2c2c3c3c3c4c5c4c5圖 7-11 n0=3, k0=1,m=2 的卷積編碼器圖 7-12 卷積子碼間的約束關(guān)系n編碼：n輸入信息碼位一方面直接輸出，另一方面可暫存在移位器中。每當輸入編碼一個信息位，就立即計算出一監(jiān)督位，并且此監(jiān)督位緊跟此信息位之后發(fā)送出去。tm1m2m3m4tm1c1m2c2m3c3m4c4n編碼器工作過程：移位寄存器按信息位的節(jié)拍工作，輸入一位

17、信息，電子開關(guān)倒換一次，即前半拍（半個輸入碼元寬）接通m端，后半拍接通c端。n編碼公式：c1=0+m1 c2=m1+m2 c3=m2+m3 ci=mi-1+min可見：n卷積碼結(jié)構(gòu)為：“信息碼元、監(jiān)督碼元、信息碼元、監(jiān)督碼元、 ”。n一個信息碼元和一個監(jiān)督碼元組成一組，但每組中的監(jiān)督碼元除與本組信息碼元有關(guān)外，還跟上一組信息碼元有關(guān)。n譯碼：c簡單 (2,1,2)卷積碼譯碼器1D2D1+信息碼輸出卷積碼輸入+D3+Smc32解碼器工作過程n解碼器輸入端的電子開關(guān)按節(jié)拍把信息碼元與監(jiān)督碼元分接到m端與c端；n3個移位寄存器的節(jié)拍比碼序列節(jié)拍低一倍，其中移位寄存器D1，D2在信息碼元到達時移位，監(jiān)

18、督碼元到達期間保持原狀；而移位寄存器D3在監(jiān)督碼元到達時移位，信息碼元到達期間保持原狀；3. 移位寄存器D1，D2和模2加法器1構(gòu)成與發(fā)端一樣的編碼器，它從接收到的信息序列中計算出對應的監(jiān)督序列來；4. 模2加法器2把計算出的監(jiān)督序列與接收到的監(jiān)督序列進行比較：兩者相同，輸出“0”；兩者不同，輸出“1”，顯然此時，必定出現(xiàn)了差錯。5. 如果有差錯，則要確定差錯位置并糾錯n具體判決如下：n根據(jù)譯碼圖，有校驗子S的方程即解碼方程如下：S0=（0+m1)+c1S1=（ m1 +m2)+c2 S2=（ m2 +m3)+c3 Si=（ mi +mi+1)+ci+1 n可見每個信息碼元出現(xiàn)在兩個S方程中，即mi與Si-1和Si有關(guān)，在判決mi是否有錯時，應根據(jù)Si-1和Si的值。n（正交正交：決定Si-1和Si值的共有5個碼元，但其中只有mi與Si-1、Si兩值都有關(guān)，而其他碼元只與一個值有關(guān)，這稱為方程Si-1與Si正交于mi；或者說校驗子方程Si-1與Si構(gòu)成mi的正交方程組。）n在差錯不多于1個條件下，根據(jù)正交性得判決規(guī)則如下：n當Si-1、S