《信息论与编码》_第18,19讲_信道编码课件

1、网络网络工程系工程系- -Information Theory and Coding第六章信道编码信道编码赵永斌石家庄铁道大学信息科学与技术学院 2021年12月16日第第18讲讲网络网络工程系工程系- -Information Theory and Coding2回顾l 信道编码信道编码: (N, L)码码。L称为信息长，称为信息长，N称为码长。称为码长。l 译码准则：译码准则：最小后验概率译码准则最小后验概率译码准则最大似然译码最大似然译码最小距离译码最小距离译码l Shannon信道编码定理信道编码定理 给定容量为给定容量为C的离散无记忆信道的离散无记忆信道X,p(x|y),Y，若编码速

2、率若编码速率RC ，则，则R是可达的。是可达的。网络网络工程系工程系- -Information Theory and Coding6.2 线性分组码基础线性分组码基础6.2.1 数学基础数学基础6.2.2 线性分组码概念线性分组码概念6.2.3 线性分组码代数结构线性分组码代数结构6.2.4 线性分组码的一致校验矩阵线性分组码的一致校验矩阵6.2.5 一致校验矩阵与译码一致校验矩阵与译码网络网络工程系工程系- -Information Theory and Coding6.2.1 数学基础数学基础l 有限域有限域 设设D是一个素数。于是字母表是一个素数。于是字母表0, 1, , D-1中的所

3、中的所有字母关于有字母关于(mod D)加法、加法、(mod D)乘法构成了一个代数乘法构成了一个代数结构，称作结构，称作有限域有限域，记作，记作GF(D)=(0, 1, , D-1, (mod D)加法加法, (mod D)乘法乘法)。即即（1）(0, 1, , D-1, (mod D)加法加法) 构成交换群（构成交换群（Abel群）群）。（2）(1, , D-1, (mod D)乘法乘法) 构成交换群（构成交换群（Abel群）。群）。（3）分配率成立：）分配率成立：a(b+c)=ab+ac(mod D)。 注：注： GF(D)上的线性代数完全类似于实数域上的线性代数。上的线性代数完全类似于

4、实数域上的线性代数。网络网络工程系工程系- -Information Theory and Coding6.2.1 数学基础数学基础l有限域上的代数有限域上的代数例：取例：取D=2，则，则GF(2)=(0, 1, (mod2)加法加法, (mod2)乘法乘法)的的运算规则为：运算规则为：0+0=1+1=0，0+1=1， 00=01=0，11=1。方阵方阵 是否可逆？回答是肯定的，因为是否可逆？回答是肯定的，因为01001110101000010010011101网络网络工程系工程系- -Information Theory and Coding6.2.1 数学基础数学基础该方阵的逆矩阵是什么？

5、该方阵的逆矩阵是什么？ 怎样计算？做联合可逆行变换：怎样计算？做联合可逆行变换：1111000111100011011000100111100011011000100100110011011111001000101100011111001000100011011111001100100111011网络网络工程系工程系- -Information Theory and Coding6.2.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

6、，00=01=02=0，11=22=1，12=2。 矩阵矩阵 是不是满行秩的？是不是满行秩的？ 换句话说，此矩阵的三个行向量是不是在域换句话说，此矩阵的三个行向量是不是在域GF(3)上线性无关上线性无关的？再换句话说，能否保证此矩阵的各行的任何非的？再换句话说，能否保证此矩阵的各行的任何非0线性组线性组合都不是全合都不是全0的的4维向量？再换句话说，此矩阵能否通过一维向量？再换句话说，此矩阵能否通过一些可逆行变换变成一个些可逆行变换变成一个“阶梯阵阶梯阵”？ 110121100110网络网络工程系工程系- -Information Theory and Coding6.2.1 数学基础数学基础

7、可逆行变换可逆行变换120011201011011011201011011001121011是满行秩的。011001121011网络网络工程系工程系- -Information Theory and Coding6.2.1 数学基础数学基础例：域例：域GF(D)上的一个上的一个L行行N列的矩阵（列的矩阵（LN阶的矩阵）阶的矩阵）G，设它是满行秩的（当然此时有设它是满行秩的（当然此时有LN）。则变换）。则变换(u1, u2, , uN)=(x1, x2, , xL)G一定是单射一定是单射(即即(x1, x2, , xL)的不同值一定变换为的不同值一定变换为(u1, u2, , uN)的不同值的不

8、同值)。证明证明 设设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)。网络网络工程系工程系- -Information Theory and Coding 6.2.2 线性分组码概念线性分组码概念对随机变量序列对随机变量序列X1X2进

