第四章抗干擾二元編碼原理及方法3構(gòu)造糾錯(cuò)碼的基本方法

4.3構(gòu)造糾錯(cuò)碼的根本方法一、簡(jiǎn)單重復(fù)碼1、逐位重復(fù)例：01001101三重重復(fù)碼：000，111，000，000，111，111，000，111，…優(yōu)點(diǎn)：逐位重復(fù)的設(shè)備很簡(jiǎn)單2、分組重復(fù)0100，0100，0100，1101，1101，1101，…優(yōu)點(diǎn)：可抗成群連續(xù)過(guò)失簡(jiǎn)單重復(fù)碼的重復(fù)次數(shù)應(yīng)為奇數(shù)簡(jiǎn)單重復(fù)碼的優(yōu)點(diǎn)：檢、糾錯(cuò)能力較好簡(jiǎn)單重復(fù)碼的缺點(diǎn)：編碼效率低，

n重重復(fù)碼的編碼效率：二、糾正一位錯(cuò)誤的漢明碼是一種〔n，k〕分組碼k個(gè)信息碼元+r個(gè)監(jiān)督碼元=n個(gè)碼元〔一個(gè)漢明碼碼字〕r個(gè)監(jiān)督碼元應(yīng)能監(jiān)督k個(gè)信息碼元和r個(gè)自身碼元中哪個(gè)錯(cuò)，以及無(wú)錯(cuò)情況，共k+r+1=n+1種狀態(tài)〔7，4〕漢明碼x1x2x3x4x5x6x7×××××：信息碼元：監(jiān)督碼元1、監(jiān)督矩陣監(jiān)督矩陣的每一行均表示一個(gè)監(jiān)督碼元與4個(gè)信息碼元之間的關(guān)系

