【正文】 式； （ 3） 該循環(huán)碼中其它碼多項(xiàng)式都是 g(x)的倍式。 g(x)， xg(x) … ， xk1g(x) knr ??1?nx 循環(huán)碼的編碼原理 第 5章 差錯(cuò)控制編碼 105 g(x)， … … ， xk1g(x)都是許用碼組，連同 g(x)共 k個(gè)許用碼組，構(gòu)成碼的 生成矩陣 G(x) 注：該生成矩陣并不是典型形式的，但可通過(guò)線性變換變換成典型的生成矩陣。 ???????????????????)()()()()(21xgxxgxgxxgxXGkk? 循環(huán)碼的編碼原理 第 5章 差錯(cuò)控制編碼 106 一旦生成多項(xiàng)式 g(x)確定以后，該循環(huán)碼的生成矩陣 G(x)就可以確定，進(jìn)而該循環(huán)碼的所有碼字就可以確定。生成矩陣 G(x)的每一行都是一個(gè)碼組。 循環(huán)碼的編碼原理 第 5章 差錯(cuò)控制編碼 107 [例 54]試求 表 510 （ 7， 3）循環(huán)碼的生成多項(xiàng)式和生成矩陣。 解：對(duì)（ 7,3）循環(huán)碼， n=7， k=3, r=4 由上例已知 生成多項(xiàng)式 為： g(x)= x4+x2+x+1 循環(huán)碼的編碼原理 將第 1行與第 3行 模 2加 作為第 1行，則有 ???????????111010001110101101001G為典型生成矩陣 第 5章 差錯(cuò)控制編碼 108 [接上例 ]設(shè)信息碼為 101，求整個(gè)碼組。 解： 整個(gè)碼組 A=[信息碼 ]*G（典型的） 故 A=[1 0 1] =[1 0 1 1 1 0 0] 循環(huán)碼的編碼原理 ??????????111010001110101101001第 5章 差錯(cuò)控制編碼 109 [例 55] 已知循環(huán)碼的生成多項(xiàng)式為 ， 當(dāng)信息位為 1000時(shí)，寫(xiě)出它的監(jiān)督位和整個(gè)碼組。 解：由生成多項(xiàng)式可知 nk=3，而 k=4，所以 n＝ 7 1)( 3 ??? xxxg???????????????????????????????????????????????????????????1)()()()()()()()()(3242353462321xxxxxxxxxxxxgxxgxgxxgxxgxxgxgxxgxxGkk?第 5章 差錯(cuò)控制編碼 110 ???????0001001001011011G??????011110100000 第 1行 +第 3行 +第 4行 第 1行 ???????0001001001011000G??????011110100101 第 2行 +第 4行 第 2行 ???????0001001001001000G??????011110111101 非典型 典型 當(dāng)信息位為 1000時(shí)，整個(gè)碼組為 第 5章 差錯(cuò)控制編碼 111 ???? ]1 0 0 0[][ 3456 GaaaaA??????0001001001001000??????011110111101]1 00 0 10 1[?監(jiān)督位為 101 第 5章 差錯(cuò)控制編碼 112 1111111111010011010011100010101100010100111001110100010101110100110001010110001001110011101001011000010110000000已知（ 7， 4）循環(huán)碼的全部碼組為： 試寫(xiě)出該循環(huán)碼的生成多項(xiàng)式 g(x)和生成矩陣 G， 并將 G化成典型矩陣。 循環(huán)碼的編碼原理 第 5章 差錯(cuò)控制編碼 113 解： n=7， k=4， nk=3 上述碼組中的 (nk)=3次碼多項(xiàng)式為第 2組，它所對(duì)應(yīng)的碼多項(xiàng)式 g(x)即為生成多項(xiàng)式：g(x)=x3+x+1。 生成矩陣為： 3 6 4 32 5 3 21 4 23x g ( x ) x x xx g ( x ) x x xG ( x )x g ( x ) x x xg ( x ) x x 11 0 1 1 0 0 0 1 0 0 0 1 0 10 1 0 1 1 0 0 0 1 0 0 1 1 10 0 1 0 1 1 0 0 0 1 0 1 1 00 0 0 1 0 1 1 0 0 0 1 0 1 1? ? ? ???? ? ? ???? ? ? ???? ? ? ???? ? ? ???? ? ? ?? ? ? ?? ? ? ?? ? ? ?? ? ? ???? ? ? ?? ? ? ?? ? ? ?第 5章 差錯(cuò)控制編碼 114 循環(huán)碼的編碼、解碼方法 編碼方法 （ 1）原理 用碼多項(xiàng)式來(lái)表示為： A =[ mk1 mk2 … m0 ar1 … a1 a0] 011102211 )()( axaxaxmxmxmxA rrknkkkk ??????? ??????? ??)()( xrxxM kn ?? ?式中 M(x)是信息碼組碼多項(xiàng)式，所以只需要確定 r(x) 已知循環(huán)碼的所有碼字都能夠被 g(x)整除， r(x)可由下式確定： )x(g)()( 模knxxMxr ??第 5章 差錯(cuò)控制編碼 115 設(shè)信息位對(duì)應(yīng)的多項(xiàng)式為 m(x) ? 用 xnk乘 m(x)，相當(dāng)于把信息碼后附加上（ nk）個(gè)“ 0” （詳細(xì)解釋） ? 用 g(x)除 xnk m(x)，得到余式為 r(x) ? 編出碼組為： T(x)= xnk m(x)+ r(x) ? ?? ? ? ?? ?? ?xgxrxQxgxmx kn ????(2)編碼步驟 循環(huán)碼的編碼、解碼方法 第 5章 差錯(cuò)控制編碼 116 例如 :信息碼為 110，它相當(dāng)于 m(x)＝ x2+x。當(dāng) nk＝ 73＝ 4時(shí)， xnk m （ x）＝ x4 (x2+x)= x6+x5 ，相當(dāng)于1100000。 而希望的到得系統(tǒng)循環(huán)碼多項(xiàng)式應(yīng)當(dāng)是 T(x) = xnk m(x) + r(x)。 循環(huán)碼的編碼、解碼方法 第 5章 差錯(cuò)控制編碼 117 11)1(1)()(24222456??????????????xxxxxxxxxxxxgxmx kn即余式 r(x)=x2+1 于是，對(duì)應(yīng)碼組 T(x)= xnk m(x)+r(x） = x6+x5+ x2+1 編碼為 1100101 [例題 ] 設(shè)（ 7， 3）循環(huán)碼的生成多項(xiàng)式為g(x)=x4+x2+x+1， 待編碼信息位為 110，求對(duì)應(yīng)循環(huán)碼碼組。 解： m(x)=x2+x， xnk m(x)=x4(x2+x)=x6+x5 循環(huán)碼的編碼、解碼方法 于是，以多項(xiàng)式形式表示的系統(tǒng)循環(huán)碼的生成矩陣為： ????????????????????????)()()()(2211xrxxrxxrxXGknknnnnn?其中 ,rni(x)是 g(x)除 xni (i=1,2,… ， k)所得的余式。 第 5章 差錯(cuò)控制編碼 119 譯碼方法 （ 1）目的 — 檢錯(cuò)、糾錯(cuò) 循環(huán)碼的編碼、解碼方法 第 5章 差錯(cuò)控制編碼 120 判斷接收到的碼組多項(xiàng)式 B(x)是否能被生成多項(xiàng)式g(x)整除作為依據(jù) ? 當(dāng)傳輸中未發(fā)生錯(cuò)誤時(shí)， B(x)=T(x)，則接收的碼組 B(x)必能被 g(x)整除； ? 若傳輸中發(fā)生了錯(cuò)誤， B(x)≠T(x) ， B(x)不能被 g(x)整除 B(x)≠T(x) ， B(x)能被 g(x)整除 不可檢錯(cuò)誤 （ 2）采用手段： 循環(huán)碼的編碼、解碼方法 第 5章 差錯(cuò)控制編碼 121 ? 由接收到的碼多項(xiàng)式 B(x)計(jì)算校正子（伴隨式）多項(xiàng)式 S(x)；即求解 B(x)整除 g(x)的余式 r(x) ? 由校正子 S(x)確定錯(cuò)誤圖樣 E(x)； ? 將錯(cuò)誤圖樣 E(x)與 B(x)相加，糾正錯(cuò)誤。 （ 3）譯碼步驟 循環(huán)碼的編碼、解碼方法 第 5章 差錯(cuò)控制編碼 122 ? 能檢出全部的單個(gè)錯(cuò)誤 ： 對(duì)應(yīng)一位錯(cuò)碼的錯(cuò)碼多項(xiàng)式 E(x)=xi， 而多于一項(xiàng)的生成多項(xiàng)式 g(x)=……+1 ， 顯然 xi除以 g(x)的余數(shù)不會(huì)等于 0，也即能檢測(cè)出全部單個(gè)錯(cuò)碼。 ? 能檢出全部離散的二位錯(cuò)： 對(duì)應(yīng)的錯(cuò)碼多項(xiàng)式 E(x)=xi+xj=xi(1+xji)，只要選取的 g(x)不能除盡 (xji+1)， 且 (nk)(ji) ? 能檢出全部的奇數(shù)個(gè)錯(cuò)碼： 含有奇數(shù)項(xiàng)錯(cuò)碼的多項(xiàng)式必不含 (x+1)因子， 只要選取的 g(x)含有 (x+1)因子 循環(huán)碼的檢錯(cuò)能力 第 5章 差錯(cuò)控制編碼 123 ? 能檢測(cè)所有長(zhǎng)度不超過(guò) (nk)的突發(fā)錯(cuò)誤： 突發(fā)長(zhǎng)度不大于 b的突發(fā)錯(cuò)誤對(duì)應(yīng)的錯(cuò)碼多項(xiàng)式 為 : E(x)=xi(eb1xb1+ eb2xb2+……+e 1x+1)= xi E1(x) 由于 g(x)除不盡 xi； g(x)為 nk次多項(xiàng)式，只要 E1(x)的次數(shù) b1不超過(guò) (nk1)次， g(x)便除不盡 E1(x)。也就是說(shuō)，能 檢測(cè)長(zhǎng)度不超過(guò) (nk)的突發(fā)錯(cuò)誤。 循環(huán)碼的檢錯(cuò)能力 第 5章 差錯(cuò)控制編碼 124 1. 信道編碼與信源編碼有什么不同 ？ 糾錯(cuò)碼能夠檢錯(cuò)或糾錯(cuò)的根本原因是什么 ？ 2. 差錯(cuò)控制的基本工作方式有哪幾種 ?各有什么特點(diǎn) ？ 3. 漢明碼有哪些特點(diǎn) ? 4. 分組碼的檢 (糾 )錯(cuò)能力與最小碼距有什么關(guān)系 ?檢 、 糾錯(cuò)能力之間有什么關(guān)系 ? 5. 什么叫做奇偶監(jiān)督碼 ?其檢錯(cuò)能力如何 ? 6. 什么是線性碼 ?它具有哪些重要性質(zhì) ? 7. 什么是循環(huán)碼 ?循環(huán)碼的生成多項(xiàng)式如何確定 ?