信息论课件chap61教材

第六章线性分组码线性分组码一、引言

讨论的问题是什么？

如何寻找合适的分组码（编码、译码） 问题的由来： 由信道编码定理可知对随机变量序列X1X2…进行的信道编码为(N,L)码：(X0X1…XL-1)→(U0U1…UN-1)=C(X0X1…XL-1)。这个(N,L)码又称为(N,L)分组码。有如下结论：当R<C/H(X)时存在(N,L)分组码，使得信息率(L/N)任意接近R译码错误的概率任意接近0

纠错码的目的：寻找一种在实际中易于实现且能达到有效可靠地通信的编码方法 总的原理：利用冗余实现纠检错线性分组码二、基本概念

1、信息段、信息空间

2、码字、码空间

3、q元分组码的定义（N、L、D）

4、许用序列和禁用序列

许用序列： 禁用序列： 线性码：线性分组码

5、汉明重量、码重

向量x中非零分量的数目

6、汉明距离 两个长为N的q元序列之间对应位不相同的位数。线性分组码

7、最小汉明距离

对码整体而言的概念，码字中所有任意两个码字间汉明距离的最小值。

8、GF（2）上的向量包含0,1定义了两个运算加法：0＋0＝0，0＋1＝1＋0＝1，1＋1＝0乘法：0×0＝0，0×1＝0，1×0＝0，1×1＝1d(x,y)=w(x+y)

9、矩阵的初等变换10、线性无关与基矢11、生成矩阵12、系统码线性分组码定义取GF(D)上的一个L行N列的矩阵G，它是满行秩的。(N,L)分组码定义为(u0,u1,…,uN-1)=(x0,x1,…,xL-1)G其中(x0,x1,…,xL-1)是信息向量，(u0,u1,…,uN-1)是对应的码字。（1）称此码为D元(N,L)线性分组码。（2）称矩阵G为此码的生成矩阵。生成矩阵生成矩阵L维子空间的基底C=x0g0+x1g1+…+xL-1gL-1(7,4)汉明码消息序列码字消息序列码字00000001001000110100010101100111000000010100011110010010001101101001100101100011000101111000100110101011110011011110111111010000111001001101010010110101100000110101011101111111结论1不同的信息向量对应不同的码字

域GF(D)上的一个L行N列的矩阵（L×N阶的矩阵）G，设它是满行秩的。则变换(u0,u1,…,uN-1)=(x0,x1,…,xL-1)G一定是单射【即(x0,x1,…,xL-1)的不同值一定变换为(u0,u1,…,uN-1)的不同值)】。证明：

设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)。生成矩阵结论2生成矩阵G的第1行是信息向量(1,0,0,…,0)的码字；生成矩阵G的第2行是信息向量(0,1,0,…,0)的码字；…生成矩阵G的第L行是信息向量(0,…,0,0,1)的码字。生成矩阵结论3信息向量(x0,x1,…,xL-1)的码字是：

C=x0g0+x1g1+…+uL-1gL-1x0数乘G的第1行，加x1数乘G的第2行，加…，加xL-1数乘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))的码字。证完一个N维向量是一个码字，当且仅当它是G的第1行~第L行的线性组合。线性分组码的码字集合构成一个线性空间。这个线性空间是L维的，因为生成矩阵G的第1行~第L行恰好是该线性空间的一组基。生成矩阵结论5设一个D元(N,L)线性分组码的生成矩阵为G。设另一个D元(N,L)线性分组码的生成矩阵为G’=MG，其中M是L阶可逆方阵。则两个码的码字集合完全重合，只是信息向量与码字的对应关系不同。 结论的通俗描述为：如果把线性分组码的生成矩阵G做可逆行变换变成另一个生成矩阵，则不改变码字集合，只改变信息向量与码字的对应关系。生成矩阵证明：证明的核心思想是证明，第一个码中任一个码字也是第二个码中的码字；第二个码中任一个码字也是第一个码中的码字。 设在第一个码中，u是信息向量x的码字：则u=xG； 那么在第二个码中，因为

u=xM-1G’=xM-1MG=xG

。所以其是信息向量xM-1的码字。 设在第二个码中，u是信息向量x的码字：则u=xG’； 那么在第一个码中，因为u=

xMG=xMM-1G’=xG’，所以u是信息向量xM的码字。证完

