编码理论第3章

《编码理论第3章》由会员分享，可在线阅读，更多相关《编码理论第3章（43页珍藏版）》请在文档大全上搜索。

1、v分组码：分组码：将消息序列分组进行编码将消息序列分组进行编码v在分组码中，二元信息序列被分成长度固定的一在分组码中，二元信息序列被分成长度固定的一组组消息；每组组组消息；每组消息消息u有有k个信息位，共有个信息位，共有2k个不个不同的消息同的消息v编码器按照一定规则将每个输入消息编码器按照一定规则将每个输入消息u变换成二变换成二元元n重重v，nk，这个二元，这个二元n重重v称作消息称作消息u的的码字码字或码矢。所有或码矢。所有2k个码字组成的集合称作是分组码个码字组成的集合称作是分组码v线性分组码：线性分组码：具有线性性质的分组码具有线性性质的分组码v定义：定义：长为长为n，有，有2k个码字

2、的分组码，当且仅当个码字的分组码，当且仅当其其2k个码字构成个码字构成GF(2)上所有上所有n重矢量空间的一个重矢量空间的一个k维子空间时，称作维子空间时，称作线性线性(n,k)分组码分组码message（0 0 0 0）（1 0 0 0）（0 1 0 0）（1 1 0 0）（0 0 1 0）（1 0 1 0）（0 1 1 0）（1 1 1 0）（0 0 0 1）（1 0 0 1）（0 1 0 1）（1 1 0 1）（0 0 1 1）（0 1 1 1）（1 1 1 1）Code words（0 0 0 0 0 0 0）（1 1 0 1 0 0 0）（0 1 1 0 1 0 0）（1 0 1 1

3、 1 0 0）（1 1 1 0 0 1 0）（0 0 1 1 0 1 0）（1 0 0 0 1 1 0）（0 1 0 1 1 1 0）（1 0 1 0 0 0 1）（0 1 1 1 0 0 1）（1 1 0 0 1 0 1）（0 0 0 1 1 0 1）（0 1 0 0 0 1 1）（0 0 1 0 1 1 1）（1 1 1 1 1 1 1）v因为线性因为线性(n,k)分组码分组码C是一个是一个k维子空间，所以在码维子空间，所以在码C中中能找到能找到k个线性独立的码字个线性独立的码字g0, g1, gk-1,使得使得C中的每个中的每个码字码字v都是这都是这k个码字的一种线性组合，即个码字的一种

4、线性组合，即v=u0g0+u1g1+uk-1gk-1v将这将这k个线性独立的码字作为行，得到个线性独立的码字作为行，得到kn阶矩阵阶矩阵v此矩阵称为码此矩阵称为码C的的生成矩阵生成矩阵。线性线性(n,k)分组码任何分组码任何k个线个线性独立的码字都可以用来构成性独立的码字都可以用来构成码码C的生成矩阵的生成矩阵111110111110100100110nkkknnkggggggggggggGv如果本章如果本章PPT第第3页的表格所表示的线性分页的表格所表示的线性分组码，有如下的生成矩阵组码，有如下的生成矩阵10001010100111001011000010113210ggggG)000110