9、行的信道编码为进行的信道编码为(N, L)码：码：(X1X2XL)(U1U2UN)=C(X1X2XL)。这个这个(N, L)码又称为码又称为(N, L)分组码分组码。已经有结论：当已经有结论：当RC/H(X)时存在时存在(N, L)分组码，使得分组码，使得l 信息率信息率(L/N)任意接近任意接近R，l 译码错误的概率任意接近译码错误的概率任意接近0。问题是：怎样构造这样的分组码？这样的分组码的编问题是：怎样构造这样的分组码？这样的分组码的编码、译码计算量会不会太大？（这才是研究分组码码、译码计算量会不会太大？（这才是研究分组码的含义）的含义） 网络网络工程系工程系- -Information

10、 Theory and Coding6.2.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为此码的为此码的生成矩阵生成矩阵。当当D是素数时，分组码可以充分利用有限域是素数时，分组码可以充分利用有限域GF(D)的代数运的代数运算

11、，使得编码和译码更加简便。算，使得编码和译码更加简便。网络网络工程系工程系- -Information Theory and Coding6.2.3 线性分组码的代数结构线性分组码的代数结构性质性质1 不同的信息向量对应不同的码字。不同的信息向量对应不同的码字。（因为变换（因为变换u=xG是单射）是单射）性质性质2 生成矩阵生成矩阵G的第的第1行是信息向量行是信息向量(1, 0, 0, , 0)的码字的码字；生成矩阵生成矩阵G的第的第2行是信息向量行是信息向量(0, 1, 0, , 0)的码字的码字；生成矩阵生成矩阵G的第的第L行是信息向量行是信息向量(0, , 0, 0, 1)的码字的码字。

12、网络网络工程系工程系- -Information Theory and Coding6.2.3 线性分组码的代数结构线性分组码的代数结构性质性质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)是信息向量

13、是信息向量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)的码字。的码字。证完。证完。网络网络工程系工程系- -Information Theory and Coding性质性质3 信息向量信息向量(x1, x2, , xL)的码字是：的码字是：x1数乘数乘G的第的第1行，加行，加x2数乘数乘G的第的第2行，加行，加，加，加xL数乘数乘G的第的第L行。行。 性质性质4 当当u(1)和和u(2)都是码字，都是码字， u(1)+u(2)也是码字。（也是码字。（线性分

14、组码的码字关于线性运算封闭）线性分组码的码字关于线性运算封闭）证明证明 设设 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)的码字。的码字。6.2.3 线性分组码的代数结构线性分组码的代数结构网络网络工程系工程系- -Information Theory and Coding（命题（命题3和命题和命题4告诉我们，一个告诉我们，一个N维向量是维向量是一个码字，

15、当且仅当它是一个码字，当且仅当它是G的第的第1行行第第L行行的线性组合。还告诉我们，线性分组码的的线性组合。还告诉我们，线性分组码的码字集合构成一个线性空间。这个线性空码字集合构成一个线性空间。这个线性空间是几维的？间是几维的？L维的，因为生成矩阵维的，因为生成矩阵G的第的第1行行第第L行恰好是该线性空间的一组基）行恰好是该线性空间的一组基）6.2.3 线性分组码的代数结构线性分组码的代数结构网络网络工程系工程系- -Information Theory and Coding命题命题5 设一个设一个D元元(N, L)线性分组码的生成矩阵为线性分组码的生成矩阵为G。设另一个。设另一个D元元(N,

16、 L)线性分组码的生成矩阵为线性分组码的生成矩阵为G=MG，其中，其中M是是L阶可逆方阵。则两个码的码字阶可逆方阵。则两个码的码字集合完全重合，只是信息向量与码字的对应关系集合完全重合，只是信息向量与码字的对应关系不同。不同。即，如果把线性分组码的生成矩阵即，如果把线性分组码的生成矩阵G做可逆行变换变做可逆行变换变成另一个生成矩阵，则不改变码字集合，只改变成另一个生成矩阵，则不改变码字集合，只改变信息向量与码字的对应关系。信息向量与码字的对应关系。 6.2.3 线性分组码的代数结构线性分组码的代数结构网络网络工程系工程系- -Information Theory and Coding证明证明

17、（要证明，第一个码中任一个码字也是第二个码中的码（要证明，第一个码中任一个码字也是第二个码中的码字；第二个码中任一个码字也是第一个码中的码字）字；第二个码中任一个码字也是第一个码中的码字）设在第一个码中，设在第一个码中，u是信息向量是信息向量x的码字：的码字：u=xG；则在第二个码中，则在第二个码中，u是信息向量是信息向量xM-1的码字：的码字：u=xM-1MG= xM-1G。设在第二个码中，设在第二个码中，u是信息向量是信息向量x的码字：的码字：u=xG；则在第一个码中，则在第一个码中，u是信息向量是信息向量xM的码字：的码字：u=xMM-1G= xMG。证完。证完。 6.2.3 线性分组码

