線(xiàn)性分組碼的例子

線(xiàn)性分組碼的例子第一頁(yè)，共十八頁(yè)，編輯于2023年，星期三內(nèi)容提要漢明碼RM碼格雷碼交織碼第二頁(yè)，共十八頁(yè)，編輯于2023年，星期三漢明碼對(duì)任意整數(shù)m>2，存在滿(mǎn)足如下條件的漢明碼碼長(zhǎng)n=2m-1信息符號(hào)數(shù)k=2m-m-1校驗(yàn)符號(hào)數(shù)n-k=m糾錯(cuò)能力t=1（dmin=3）該碼的奇偶校驗(yàn)陣H由所有非零的m維列向量構(gòu)成，前m列可寫(xiě)成單位陣。H的任何兩列都不同，且非零，故任意兩列相加不為0，故最小距離至少為3；而任意兩列之和必定為H的某個(gè)列向量，因?yàn)镠包括所有非零m維列向量，故有三個(gè)列向量之和為0，所以最小距離為3第三頁(yè)，共十八頁(yè)，編輯于2023年，星期三漢明碼的標(biāo)準(zhǔn)陣可將所有重量為t=1的n=2m-1個(gè)向量作為陪集首，共2m-1個(gè)，又因?yàn)閚-k=m，即該碼有2m個(gè)陪集，因此0向量和所有重量為1的m維向量首構(gòu)成了標(biāo)準(zhǔn)陣的所有陪集首故漢明碼只能糾正t=1個(gè)錯(cuò)誤，可用查表譯碼完備碼：若標(biāo)準(zhǔn)陣的陪集首全都是重量小于等于t的向量（錯(cuò)誤模式），即可糾正錯(cuò)誤模式的重量都小于等于t。漢明碼和(23,12)格雷碼是完備碼，完備碼很少第四頁(yè)，共十八頁(yè)，編輯于2023年，星期三漢明碼的改造刪除H的若干列，如重量為偶數(shù)的列，得到新的H，其最小距離為4，稱(chēng)為“縮短的漢明碼”縮短漢明碼保證校驗(yàn)位數(shù)目不變，減少了信息位的數(shù)目，降低了碼率糾錯(cuò)能力沒(méi)變，陪集首依然沒(méi)變，全是重量為1的錯(cuò)誤模式，檢錯(cuò)能力？譯碼：看校正子的情況：0，重量為奇數(shù)（可糾正1個(gè)錯(cuò)，查表），重量為偶數(shù)（不可糾正錯(cuò)誤）漏檢率很低，符合漏檢率的理論上界，故是好的差錯(cuò)檢測(cè)碼第五頁(yè)，共十八頁(yè)，編輯于2023年，星期三檢測(cè)兩個(gè)錯(cuò)，糾正一個(gè)錯(cuò)的碼SEC-DED首先構(gòu)造碼長(zhǎng)n=2m-1，最小距離為3的漢明碼從此漢明碼的H陣中刪除一些列，得到H0滿(mǎn)足：每列有奇數(shù)個(gè)11的個(gè)數(shù)盡可能小每一行中1的個(gè)數(shù)都應(yīng)該相等或極可能接近均值第一個(gè)條件保證最小距離至少為4，二、三個(gè)條件為了實(shí)現(xiàn)簡(jiǎn)單Hsiao提出了一種構(gòu)造H0的算法并找到了一些最優(yōu)的SEC-DED碼第六頁(yè)，共十八頁(yè)，編輯于2023年，星期三Reed-Muller，RM碼r階RM(r,m)碼，糾正多個(gè)錯(cuò)誤，Muller提出，Reed譯碼碼長(zhǎng)：n=2m維數(shù)(信息序列的長(zhǎng)度)：最小距離：dmin=2m-r若令m=5，r=2，那么n=32，k(2,5)=16,dmin=8，即存在一個(gè)(32,16)RM碼第七頁(yè)，共十八頁(yè)，編輯于2023年，星期三RM碼的構(gòu)造設(shè)v0是全1向量，

1<=i<=m，由此定義了v0,v1,…,vm定義向量運(yùn)算“·”，a·b=(a1·b1,a2·b2,…,an·bn)，簡(jiǎn)記為ab集合Grm(r,m)={v0,v1,…,vm,v1v2,v1v3,…,vm-1vm,…,vm-r+1…vm}共有k(r,m)個(gè)元素，是(2m,k)RM碼的生成向量，即可張成整個(gè)碼空間的基。將每個(gè)元素看成矩陣的一行，就得到生成矩陣。集合Grm(r-1,m)是Grm(r,m)的真子集，是r-1階RM碼的生成矩陣。第八頁(yè)，共十八頁(yè)，編輯于2023年，星期三RM碼Grm(r,m)中所有向量都是偶數(shù)重量m-r-1階RM碼(m-r-1,m)的對(duì)偶碼是r階RM碼(r,m)零階RM碼RM(0,m)是重復(fù)碼而(m-1)階RM碼是單奇偶校驗(yàn)碼，k=2m-1第九頁(yè)，共十八頁(yè)，編輯于2023年，星期三RM碼的譯碼，例子說(shuō)明此碼是最小距離為4的(16,11)線(xiàn)性碼，假設(shè)信息序列：

