通信原理 信道編碼基本概念漢明碼編碼錯(cuò)誤圖樣糾檢過(guò)程PPT課件

1、第1頁(yè)/共35頁(yè)有上述分析可知：假設(shè)一個(gè)碼能檢測(cè)e個(gè)獨(dú)立錯(cuò)誤，則要求其最小碼距 dmine + 1反之，若碼的最小距離為dmin，則最多能檢測(cè)dmin-1個(gè)錯(cuò)碼第2頁(yè)/共35頁(yè)第3頁(yè)/共35頁(yè)第4頁(yè)/共35頁(yè)由上述分析可知：一個(gè)碼能糾正t個(gè)錯(cuò)碼，則要求其最小碼距 dmin 2t+1反之，若碼的最小距離為dmin ，則最多能糾正 (dmin-1)/2個(gè)錯(cuò)碼第5頁(yè)/共35頁(yè)一個(gè)碼能糾正t個(gè)錯(cuò)碼，同時(shí)能檢測(cè)e個(gè)錯(cuò)碼，則要求其最小碼距 dmine+t+1 (et)糾正t個(gè)錯(cuò)碼，同時(shí)能檢測(cè)e個(gè)錯(cuò)碼，稱為糾檢結(jié)合，錯(cuò)碼數(shù)較少時(shí)執(zhí)行糾錯(cuò)方式，錯(cuò)碼數(shù)較多時(shí)執(zhí)行檢錯(cuò)方式第6頁(yè)/共35頁(yè)有限域的簡(jiǎn)單知識(shí)所謂有限域

2、是指包含有限個(gè)元素的集合，按照所規(guī)定的運(yùn)算規(guī)則運(yùn)算后的結(jié)果仍為集合中的元素編碼理論中有限域?yàn)?, 1二元集合，記為GF(2)GF(2)的加法與乘法： 1）加法：相同為0，相異為1； 2）乘法：除了11 = 1，其他均為0二元擴(kuò)展域，記為GF(2n) ：由GF(2)中的元素構(gòu)成的長(zhǎng)為n的序列的集合，若 1）加法 2）乘法112200(, )nnnnXXxxxxxx112200(, )nnnnX Xxxxxxx120(,)(2 )GFnnnX xxx第7頁(yè)/共35頁(yè)二、線性分組碼線性分組碼的數(shù)學(xué)定義： 信道編碼可表示為由編碼前的信息碼元空間Uk到編碼后的碼字空間Cn的一個(gè)映射f，即：f： Uk C

3、n 其中( n k ) 若f進(jìn)一步滿足線性關(guān)系：則稱f為線性編碼映射，若f為一一對(duì)應(yīng)映射，則稱f為唯一可譯線性編碼，由f編寫的碼c = (cn-1cn-2c0)稱為線性分組碼，u = (un-1un-2 u0 )為編碼前的信息分組，其中k為信息位數(shù)，n為碼長(zhǎng)，其編碼效率為= k/n()()(),(2)0,1, GF kfuufufuu uU 第8頁(yè)/共35頁(yè)數(shù)學(xué)定義的解釋： 1）“線性”是指碼組中碼元之間的約束關(guān)系為線性； 2）“分組”是在編碼時(shí)將每k個(gè)信息位分為一組進(jìn)行獨(dú)立處理； 3）將其變換成長(zhǎng)度為n（nk）的二進(jìn)制碼組，一般稱為（n, k）線性分組碼線性分組碼的特征： 1）加法封閉性：碼

4、組集合中任意兩個(gè)碼組相加仍為集合中的一個(gè)許用碼組； 2）全零序列是線性分組碼中的一個(gè)碼字； 3）碼組集合中碼組之間的最小碼距等于某非零碼字的最小碼重第9頁(yè)/共35頁(yè)偶監(jiān)督偶校驗(yàn)碼發(fā)送端編碼：將一位監(jiān)督碼元附加在信息碼元后，使得碼組中“1”碼元個(gè)數(shù)為偶數(shù)（偶監(jiān)督）接收端譯碼校驗(yàn)： 1）計(jì)數(shù)接收碼組中“1”碼元個(gè)數(shù)是否為偶數(shù)，即計(jì)算 S = an-1+ an-2+ a0 2）S = 0認(rèn)為沒(méi)錯(cuò)，S = 1認(rèn)為有錯(cuò) 3）上式稱為監(jiān)督方程（監(jiān)督關(guān)系式），其中S 稱為校正子（校驗(yàn)子、伴隨式） 4）S只能判斷有錯(cuò)無(wú)措，而不能糾錯(cuò)漢明碼的構(gòu)造第10頁(yè)/共35頁(yè) 假設(shè)有1個(gè)信息碼組由4位二進(jìn)制位組成，在其后添