信息碼元，根據(jù)監(jiān)督矩陣，由上式求出監(jiān)督碼元，并將監(jiān)督碼元加在信息碼元后面，構(gòu)成漢明碼字，即完成編碼。漢明碼字是一種系統(tǒng)碼。例：〔7，4〕漢明碼的監(jiān)督矩陣[H]為：解：由監(jiān)督矩陣得監(jiān)督碼元與信息碼元的關(guān)系：根據(jù)上式，對(duì)信源序列編碼得漢明碼字：0110011，1001100，0010110，0101010，0110011，…對(duì)信源序列為0110，1001，0010，0101，0110,…進(jìn)行編碼編碼后的碼字可由以下矩陣乘法驗(yàn)證對(duì)上例編碼得到的漢明碼字：0110011，1001100，0010110，0101010，0110011,…進(jìn)行驗(yàn)證，均為[0]2、校驗(yàn)矩陣校驗(yàn)子無(wú)差錯(cuò)x1*x2*x3*x4*x5*x6*x7*s100111100s201011010s301101001校驗(yàn)表校驗(yàn)子無(wú)差錯(cuò)x1*x2*x3*x4*x5*x6*x7*s100111100s201011010s301101001例：假設(shè)接收機(jī)收到的漢明碼字為：0110111，1011100，0010110，…，求譯碼輸出解：根據(jù)校驗(yàn)子01101111011100[S]=[100]x5*錯(cuò)01100110110[S]=[110]x3*錯(cuò)100110010010010110[S]=[000]無(wú)錯(cuò)00101100010得譯碼輸出：0110，1001，0010，…3、生成矩陣漢明碼的編碼也可以由生成矩陣[G]完成，而生成矩陣[G]可由監(jiān)督矩陣[H]導(dǎo)出解：用信息碼元乘以生成矩陣[G]編碼：對(duì)信源序列編碼得：0110011，1001100，0010110，0101010，0110011，…例：〔7，4〕漢明碼的生成矩陣[H]為：對(duì)信源序列為0110，1001，0010，0101，0110,…進(jìn)行編碼k×n階生成矩陣[G]和r×n階監(jiān)督矩陣[H]可互相轉(zhuǎn)換：[H]右邊的r×r階單位陣[G]左邊的k×k階單位陣[H]左邊的r×k階子陣的轉(zhuǎn)置[G]右邊的k×r階子陣4、錯(cuò)誤概率和編碼效率漢明碼的錯(cuò)誤接收概率：〔7，4〕漢明碼的編碼效率：三、循環(huán)碼屬于〔n，k〕分組碼分線性循環(huán)碼和非線性循環(huán)碼兩類(lèi)1、循環(huán)碼的碼字和多項(xiàng)式一一對(duì)應(yīng)多項(xiàng)式運(yùn)算：加法〔模2加〕多項(xiàng)式運(yùn)算：除法〔長(zhǎng)除法〕2、生成多項(xiàng)式存在唯一的一個(gè)r次多項(xiàng)式g(x)，稱(chēng)為生成多項(xiàng)式。生成多項(xiàng)式生成矩陣監(jiān)督矩陣編碼幾種〔7，k〕循環(huán)碼(n,k)碼dming(x)h(x)(7,6)2x+1(x3+x+1)(x3+x2+1)(7,4)3x3+x+1(x3+x2+1)(x+1)(7,4)3x3+x2+1(x3+x+1)(x+1)(7,3)4(x3+x+1)(x+1)x3+x2+1(7,3)4(x3+x2+1)(x+1)x3+x+1(7,1)7(x3+x+1)(x3+x2+1)x+13、生成矩陣和監(jiān)督矩陣由多項(xiàng)式導(dǎo)出生成矩陣和監(jiān)督矩陣的方法：1〕根據(jù)生成多項(xiàng)式及碼字長(zhǎng)n決定生成矩陣[G]的行列數(shù)為k×n，監(jiān)督矩陣[H]的行列數(shù)為r×n2〕生成矩陣的行向量為g(x)系數(shù)的降冪排列，監(jiān)督矩陣的行向量為h(x)系數(shù)的升冪排列，或兩者均反之。例：〔7，4〕循環(huán)碼的生成多項(xiàng)式g(x)=x3+x+1求生成矩陣[G]和監(jiān)督矩陣[H]，并利用生成矩陣[G]求出〔7，4〕循環(huán)碼的所有碼字得生成矩陣：解：〔7，4〕循環(huán)碼，n=7，k=4，r=n–k=31011由生成多項(xiàng)式g(x)=x3+x+1得監(jiān)督矩陣：10111由檢驗(yàn)多項(xiàng)式h(x)=x4+x2+x+1根據(jù)生成矩陣編碼：[C]=[X]·[G]如信息碼0110的循環(huán)碼字：是非系統(tǒng)碼生成多項(xiàng)式為g(x)=x3+x+1的〔7,4〕循環(huán)碼碼字表序號(hào)信息碼非系統(tǒng)碼序號(hào)信息碼非系統(tǒng)碼0000000000008100010110001000100010119100110100112001000101101010101001110300110011101111011100010140100010110012110011101005010101001111311011111111601100111010141110110001070111011000115111111010010001011和0011101各7個(gè)循環(huán)碼字，加0000000和1111111，共16個(gè)碼字。最小碼距dmin=34、直接利用生成多項(xiàng)式進(jìn)行循環(huán)碼編碼1〕用xr乘以信息碼組多項(xiàng)式m(x)〔(k-1)次〕得xrm(x)〔(n-1)次〕。相當(dāng)于m(x)左移r位，從而使信息位在前，監(jiān)督位在后，形成系統(tǒng)碼2〕用生成多項(xiàng)式g(x)去除xrm(x)得余式r(x)，把余式的系數(shù)作為監(jiān)督碼元附加在信息碼組后面，即構(gòu)成編碼后的碼字碼多項(xiàng)式加上余式后，循環(huán)碼字C(x)能被g(x)整除，即為譯碼判決例：利用〔7，4〕循環(huán)碼的生成多項(xiàng)式g(x)=x3+x+1，求循環(huán)碼的所有碼字解：1〕000000000002〕0001m(x)=1xrm(x)=x300010113〕0010m(x)=xxrm(x)=x400101104〕0011m(x)=x+1xrm(x)=x4+x3001110116〕1111m(x)=x3+x2+x+1xrm(x)=x6+x5+x4+x31111111……信息碼系統(tǒng)碼非系統(tǒng)碼信息碼系統(tǒng)碼非系統(tǒng)碼000000000000000000100010001011011000000100010110001011100110011101010011001000101100010110101010100111001110001100111010011101101110110001000101010001001110101100110011000101110100010101011000100111110111010011111111011001100010111010111011101001100010011101110100110001111111111111101001生成多項(xiàng)式為g(x)=x3+x+1的〔7,4〕循環(huán)碼碼字表5、循環(huán)碼的校驗(yàn)子根據(jù)循環(huán)碼字求校驗(yàn)子/校驗(yàn)表例：生成多項(xiàng)式為g(x)=x3+x+1的〔7，4〕循環(huán)碼000100010111〕將該循環(huán)碼字0001011錯(cuò)成0001010，那么2〕將該循環(huán)碼字0001011錯(cuò)成0001001，那么3〕將該循環(huán)碼字0001011錯(cuò)成0001111，那么4〕將該循環(huán)碼字0001011錯(cuò)成0000011，那么校驗(yàn)子無(wú)差錯(cuò)C0*C1*C2*C3*C4*C5*C6*s200010111s100101110s001001011生成多項(xiàng)式為g(x)=x3+x+1的〔7,4〕循環(huán)碼校驗(yàn)表校驗(yàn)子無(wú)差錯(cuò)C0*C1*C2*C3*C4*C5*C6*s200010111s100101110s001001011根據(jù)校驗(yàn)表譯碼例：生成多項(xiàng)式為g(x)=x3+x+1的〔7，4〕循環(huán)碼假設(shè)接收到循環(huán)碼字1110011故糾錯(cuò)得1010011假設(shè)該碼字是系統(tǒng)碼，那么譯碼為1010〔7，4〕循環(huán)碼的生成多項(xiàng)式為g(x)=x3+x2+1得生成矩陣：n=7，k=4，r=n–k=31101由生成多項(xiàng)式g(x)=x3+x2+1得監(jiān)督矩陣：11101由檢驗(yàn)多項(xiàng)式h(x)=x4+x3+x2+1信息碼系統(tǒng)碼非系統(tǒng)碼信息碼系統(tǒng)碼非系統(tǒng)碼00000000000000000010001000110110100000010001101000110110011001011110010100100010111001101010101010001111001000110011010001011110111011100111111101000100011011010011001100101101110001010101110011100111011101000101000101100110