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

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

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

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

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

5、加3位二進制位作為監(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，即接收端譯碼校驗，得到監(jiān)督方程：65310uuuc65420uuuc64300uuuc654226531164300uuucSuuucSuuucS6542uuuc6531uuuc6430uuuc第11頁/共35頁對于上式，若無錯誤發(fā)生，三個校驗子均為0；假設傳輸過程中有且僅有一位發(fā)生錯誤：1）若c0發(fā)生錯誤，觀察監(jiān)督方程，則三個校驗子S2 S1 S0的組合為001；2）若c1發(fā)生錯誤， S2 S1

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

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

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

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

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

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

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

13、陣H解：根據生成矩陣和監(jiān)督矩陣的關系：G = IkQ，H=PIr可得監(jiān)督矩陣H為：100110101010110010111第23頁/共35頁對偶碼定義：對于線性分組碼： 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 )碼互為對偶碼第24頁/共35頁編碼過程觀察(7, 4)碼的監(jiān)督關系式：可設計出相應的編碼電路：654265316430uuucuuucuuuc第25頁/共35頁譯碼糾、檢過程錯誤矩陣/錯誤圖樣E：設發(fā)送碼組為c，接收碼組為y

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

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

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

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

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