第7章數(shù)據(jù)傳輸

第7章數(shù)據(jù)傳輸7.1糾錯與線性分組碼的編碼原則1、糾錯——信道編碼通過在發(fā)送端增加冗余使消息出現(xiàn)傳輸錯誤時(shí)由接收端進(jìn)行糾正——糾錯2、n重復(fù)碼求信源等概率時(shí)的平均譯碼錯誤概率最大似然準(zhǔn)則譯碼收到y(tǒng)1時(shí)收到y(tǒng)2時(shí)平均譯碼錯誤概率通信系統(tǒng)中一般要求平均譯碼錯誤概率的數(shù)量級10-6-10-9三重復(fù)碼——消息重復(fù)三次——x1=0→c1=000，x2=1→c2=111——三次擴(kuò)展信源的子信源，三次擴(kuò)展信宿三次擴(kuò)展信道的子信道最大似然準(zhǔn)則譯碼收到y(tǒng)1=000時(shí)收到y(tǒng)2=001時(shí)收到y(tǒng)3=010時(shí)收到y(tǒng)4=011時(shí)收到y(tǒng)5=100時(shí)收到y(tǒng)6=101時(shí)收到y(tǒng)7=110時(shí)收到y(tǒng)8=111時(shí)三重復(fù)碼——通過在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯誤時(shí)由接收端進(jìn)行糾正——糾錯平均譯碼錯誤概率重復(fù)n次——n重復(fù)碼n重復(fù)碼的碼長為原來的n倍——編碼效率為1/n需要找的“好碼”足夠小的平均譯碼錯誤概率Pe較高的編碼效率3、線性分組碼及其編碼原則①線性分組碼具有恒定碼字長度和消息長度，消息相加后的編碼等同于各自編碼相加的糾錯碼，用(n,k)表示其中n為碼字長度，k為消息長度，n-k為校驗(yàn)長度例2：(4,3)偶校驗(yàn)碼②碼距和最小碼距2k個(gè)碼字構(gòu)成的碼表中，任意兩個(gè)碼字之間的碼距(漢明距離)——任意兩個(gè)碼字對應(yīng)位上不同碼元的個(gè)數(shù)，用dij表示例3：(4,3)偶校驗(yàn)碼中碼字c2和c3之間的碼距d232k個(gè)碼字構(gòu)成的碼表中，碼字之間的最小碼距——所有碼字之間碼距的最小值，用dmin表示③線性分組碼的編碼原則例4：(3,1)線性分組碼三次擴(kuò)展信源中8個(gè)可能的碼字8個(gè)可能的碼字構(gòu)成的碼表中，任意兩個(gè)碼字之間的碼距如果選取其中c1=000，c8=111為許用碼，其余為禁用碼——三重復(fù)碼——2個(gè)碼字構(gòu)成的碼表中及信源等概率條件下的平均譯碼錯誤概率在信道如果選取其中c2=001，c7=110為許用碼，其余為禁用碼——2個(gè)碼字構(gòu)成的碼表中及信源等概率條件下在信道x=0→c2=001，x=1→c7=110——三次擴(kuò)展信源的子信源，三次擴(kuò)展信宿三次擴(kuò)展信道的子信道最大似然準(zhǔn)則譯碼收到y(tǒng)1=000時(shí)收到y(tǒng)2=001時(shí)收到y(tǒng)3=010時(shí)收到y(tǒng)4=011時(shí)收到y(tǒng)5=100時(shí)收到y(tǒng)6=101時(shí)收到y(tǒng)7=110時(shí)收到y(tǒng)8=111時(shí)通過在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯誤時(shí)由接收端進(jìn)行糾正——糾錯平均譯碼錯誤概率如果選取其中c1=000，c5=100為許用碼，其余為禁用碼——2個(gè)碼字構(gòu)成的碼表中及信源等概率條件下在信道x=0→c1=000，x=1→c5=100——三次擴(kuò)展信源的子信源，三次擴(kuò)展信宿三次擴(kuò)展信道的子信道最大似然準(zhǔn)則譯碼收到y(tǒng)1=000時(shí)收到y(tǒng)2=001時(shí)收到y(tǒng)3=010時(shí)收到y(tǒng)4=011時(shí)收到y(tǒng)5=100時(shí)收到y(tǒng)6=101時(shí)收到y(tǒng)7=110時(shí)收到y(tǒng)8=111時(shí)通過在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯誤時(shí)不能完全由接收端進(jìn)行糾正平均譯碼錯誤概率線性分組碼的編碼——選取許用碼線性分組碼的編碼原則——保證最小碼距足夠大④線性分組碼檢錯糾錯的充要條件線性分組碼(n,k)檢e位錯并同時(shí)糾t位錯的充要條件——檢一位錯并同時(shí)糾一位錯的充要條件——7.2漢明碼漢明碼——最小碼距dmin=3的線性分組碼設(shè)(n,k)漢明碼的碼字為校驗(yàn)位，校驗(yàn)長度為n-k其中為消息位，消息長度為k1、漢明碼的編碼編碼步驟①構(gòu)造滿秩的(n-k)×n校驗(yàn)矩陣Hri——第i個(gè)接收碼字，1×n向量si——第i個(gè)接收碼字的誤碼標(biāo)志，1×(n-k)向量ci——第i個(gè)發(fā)送碼字，1×n向量②設(shè)滿秩的k×n生成矩陣Gxi——第i個(gè)發(fā)送消息，1×k向量由生成矩陣G與校驗(yàn)矩陣H之間GHT=0求出G即可編碼例1：(3,1)漢明碼的編碼①構(gòu)造滿秩的2×3校驗(yàn)矩陣H所有2維非零列向量構(gòu)成校驗(yàn)矩陣H，如②設(shè)滿秩的1×3生成矩陣G最小碼距(3,1)漢明碼——三重復(fù)碼能檢一位錯并同時(shí)糾一位錯(3,1)漢明碼的碼長為原來的3倍→編碼效率為1/3例2：(7,4)漢明碼的編碼①構(gòu)造滿秩的3×7校驗(yàn)矩陣H所有3維非零列向量構(gòu)成校驗(yàn)矩陣H，如②設(shè)滿秩的4×7生成矩陣G任意兩個(gè)碼字之間的碼距…最小碼距(7,4)漢明碼能檢一位錯并同時(shí)糾一位錯(7,4)漢明碼的碼長為原來的7/4倍→編碼效率為4/72、漢明碼的譯碼譯碼步驟①檢錯——誤碼標(biāo)志si當(dāng)出現(xiàn)一位傳輸錯誤…②糾錯——(n-k)→n變換+模二加通過(n-k)→n變換將誤碼標(biāo)志si變換為形如10…00，01…00，…，00…01，00…00的錯誤