觀察上述11個(gè)生成向量，注意到除了v1v2，其他生成向量每連續(xù)4個(gè)分量一組求和都是0，可推出：4個(gè)彼此獨(dú)立的方程求a12的值，可用于校驗(yàn)，若接受序列中只有一個(gè)錯(cuò)誤，則4個(gè)值中只錯(cuò)一個(gè)，采用大多數(shù)原則可糾錯(cuò)，這就是大數(shù)邏輯判決準(zhǔn)則譯碼第十頁(yè)，共十八頁(yè)，編輯于2023年，星期三RM碼的譯碼aij被正確譯碼后，考慮傳輸沒(méi)出錯(cuò)，則有利用基向量的特點(diǎn)，發(fā)現(xiàn)兩個(gè)連續(xù)分量的和的關(guān)系，構(gòu)建ai的獨(dú)立判定方程，再用大數(shù)邏輯判決譯碼類(lèi)似上面步驟，最后譯碼a0，共三步（r+1步）第十一頁(yè)，共十八頁(yè)，編輯于2023年，星期三(24,12)格雷碼漢明碼外唯一一個(gè)非平凡二進(jìn)制完備碼(23,12)格雷碼，最小距離7(23,12)格雷碼通過(guò)增加一個(gè)總的奇偶校驗(yàn)位，構(gòu)成(24,12)碼，最小距離為8，但非完備碼設(shè)其生成矩陣G=[PI12],P

如右，且滿(mǎn)足：

P沿對(duì)角線(xiàn)對(duì)稱(chēng)，且PP=IH=[I12,P]，自偶碼第十二頁(yè)，共十八頁(yè)，編輯于2023年，星期三格雷碼的譯碼設(shè)錯(cuò)誤模式為e=(x,y)，校正子s=eHT=(x,y)HT=(x,y)[IP]T=x+yPT=x+yP，可得到y(tǒng)=(x+s)P對(duì)任何可糾正錯(cuò)誤模式e，滿(mǎn)足w(e)<4，有四種可能:(1)w(y)=0,w(x)<=3,(2)w(y)=1,w(x)<=2,(3)w(y)=2,w(x)<=1,(4)w(y)=3,w(x)<=0，令ej分別表示這四種可能的錯(cuò)誤模式，ej=(x,y)，其中w(y)=j，0<=j<4,令ui表示僅第i個(gè)分量為1的12維向量，pi=uiP表示P的第i行若e=e0，則有s=x，w(s)=w(x)<=3,e=(x,y)=(s,0)若e=e1,令y=ui,則有s=x+pi,即x=s+pi,e=(x,y)=(s+pi,ui)若e=e2或e3,w(x)=0,則有e=(x,y)=(0,sP)若e=e2且w(x)=1,令x=ui,則y=(x+s)P=(ui+s)P=pi+sP,故e=(x,y)=(ui,pi+sP)第十三頁(yè)，共十八頁(yè)，編輯于2023年，星期三(24,12)格雷碼的譯碼計(jì)算接受序列r的校正子s若w(s)<=3，則令e=(s,0)，跳到步驟8若某個(gè)pi，有w(s+pi)<=2，令e=(s+pi,ui)，跳到步驟8計(jì)算sP若w(sP)=2or3,則令e=(0,sP)并轉(zhuǎn)步驟8若某個(gè)pi,w(sP+pi)=2，則令e=(ui,sP+pi),跳到步驟8若校正子s與可糾錯(cuò)模式e不相同，則停止譯碼或要求重傳，譯碼錯(cuò)誤令譯出的碼字v’=r+e充分利用了碼和錯(cuò)誤模式的結(jié)構(gòu)特點(diǎn)設(shè)計(jì)算法第十四頁(yè)，共十八頁(yè)，編輯于2023年，星期三乘積碼乘積碼是短的分量碼構(gòu)造高效長(zhǎng)碼的一種技術(shù)設(shè)有兩個(gè)線(xiàn)性碼C1(n1,k1)和C2(n2,k2)，可構(gòu)造一個(gè)(n1n2,k1k2)的線(xiàn)性碼，其碼字是一個(gè)n1n2的矩陣，此矩陣的每一行是C1的碼字，每一列是C2的碼字，這是一個(gè)二維碼，是C1和C2的直積如右圖所示乘積碼的碼矩陣第十五頁(yè)，共十八頁(yè)，編輯于2023年，星期三乘積碼構(gòu)造過(guò)程：對(duì)待編碼的k1k2信息序列置于右邊矩陣的右上角信息位的每一行采用C1中的碼字進(jìn)行編碼,得到行校驗(yàn)位，即得到k2xn1矩陣對(duì)每一列采用C2中的碼字進(jìn)行編碼，得到列校驗(yàn)位和校驗(yàn)位的校驗(yàn)位乘積碼的最小距離dmin=d1d2乘積碼的碼率較低第十六頁(yè)，共十八頁(yè)，編輯于2023年，星期三交織碼給定一個(gè)線(xiàn)性碼C

(n,k)，可以構(gòu)造一個(gè)()線(xiàn)性碼，交織碼,interleavedcode交織方法：取C的個(gè)碼字排成行的矩陣形式，然后按照逐列的方式傳輸該矩陣，稱(chēng)為交織深度或交織度，交織碼和碼C具有相同的dmin交織碼簡(jiǎn)單說(shuō)就是按列的方式傳輸碼字當(dāng)且僅當(dāng)