5、加3位二進(jìn)制位作為監(jiān)督碼元，最后所組成的碼組表示為：c = (u6u5u4u3c2c1c0)并且令： 1）c2監(jiān)督u6 u5 u4，即 2）c1監(jiān)督u6 u5 u3，即 3）c0監(jiān)督u6 u4 u3，即接收端譯碼校驗(yàn)，得到監(jiān)督方程：65310uuuc65420uuuc64300uuuc654226531164300uuucSuuucSuuucS6542uuuc6531uuuc6430uuuc第11頁(yè)/共35頁(yè)對(duì)于上式，若無(wú)錯(cuò)誤發(fā)生，三個(gè)校驗(yàn)子均為0；假設(shè)傳輸過(guò)程中有且僅有一位發(fā)生錯(cuò)誤：1）若c0發(fā)生錯(cuò)誤，觀察監(jiān)督方程，則三個(gè)校驗(yàn)子S2 S1 S0的組合為001；2）若c1發(fā)生錯(cuò)誤， S2 S1

6、 S0 = 010；3）若c2發(fā)生錯(cuò)誤， S2 S1 S0 = 100；4）若u3發(fā)生錯(cuò)誤， S2 S1 S0 = 011；5）若u4發(fā)生錯(cuò)誤， S2 S1 S0 = 101；6）若u5發(fā)生錯(cuò)誤， S2 S1 S0 = 110；7）若u6發(fā)生錯(cuò)誤， S2 S1 S0 = 111；654226531164300uuucSuuucSuuucS第12頁(yè)/共35頁(yè)因此依據(jù)監(jiān)督關(guān)系式就可計(jì)算出所有4位二進(jìn)制信息位u6u5u4u3的監(jiān)督位c2c1c0，這一過(guò)程即為( 7, 4 )線性碼的構(gòu)造過(guò)程，其碼組空間為：654265316430000uuucuuucuuuc第13頁(yè)/共35頁(yè)監(jiān)督矩陣的推導(dǎo)將監(jiān)督關(guān)系

7、式進(jìn)行變換觀察發(fā)現(xiàn)上式即為一個(gè)線性方程組，因此可用矩陣方程來(lái)表示：654265316430000uuucuuucuuuc654321065432106543210111010001101010010110010uuuucccuuuucccuuuuccc 6543210111010001101010010110010uuuuccc 第14頁(yè)/共35頁(yè)對(duì)于上面的矩陣方程，令：則矩陣方程可化簡(jiǎn)為：HCT=OT 或 CHT=O那么H稱為線性碼監(jiān)督矩陣，rn 階的矩陣，由r（監(jiān)督位個(gè)數(shù)）個(gè)線性獨(dú)立方程組的系數(shù)組成，每一行代表了監(jiān)督位與信息位間的監(jiān)督關(guān)系。觀察矩陣H：把具有(PIr)形式的H矩陣稱為典型形

8、式的監(jiān)督矩陣，其中P矩陣為rk 階矩陣, Ir矩陣為rr 階單位方陣H矩陣的各行應(yīng)線性無(wú)關(guān)。矩陣若能寫成典型形式，則其各行一定線性無(wú)關(guān)111010011010101011001H6543210 Cuuuuccc111010011010101011001rHP I0 0 0 O 第15頁(yè)/共35頁(yè)生成矩陣的推導(dǎo)對(duì)監(jiān)督關(guān)系式進(jìn)行移項(xiàng)變換（移動(dòng)紅色部分）：654321065432106543210111010011010101011001uuuucccuuuucccuuuuccc 210265436543654310210100011100110101010110001ccuucccuuuuuccc

9、uuuuuc 654326543165430111011101110111uuuucuuuucuuuuc 6251403111011011011ucucucu第16頁(yè)/共35頁(yè)觀察上面的矩陣方程：其中系數(shù)矩陣與監(jiān)督矩陣H中的P矩陣一樣，對(duì)此矩陣方程兩邊做轉(zhuǎn)置變換：其中Q = PT，為kr 階矩陣；U矩陣表示信息位由上面的矩陣方程可知，只要用信息位與矩陣Q相乘就可得到監(jiān)督位，然后拼接在信息位之后就是一個(gè)（n, k）線性分組碼集合中的一個(gè)碼字6251403111011011011ucucucu 21065436543111110101011TcccuuuuuuuuPUQ第17頁(yè)/共35頁(yè)雖然通過(guò)Q

