信息论与编码-第7章线性分组码ppt课件.ppt

《信息论与编码-第7章线性分组码ppt课件.ppt》由会员分享，可在线阅读，更多相关《信息论与编码-第7章线性分组码ppt课件.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章 线性分组码线性分组码王永容王永容 机械与电气工程学院机械与电气工程学院 信息论与编码 Information and Coding Theory 1资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码线性分组码 线性分组码概念线性分组码概念 线性分组码的生成矩阵线性分组码的生成矩阵 线性分组码的校验矩阵线性分组码的校验矩阵 线性分组码的最小汉明重量线性分组码的最小汉明重量 线性分组码的译码线性分组码的译码 完备码完备码 汉明码汉明码2资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随

2、时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码概念线性分组码概念l(n,k)线性分组码线性分组码=“(n,k)分组分组”+“线性线性”u2元(n,k)分组码 f:S=(F2)k C(F2)n m=(m2,mk)c=(c1c2,cn)uC是(F2)n的一个k维线性子空间！S=F2kCF2nf 3资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码概念线性分组码概念l定义定义7-1 一个(n,k)分组码C被称为线性分组码线性分组码，如果它满足全零u（0,0,0)Cu任意两个码字的和也是码字.

3、即,c=(c0,c1,cn1),d=(d0,d1,dn1)C c+d=(c0+d0,c1+d1,cn1+dn1)CS=F2kCF2nf 4资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码线性分组码 线性分组码概念线性分组码概念 线性分组码的生成矩阵线性分组码的生成矩阵 线性分组码的校验矩阵线性分组码的校验矩阵 线性分组码的最小汉明重量线性分组码的最小汉明重量 线性分组码的译码线性分组码的译码 完备码完备码 汉明码汉明码5资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增

4、值的这部分资金就是原有资金的时间价值 线性分组码的生成矩阵线性分组码的生成矩阵 k n矩阵矩阵G称为生成矩阵称为生成矩阵l生成矩阵生成矩阵 C是F2n的一个k维线性子空间，设g1,g2,gk是C的一个基6资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的生成矩阵线性分组码的生成矩阵l例例7-1 （4,2）分组码 C=(0,0,0,0),(0,1,0,1),(0,1,1,0),(0,0,1,1)是线性分组码，其生成矩阵有三个：7资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值

5、，其增值的这部分资金就是原有资金的时间价值 线性分组码的生成矩阵线性分组码的生成矩阵l例例7-2 已知(6,3)线性分组码的生成矩阵G为 则编码函数f：8资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的生成矩阵线性分组码的生成矩阵l例例7-2 全体码字为：信息元信息元码字码字0000010100111001011101110000000111011100011011001110101001110010110101109资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增

6、值的这部分资金就是原有资金的时间价值 线性分组码的生成矩阵线性分组码的生成矩阵l系统线性分组码系统线性分组码 m1m2,mkm1m2,mkck+1ck+2,cn ck+1ck+2,cn称称为校验位！为校验位！10资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的生成矩阵线性分组码的生成矩阵l非系统码转换为系统码非系统码转换为系统码系统化系统化 l例例7-2（续（续1）：）：求系统生成矩阵Gs及全部码字编编码码函函数数f 编编码码函函数数f s 11资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函

7、数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的生成矩阵线性分组码的生成矩阵信息元信息元码码f系统码系统码fs000001010011100101110111000000011101110001101100111010100111001011010110000 000001 011010 110011 101100 111101 100110 001111 010u编码函数不同编码函数不同:f fsu码字相同码字相同l例例7-2（续（续1）：）：求系统生成矩阵Gs及全部码字12资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增

8、值的这部分资金就是原有资金的时间价值 线性分组码线性分组码 线性分组码概念线性分组码概念 线性分组码的生成矩阵线性分组码的生成矩阵 线性分组码的校验矩阵线性分组码的校验矩阵 线性分组码的最小汉明重量线性分组码的最小汉明重量 线性分组码的译码线性分组码的译码 完备码完备码 汉明码汉明码13资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的校验矩阵线性分组码的校验矩阵l对偶码对偶码 线性码C k维线性子空间C0,1n 对偶空间V=a=(a0,a1,an1)0,1n，c=(c0,c1,cn1)C,ac 0,1n

9、是nk维子空间 C确定一个（n,nk）线性分组码，称为码C的对偶码对偶码C，其生成矩阵记为H14资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的校验矩阵线性分组码的校验矩阵l校验（监督）矩阵校验（监督）矩阵 定理定理7-2 c是（n,k）线性分组码C的一个码字当且仅当 HcT=0 H被称为被称为C的校验（监督）矩阵的校验（监督）矩阵 cHT=0 GHT=0：G与H正交！15资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组

10、码的校验矩阵线性分组码的校验矩阵l系统线性码的校验（监督）矩阵系统线性码的校验（监督）矩阵16资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的校验矩阵线性分组码的校验矩阵l例例7-2（续（续2）：）：求系统码的校验矩阵H.若收到码元序列r=(100110)，d=(101100)，验证是否为码字？17资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的校验矩阵线性分组码的校验矩阵l例例7-2（续（续2）：）：求对偶码C 信

