线性分组码课件

第七章：线性分组码§7.1

分组码的概念§7.2线性分组码§7.4循环码§7.5卷积码2022/11/251第七章：线性分组码§7.1分组码的概念2022/10/1§7.1分组码的概念设信道是一个D元字母输入/D元字母输出的DMC信道，字母表为{0,1,…,D-1}。其信道转移概率矩阵为D×D矩阵传输错误的概率为

p。信道容量为C=logD-H(p)-plog(D-1)。2022/11/252§7.1分组码的概念设信道是一个D元字母输入/D元字母§7.1分组码的概念对随机变量序列X1X2…进行的信道编码为(N,L)码：(X1X2…XL)→(U1U2…UN)=C(X1X2…XL)。这个(N,L)码又称为(N,L)分组码。已经有结论：当R<C/H(X)时存在(N,L)分组码，使得信息率(L/N)任意接近R，译码错误的概率任意接近0。问题是：怎样构造这样的分组码？这样的分组码的编码、译码计算量会不会太大？（这才是研究分组码的含义）

2022/11/253§7.1分组码的概念对随机变量序列X1X2…进行的信道编§7.1分组码的概念预备知识1：有限域设D是一个素数。于是字母表{0,1,…,D-1}中的所有字母关于(modD)加法、(modD)乘法构成了一个代数结构，称作有限域，记作GF(D)=({0,1,…,D-1},(modD)加法,(modD)乘法)。即（1）({0,1,…,D-1},(modD)加法)构成交换群（Abel群）。（2）({1,…,D-1},(modD)乘法)构成交换群（Abel群）。（3）分配率成立：a(b+c)=ab+ac(modD)。注：GF(D)上的线性代数完全类似于实数域上的线性代数。2022/11/254§7.1分组码的概念预备知识1：有限域2022/10/1§7.1分组码的概念例：取D=2，则GF(2)=({0,1},(mod2)加法,(mod2)乘法)的运算规则为：0+0=1+1=0，0+1=1，0×0=0×1=0，1×1=1。方阵是否可逆？回答是肯定的，因为2022/11/255§7.1分组码的概念例：取D=2，则GF(2)=({0,§7.1分组码的概念该方阵的逆矩阵是什么？怎样计算？做联合可逆行变换：2022/11/256§7.1分组码的概念该方阵的逆矩阵是什么？怎样计算？做§7.1分组码的概念例：取D=3，则GF(3)=({0,1,2},(mod3)加法,(mod3)乘法)的运算规则为：0+0=1+2=0，0+1=2+2=1，0+2=1+1=2，0×0=0×1==0×2=0，1×1=2×2=1，1×2=2。矩阵是不是满行秩的？换句话说，此矩阵的三个行向量是不是在域GF(3)上线性无关的？再换句话说，能否保证此矩阵的各行的任何非0线性组合都不是全0的4维向量？再换句话说，此矩阵能否通过一些可逆行变换变成一个“阶梯阵”？2022/11/257§7.1分组码的概念例：取D=3，则GF(3)=({0,§7.1分组码的概念可逆行变换2022/11/258§7.1分组码的概念可逆行变换2022/10/118§7.1分组码的概念例：域GF(D)上的一个L行N列的矩阵（L×N阶的矩阵）G，设它是满行秩的（当然此时有L≤N）。则变换(u1,u2,…,uN)=(x1,x2,…,xL)G一定是单射(即(x1,x2,…,xL)的不同值一定变换为(u1,u2,…,uN)的不同值)。证明设u(1)=x(1)G，u(2)=x(2)G，且x(1)≠x(2)。要证明u(1)≠u(2)。根据线性性质，u(1)-u(2)=(x(1)-x(2))G，因为(x(1)-x(2))≠全0的L维向量，所以(x(1)-x(2))G是G的各行的非0线性组合。G满行秩，所以(x(1)-x(2))G≠全0的N维向量。所以u(1)≠u(2)。2022/11/259§7.1分组码的概念例：域GF(D)上的一个L行N列的矩§7.1分组码的概念预备知识2：有限域上的分组码当D是素数时，分组码可以充分利用有限域GF(D)的代数运算，使得编码和译码更加简便。2022/11/2510§7.1分组码的概念预备知识2：有限域上的分组码2022§7.2线性分组码定义取GF(D)上的一个L行N列的矩阵G，它是满行秩的。(N,L)分组码定义为(u1,u2,…,uN)=(x1,x2,…,xL)G其中(x1,x2,…,xL)是信息向量，(u1,u2,…,uN)是对应的码字。（1）称此码为D元(N,L)线性分组码。（2）称矩阵G为此码的生成矩阵。2022/11/2511§7.2线性分组码定义取GF(D)上的一个L行N列的§7.2线性分组码线性分组码的代数结构命题1不同的信息向量对应不同的码字。（因为变换u=xG是单射）命题2生成矩阵G的第1行是信息向量(1,0,0,…,0)的码字；生成矩阵G的第2行是信息向量(0,1,0,…,0)的码字；…生成矩阵G的第L行是信息向量(0,…,0,0,1)的码字。2022/11/2512§7.2线性分组码线性分组码的代数结构2022/10/1§7.2线性分组码命题3信息向量(x1,x2,…,xL)的码字是：x1数乘G的第1行，加x2数乘G的第2行，加…，加xL数乘G的第L行。命题4当u(1)和u(2)都是码字，u(1)+u(2)也是码字。（线性分组码的码字关于线性运算封闭）证明设u(1)是信息向量x(1)的码字：u(1)=x(1)G；u(2)是信息向量x(2)的码字：u(2)=x(2)G。则u(1)+u(2)=x(1)G+x(2)G=(x(1)+x(2))G，即u(1)+u(2)是信息向量(x(1)+x(2))的码字。证完。2022/11/2513§7.2线性分组码命题3信息向量(x1,x2,…§7.2线性分组码（命题3和命题4告诉我们，一个N维向量是一个码字，当且仅当它是G的第1行~第L行的线性组合。还告诉我们，线性分组码的码字集合构成一个线性空间。这个线性空间是几维的？L维的，因为生成矩阵G的第1行~第L行恰好是该线性空间的一组基）命题5设一个D元(N,L)线性分组码的生成矩阵为G。设另一个D元(N,L)线性分组码的生成矩阵为G’=MG，其中M是L阶可逆方阵。则两个码的码字集合完全重合，只是信息向量与码字的对应关系不同。换句话说，如果把线性分组码的生成矩阵G做可逆行变换变成另一个生成矩阵，则不改变码字集合，只改变信息向量与码字的对应关系。2022/11/2514§7.2线性分组码（命题3和命题4告诉我们，一个N维向量§7.2线性分组码证明（要证明，第一个码中任一个码字也是第二个码中的码字；第二个码中任一个码字也是第一个码中的码字）设在第一个码中，u是信息向量x的码字：u=xG；则在第二个码中，u是信息向量xM-1的码字：u=xM-1MG=xM-1G’。设在第二个码中，u是信息向量x的码字：u=xG’；则在第一个码中，u是信息向量xM的码字：u=xMM-1G’=xMG。证完。

2022/11/2515§7.2线性分组码证明（要证明，第一个码中任一个码字§7.2线性分组码线性分组码的特例：系统码定义(p192)

D元(N,L)线性分组码的生成矩阵为G=[PL×(N-L),IL]，其中IL是L阶单位阵，PL×(N-L)是(N-L)×L阶矩阵。则称此码为系统码。此时信息向量(x1,x2,…,xL)的码字是(u1,u2,…,uN)=(x1,x2,…,xL)G=((x1,x2,…,xL)PL×(N-L),x1,x2,…,xL)。码字的后L位恰好是信息向量(x1,x2,…,xL)，称为码字的信息位。称码字的前N-L位为码字的一致校验位。2022/11/2516§7.2线性分组码线性分组码的特例：系统码2022/10§7.2线性分组码例6.1.2(p190)此二元(7,4)码是线性分组码，生成矩阵G是由信息向量(1000)、(0100)、(0010)、(0001)的码字组成的4行2022/11/2517§7.2线性分组码例6.1.2(p190)此二元(7§7.2线性分组码例6.1.4(p192)此二元(5,3)线性分组码的生成矩阵是2022/11/2518§7.2线性分组码例6.1.4(p192)此二元(5§7.2线性分组码线性分组码的一致校验矩阵定理(p193)

对于D元(N,L)线性分组码的生成矩阵G（G是L×N阶矩阵），必存在一个(N-L)×N阶矩阵H，（1）H是满行秩的；（2）GHT=OL×(N-L)。（HT是H的转置矩阵，OL×(N-L)是全0的L×(N-L)阶矩阵。不证明。这方面的知识属于有限域上的线性代数）定义6.1.7(p193)

由上述定理所描述的矩阵H称为D元(N,L)线性分组码的一致校验矩阵。2022/11/2519§7.2线性分组码线性分组码的一致校验矩阵2022/10§7.2线性分组码有以下的结论。（1）一个线性分组码有很多一致校验矩阵。一个一致校验矩阵H经过可逆行变换变为H’，

H’是同一个线性分组码的另一个一致校验矩阵。（2）一个N维向量u是一个码字，当且仅当：uHT=全0的N-L维行向量。（3）设一个D元(N,L)线性分组码的生成矩阵G，一致校验矩阵H。则H是一个D元(N,N-L)线性分组码的生成矩阵，G是此码的一致校验矩阵。称这两个码互为对偶码。2022/11/2520§7.2线性分组码有以下的结论。2022/10/1120§7.2线性分组码（怎样由生成矩阵G计算出一致校验矩阵H？）（4）设D元(N,L)线性分组码是系统码，生成矩阵为G=[P,IL]，其中IL是L阶单位阵，P是L×(N-L)阶矩阵。则一致校验矩阵可以取为H=[IN-L,-PT]，其中IN-L是N-L阶单位阵，PT是P

的转置矩阵。证明GHT=[P,IL][IN-L,-PT]T=P-P=OL×(N-L)。证完。（5）设D元(N,L)线性分组码的生成矩阵经过可逆行变换后变为[P,IL]，则一致校验矩阵也可以取为H=[IN-L,-PT]。2022/11/2521§7.2线性分组码（怎样由生成矩阵G计算出一致校验矩阵H§7.2线性分组码线性分组码的纠错译码准则定义6.1.2