10、矩陣可以產(chǎn)生線性分組碼，但需要分為兩步，如果對(duì)Q矩陣做變換： 在Q矩陣的左邊加上一個(gè)kk階單位陣，即：則一個(gè)（n, k）線性分組碼可以通過(guò)下面的矩陣方程產(chǎn)生65436543654365432101000111010011000101010001011 kuuuu GuuuuIQuuuuuuuuccc1000111010011000101010001011kGIQ第18頁(yè)/共35頁(yè)對(duì)于生成矩陣G：1）kn階矩陣；2）編碼方法完全由生成矩陣G確定；3）把具有IkQ形式的G矩陣稱為典型形式的生成矩陣，其中Ik為kk階單位方陣，Q為k r階矩陣；4）由典型生成矩陣產(chǎn)生的分組碼一定是系統(tǒng)碼；5）若某生成

11、矩陣G不具有典型形式，則產(chǎn)生的線性分組碼為非系統(tǒng)碼；若將G進(jìn)行線性初等矩陣變換，使其具有典型形式，則產(chǎn)生的碼組與不變換產(chǎn)生的碼組有同樣的糾檢能力，即系統(tǒng)碼與非系統(tǒng)碼的糾檢能力相同；6）H = PIr = QTIr G = IkQ = IkPT7）生成矩陣G的各行線性無(wú)關(guān)第19頁(yè)/共35頁(yè)對(duì)于監(jiān)督矩陣H：1）H矩陣rn 階的矩陣2）H矩陣中每行和其碼組集合中的任一碼字的內(nèi)積為0；3）任意一個(gè)( n, k )線性分組碼的H矩陣行線性無(wú)關(guān)；4）一個(gè)( n, k, d )線性分組碼，若要至多糾正t個(gè)錯(cuò)誤，則其充要條件是H矩陣中任何2t列線性無(wú)關(guān)，由于最小距離d = 2t + 1，所以也相當(dāng)于要求H矩陣

12、中任意(d 1)列線性無(wú)關(guān)654321065432106543210111010001101010010110010ccccccccccccccccccccc 第20頁(yè)/共35頁(yè)生成矩陣G與監(jiān)督矩陣H的關(guān)系：因?yàn)樾畔⑽徊粫?huì)全零，因此：再由： H = PIr，G = IkQ，代入上式，得：上式中矩陣的下標(biāo)為其階數(shù)TTTk rkk rrPG HIQPQOITTTTH COC HOU G HOCU GTG HO第21頁(yè)/共35頁(yè)例：設(shè)（7, 4）線性碼的生成矩陣G為：當(dāng)信息位為0001時(shí)，試求其后的監(jiān)督位。1101000101010001100101110001第22頁(yè)/共35頁(yè)例：試求上例的監(jiān)督矩

13、陣H解：根據(jù)生成矩陣和監(jiān)督矩陣的關(guān)系：G = IkQ，H=PIr可得監(jiān)督矩陣H為：100110101010110010111第23頁(yè)/共35頁(yè)對(duì)偶碼定義：對(duì)于線性分組碼： 1）將( n, k ) 碼的監(jiān)督矩陣H作為( n, n k )碼的生成矩陣G； 2）將( n, k ) 碼的生成矩陣G作為( n, n k )碼的監(jiān)督矩陣H這樣的( n, k ) 碼與( n, n k )碼互為對(duì)偶碼第24頁(yè)/共35頁(yè)編碼過(guò)程觀察(7, 4)碼的監(jiān)督關(guān)系式：可設(shè)計(jì)出相應(yīng)的編碼電路：654265316430uuucuuucuuuc第25頁(yè)/共35頁(yè)譯碼糾、檢過(guò)程錯(cuò)誤矩陣/錯(cuò)誤圖樣E：設(shè)發(fā)送碼組為c，接收碼組為y