11、息元信息元码码f系统码系统码fs对偶码对偶码C 000001010011100101110111000000011101110001101100111010100111001011010110000 000001 011010 110011 101100 111101 100110 001111 010000 000101 001111 010010 011110 100011 101001 110100 11118资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的校验矩阵线性分组码的校验矩阵 求全体码字C

12、，系统生成矩阵Gs，校验矩阵Hs，系统码Cs，对偶码C。信息元信息元码码C系统码系统码Cs对偶码对偶码C 000001010011100101110111l课堂练习：课堂练习：已知(5,3)线性分组码的生成矩阵为G19资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的校验矩阵线性分组码的校验矩阵 求全体码字C，系统生成矩阵Gs，校验矩阵Hs，系统码Cs，对偶码C。l课堂练习：课堂练习：已知(5,3)线性分组码的生成矩阵为G20资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值

13、，其增值的这部分资金就是原有资金的时间价值 线性分组码线性分组码 线性分组码概念线性分组码概念 线性分组码的生成矩阵线性分组码的生成矩阵 线性分组码的校验矩阵线性分组码的校验矩阵 线性分组码的最小汉明重量线性分组码的最小汉明重量 线性分组码的译码线性分组码的译码 完备码完备码 汉明码汉明码21资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的最小汉明重量线性分组码的最小汉明重量l定理定理7-4 线性分组码C的最小汉明距离等于该码中非零码字的最小 汉明重量。l例例7-2（续（续3）全体码字为：码字码字0000

14、00011101110001101100111010100111001011010110 C的最小汉明距离的最小汉明距离=3，可以纠可以纠1个错，检个错，检2个错个错22资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的最小汉明重量线性分组码的最小汉明重量l定理定理7-5 线性分组码C的最小汉明距离是d当且仅当它的校验矩阵H的任意d1列线性无关，而存在d列线性相关。l例例7-2（续（续4）校验矩阵为 任何任何2列线性无关，列线性无关，第第2、4、5列线性相列线性相关，关，C的最小汉明距的最小汉明距离离=3l

15、例例7-3 设一个（6,3）线性分组码C的校验矩阵为 任何任何1列线性无关，列线性无关，第第1、2列线性相关，列线性相关，C的最小汉明距离的最小汉明距离=223资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码线性分组码 线性分组码概念线性分组码概念 线性分组码的生成矩阵线性分组码的生成矩阵 线性分组码的校验矩阵线性分组码的校验矩阵 线性分组码的最小汉明重量线性分组码的最小汉明重量 线性分组码的译码线性分组码的译码 完备码完备码 汉明码汉明码24资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，

16、随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的译码线性分组码的译码l差错图样（错误图样）差错图样（错误图样）c发送的码字，r接收的码字，差错图样：e=rc.对二进制码,有:e=rc,r=ce，c=re.因为 rHT=(ce)HT=cHTeHT=0eHT=eHT eHT=0 接收码字r无差错！25资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的译码线性分组码的译码l(n,k)线性分组码的标准阵列：线性分组码的标准阵列：(n,k)线性码有2k=m个码字:C=c0=(00,0),c1

17、,cm1.全部n重有2n个元素，排成一个h=2nk行m=2k列的表c0c1 c2cm 1 e1e1+c1e1+c2e1+cm1 e2e2+c1e2+c2e2+cm1eh 1 eh1+c1eh1+c2eh1+cm1u元素元素ei 为不在前面行中，且重量最轻的为不在前面行中，且重量最轻的n重！重！u每行元素称为一个陪集陪集u第一列的元素称为陪集首陪集首u不同位置的元素不相同26资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的译码线性分组码的译码l标准阵列译码方法：标准阵列译码方法：设接收的n重为r,位于第i行

18、第j列：r=ei+cj 将r译为cl的错误图样为:el=rcl=ei+(cjcl)=ei+ck位于第i行，在第i行，ei的重量最小，所以：应使得el=ei，cl=cj，将r译为cj。将将r译为与译为与r同列的码字同列的码字cj,差错图样为差错图样为eic0c1 c2cm 1 e1e1+c1e1+c2e1+cm1 e2e2+c1e2+c2e2+cm1eh 1 eh1+c1eh1+c2eh1+cm127资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的译码线性分组码的译码00000011011011111010

19、10000111010011101010010000010111111100100010001001100111111000010011111010111001000010110010110110110001101110101001100100110010111000111100 设接收的5重为r=(10101),应将r译为那个码字c.解解:消息序列为m=00,01,10,11.由c=mG 得码字序列 l例例7-3 已知一个(5,2)线性码的生成矩阵Gc0=00000,c1=01101,c2=10111,c3=11010.作出标准阵列.将r=(10101)译为 c=(10111).28资金是运

20、动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的译码线性分组码的译码l例例7-3 讨论：讨论：u码的汉明距离为3u最多能纠正1个错误u能发现2个错误(最后2行)u陪集首选择不唯一！0000001101101111101010000111010011101010010000010111111100100010001001100111111000010011111010111001000010110010110110110001101110101001100100110010111000111100l标准阵列译码局限