生成矩阵结论2生成矩阵G的第1行是信息向量(1,0,0,…,0)的码字；生成矩阵G的第2行是信息向量(0,1,0,…,0)的码字；…生成矩阵G的第L行是信息向量(0,…,0,0,1)的码字。系统码系统码例：二元(7,4)码生成矩阵如下：是由信息向量(1000)、(0100)、(0010)、(0001)的码字组成的4行。系统码例：二元(5,3)线性分组码的生成矩阵如下

将其进行初等行变换，变成如下模式：系统码定义：D元(N,L)线性分组码的生成矩阵为G=[PL×(N-L),IL]，其中IL是L阶单位阵，PL×(N-L)是(N-L)×L阶矩阵。则称此码为系统码。此时信息向量(x0,x1,…,xL-1)的码字是(u0,u1,…,uN-1)=(x0,x1,…,xL-1)G=((x0,x1,…,xL-1)PL×(N-L),x0,x1,…,xL-1)。码字的后L位恰好是信息向量(x0,x1,…,xL-1)，称为码字的信息位。称码字的前N-L位为码字的一致校验位。系统码校验位信息位生成矩阵校验矩阵C的对偶空间VCV=0V的生成矩阵H是G的校验矩阵V的维数是N-K校验矩阵校验矩阵结论：（1）一个线性分组码有很多一致校验矩阵。一个一致校验矩阵H经过可逆行变换变为H’，

H’是同一个线性分组码的另一个一致校验矩阵。（2）一个N维向量u是一个码字，当且仅当：uHT=全0的N-L维行向量。（3）设一个D元(N,L)线性分组码的生成矩阵G，一致校验矩阵H。则H是一个D元(N,N-L)线性分组码的生成矩阵，G是此码的一致校验矩阵。称这两个码互为对偶码。校验矩阵（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]。生成矩阵和校验矩阵的关系错误图样信道干扰Xm10101010Ym10101011CV错误图样错误图样最小汉明距离译码什么是汉明距离

d(x,y),x,y中分量不同的数目最大似然比译码离散无记忆对称信道最小汉明距离译码最小汉明距离译码最小汉明距离译码准则

给定输出值y，寻找码字u使d(y,u)最小。将输出值y译为码字u译码的最佳性与不足

需要计算大量最小距离举例(7,4)汉明码消息序列码字消息序列码字00000001001000110100010101100111000000010100011110010010001101101001100101100011000101111000100110101011110011011110111111010000111001001101010010110101100000110101011101111111伴随式伴随式结论：（1）当两个错误图样相同时，它们的伴随式相同。即：伴随式s的值仅仅与信道传输错误有关，与输入信道的码字无关。

证明：

s=yHT=(u+e)HT=uHT+eHT=

eHT。（2）两个错误图样的伴随式相同，当且仅当它们的差向量是码字。

证明：设有两个差错向量e(1)和e(2)。e(1)HT=e(2)HT， 当且仅当(e(1)-e(2))HT=全0的N-L维行向量， 当且仅当(e(1)-e(2))是码字。伴随式（3）给定一个差错向量e。则与e具有相同伴随式的所有差错向量恰好是e加上所有码字。即：设s是一个伴随式。以s为伴随式的全体差错向量，就是以s为伴随式的一个差错向量加上全体码字。（4）伴随式s是N-L维行向量，因此有DN-L个不同的伴随式。差错向量e是N维行向量，因此有DN个不同的差错向量。具有相同伴随式的差错向量的个数为DL。DLDN-L=DN。伴随式和错误的关系s≠0,有错误出现S=0e＝0，没有错误e=ci,不可检错误不可检错误概率(7,4)汉明码消息序列码字消息序列码字00000001001000110100010101100111000000010100011110010010001101101001100101100011000101111000100110101011110011011110111111010000111001001101010010110101100000110101011101111111重量分布矢量Ai码中重量为i的码字数目陪集将DN个可能的向量分为DN-L个集合集合中每个向量的伴随式相同这样的集合称为陪集选择陪集中重量最轻的向量作为陪集代表，称为陪集首。陪集结论：对信道的输出向量y，计算伴随式s=yHT，以s为地址查找陪集首e(s)，计算u=y-e(s)。则u就是在所有码字中与y的Hamming距离最小的码字。证明：首先，u=y-