14、，則 對(duì)于二元有限域，上式中的減法等價(jià)于加法，即： 對(duì)于二元有限域的加法的具有確定兩個(gè)碼組中不同比特位的特性，例如：假設(shè)長(zhǎng)度為n的碼組A和B分別為：假設(shè)這兩個(gè)碼組的第k位不同，其他位相同，根據(jù)加法規(guī)則：因此接收端可以利用這種特性進(jìn)行糾錯(cuò)，即若能確定錯(cuò)誤圖樣就可以進(jìn)行糾錯(cuò)：120nnecyeee120nnecyeee10()nnka aaa10()nnkb bbb1010()(0010)() nnknnka aaab bbb cey第26頁(yè)/共35頁(yè)接收端利用監(jiān)督矩陣計(jì)算校正子S，即可見校正子S只與E有關(guān)，即錯(cuò)誤圖樣與校正子之間有確定的關(guān)系而校正子S可以用接收碼組y與監(jiān)督矩陣HT相乘獲得，則錯(cuò)誤

15、圖樣也就得到確認(rèn)，即：上式即為一個(gè)線性方程組，但它的解不唯一，即求得的錯(cuò)誤圖樣不唯一。假設(shè)其中一個(gè)解為e0，即e0 HT = S，則對(duì)于碼組集合中的任一許用碼組c，下式一定成立：因此這個(gè)線性方程組一共有2k個(gè)解，即2k個(gè)錯(cuò)誤圖樣TTTTTSyHec HeHcHeHTSeH000()TTTTec He HcHe HS第27頁(yè)/共35頁(yè)因此利用等式 及2k個(gè)錯(cuò)誤圖樣可以糾正出2k個(gè)碼組，即：稍作變換，每個(gè)等式進(jìn)行移項(xiàng)：再由兩個(gè)碼組之和的碼重等于兩個(gè)碼組的碼距，可得：最佳譯碼應(yīng)選擇那些離y最近的 ，再由上式可知： 1）所有錯(cuò)誤圖樣中選擇碼重最小圖樣； 2）該圖樣所對(duì)應(yīng)的 作為糾正后的碼組 cey00

16、 cey11 cey2121kkcey00ecy11ecy2121kkecy00( ,)( )d y cW e11( , )( )d y cW e2121( ,)()kkd y cW e c c第28頁(yè)/共35頁(yè)例如，某( 7, 3 )線性分組碼的監(jiān)督矩陣為：1）若收到的碼組y = ( 1001001 )，則利用式S = yHT計(jì)算出校正子，其結(jié)果為S = ( 0111 )；2）再利用式eHT = S計(jì)算出所有可能的錯(cuò)誤圖樣，因?yàn)閗 = 3，則共有8個(gè)圖樣分別為：( 1001001 ) ( 1010100 ) ( 1101110 ) ( 1110011 ) ( 0000111 ) ( 0011

17、010 ) ( 0100000 ) ( 0111101 )3）其中圖樣( 0100000 )的碼重最小，則糾正后的碼組為：e + y = ( 0100000 ) + ( 1001001 ) = ( 1101001 )1011000111010011000100110001H 第29頁(yè)/共35頁(yè)在實(shí)際中譯碼： 1）一般事先確定好每種校正子S所對(duì)應(yīng)的所有錯(cuò)誤圖樣； 2）選擇碼重最小的錯(cuò)誤圖樣作為可糾正的錯(cuò)誤圖樣； 3）然后將校正子與最小碼重的錯(cuò)誤圖樣制成表格； 4）譯碼時(shí)，利用校正子查表，然后用等式c = e + y進(jìn)行糾正譯碼電路包括三個(gè)部分： 1）計(jì)算校正子； 2）查找確定糾正圖樣； 3）糾正

18、接收碼組中的錯(cuò)誤譯碼糾、檢過(guò)程第30頁(yè)/共35頁(yè)某（7，4）碼的監(jiān)督矩陣以及校正子錯(cuò)誤圖樣表：查表方法如下：第31頁(yè)/共35頁(yè)觀察錯(cuò)誤圖樣表發(fā)現(xiàn)校正子與錯(cuò)誤圖樣一一對(duì)應(yīng)利用二元有限域的乘法規(guī)則，對(duì)于等式：S2 S1 S0 = 1當(dāng)且僅當(dāng)S2、S1、S0全為1時(shí)成立，因此： 1）對(duì)每一校正子設(shè)計(jì)一個(gè)這樣的乘式，保證其乘積為1； 2）對(duì)于右表共設(shè)計(jì)7個(gè)乘式，對(duì)應(yīng)于7種可能出現(xiàn)的錯(cuò)誤圖樣； 3）當(dāng)三位校正子確定后，代入到7個(gè)乘式中計(jì)算，哪個(gè)乘式為1，就表明是哪一個(gè)圖樣2101SSS2101SSS21021021021021011111SSSSSSSSSSSSSSS第32頁(yè)/共35頁(yè)653226541154300uuucSuuucSuuucS c e y 210