5、1(10113210ggggvv若若u=(1101)，则，则v线性系统分组码：线性系统分组码：若若(n,k)线性分组码线性分组码C的生成矩的生成矩阵形如阵形如G=P Ik( (或或G=Ik P) )，此时称，此时称C为线性系为线性系统分组码。此时，每个码字都可以被分成两个部统分组码。此时，每个码字都可以被分成两个部分，即消息部分和冗余部分分，即消息部分和冗余部分10000100001000011, 11 , 10 , 11, 221121, 111101, 00100110knkkkknknknkkppppppppppppIPgggGv关于线性系统分组码，对应于消息关于线性系统分组码，对应于消

6、息u=(u0, u1, uk-1)的码的码字是字是v=(v0, v1, vn-1)=uG=uP Ik，即，即 vn-k+i=ui , 0ik-1, vj=u0P0j+u1P1j+uk-1Pk-1j, 0jn-k-1 上面两个式子正好反映系统的组成特性，最后这上面两个式子正好反映系统的组成特性，最后这n-k个方个方程称为码程称为码C的的一致校验方程一致校验方程1000010000100001,1, 11 , 10 , 11, 221121, 111101, 00100110knkkkknknknkppppppppppppuuuGuvv定义：定义：与与(n,k)线性分组码线性分组码C的生成矩阵的生

7、成矩阵G相对应相对应有一个有一个(n-k)n阶矩阵阶矩阵H，它的，它的n-k个行是码个行是码C的的对偶空间的一组基底，该矩阵对偶空间的一组基底，该矩阵H称为码称为码C的的一致一致校验矩阵校验矩阵v因此，一个因此，一个n重重v是由是由G生成的码中的码字，当且生成的码中的码字，当且仅当仅当vHT=0v对偶码：对偶码：以以H为生成矩阵得到的为生成矩阵得到的(n,n-k)码称为码码称为码C的的对偶码对偶码，记为，记为Cdv若码若码C的生成矩阵具有系统形式的生成矩阵具有系统形式G=P Ik，则其，则其一致校验矩阵形如一致校验矩阵形如H=In-k PTv定理：定理：如果线性码如果线性码C是是H矩阵的零化空

8、间，矩阵的零化空间，则对每一个重量为则对每一个重量为w的码矢，的码矢，H中有相应中有相应的的w列线性相关。反之，列线性相关。反之，H中若有中若有w列线性列线性相关，那么就有相应的重量为相关，那么就有相应的重量为w的一个码的一个码矢矢0,12121niiiTnnThvhhhvvvvHv(7,4)线性码的生成矩阵和一致校验矩阵线性码的生成矩阵和一致校验矩阵100111001001110011101,1011000111010011000100110001HGv设设(n,k)线性分组码线性分组码C的生成矩阵为的生成矩阵为G，其校验矩，其校验矩阵为阵为H，令，令v=(v0, v1, vn-1)是经有扰

9、信道传送的是经有扰信道传送的码字，码字，r=(r0, r1, rn-1)是信道输出端的接收矢量。是信道输出端的接收矢量。称矢量和称矢量和e=v+r=( (e0, e1, en-1) )为为错误矢量错误矢量v伴随式：伴随式：当接收到当接收到r后，译码器计算下述后，译码器计算下述n-k重重S=rHT =(s0, s1, sn-k-1)，称，称S为为r的伴随式的伴随式v当且仅当是一个码字当且仅当是一个码字(即无传输错误即无传输错误)时有时有S=0，否则错误矢量本身就是一个码字，此时出现了不否则错误矢量本身就是一个码字，此时出现了不可检错误。只要码可检错误。只要码C设计适当，就几乎不会出现设计适当，就

10、几乎不会出现不可检错误。不可检错误。v根据根据伴随式定义，伴随式定义， S=rHT =(v+e)HT=vHT+eHT=eHT，展开后，有，展开后，有v从上式容易看出，从上式容易看出，伴随式是错误图样的组合伴随式是错误图样的组合，即伴随式包含了一定程度的错误图样信息，因即伴随式包含了一定程度的错误图样信息，因而可以用来纠错而可以用来纠错伴随式纠错伴随式纠错1, 111, 111,0111 , 1111101110, 111010000knknknknknknknknknknknknknknpepepeespepepeespepepeesv上述方程有上述方程有2k个解，即，对同一个伴随式，个解，即

11、，对同一个伴随式，存在存在2k个可能的错误图样，因此上述方程个可能的错误图样，因此上述方程虽然包含错误图样的信息，但是实际应用虽然包含错误图样的信息，但是实际应用起来纠错困难。实际中的纠错，都是如何起来纠错困难。实际中的纠错，都是如何有效地从这些错误图样中选取真正的错误有效地从这些错误图样中选取真正的错误图样，从而得到正确的发送矢量。图样，从而得到正确的发送矢量。对于对于BSC信道，最可能的错误图样是非零数字信道，最可能的错误图样是非零数字最少的那个最少的那个v考虑某考虑某(7,4)码，令码，令v=(1001011)是发送码字，是发送码字，r=(1001001)是接收矢量，收到是接收矢量，收到