第三章线性分组码 陆以勤 2005年3月
第三章 线性分组码 陆以勤 2005年3月
一、线性分组码的一般性定义 定义：通过预定的线性运算将k维q元(q为素数幂)信息数组变换成n维 (n>k)码数组（称码字)，由gk个码字所成的集合，称为n,k线性分组码， 简称分组码。 码字用（cn1,Cn-2,,Cn-k,Cnk1,,C1,Co)表示。 码率（传信率，信道利用率）R=kWn表示信息位所占的比重。 最简单的情况：在后面添加n-k个监督元，叫系统码（定义3.2.2)。 Cn-k-1=h1.n-1Cn-1+h1.n-2Cn-2+...+h1.n-kCn-1 Cn-k-2=h2.n-1Cn-1+h2.n-2Cn-2+...+h2.n-kCn-1 Co=hn-k.n-1Cn-1+hn-k.n-2Cn-2+...+hn-k.n-kCn-1 h1.n1h1,n-2.h1.n-k10.0 Cn-1 h2.n-1h2.n-2.h2.nk010 Cn-2 =0 →HcT=0 ho-k.n-1hn-k.n2..n-k.n-k00..1 Co
一、线性分组码的一般性定义 定义：通过预定的线性运算将k维q元（q为素数幂）信息数组变换成n维 （n>k)码数组（称码字），由qk个码字所成的集合，称为[n,k]线性分组码， 简称分组码。 码字用 （cn-1 , cn-2 , … , cn-k , cn-k-1 , … , c1 , c0 )表示。 码率（传信率，信道利用率）R=k/n表示信息位所占的比重。 最简单的情况：在后面添加n-k个监督元，叫系统码（定义3.2.2)。 cn-k-1= h1,n-1cn-1+h1,n-2cn-2+…+h1,n-kcn-1 cn-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-1 h1,n-1 h1,n-2 … h1,n-k 10 … 0 cn-1 h2,n-1 h2,n-2 … h2,n-k 01… 0 cn-2 =0 .......... hn-k,n-1hn-k,n-2 … hn-k,n-k00…1 c0 Hc T=0 T
二、线性分组码的严格数学定义 1.定义 GF(q)中的元素（q为素数幂)组成的(n-k)xn矩阵，其秩为n-k。满足方程 HcT=0T的矢量c=(cn1,cn-2,.C,,co)(c∈GF(q)的集合称为n,k灯线性分组 码。H称为监督（检验）矩阵。HcT=0T称为（一致）监督矩阵。 为什么秩为n-k? 致：同一规则 h1,n-1h1n-2.h1,nk10.0 对进行初等变换，化为 h2n-1h2n-2.h2nk01.0 =[QInk]的形式，称为 hn-k.n-1hn-k.n-2...n-k.n.. H的标准形式。H称为典型监督矩阵
二、线性分组码的严格数学定义 1.定义 GF(q)中的元素（q为素数幂）组成的(n-k)n矩阵，其秩为n-k。满足方程 Hc T=0 T的矢量c=(cn-1 , cn-2 , …ci ,… ,c0 ) （ ciGF(q) )的集合称为[n,k]线性分组 码。H称为监督（检验)矩阵。 Hc T=0 T称为（一致）监督矩阵。 为什么秩为n-k？ 一致：同一规则 对H进行初等变换，化为 h1,n-1 h1,n-2 … h1,n-k 10 … 0 h2,n-1 h2,n-2 … h2,n-k 01… 0 .......... hn-k,n-1hn-k,n-2 … hn-k,n-k00…1 =[Q In-k]的形式，称为 H的标准形式。H称为典型监督矩阵
二、线性分组码的严格数学定义2 2.定理1（码的封闭性） 设C为由监督矩阵H定义的分组码，则Hc1,c2∈CH:c+c2∈CH 证明：由c1eCH,得HcT=0 由c2∈CH,得Hc2T=O; 所以H(C+c2)T=H(c1T+C2)=Hc,T+Hc2T=0T C+C2满足HcT=OT,所以c+C2∈CH 3.定理2 [n,k]线性分组码对矢量相加构成阿贝尔群。 封闭性（定理1)，结合律，有恒等元和逆元
二、线性分组码的严格数学定义2 2. 定理1 (码的封闭性） 设CH为由监督矩阵H定义的分组码，则c1 ,c2CH : c1+c2CH 证明： 由c1CH，得Hc1 T=0 T; 由c2CH，得Hc2 T=0 T; 所以 H(c1+c2 ) T=H(c1 T+c2 T) =Hc1 T+Hc2 T=0 T c1+c2满足Hc T=0 T，所以c1+c2 CH 3. 定理2 [n,k]线性分组码对矢量相加构成阿贝尔群。 封闭性（定理1），结合律，有恒等元和逆元
二、线性分组码的严格数学定义3 3.定理3 [n,k]线性分组码是GF(q)上的n维线性空间n中的一个k维子空间。 证：设C是由监督矩阵H定义的[n,k]线性码。 1.先证C为子空间。 (1)C是阿贝尔群（定理2）； (2)Va∈GF(q),ceCH:ac∈CH; (3)分配律：c,c2∈CH,Ha,beGF(q):a(c+c2)=ac+ac2且(a+b)c1=ac,+bc1; (4)结合律成立：a,a2∈GF(q),ceCH:(aa2)c=a1(a2c. 2.再证维数为k 设c∈CH,则HcT=OT.c与H的每一行矢量正交，故c在由H的行矢量张成的n-k维线 性子空间Vnn-k的零空间中（第2章定理17，定理2.6.9），CH中每个码字和H张成的子 空间的矢量正交，所以C1为H张成的子空间的零空间（第2章定理16，定理2.6.8），维 数为k(第2章定理18，定理2.6.10)
二、线性分组码的严格数学定义3 3. 定理3 [n,k]线性分组码是GF(q)上的n维线性空间Vn中的一个k维子空间。 证：设CH是由监督矩阵H定义的[n,k]线性码。 1.先证CH为子空间。 (1)CH是阿贝尔群(定理2); (2)aGF(q),cCH: a c CH; (3) 分配律: c1 , c2 CH, a,bGF(q): a (c1+c2 )=ac1+ac2且(a+b)c1=ac1+bc1 ; (4) 结合律成立: a1 , a2 GF(q), cCH: (a1a2 )c=a1 (a2c). 2.再证维数为k 设cCH, 则Hc T=0 T. c与H的每一行矢量正交, 故c在由H的行矢量张成的n-k维线 性子空间Vn,n-k的零空间中(第2章定理17, 定理2.6.9), CH中每个码字和H张成的子 空间的矢量正交, 所以CH为H张成的子空间的零空间(第2章定理16, 定理2.6.8), 维 数为k (第2章定理18, 定理2.6.10)