18、的代数结构线性分组码的代数结构网络网络工程系工程系- -Information Theory and Coding线性分组码的特例：系统码线性分组码的特例：系统码定义：定义：D D元元( (N N, , L L) )线性分组码的生成矩阵为线性分组码的生成矩阵为G G=P PL L( (N N- -L L) ), , I IL L ，其中其中I IL L是是L L阶单位阵，阶单位阵， P PL L( (N N- -L L) )是是( (N N- -L L) )L L阶矩阵。则称此阶矩阵。则称此码为系统码。此时信息向量码为系统码。此时信息向量( (x x1 1, , x x2 2, , , , x

19、 xL L) )的码字是的码字是( (u u1 1, , u u2 2, , , , u uN N)=()=(x x1 1, , x x2 2, , , , x xL L) )G G=(=(x x1 1, , x x2 2, , , , x xL L) ) P PL L( (N N- -L L) ), , x x1 1, , x x2 2, , , , x xL L) )。码字的后码字的后L L位恰好是信息向量位恰好是信息向量( (x x1 1, , x x2 2, , , , x xL L) )，称为码字，称为码字的信息位。称码字的前的信息位。称码字的前N-LN-L位为码字的一致校验位。位为

20、码字的一致校验位。6.2.3 线性分组码的代数结构线性分组码的代数结构网络网络工程系工程系- -Information Theory and Coding此二元此二元(7, 4)码是线性分组码，生成矩阵码是线性分组码，生成矩阵G是由是由信息向量信息向量(1000)、(0100)、(0010)、(0001)的码字的码字组成的组成的4行，该码是系统码行，该码是系统码1000101010011100101100001011G6.2.3 线性分组码的代数结构线性分组码的代数结构网络网络工程系工程系- -Information Theory and Coding二元二元(5, 3)线性分组码的生成矩阵是

21、线性分组码的生成矩阵是 111110110000111G的生成矩阵。码变换后，变成一个系统将生成矩阵经过可逆行该码不是系统码。但是100110101100111100110110000111111110110000111合相同。与一个系统码的码字集因此，该码的码字集合6.2.3 线性分组码的代数结构线性分组码的代数结构网络网络工程系工程系- -Information Theory and Coding6.2.4 线性分组码的一致校验矩阵线性分组码的一致校验矩阵定理对于定理对于D元元(N, L)线性分组码的生成矩阵线性分组码的生成矩阵G（ G 是是LN阶矩阵），必存在一个阶矩阵），必存在一个(N

22、-L)N阶矩阵阶矩阵H，（1）H是满行秩的；是满行秩的；（2）GHT= OL(N-L)。（HT是是H的转置矩阵，的转置矩阵， OL(N-L)是全是全0的的L(N-L) 阶矩阶矩阵。不证明。这方面的知识属于有限域上的线性代阵。不证明。这方面的知识属于有限域上的线性代数）数）定义定义 由上述定理所描述的矩阵由上述定理所描述的矩阵H称为称为D元元(N, L)线性线性分组码的分组码的一致校验矩阵一致校验矩阵。 网络网络工程系工程系- -Information Theory and Coding有以下的性质。有以下的性质。（1）一个线性分组码有很多一致校验矩阵。一个一致）一个线性分组码有很多一致校验矩阵

23、。一个一致校验矩阵校验矩阵H经过可逆行变换变为经过可逆行变换变为H， H是同一个线是同一个线性分组码的另一个一致校验矩阵。性分组码的另一个一致校验矩阵。（2）一个）一个N维向量维向量u是一个码字，当且仅当：是一个码字，当且仅当：uHT=全全0的的N-L维行向量。维行向量。（3）设一个）设一个D元元(N, L)线性分组码的生成矩阵线性分组码的生成矩阵G，一致，一致校验矩阵校验矩阵H。则。则H是一个是一个D元元(N, N-L)线性分组码的线性分组码的生成矩阵，生成矩阵，G是此码的一致校验矩阵。称这两个码是此码的一致校验矩阵。称这两个码互为互为对偶码对偶码。 6.2.4 线性分组码的一致校验矩阵线性

24、分组码的一致校验矩阵网络网络工程系工程系- -Information Theory and Coding（怎样由生成矩阵（怎样由生成矩阵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, -PTT=P-P=OL(N-L)。证完。证

