编码chapter3线性分组码.ppt

第三章线性分组码2005年3月一、线性分组码的一般性定义定义:通过预定的线性运算将k维q元(q为素数幂)信息数组变换成n维(n>k)码数组(称码字),由qk个码字所成的集合,称为[n,k]线性分组码,简称分组码。--2,…,cn--k-1,…,c1,c0)表示。码率(传信率,信道利用率)R=k/n表示信息位所占的比重。最简单的情况:在后面添加n-k个监督元,叫系统码()。cn-k-1=h1,n-1cn-1+h1,n-2cn-2+…+h1,n-kcn-1cn-k-2=h2,n-1cn-1+h2,n-2cn-2+…+h2,n-kcn-1..........c0=hn-k,n-1cn-1+hn-k,n-2cn-2+…+hn-k,n-kcn-1h1,n-1h1,n-2…h1,n-k10…0cn-1h2,n-1h2,n-2…h2,n-k01…0cn-2=0..........hn-k,n-1hn-k,n-2…hn-k,n-k00…1c0HcT=0T二、(q)中的元素(q为素数幂)组成的(n-k)n矩阵,其秩为n-k。满足方程HcT=0T的矢量c=(cn--2,…ci,…,c0)(ciGF(q))的集合称为[n,k]线性分组码。H称为监督(检验)矩阵。HcT=0T称为(一致)监督矩阵。为什么秩为n-k?一致:同一规则对H进行初等变换,化为h1,n-1h1,n-2…h1,n-k10…0h2,n-1h2,n-2…h2,n-k01…0..........hn-k,n-1hn-k,n-2…hn-k,n-k00…1=[QIn-k]的形式,称为H的标准形式。H称为典型监督矩阵。二、(码的封闭性)设CH为由监督矩阵H定义的分组码,则c1,c2CH:c1+c2CH证明:由c1CH,得Hc1T=0T; 由c2CH,得Hc2T=0T; 所以H(c1+c2)T=H(c1T+c2T)=Hc1T+Hc2T=0T c1+c2满足HcT=0T,所以c1+c2[n,k]线性分组码对矢量相加构成阿贝尔群。封闭性(定理1),结合律,有恒等元和逆元。二、[n,k]线性分组码是GF(q)上的n维线性空间Vn中的一个k维子空间。证:设CH是由监督矩阵H定义的[n,k]线性码。。(1)CH是阿贝尔群(定理2);(2)aGF(q),cCH:acCH;(3)分配律:c1,c2CH,a,bGF(q):a(c1+c2)=ac1+ac2且(a+b)c1=ac1+bc1;(4)结合律成立:a1,a2GF(q),cCH:(a1a2)c=a1(a2c).cCH,则HcT=,故c在由H的行矢量张成的n-k维线性子空间Vn,n-k的零空间中(第2章定理17,),CH中每个码字和H张成的子空间的矢量正交,所以CH为H张成的子空间的零空间(第2章定理16,),维数为k(第2章定理18,)。二、线性分组码的严格数学定义4由第2章定理3可知,必存在k个线性独立的码字g1,g2,…,gk,使cCH:c=mn-1g1+mn-2g2+…+mn-kgk=mGg1,n-1g1,n-2…g1,0g2,n-1g2,n-2…g2,0..........gk,n-1gk,n-2…gk,0G=G称为[n,k]码的生成矩阵。G的标准形式[IkP],称为典型生成矩阵。基不同,G不同,但生成的空间是一样的,不同的G的意义是什么?秩是多少?三、G与H的关系G的行矢量是码字,HgiT=0T,有HGT=0T,H与G所张成的空间互为零空间。CH:H校验,G生成。CG:G校验,H生成。互为对偶码,若CH=CG,则称为自对偶码(P62)[QIn-k][IkP]T=[QIn-k][IkTPT]T=Q+PT=0所以P=-QT或Q=-PT由此得G=[IkP]=[Ik–QT] H=[QIn-k]=[-PTIn-k]三、G与H的关系2例:已知[7,3]码(p52,)101|1000111|0100110|0010011|0001H=c=(c6c5c4c3c2c1c0)由HcT=0T得c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c41**********P=-QT=G=[IkP]=100|1110010|0111001|1101三、G与H的关系3设信息组m=(m6m5m4)c6=m6c5=m5c4=m4c3=m6+m4=c6+c4c2=m6+m5+m4=c6+c5+c4c1=m6+m5=c6+c5c0=m5+m4=c5+c4考虑如何用串