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

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

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

如右，且滿足：

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

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