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

第7章數(shù)據(jù)傳輸7.1糾錯(cuò)與線性分組碼的編碼原則1、糾錯(cuò)——信道編碼通過(guò)在發(fā)送端增加冗余使消息出現(xiàn)傳輸錯(cuò)誤時(shí)由接收端進(jìn)行糾正——糾錯(cuò)2、n重復(fù)碼求信源等概率時(shí)的平均譯碼錯(cuò)誤概率最大似然準(zhǔn)則譯碼收到y(tǒng)1時(shí)收到y(tǒng)2時(shí)平均譯碼錯(cuò)誤概率通信系統(tǒng)中一般要求平均譯碼錯(cuò)誤概率的數(shù)量級(jí)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ù)碼——通過(guò)在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯(cuò)誤時(shí)由接收端進(jìn)行糾正——糾錯(cuò)平均譯碼錯(cuò)誤概率重復(fù)n次——n重復(fù)碼n重復(fù)碼的碼長(zhǎng)為原來(lái)的n倍——編碼效率為1/n需要找的“好碼”足夠小的平均譯碼錯(cuò)誤概率Pe較高的編碼效率3、線性分組碼及其編碼原則①線性分組碼具有恒定碼字長(zhǎng)度和消息長(zhǎng)度，消息相加后的編碼等同于各自編碼相加的糾錯(cuò)碼，用(n,k)表示其中n為碼字長(zhǎng)度，k為消息長(zhǎng)度，n-k為校驗(yàn)長(zhǎng)度例2：(4,3)偶校驗(yàn)碼②碼距和最小碼距2k個(gè)碼字構(gòu)成的碼表中，任意兩個(gè)碼字之間的碼距(漢明距離)——任意兩個(gè)碼字對(duì)應(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)成的碼表中及信源等概率條件下的平均譯碼錯(cuò)誤概率在信道如果選取其中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í)通過(guò)在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯(cuò)誤時(shí)由接收端進(jìn)行糾正——糾錯(cuò)平均譯碼錯(cuò)誤概率如果選取其中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í)通過(guò)在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯(cuò)誤時(shí)不能完全由接收端進(jìn)行糾正平均譯碼錯(cuò)誤概率線性分組碼的編碼——選取許用碼線性分組碼的編碼原則——保證最小碼距足夠大④線性分組碼檢錯(cuò)糾錯(cuò)的充要條件線性分組碼(n,k)檢e位錯(cuò)并同時(shí)糾t位錯(cuò)的充要條件——檢一位錯(cuò)并同時(shí)糾一位錯(cuò)的充要條件——7.2漢明碼漢明碼——最小碼距dmin=3的線性分組碼設(shè)(n,k)漢明碼的碼字為校驗(yàn)位，校驗(yàn)長(zhǎng)度為n-k其中為消息位，消息長(zhǎng)度為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ù)碼能檢一位錯(cuò)并同時(shí)糾一位錯(cuò)(3,1)漢明碼的碼長(zhǎng)為原來(lái)的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)漢明碼能檢一位錯(cuò)并同時(shí)糾一位錯(cuò)(7,4)漢明碼的碼長(zhǎng)為原來(lái)的7/4倍→編碼效率為4/72、漢明碼的譯碼譯碼步驟①檢錯(cuò)——誤碼標(biāo)志si當(dāng)出現(xiàn)一位傳輸錯(cuò)誤…②糾錯(cuò)——(n-k)→n變換+模二加通過(guò)(n-k)→n變換將誤碼標(biāo)志si變換為形如10…00，01…00，…，00…01，00…00的錯(cuò)誤