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

《信息论与编码》_第20讲_信道编码第一页，共26页。2回顾线性分组码码字间的关系生成矩阵一致校验矩阵与生成矩阵的关系错误图样与伴随式陪集与译码第二页，共26页。6.3线性分组码原理6.3.1汉明距离与汉明重量6.3.2汉明距离与汉明重量间关系6.3.3线性分组码译码6.3.4检错与纠错第三页，共26页。6.3.1汉明距离、汉明重量最小Hamming距离

线性分组码的最小Hamming距离定义为两个不同码字的Hamming距离的最小值，记为dmin。 区别：汉明距离与最小汉明距离第四页，共26页。6.3.1汉明距离、汉明重量最小Hamming重量 线性分组码的最小Hamming重量定义为非全0码字的Hamming重量的最小值，记为wmin。区别：汉明重量与最小汉明重量第五页，共26页。6.3.2汉明距离与汉明重量关系定理1线性分组码的最小汉明距离等于最小汉明重 量，即dmin=wmin。证明：设两个不同的码字u(1)和u(2)，使得dmin=d(u(1),u(2))=w(u(1)-u(2))。注意到(u(1)-u(2))是一个非全0码字，所以dmin≥wmin。设一个非全0码字u，使得wmin=w(u)=w(u-全0码字)=d(u,全0码字)。所以dmin≤wmin。 证完。第六页，共26页。6.3.2汉明距离与汉明重量关系定理2设信道的输入为码字u，信道的输出为向量y，差错向量为e=y-u。则（1）当w(e)<dmin，yHT肯定不是全0的N-L维向量，因而发现信道传输错误。（2）当w(e)≤[(dmin-1)/2]（下方取整），由上述实用纠错译码算法肯定将y译为真正的原发码字u，而不会将y译为其它码字。第七页，共26页。6.3.2汉明距离与汉明重量关系证明（1）当w(e)<dmin，e肯定不是码字。 因此yHT=eHT≠全0的N-L维向量。注：原因？第八页，共26页。6.3.2汉明距离与汉明重量关系（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距离最小。第九页，共26页。6.3.3线性分组码译码定理1设信道的输入为码字u，信道的输出为向量y，差错向量为e=y-u。当w(e)>[(dmin-1)/2]（下方取整），由上述实用纠错译码算法未必将y译为u。证明设信道的输入为码字u，设另一个码字c恰好满足d(c,u)=dmin。第十页，共26页。6.3.3线性分组码译码设输出向量是这样的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]。第十一页，共26页。当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都符合最小距离准则。说明 设信道真正的输入码字为u，信道的输出向量为y，真正的差错向量为e=y-u。第十二页，共26页。6.3.3线性分组码译码采用实用纠错译码算法： 接收y→计算伴随式s=yHT→以s为地址查找e(s)→计算c=y-e(s)→认为陪集首e(s)就是差错向量；认为c就是输入码字。由定理得，如果w(e)≤[(dmin-1)/2]

，则e(s)=e，因而c=u。 如果w(e)>[(dmin-1)/2]

，则未必e(s)=e，因而未必c=u。换句话说，如果w(e)≤[(dmin-1)/2]

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

，则e未必是s=eHT的陪集首。第十三页，共26页。6.3.3线性分组码译码说明设信道真正的输入码字为u，信道的输出向量为y，真正的差错向量为e=y-u。第十四页，共26页。6.3.4检错与纠错定理

设真正的差错向量为e。w(e)≤t时肯定正确译 码，当且仅当dmin≥2t+1。推论设真正的差错向量为e。肯定正确译码的概率为第十五页，共26页。说明

dmin是线性分组码纠错能力的一个指标。dmin越大，[(dmin-1)/2]就越大，肯定正确译码的概率也越大。当N比L大得越多，码字在所有N维向量中占的比例越小，越容易使得dmin大。问题是，当N和L都确定时，如何设计码使得dmin大。纠正一种误解： dmin越大，肯定正确译码的概率越大。决不能说：dmin越大，正确译码的概率越大。（怎么回事？）6.3.4检错与纠错第十六页，共26页。“肯定正确译码”={w(e)≤[(dmin-1)/2]}；“不能肯定正确译码”={w(e)>[(dmin-1)/2]}。注意： P(肯定正确译码)+P(不能肯定正确译码)=1。 这就是说，“肯定正确译码”的概率越大，“不能肯定正确译码”的概率越小。“正确译码”=“肯定正确译码”∪“不能肯定正确译码中的一部分”。6.3.4检错与纠错第十七页，共26页。6.3.4检错与纠错 一个线性分组码，dmin小，肯定正确译码的概率小，但“不能肯定正确译码中的一部分”的概率很大，则正确译码的概率也可能很大。第十八页，共26页。“肯定正确译码”={w(e)≤[(dmin-1)/2]}；“不能肯定正确译码”={w(e)>[(dmin-1)/2]}。注意： P(肯定正确译码)+P(不能肯定正确译码)=1。 这就是说，“肯定正确译码”的概率越大，“不能肯定正确译码”的概率越小。6.3.4检错与纠错第十九页，共26页。6.3.4检错与纠错练习回答“肯定正确译码”、“不能肯定正确译码”、“肯定不能正确译码”。（1）w(e)≤[(dmin-1)/2]；（2）w(e)>[(dmin-1)/2]；（3）e是一个码字；（4）e不是一个码字。第二十页，共26页。例

求一致校验矩阵；码字集合；译码预计算（简化计算量）。显然是系统码。第二十一页，共26页。信息向量→码字000→000000100→011100010→101010001→110001110→110110101→101101011→011011111→000111伴随式s→陪集首e(s)000→000000100→100000010→010000001→001000110→000100101→000010011→000001111→100100第二十二页，共26页。观察有，dmin=3；[(dmin-1)/2]=1。当 真正的差错向量的Hamming重量不超过1时，肯定正确译码；当 真正的差错向量的Hamming重量超过1时，未必正确译码。第二十三页，共26页。肯定正确译码的概率为(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)