e(s)是码字。这是因为uHT=yHT-

e(s)HT=s-s=全0的N-L维行向量。其次，对任意另一个码字c，(y-

c)HT=yHT-

cHT=yHT=s。这就是说，(y-c)是以s为伴随式的一个差错向量。另一方面，(y-u)=e(s)是以s为伴随式的Hamming重量最小的差错向量。所以w(y-

u)≤w(y-c)，即d(y,

u)≤w(y,c)。证完。译码步骤计算接收矢量的伴随式由伴随式确定陪集首将陪集首作为错误图样eC=v-e标准阵伴随式陪集首陪集例6.1.8

求一致校验矩阵；码字集合；译码预计算（简化计算量）。

显然是系统码。标准阵标准阵信息向量→码字000→000000100→011100010→101010001→110001110→110110101→101101011→011011111→000111伴随式s→陪集首e(s)000→000000100→100000010→010000001→001000011→000100101→000010110→000001111→100100(6,3)码的标准阵陪集首伴随式正确译码概率第l个陪集首的重量重量为i的陪集首的数量分析：设信道的输入为码字u，信道的输出为向量y，差错向量为e=y-u。则（1）检错 问题：检错是如何实现的？ 通过校验矩阵来判断，即以yHT的结果来判定，其本质还是看y是否属于码集w(e)<dmin：因为yHT肯定不是全0的N-L维向量，因而必然可以发现信道传输错误。（原因？）w(e)≥dmin

：因为yHT有时候可以是全0的N-L维向量，所以不一定能发现信道传输错误。（原因？） 结论1：线性分组码的最小距离为dmin则其可以检测所有dmin-1位错误。纠检错能力分析：设信道的输入为码字u，信道的输出为向量y，差错向量为e=y-u。则（2）纠错 问题：纠错是如何实现的？ 通过陪集首来判断，即以标准阵来判定，其本质是通过最小汉明距离来加以判断。w(e)≤[(dmin-1)/2]（下方取整）

：因为按照实际译码准则不会与其它码字产生歧义，因而必然可以发现并纠正信道传输错误。（原因？）纠检错能力证明：（1）当w(e)<dmin，e肯定不是码字（因为最小汉明距离就是最小码重）。所以有yHT=eHT≠全0的N-L维向量。因此可以检错。（2）当w(e)≤[(dmin-1)/2]（下方取整），则y与任意另一个码字c的Hamming距离

d(c,

y)≥d(c,

u)-d(y,u)（三角不等式） ≥dmin-d(y,u)=

dmin-w(e)≥dmin-[(dmin-1)/2]>[(dmin-1)/2]≥w(e)=d(y,u)。因此，所有码字中，u与y的Hamming距离最小。所以按照最小汉明距离译码准则可以译码。证完。纠检错能力分析：设信道的输入为码字u，信道的输出为向量y，差错向量为e=y-u。则（3）超出纠错

当w(e)>[(dmin-1)/2]（下方取整），通过最小汉明距离未必将y译为u（即此时不能保证纠错）。纠检错能力证明：

设信道的输入为码字u，另一个码字c恰好满足d(c,u)=

dmin。输出向量y如下：d(c,u)=

d(c,

y)+d(y,u)；（三角不等式变为等式）w(e)=d(y,u)=[(dmin-1)/2]+1>[(dmin-1)/2]。请注意，这样的输出向量y存在！而且此时d(c,y)=d(c,

u)-d(y,u)=dmin-{[(dmin-1)/2]+1}=dmin-1-[(dmin-1)/2]。纠检错能力d(y,u)=[(dmin-1)/2]+1；

d(c,y)=dmin-1-[(dmin-1)/2]。当dmin是奇数时，d(y,u)=(dmin-1)/2+1，d(c,y)=(dmin-1)/2，故d(c,y)<d(y,u)。当dmin是偶数时，d(y,u)=dmin/2，d(c,y)=dmin/2，故d(c,y)=d(y,u)。这就是说，当dmin是奇数时，将y译为c而不是u；当dmin是偶数时，将y译为c或u都符合最小距离准则。证完。结论： w(e)≤[(dmin-1)/2]

，则e一定是s=eHT的陪集首；如果w(e)>[(dmin-1)/2]

，则e未必是s=eHT的陪集首。纠检错能力最小距离和纠错能力的