《信息理论与编码》课程教学资源（复习小结）第五章 有噪信道编码

第5章基本概念1.译码规则F：F是从输出符号集合B到输入符号集合A的映射，即F(b,)=a,eA, j=1,2...2.平均译码错误概率或平均差错率P：P=P(6)P(e1b,)=P(b)(1-P[F(b)16)])j=lj=l3.最佳译码规则：使P达到最小的译码规则。4.两种典型的译码规则（1）最大后验概率译码规则：F(b,)=a,EA, b, EBHP(a,[b,)≥ P(a, [b,), a, E A最大后验概率译码规则可使P达到最小，因此是最佳译码规则。（2）极大似然译码规则：F(b,)=a,EA, b,EBFP(b, [a,)≥P(b,la,), a, E A一般来说，极大似然译码规则不是最佳译码规则，但方便实用。当输入等概时，极大似然译码规则与最大后验概率译码规则等价，也是最佳译码规则。5.汉明距离：两个等长符号序列x和之间的汉明距离D（x），是x与之间对应位置上不同符号的个数。汉明距离D（x，）满足如下性质（距离公理）：（1）非负性：D(X，)≥0，当且仅当X=时等号成立；(2）对称性：D(X,)=D(,x);(3）三角不等式：D(x,)+D(三,)≥D(x,)。6.汉明重量W(x)：W(X)= D(X,ON)7.码C的最小码间距离：dmn =min[D(c,c,)]C,*c, C,C,EC8.最小（汉明）距离译码规则：F(β,)=ceC,β,eBNFD(c,β,)=min[D(c,β)], c, ECc AN最小距离译码规则可在一般信道中采用，但不一定与极大似然译码规则等价，只有对于二元对称信道（p<1/2），它才与极大似然译码规则等价，并且当输入等概时是最佳的。9.平均差错率都可用汉明距离表示：1PlpGi)pIN-DG D)P =1-B.IcMJM410.有噪信道编码定理（香农第二定理）若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R<C，就一定能找到一种信道编码方法，使得码长N足够大时，平均差错率P任意接近于零。11.Fano不等式1

1 第 5 章基本概念 1. 译码规则 F ： F 是从输出符号集合 B 到输入符号集合 A 的映射，即 * ( ) Fb a A j j = ∈ ， j s =1, 2,. 2. 平均译码错误概率或平均差错率 Pe ： { } 1 1 ( ) ( | ) ( ) 1 ( )| s s e j j j j j j j P Pb Pe b Pb P Fb b = = = = −   ∑ ∑   3. 最佳译码规则：使 Pe 达到最小的译码规则。 4. 两种典型的译码规则 （1）最大后验概率译码规则： * * () , : ( | ) ( | ), jj j jj ij i Fb a A b B F Pa b Pa b a A  =∈ ∈   ∈  ≥ 最大后验概率译码规则可使 Pe 达到最小，因此是最佳译码规则。 （2）极大似然译码规则： * * () , : ( | ) ( | ), jj j j j ji i Fb a A b B F Pb a Pb a a A   =∈ ∈   ∈  ≥ 一般来说，极大似然译码规则不是最佳译码规则，但方便实用。当输入等概时，极大似然译 码规则与最大后验概率译码规则等价，也是最佳译码规则。 5. 汉明距离：两个等长符号序列 x 和 y 之间的汉明距离 Dxy (, ) ，是 x 与 y 之间对应 位置上不同符号的个数。 汉明距离 Dx y (, ) 满足如下性质（距离公理）： （1）非负性： Dxy (, ) 0 ≥ ，当且仅当 x y = 时等号成立； （2）对称性： Dx y Dyx (, ) (,) = ； （3）三角不等式： Dxz Dz y Dx y (,) (, ) (, ) + ≥ 。 6. 汉明重量W x( ) ： () (, ) Wx Dx = ON 7. 码C 的最小码间距离： min min ( , ) , ij i j ij d Dc c c c c c C =   ≠ ∈   8. 最小（汉明）距离译码规则： * * () , : ( , ) min ( , ) , N jj j N j j ij i F cC B F Dc Dc c C A β β β β  =∈ ∈    =   ∈ ⊂    最小距离译码规则可在一般信道中采用，但不一定与极大似然译码规则等价，只有对于二元 对称信道（ p < 1 2 ），它才与极大似然译码规则等价，并且当输入等概时是最佳的。 9. 平均差错率都可用汉明距离表示： * * 1 1 * ( , ) [ ( , )] 1 |1 Dc N Dc j j j j e j j j j P Pc p p M M β β β − = − =   − ∑ ∑   10. 有噪信道编码定理(香农第二定理) 若信道是离散、无记忆、平稳的，且信道容量为C ，只要待传送的信息率 R C< ，就 一定能找到一种信道编码方法，使得码长 N 足够大时，平均差错率 Pe 任意接近于零。 11. Fano 不等式

H(XIY)≤H(P,1-P)+P log(r-1)12.和有噪信道编码逆定理若信道是离散、无记忆、平稳的，且信道容量为C，如果信息率R>C，则肯定找不到一种信道编码方法，使得码长N足够大时，平均差错率P任意接近于零。13.线性分组码线性分组码的生成式：c=mG线性分组码的校验方程：cH=0或Hc=014.汉明距离和码的纠、检错能力(1）一个码能够检测出ta个错误的充要条件是dmim≥ta+1；(2）一个码能够纠正t。个错误的充要条件是dmin≥2t。+1；(3）一个码能够纠正t。个错误，同时又能够检测出ta>t。个错误的充要条件是dmin>2t。+1和dmin≥t。+ta+1。2

2 ( | ) ( ,1 ) log( 1) HX Y HP P P r ≤ e ee −+ − 12. 和有噪信道编码逆定理 若信道是离散、无记忆、平稳的，且信道容量为C ，如果信息率 R C> ，则肯定找不 到一种信道编码方法，使得码长 N 足够大时，平均差错率 Pe 任意接近于零。 13. 线性分组码 线性分组码的生成式： c mG = 线性分组码的校验方程： T cH = 0或 T Hc = 0 14. 汉明距离和码的纠、检错能力 (1) 一个码能够检测出 dt 个错误的充要条件是 min 1 d d t ≥ + ； (2) 一个码能够纠正 ct 个错误的充要条件是 min 2 1 c d t ≥ + ； (3) 一个码能够纠正 ct 个错误，同时又能够检测出 d c t t > 个错误的充要条件是 min 2 1 c d t > + 和 min 1 c d d tt ≥ + +