《信息论与编码》_第20讲_信道编码

1、网络网络工程系工程系- -Information Theory and Coding第六章信道编码信道编码赵永斌石家庄铁道大学信息科学与技术学院 2021年12月16日第第20讲讲网络网络工程系工程系- -Information Theory and Coding2回顾l线性分组码码字间的关系l生成矩阵l一致校验矩阵与生成矩阵的关系错误图样与伴随式l陪集与译码网络网络工程系工程系- -Information Theory and Coding6.3 线性分组码原理线性分组码原理6.3.1 汉明距离与汉明重量汉明距离与汉明重量6.3.2 汉明距离与汉明重量间关系汉明距离与汉明重量间关系6.3.3

2、 线性分组码译码线性分组码译码6.3.4 检错与纠错检错与纠错网络网络工程系工程系- -Information Theory and Coding6.3.1 汉明距离、汉明重量汉明距离、汉明重量l最小最小Hamming距离距离线性分组码的最小线性分组码的最小Hamming距离定义距离定义为两个不同码字的为两个不同码字的Hamming距离的最距离的最小值，记为小值，记为dmin。区别：区别：汉明距离汉明距离与与最小最小汉明距离汉明距离网络网络工程系工程系- -Information Theory and Coding6.3.1 汉明距离、汉明重量汉明距离、汉明重量l最小最小Hamming重量重量

