信息论与编码-第7章线性分组码

1第7章线性分组码王永容机械与电气工程学院[e-mail]信息论与编码InformationandCodingTheory2线性分组码线性分组码概念线性分组码的生成矩阵线性分组码的校验矩阵线性分组码的最小汉明重量线性分组码的译码完备码汉明码3线性分组码概念(n,k)线性分组码=“(n,k)分组”+“线性”2元(n,k)分组码f:S=(F2)kC(F2)nm=(m2,…,mk)c=(c1c2,…,cn)C是(F2)n的一个k维线性子空间！S=F2kCF2nf4线性分组码概念定义7-1一个(n,k)分组码C被称为线性分组码，如果它满足全零（0,0,…,0)C任意两个码字的和也是码字.即,c=(c0,c1,…,cn1),d=(d0,d1,…,dn1)Cc+d=(c0+d0,c1+d1,…,cn1+dn1)CS=F2kCF2nf5线性分组码线性分组码概念线性分组码的生成矩阵线性分组码的校验矩阵线性分组码的最小汉明重量线性分组码的译码完备码汉明码6线性分组码的生成矩阵kn矩阵G称为生成矩阵生成矩阵C是F2n的一个k维线性子空间，设{g1,g2,…,gk}是C的一个基121122...++...+.nkkccccmgmgmgmG码字：11112122122212............nnkkkkngggggggggggg11121122122212.........nnkkkknggggggggGgggg7线性分组码的生成矩阵例7-1（4,2）分组码C={(0,0,0,0),(0,1,0,1),(0,1,1,0),(0,0,1,1)}是线性分组码，其生成矩阵有三个：010101100011,,0110001101018线性分组码的生成矩阵例7-2已知(6,3)线性分组码的生成矩阵G为111010110001.011101G则编码函数f：123()[111010][110001][011101].cfmmmm11221233134351623cmmcmmmcmmcmcmcmm9线性分组码的生成矩阵例7-2全体码字为：信息元码字00000101001110010111011100000001110111000110110011101010011100101101011011221233134351623cmmcmmmcmmcmcmcmm10线性分组码的生成矩阵系统线性分组码m1m2,…,mkm1m2,…,mkck+1ck+2,…,cn11111121211122............kkkkkkkknnnknkcmcmcgmgmgmcgmgmgmck+1ck+2,…,cn称为校验位！11121212221210...0...01...0...[|]00...1...kknkknkkkrkkkkknggggggGIPggg系统生成矩阵：11线性分组码的生成矩阵非系统码转换为系统码—系统化例7-2（续1）：求系统生成矩阵Gs及全部码字123100111010110001011.dmmm:(1)(3)(1)+(2);(2)+(3)111010100111110001010110011101001011sGG行变换编码函数f11221233134351623cmmcmmmcmmcmcmcmm1122334125123613dmdmdmdmmdmmmdmm编码函数fs12线性分组码的生成矩阵信息元码f系统码fs000001010011100101110111000000011101110001101100111010100111001011010110000000001011010110011101100111101100110001111010编码函数不同:ffs码字相同例7-2（续1）：求系统生成矩阵Gs及全部码字13线性分组码线性分组码概念线性分组码的生成矩阵线性分组码的校验矩阵线性分组码的最小汉明重量线性分组码的译码完备码汉明码14线性分组码的校验矩阵对偶码线性码Ck维线性子空间C{0,1}n对偶空间V={a=(a0,a1,…,an1){0,1}n，c=(c0,c1,…,cn1)C,ac}{0,1}n是nk维子空间C确定一个（n,nk）线性分组码，称为码C的对偶码C，其生成矩阵记为H15线性分组码的校验矩阵校验（监督）矩阵定理7-2c是（n,k）线性分组码C的一个码字当且仅当HcT=0H被称为C的校验（监督）矩阵cHT=0GHT=0：G与H正交！16线性分组码的校验矩阵系统线性码的校验（监督）矩阵()()[][].kknkTknkkGIPHPI系统生成矩阵：，校验矩阵:[|]00.TTkkccmGPcHmGHmIPmI证明：是码字17线性分组码的校验矩阵111110011[101100][000].100010001.TdHd是码字例7-2（续2）：求系统码的校验矩阵H.若收到码元序列r=(100110)，d=(101100)，验证是否为码字？111110011[100110][001][000].100010001.TrHr不是码字100111010110|001011sGIP系统生成矩阵110100|111010.101001THPI校验矩阵18线性分组码的校验矩阵110100111010.101001H对偶码的生成矩阵=校验矩阵例7-2（续2）：求对偶码C信息元码f系统码fs对偶码C0000010100111001011101110000000111011100011011001110101001110010110101100000000010110101100111011001111011001100011110100000001010011110100100111101000111010011101001111123212323415263,cmHcmmmcmmcmmcmcmcm19线性分组码的校验矩阵求全体码字C，系统生成矩阵Gs，校验矩阵Hs，系统码Cs，对偶码C。信息元码C系统码Cs对偶码C000001010011100101110111课堂练习：已知(5,3)线性分组码的生成矩阵为G010111101001101G20线性分组码的校验矩阵求全体码字C，系统生成矩阵Gs，校验矩阵Hs，系统码Cs，对偶码C。课堂练习：已知(5,3)线性分组码的生成矩阵为G010111101001101G111001101010001sG1011101110sH21线性分组码线性分组码概念线性分组码的生成矩阵线性分组码的校验矩阵线性分组码的最小汉明重量线性分组码的译码完备码汉明码22线性分组码的最小汉明重量定理7-4线性分组码C的最小汉明距离等于该码中非零码字的最小汉明重量。例7-2（续3）全体码字为：码字000000011101110001101100111010100111001011010110C的最小汉明距离=3，可以纠1个错，检2个错23线性分组码的最小汉明重量定理7-5线性分组码C的最小汉明距离是d当且仅当它的校验矩阵H的任意d1列线性无关，而存在d列线性相关。例7-2（续4）校验矩阵为任何2列线性无关，第2、4、5列线性相关，C的最小汉明距离=3110100111010101001H例7-3设一个（6,3）线性分组码C的校验矩阵为任何1列线性无关，第1、2列线性相关，C的最小汉明距离=2110100111010001001H24线性分组码线性分组码概念线性分组码的生成矩阵线性分组码的校验矩阵线性分组码的最小汉明重量线性分组码的译码完备码汉明码25线性分组码的译码差错图样（错误图样）c→发送的码字，r→接收的码字，差错图样：e=rc.对二进制码,有:e=r⊕c,r=c⊕e，c=r⊕e.因为rHT=(c⊕e)HT=cHT⊕eHT=0⊕eHT=eHTeHT=0接收码字r无差错！26线性分组码的译码(n,k)线性分组码的标准阵列：(n,k)线性码有2k=m个码字:C={c0=(00,…,0),c1,…,cm1}.全部n重有2n个元素，排成一个h=2nk行m=2k列的表c0c1c2…cm1e1e1+c1e1+c2…e1+cm1e2e2+c1e2+c2…e2+cm1……………eh1eh1+c1eh1+c2…eh1+cm1元素ei为不在前面行中，且重量最轻的n重！每行元素称为一个陪集第一列的元素称为陪集首不同位置的元素不相同27线性分组码的译码标准阵列译码方法：设接收的n重为r,位于第i行第j列：r=ei+cj将r译为cl的错误图样为:el=rcl=ei+(cjcl)=ei+ck位于第i行，在第i行，ei的重量最小，所以：应使得el=ei，cl=cj，将r译为cj。将r译为与r同列的码字cj,差错图样为eic0c1c2…cm1e1e1+c1e1+c2…e1+cm1e2e2+c1e2+c2…e2+cm1……………eh1eh1+c1eh1+c2…eh1+cm128线性分组码的译码0000001101101111101010000111010011101010010000010111111100100010001001100111111000010011111010111001000010110010110110110001101110101001100100110010111000111100设接收的5重为r=(10101),应将r译为那个码字c.解:消息序列为m=00,01,10,11.由c=mG得码字序列10111.01101G例7-3已知一个(5,2)线性码的生成矩阵Gc0=00000,c1=01101,c2=10111,c3=11010.作出标准阵列.将r=(10101)译为c=(10111).29线性分组码的译码例7-3讨论：码的汉明距离为3最多能纠正1个错误能发现2个错误(最后2行)陪集首选择不唯一！0000001101101111101010000111010011101010010000010111111100100010001001100111111000010011111010111001000010110010110110110001101110101001100100110010111000111100标准阵列译码局限如当n、k较大时，译码需要较大的存储空间查找r需要较长的时间。30线性分组码的译码r的伴随式s=s(r)=rHTr=c⊕es(r)=s(e).标准阵列中同一个陪集的所有向量的伴随式相同！31线性分组码的译码伴随式译码保留标准阵列的陪集首，计算其伴随式，构造伴随式表计算r的伴随式s(r)=rHT在伴随式表中查找s(r)，确定陪集首e，译码为c=r+e。伴随式