华南理工大学：《现代编码理论与技术》课程教学资源（PPT课件讲稿）第三章 线性分码组

第三章线性分组码 陆以勤 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 ) （ ciGF(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 ,c2CH : c1+c2CH 证明： 由c1CH，得Hc1 T=0 T; 由c2CH，得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)aGF(q),cCH: a c 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). 2.再证维数为k 设cCH, 则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)

二、线性分组码的严格数学定义4 由第2章定理3可知，必存在k个线性独立的码字g192,,9k,使∀c∈CH c=mn-191+mn-292+...+mn-kgk =m G 基不同，G不同，但 生成的空间是一样的， 不同的G的意义是什 91,n-191,n-2…g1,0 么？ G= 92.n-192,n-2…92.0 gkn-19kn-2…9k,0 秩是多少？ G称为[n,k]码的生成矩阵。 G的标准形式kP],称为典型生成矩阵

二、线性分组码的严格数学定义4 由第2章定理3可知，必存在k个线性独立的码字g1 , g2 , … , gk , 使cCH: c=mn-1g1+mn-2g2+… + mn-kgk =m G g1,n-1 g1,n-2 … g1,0 g2,n-1 g2,n-2 … g2,0 .......... gk,n-1 gk,n-2 … gk,0 G= G称为[n,k]码的生成矩阵。 G的标准形式[IkP], 称为典型生成矩阵。 基不同，G不同，但 生成的空间是一样的， 不同的G的意义是什 么？ 秩是多少？

三、G与H的关系 G的行矢量是码字，HgT=0T,有HGT=0T,H与G所张成的空间互为零空间。 CH:H校验，G生成 CG:G校验，H生成。j 互为对偶码，若Cu=Cc,则称为自对偶码(P62) [Q In-K][lkP]T=[QIn-k][lKT PT]T=Q+PT =0 所以P=-QT或Q=PT 由此得G=[kP]=[lkQ门 H=[Q In-K]=[-PT In-k]

三、G与H的关系 G的行矢量是码字，Hgi T=0 T , 有HGT= 0 T, H与G所张成的空间互为零空间。 CH: H校验，G生成。 CG: G校验，H生成。 互为对偶码，若CH=CG, 则称为自对偶码（P62) [Q In-k ] [IkP]T= [QIn-k ] [Ik T PT] T= Q + PT = 0 所以 P= - QT 或 Q = -PT 由此得 G=[Ik P] = [ Ik –QT] H=[Q In-k ]= [ -PT In-k ]

三、G与H的关系2 例：已知[7,3]码（p52,例3.1) :1011000 0100 H= :111 1100010 011:0001 C=(C6C5C4C3C2C1Co) 由HcT=0T得 C3=C6+C4 C2=C6+C5+C4 C1=C6+C5 C0=C5+C4 1110 1001110 P=-QT= 0111 G=[lk P]= 010|0111 1101 001|1101

三、G与H的关系2 例： 已知[7，3]码（p52, 例3.1) 1 0 1 | 1 0 0 0 1 1 1 | 0 1 0 0 1 1 0 | 0 0 1 0 0 1 1 | 0 0 0 1 H= c=(c6c5c4c3c2c1c0 ) 由Hc T=0 T得 c3=c6+c4 c2=c6+c5+c4 c1=c6+c5 c0=c5+c4 1 1 1 0 0 1 1 1 1 1 0 1 P= -QT= G=[Ik P] = 1 0 0 | 1 1 1 0 0 1 0 | 0 1 1 1 0 0 1 | 1 1 0 1

三、G与H的关系3 设信息组m=(memsm4) C6=m6 c5=m5 C4=m4 C3=m6+m4=C6+C4 C2=m6+m5+m4=C6+C5+C4 C1=m6+m5=C6+C5 Co=m5+m4=C5+C4 考虑如何用串行方式？

三、G与H的关系3 设信息组m = (m6m5m4 ) c6=m6 c5=m5 c4=m4 c3=m6+m4=c6+c4 c2=m6+m5+m4=c6+c5+c4 c1=m6+m5=c6+c5 c0=m5+m4=c5+c4 + + + + 考虑如何用串行方式？

三、G与H的关系4 0123487890218 Do D2 2

三、G与H的关系4 + + + 0 1 2 3 4 5 6 7 8 9 10 11 12 13 D0 D1 D2 D3