3、线性分组码的最小线性分组码的最小Hamming重量定义为非全重量定义为非全0码字的码字的Hamming重量的最小值，记为重量的最小值，记为wmin。区别：区别：汉明重量汉明重量与与最小最小汉明重量汉明重量网络网络工程系工程系- -Information Theory and Coding6.3.2 汉明距离与汉明重量关系汉明距离与汉明重量关系定理定理1 线性分组码的最小汉明距离等于最小汉明重线性分组码的最小汉明距离等于最小汉明重量，即量，即dmin=wmin。证明：设两个不同的码字证明：设两个不同的码字u(1)和和u(2)，使得，使得dmin=d(u(1) , u(2)=w(u(1)-u(2)

4、。注意到注意到(u(1)-u(2)是一个非全是一个非全0码字，所以码字，所以dminwmin。设一个非全设一个非全0码字码字u，使得，使得wmin=w(u)=w(u-全全0码字码字)=d(u, 全全0码字码字)。所以所以dminwmin。证完。证完。 网络网络工程系工程系- -Information Theory and Coding6.3.2 汉明距离与汉明重量关系汉明距离与汉明重量关系定理定理2 设信道的输入为码字设信道的输入为码字u，信道的输出为向量，信道的输出为向量y，差错向量为，差错向量为e=y-u。则。则（1）当）当w(e)dmin，yHT肯定不是全肯定不是全0的的N-L维向量维向

5、量，因而发现信道传输错误。，因而发现信道传输错误。（2）当）当w(e)(dmin-1)/2（下方取整），由上述实（下方取整），由上述实用纠错译码算法肯定将用纠错译码算法肯定将y译为真正的原发码字译为真正的原发码字u，而不会将，而不会将y译为其它码字。译为其它码字。 网络网络工程系工程系- -Information Theory and Coding6.3.2 汉明距离与汉明重量关系汉明距离与汉明重量关系证明证明（1）当）当w(e)(dmin-1)/2w(e)=d(y,u)。因此，所有码字中因此，所有码字中,u与与y的的Hamming距离最小。距离最小。网络网络工程系工程系- -Informat

6、ion Theory and Coding6.3.3 线性分组码译码线性分组码译码定理定理1 设信道的输入为码字设信道的输入为码字u，信道的输出为向量，信道的输出为向量y，差错向量为，差错向量为e=y-u。当。当w(e)(dmin-1)/2（下方取（下方取整），由上述实用纠错译码算法未必将整），由上述实用纠错译码算法未必将y译为译为u。证明证明 设信道的输入为码字设信道的输入为码字u，设另一个码字，设另一个码字c恰好满恰好满足足d(c, u)= dmin。网络网络工程系工程系- -Information Theory and Coding6.3.3 线性分组码译码线性分组码译码设输出向量是这样

7、的设输出向量是这样的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。网络网络工程系工程系- -Information Theory and Coding当当dmin是奇数时，是奇数时，d(y,u

8、)=(dmin-1)/2+1，d(c, y)= (dmin-1)/2，故故d(c, y)(dmin-1)/2 ，则未必，则未必e(s)=e，因而未必，因而未必c=u。换句话说，如果换句话说，如果w(e)(dmin-1)/2 ，则，则e一定是一定是s=eHT的陪的陪集首；如果集首；如果w(e)(dmin-1)/2 ，则，则e未必是未必是s=eHT的陪集的陪集首。首。网络网络工程系工程系- -Information Theory and Coding6.3.3 线性分组码译码线性分组码译码l说明说明 设信道真正的输入码字为设信道真正的输入码字为u，信道的输，信道的输出向量为出向量为y，真正的差错向

9、量为，真正的差错向量为e=y-u。网络网络工程系工程系- -Information Theory and Coding6.3.4 检错与纠错检错与纠错定理定理 设真正的差错向量为设真正的差错向量为e。w(e)t时肯定正确译时肯定正确译码，当且仅当码，当且仅当dmin2t+1。推论推论 设真正的差错向量为设真正的差错向量为e。肯定正确译码肯定正确译码的概率的概率为为 2/ ) 1(0minmin)1 ()2/ ) 1()(dttNttNppCdewP网络网络工程系工程系- -Information Theory and Codingl 说明说明dmin是线性分组码纠错能力的一个指标。是线性分组码

10、纠错能力的一个指标。dmin越越大，大，(dmin-1)/2就越大，就越大，肯定正确译码的肯定正确译码的概率也越概率也越大。当大。当N比比L大得越多，码字在所有大得越多，码字在所有N维向量中占的维向量中占的比例越小，越容易使得比例越小，越容易使得dmin大。问题是，当大。问题是，当N和和L都都确定时，如何设计码使得确定时，如何设计码使得dmin大。大。l 纠正一种误解：纠正一种误解：dmin越大，越大，肯定正确译码肯定正确译码的概率越大。决不能说：的概率越大。决不能说：dmin越大，越大，正确译码正确译码的概率越大。（怎么回事？）的概率越大。（怎么回事？）6.3.4 检错与纠错检错与纠错网络网

11、络工程系工程系- -Information Theory and Codingl “肯定正确译码肯定正确译码”=w(e)(dmin-1)/2； “不能肯定正确译码不能肯定正确译码”=w(e)(dmin-1)/2。注意：注意：P(肯定正确译码肯定正确译码)+ P(不能肯定正确译码不能肯定正确译码)=1。这就是说，这就是说，“肯定正确译码肯定正确译码”的概率越大，的概率越大，“不能不能肯定正确译码肯定正确译码” 的概率越小。的概率越小。“正确译码正确译码”=“肯定正确译码肯定正确译码”“不能肯定正确译不能肯定正确译码中的一部分码中的一部分”。6.3.4 检错与纠错检错与纠错网络网络工程系工程系-

12、-Information Theory and Coding6.3.4 检错与纠错检错与纠错 一个线性分组码，一个线性分组码，dmin小，肯定正确译小，肯定正确译码的概率小，但码的概率小，但“不能肯定正确译码中的不能肯定正确译码中的一部分一部分” 的概率很大，则正确译码的概率的概率很大，则正确译码的概率也可能很大。也可能很大。网络网络工程系工程系- -Information Theory and Codingl“肯定正确译码肯定正确译码”=w(e)(dmin-1)/2； “不能肯定正确译码不能肯定正确译码”=w(e)(dmin-1)/2。注意：注意：P(肯定正确译码肯定正确译码)+ P(不能肯

13、定正确译码不能肯定正确译码)=1。这就是说，这就是说，“肯定正确译码肯定正确译码”的概率越大，的概率越大，“不能肯定正确译码不能肯定正确译码” 的概率越小。的概率越小。6.3.4 检错与纠错检错与纠错网络网络工程系工程系- -Information Theory and Coding6.3.4 检错与纠错检错与纠错练习练习回答“肯定正确译码”、“不能肯定正确译码”、“肯定不能正确译码”。（1）w(e)(dmin-1)/2；（2）w(e)(dmin-1)/2；（3）e是一个码字；（4）e不是一个码字。网络网络工程系工程系- -Information Theory and Coding例例 求一致

14、校验矩阵；码字集合；译码预计算（简化计算量）。求一致校验矩阵；码字集合；译码预计算（简化计算量）。 显然是系统码。显然是系统码。100011010101001110G011100101010110001H网络网络工程系工程系- -Information Theory and Coding信息向量码字000 000000100 011100010 101010001 110001110 110110101 101101011 011011111 000111伴随式s陪集首e(s)000 000000100 100000010 010000001 001000110 000100101 00001

15、0011 000001111 100100网络网络工程系工程系- -Information Theory and Coding观察有，观察有，dmin=3；(dmin-1)/2=1。当当真正的差错向量的真正的差错向量的Hamming重量不超过重量不超过1时，时，肯定正确译码；肯定正确译码；当当真正的差错向量的真正的差错向量的Hamming重量超过重量超过1时，未时，未必正确译码。必正确译码。网络网络工程系工程系- -Information Theory and Coding肯定正确译码肯定正确译码的概率为的概率为(1-p)6+6(1-p)5p。正确译码正确译码的概率为的概率为(1-p)6+6(1-p)5p+(1-p)4p2。若若p=10-2，则，则(1-p)6=0.9415； (1-p)6+6(1-p)5p=0.9986； (1-p)6+6(1-p)5p+(1-p)4p2=0.9987。网络网络工程系工程系- -Information Theory and Coding设信道的输出