21、标准阵列译码局限u如当n、k较大时，译码需要较大的存储空间u查找r 需要较长的时间。29资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的译码线性分组码的译码lr的伴随式的伴随式 s=s(r)=rHT r=ce s(r)=s(e).标准阵列中同一个陪集的所有向量的伴随式相同！标准阵列中同一个陪集的所有向量的伴随式相同！30资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的译码线性分组码的译码l伴随式译码伴随式译码u保留标

22、准阵列的陪集首，计算其伴随式，构造伴随式表伴随式表u计算r的伴随式s(r)=rHTu在伴随式表中查找s(r)，确定陪集首e，译码为 c=r+e。伴随式陪集首 s(c0)c0s(e1)e1s(eh1)eh1 rr+e231资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码的译码线性分组码的译码伴随式陪集首 0000000011110000101010001000010001000010001000010110001111000110 设接收的5重为r=(10101),应将r译为那个码字c.解解:作出标准阵列的首

23、列.校验矩阵为:l例例7-3(续续1)已知一个(5,2)线性码的生成矩阵G计算陪集首的伴随式，构造伴随式表。对r=(10101)rHT=(010)e=00010 c=r+e=(10111).32资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码线性分组码 线性分组码概念线性分组码概念 线性分组码的生成矩阵线性分组码的生成矩阵 线性分组码的校验矩阵线性分组码的校验矩阵 线性分组码的最小汉明重量线性分组码的最小汉明重量 线性分组码的译码线性分组码的译码 完备码完备码 汉明码汉明码33资金是运动的价值，资金的价值是

24、随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 完备码完备码l线性分组码的纠错能力线性分组码的纠错能力 定理定理7-6(Singleton界界)(n,k)线性分组码的最小距离 d(C)nk+1.证明：利用系统生成矩阵的结构 定理定理7-7(Plotkin界界)设(n,k)线性分组码的码字个数为M，则其最小Hamming距离d满足34资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 完备码完备码 对于二元线性分组码(n,k)，有：使等号成立的使等号成立的分组码称为完备码称为

25、完备码.l线性分组码的纠错能力线性分组码的纠错能力 定理定理7-8(Hamming界界)能纠正t个错误的二元分组码(n,k)的码字个数M满足：35资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 完备码完备码l二元完备码二元完备码u汉明码（d=3）u格雷（Golay）码（d=7）u（n,2）线性分组码（d=n）36资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 线性分组码线性分组码 线性分组码概念线性分组码概念 线性分组码的生成矩阵线性分组码

26、的生成矩阵 线性分组码的校验矩阵线性分组码的校验矩阵 线性分组码的最小汉明重量线性分组码的最小汉明重量 线性分组码的译码线性分组码的译码 完备码完备码 汉明码汉明码37资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 汉明码汉明码l二元汉明码二元汉明码 最小汉明距离为3的二元线性分组码(2m-1,2m-1-m)(m2)称为二元汉明码.u汉明码是完备码 u汉明码能纠正一位错误u汉明码的校验矩阵H由全部2m-1个长度为m的非零、不相同的列向量构成.完备性证明：38资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函

27、数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 汉明码汉明码l例例7-4 求(7,4)汉明码的校验矩阵H与生成矩阵G.解：m=3，校验矩阵H由全部23-1=7个长度为3的非零、不相同的列向量构成.生成矩阵G:39资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 汉明码汉明码l汉明码校验矩阵汉明码校验矩阵H的一般形式的一般形式l例例7-4 求(7,4)汉明码的一般校验矩阵H.解：m=3，H由全部7个长度为3的非零列向量构成.1 2 3 4 5 6 740资金是运动的价值，资金的价值是随时间变化而变化的，

28、是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 汉明码汉明码l汉明码的译码汉明码的译码 设汉明码的校验矩阵H=H1,H2,Hn，发送码字：c=(c1,c2,cn)，接收向量：r=(r1,r2,rn)(至多一位错!)，差错图样：e=rc=(0,0,ei,0,0)至多1位(第i位)为“1”。译码过程就是确定i.译码步骤：u计算伴随式s=rHT=(e+c)HT=eHT=eiHiTu如果s=0，r就译为ru如果s0 存在i使得s=Hi r的第i位出错 将r的第i位纠正！41资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金

29、就是原有资金的时间价值 汉明码汉明码l汉明码的译码汉明码的译码 对于一般校验矩阵H=H1,H2,Hn，设 s=(sm,s2,s1)则i为：42资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 汉明码汉明码l例例7-4（续（续1）对于(7,4)汉明码，接收向量r=(1001110),试译码.解1：利用校验矩阵u计算伴随式s=rHT=(010)us0 存在i使得s=H6 r的第6位出错 将r译为c=(1001100)43资金是运动的价值，资金的价值是随时间变化而变化的，是时间的函数，随时间的推移而增值，其增值的这部分资金就是原有资金的时间价值 汉明码汉明码l例例7-4（续（续1）对于(7,4)汉明码，接收向量r=(1001110),试译码.解2：利用一般校验矩阵u计算伴随式s=rHT=(110)ui=2+4=6 将r译为c=(1001100)1 2 3 4 5 6 744