25、完。 （5）设）设D元元(N, L)线性分组码的生成矩阵经过可逆行线性分组码的生成矩阵经过可逆行变换后变为变换后变为P, IL，则一致校验矩阵也可以取为，则一致校验矩阵也可以取为H=IN-L, -PT。6.2.4 线性分组码的一致校验矩阵线性分组码的一致校验矩阵网络网络工程系工程系- -Information Theory and Coding线性分组码的纠错译码准则线性分组码的纠错译码准则定义定义 (已知已知)一个一个N维向量维向量u的的Hamming重量重量定义为它定义为它的对应位置值等于的对应位置值等于0的位数。记为的位数。记为w(u);两个两个N维向维向量量u(1)和和u(2)的的Ha

26、mming距离距离定义为它们的对应位定义为它们的对应位置值不相同的位数。记为置值不相同的位数。记为d(u(1), u(2)。显然有以下的结论显然有以下的结论d(u(1), u(2)=w(u(1)-u(2)。三角不等式：三角不等式： d(u(1), u(3)d(u(1), u(2)+ d(u(2), u(3)。或或w(u(1)-u(3) w(u(1)-u(2)+ w(u(2)-u(3)。6.2.5 一致校验矩阵与译码一致校验矩阵与译码网络网络工程系工程系- -Information Theory and Coding设设GF(D)上的上的D元元(N, L)线性分组码线性分组码u=xG。将。将u输

27、入输入信道；信道的输出为信道；信道的输出为y。使用最小距离准则：给定输出值使用最小距离准则：给定输出值y，寻找码字，寻找码字u使使d(y, u)最小。将输出值最小。将输出值y译为码字译为码字u。直接使用最小距离准则的困难：需要将直接使用最小距离准则的困难：需要将DL个码字与个码字与y的的Hamming距离进行对比，才能找到码字距离进行对比，才能找到码字u使使d(y, u)最小。计算量大。最小。计算量大。 6.2.5 一致校验矩阵与译码一致校验矩阵与译码网络网络工程系工程系- -Information Theory and Coding实用纠错译码算法的预备知识：差错向量和伴随式实用纠错译码算法

28、的预备知识：差错向量和伴随式定义定义 设：信道的输入为码字设：信道的输入为码字u；信道的输出为向量；信道的输出为向量y。称向。称向量量e=y- u为为差错向量差错向量，或，或差错图样差错图样。（请注意，此时。（请注意，此时y=u+e；向量的；向量的加减法是对应分量的加减法是对应分量的(modD) 加减法）加减法）定义定义 设信道的输出为设信道的输出为y。记。记s=yHT其中其中H是一致校验矩阵。称是一致校验矩阵。称N-L维行向量维行向量s为为y的的伴随式伴随式。 有以下的结论。有以下的结论。 6.2.5 一致校验矩阵与译码一致校验矩阵与译码网络网络工程系工程系- -Information Th

29、eory and Coding（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维行向

30、量，维行向量，当且仅当当且仅当(e(1)-e(2)是码字。是码字。证完。证完。6.2.5 一致校验矩阵与译码一致校验矩阵与译码网络网络工程系工程系- -Information Theory and Coding 6.3 线性分组码线性分组码（3）给定一个差错向量）给定一个差错向量e。则与。则与e具有相同伴随式的所有差错具有相同伴随式的所有差错向量恰好是向量恰好是e加上所有码字。加上所有码字。换句话说。设换句话说。设s是一个伴随式。以是一个伴随式。以s为伴随式的全体差错向量，为伴随式的全体差错向量， 就是以就是以s为伴随式的一个差错向量加上全体码字。为伴随式的一个差错向量加上全体码字。（4）伴随

31、式）伴随式s是是N-L维行向量，因此有维行向量，因此有DN-L个不同的伴随式。个不同的伴随式。差错向量差错向量e是是N维行向量，因此有维行向量，因此有DN个不同的差错向量。具个不同的差错向量。具有相同伴随式的差错向量的个数为有相同伴随式的差错向量的个数为DL。DLDN-L=DN。 定义定义 在以在以s为伴随式的全体差错向量中，为伴随式的全体差错向量中，Hamming重量最小重量最小的差错向量称为的差错向量称为s的陪集首的陪集首，记为，记为e(s)。（s可能有不止一个可能有不止一个Hamming重量最小的差错向量，任意选择重量最小的差错向量，任意选择一个作为陪集首一个作为陪集首e(s)即可）即可）网络网络工程系工程系- -Information Theory and Coding（5）对信道的输出向量）对信道的输出向量y，计算伴随式计算伴随式s=yHT，以，以s为地址查为地址查找陪集首找陪集首e(s)，计算，计算u=y- e(s)。则则u就是在所有码字中与就是在所有码字中与y的的Hamming距离最小的码字。距离最小的码字。证明证明