《信息理论与编码》课程教学资源（知识点）第5章 有噪信道编码

第5章有噪信道编码5.1基本要求通过本章学习，了解信道编码的目的、译码规则对错误概率的影响，掌握两种典型的译码规则：最佳译码规则和极大似然译码规则。掌握信息率与平均差错率的关系、最小汉明距离译码规则、有噪信道编码定理（香农第二定理）的基本思想，了解典型序列的概念、定理的证明方法。掌握线性分组码的生成和校验。学习要点5.25.2.1信道译码函数与平均差错率5.2.1.1信道译码模型从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为F。信道译码模型如图5.1所示。XXY信道译码DMCFA=(a,a2,,a,)A=(a,a2,,a,)B= {br,b2,"",b,)N图5.1信道译码模型5.2.1.2信道译码函数信道译码函数F是从输出符号集合B到输入符号集合A的映射：F(b,)=a,eA, j=l,2,...S其含义是：将接收符号b,EB译为某个输入符号a,EA。译码函数又称译码规则。5.2.1.3平均差错率在信道输出端接收到符号b,时，按译码规则F(b,)=a,eA将b,译为a，，若此时信道输入刚好是a，，则译码正确，否则译码错误。b，的译码正确概率是后验概率：(5.1)P(X =a,[Y = b,)= P(X =F(b,)/Y = b,)= P[F(b,)|b,]b,的译码错误概率：163

163 第 5 章 有噪信道编码 5.1 基本要求 通过本章学习，了解信道编码的目的、译码规则对错误概率的影响，掌握两种典型的译码规则：最 佳译码规则和极大似然译码规则。掌握信息率与平均差错率的关系、最小汉明距离译码规则、有噪信道 编码定理（香农第二定理）的基本思想，了解典型序列的概念、定理的证明方法。掌握线性分组码的生 成和校验。 5.2 学习要点 5.2.1 信道译码函数与平均差错率 5.2.1.1 信道译码模型 从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为 F。信道译码模型如图 5.1 所示。 5.2.1.2 信道译码函数 信道译码函数 F 是从输出符号集合 B 到输入符号集合 A 的映射： * ( ) Fb a A j j   ， j 1, 2,.s 其含义是：将接收符号 j b B  译为某个输入符号 * j a A  。译码函数又称译码规则。 5.2.1.3 平均差错率 在信道输出端接收到符号 j b 时，按译码规则 * ( ) Fb a A j j   将 j b 译为 * j a ，若此时信道输入刚好是 * j a ，则译码正确，否则译码错误。 j b 的译码正确概率是后验概率： * ( | ) ( ( )| ) [ ( )| ] PX a Y b PX Fb Y b PFb b     j j j j jj （5.1） j b 的译码错误概率： 图 5.1 信道译码模型 X Y DMC 1 2 {, , , } A r  aa a  1 2 {, , , } B bb b   s 信道译码 F Xˆ 1 2 {, , , } A r  aa a  N

P(e|b,)= P[X + F(b,)/Y =b,]=1-P[F(b,)|b,](5.2)平均差错率是译码错误概率的统计平均，记为P：P,=Z P(b,)P(elb,)=2 P(b,)(1-P[F(b,)1b,])j=l(5.3)=1-ZP[F(b,),b,]=1-ZP[F(b,)]P[b,|F(b,)]5.2.2两种典型的译码规则两种典型的译码规则是最佳译码规则和极大似然译码规则。5.2.2.1最佳译码规则使P达到最小的译码规则称为最佳译码规则。这种规则是按后验概率最大原则定出的，所以又称最大后验概率译码规则。F(b,)=a,eA,b,B(5.4)H:P(a,[b,)≥P(a,1b,), a, E A将P(a,Ib,)≥P(a,Ib,)两边乘以P(b,)，变换为P(a,b,)≥P(a,b,)。因此，最佳译码规则又可表示成：[F(b,)=a, eA, b, EB(5.5)HP(a,b,)≥P(a,b,), a, E A因为使用最大联合概率条件，所以又称为最大联合概率译码规则，该规则和最大后验概率规则等价。5.2.2.2极大似然译码规则按最大转移概率条件来确定的译码规则，称为极大似然译码规则：F(b,)=a,eA, b,eBF:(5.6)P(b,la,)≥P(b,la),a,EA虽然极大似然译码规则的平均差错率不一定最小，即不一定最佳，但最易找出。可以证明，当信道输入等概时，极大似然译码规则与最大联合概率译码规则等价，此时极大似然译码规则也是最佳的。5.2.3信道编码对平均差错率和信息率的影响信道编码（或称纠错编码）是靠增加穴余码元来克服或减轻噪声影响的。穴余是相对于信息的表示而言，但是对提高传送可靠性来说，穴余码元却提供了极宝贵的可靠性信息。以下以两种简单信道编码方法来说明信道编码对平均差错率和信息率的影响。164

164 ( | ) ( )| 1 ( )| Pe b P X Fb Y b P Fb b j j j jj           （5.2） 平均差错率是译码错误概率的统计平均，记为 Pe ：   1 1 1 1 ( ) ( | ) ( ) 1 ( )| 1 ( ), 1 ( ) | ( ) s s e j j j jj j j s s jj j j j j j P Pb Pe b Pb P Fb b P Fb b P Fb P b Fb                           （5.3） 5.2.2 两种典型的译码规则 两种典型的译码规则是最佳译码规则和极大似然译码规则。 5.2.2.1 最佳译码规则 使 Pe 达到最小的译码规则称为最佳译码规则。这种规则是按后验概率最大原则定出的，所以又称最 大后验概率译码规则。 * * () , : ( | ) ( | ), jj j jj ij i Fb a A b B F Pa b Pa b a A         （5.4） 将 * ( |) (|) Pa b Pa b jj ij  两边乘以 ( ) P bj ，变换为 * ( , (, ) Pa b Pa b jj ij   。 因此，最佳译码规则又可表示成： * * () , : ( , ) ( , ), jj j jj ij i Fb a A b B F Pa b Pa b a A         （5.5） 因为使用最大联合概率条件，所以又称为最大联合概率译码规则，该规则和最大后验概率规则等价。 5.2.2.2 极大似然译码规则 按最大转移概率条件来确定的译码规则，称为极大似然译码规则： * * () , : ( | ) ( | ), jj j j j ji i Fb a A b B F Pb a Pb a a A         （5.6） 虽然极大似然译码规则的平均差错率不一定最小，即不一定最佳，但最易找出。 可以证明，当信道输入等概时，极大似然译码规则与最大联合概率译码规则等价，此时极大似然译 码规则也是最佳的。 5.2.3 信道编码对平均差错率和信息率的影响 信道编码（或称纠错编码）是靠增加冗余码元来克服或减轻噪声影响的。冗余是相对于信息的表示 而言，但是对提高传送可靠性来说，冗余码元却提供了极宝贵的可靠性信息。 以下以两种简单信道编码方法来说明信道编码对平均差错率和信息率的影响

5.2.3.1“简单重复”编码日常中人们可以通过重复某句话使别人听得更清楚。数字通信中，将符号重复传几次，也会提高传送可靠性。例如，错误概率为p（pαg =图5.2重复2次"编码编码规则为[0→0001→111扩展信道的转移矩阵为β,β4β,β2β,βaβ,β[巴Pp2P'pPp2Pp2p'pPpQ[Prura] =Pp?Pp2P'ppp2p'pD3p'pP3α按极大似然译码规则得译码函数：F(β)=α,F(β,)=α,F(β,)=α,F(β)=αF(β,)=α)F(β)=αsF(β,)=αgF(β,)=αg即165

165 5.2.3.1 “简单重复”编码 日常中人们可以通过重复某句话使别人听得更清楚。数字通信中，将符号重复传几次，也会提高传 送可靠性。例如，错误概率为 p （ p 1/2 ）的二进制对称信道的“重复 2 次”编码，如图 5.2 所示。 编码规则为 0 000 : 1 111 f      扩展信道的转移矩阵为 3 3 12345678 32 2 22 2 23 1 | 3 2 22 22 2 3 8 [ ] Y X p p p p p pp p p pp pp p P p pp pp p p pp p p p p p             按极大似然译码规则得译码函数： 11 21 31 4 8 51 68 78 88 () () () () () () () () FFFF FFFF             即 图 5.2 “重复 2 次”编码 1 1 2 3 4 5 6 7 2 8 0 000 001 010 011 100 101 110 1 111 f f u u                     1 2 3 4 5 6 7 8 000 001 010 011 100 101 110 111                 F 1 8 000 111     1 8 {, }   信道译码 F 3 Xˆ 3 X 3 Y 3 3 Y X| P 信道编码 f 12 8 {, , , } 12 8    {, , , }     U 1 2 {, } u u

β, = 000β4 =011β, = 001β=101α=000>αg=111β, =010β, =110β,=111β, =100信道编码之后的信息率为H(U)R=bit/码元(5.7)N若信源等概率分布，则log MR :bit/码元(5.8)N其中M代表信源消息（符号）个数。log2P, =10-2R=N=1bit/码元无编码11log2,1R=P,=3×10-4N=3bit/码元“重复2次”编码33R=!P, =10-5“重复4次”编码N=5bit/码元51P, = 4x10-7R=“重复6次”编码N=7bit/码元7随着“重复”次数的增加，P下降，但R也跟着下降。即信息传输的有效性和可靠性是矛盾的。5.2.3.2对符号串编码对信源的符号串进行编码，即增多消息个数M，同时增大码长N，有可能使平均差错率P降低到要求的范围以内，同时使信息率R不至于降低太多。例如，取M=4（2次扩展信源）、N=5。4个消息记为S,=00,s,=01,S,=10,S4=11编码函数为i= 1,2,3,4f:s,=m,m,→α,=a,a,a,a,a[a, =m,a,=m,a,=m@m,a,=m,a,=m④m译码采用极大似然规则。编译码示意图见图5.3所示。166

166 1 4 2 6 1 8 3 7 5 8 000 011 001 101 000 111 010 110 100 111 F F                                   信道编码之后的信息率为 H U( ) R N  bit /码元 （5.7） 若信源等概率分布，则 log M R N  bit /码元 （5.8） 其中 M 代表信源消息（符号）个数。 无编码 log 2 1 1 1 N R   bit /码元 2 10 Pe   “重复 2 次”编码 log 2 1 3 3 3 N R   bit /码元 4 3 10 Pe    “重复 4 次”编码 1 5 5 N R   bit /码元 5 10 Pe   “重复 6 次”编码 1 7 7 N R   bit /码元 7 4 10 Pe    随着“重复”次数的增加， Pe 下降，但 R 也跟着下降。即信息传输的有效性和可靠性是矛盾的。 5.2.3.2 对符号串编码 对信源的符号串进行编码，即增多消息个数 M ，同时增大码长 N ，有可能使平均差错率 Pe 降低到 要求的范围以内，同时使信息率 R 不至于降低太多。 例如，取 M  4 （2 次扩展信源）、 N  5。4 个消息记为 1234 ssss  00, 01, 10, 11  编码函数为 1 2 123 4 5 : 1,2,3,4 i i i i iii i i f s mm aaaa a i     1 1 2 2 31 2 4 1 11 2 i i i i iii i i iii a m a m amm a m amm                 译码采用极大似然规则。编译码示意图见图 5.3 所示

0000000001A0001000100000000100010000100010001101101111701111010010000000011015次扩展信道001011110101>01101111000111010→101111011110110La101011001110111001111111111→1101000110101001101011011F11110110001101010010010100101111001图5.3M=4、N=5的编译码示意图编码后的信息率R和平均差错率P分别为R=log4_2bit/码元55P, =1--=(4p+20p*p+8pp)=7.86×10-44与“重复2次”编码相比，R略有增加，P处在同一数量级。因此，增大码长N和适当增多消息个数M，对兼顾P（可靠性）和R（有效性）的要求是有效的。5.2.4最小汉明距离译码规则5.2.4.1汉明距离两个等长符号序列和之间的汉明距离，记为D(，），是与之间对应位置上不同符号的个数，用来定量描述符号序列之间的“相似”程度。5.2.4.2汉明距离与信道编码性能的关系码是码字的集合，码字则是由码元组成的符号序列。假如C=(ci,C2"",C)是等长码，则C中任意两个不同码字之间的汉明距离或码间距离为D(c,c) , c,+cj, C,c,EC码C的最小码间距离定义为167

167 编码后的信息率 R 和平均差错率 Pe 分别为 log 4 2 5 5 R   bit /码元 1 5 4 32 4 1 (4 20 8 ) 7.86 10 4 P p pp pp e       与“重复 2 次”编码相比， R 略有增加， Pe 处在同一数量级。因此，增大码长 N 和适当增多消息 个数 M ，对兼顾 Pe （可靠性）和 R （有效性）的要求是有效的。 5.2.4 最小汉明距离译码规则 5.2.4.1 汉明距离 两个等长符号序列 x 和 y 之间的汉明距离，记为 D(, ) x y ，是 x 与 y 之间对应位置上不同符号的个 数，用来定量描述符号序列之间的“相似”程度。 5.2.4.2 汉明距离与信道编码性能的关系 码是码字的集合，码字则是由码元组成的符号序列。假如 1 2 {, , , } C cc c   q 是等长码，则C 中任 意两个不同码字之间的汉明距离或码间距离为 (, ) , , , D ij i j ij cc c c cc C   码C 的最小码间距离定义为 图 5.3 M  4 、 N  5 的编译码示意图 00 00000 01 01101 10 10111 11 11010 f f f f     00000 00001 00010 00100 01000 10000 10001 00011 01101 01100 01111 01001 00101 11101 11100 01110 10111 10110 10101 10011 11111 00111 00110 10100 11010 11011 11000 11110 10010 01010 01011 11001 F F F F 00000 01101 10111 11010 5 次扩展信道

dmm=min[D(c,c,)]C,+c, C,c,eC最小码间距离dm是衡量码的性能的重要参数，码的d小，说明其中有些码字受干扰后容易变为另一码字，译码时就会出错。因此，信道编码在选择码字时，应尽量使码的最小码间距离dmi大一些为好。对于二元对称信道，设信源有M个消息(si,S2"",SM)，输入和输出符号集分别为A={0,1)和B={0,1)，其N次扩展信道的输入符号集AN和输出符号集B中都含有2N个N长二元符号串，即AN={a,a2,"",a2)BN={Bi,β2,"",β2v)从A中选择M个符号串当作码字组成码C：C=(C,C2,"",CM)按极大似然译码规则进行译码时，可以推导出等价于以下规则，称为最小（汉明）距离译码规则：F(β,)=c,eC, β,eBN(5.9)F:[D(cj,β,)=min[D(c,β,)], c,ECC AN其含意是：将接收序列β,译为与之最相似的输入序列（码字）cj。5.2.5有噪信道编码定理（香农第二定理）5.2.5.1有噪信道编码定理若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R<C，就一定能找到一种信道编码方法，使得码长N足够大时，平均差错率P任意接近于零。有噪信道编码定理实际上是一个存在性定理，它指出：在R<C时，肯定存在一种好的信道编码方法，用这种好码来传送消息可使P逼近零。但香农并没有给出具体编码方法。对有噪信道编码定理的证明要用到联合典型序列。所谓典型序列，是指那些平均自信息量逼近摘的序列。联合ε典型序列，是指那些平均联合自信息量逼近联合的序列。离散无记忆信源X发出N长序列=x,xx，若[()-H(X)<8(5.10)N则称x为X的ε典型序列，否则称为X的非典型序列。168

168 min min ( , ) , ij i j ij d Dc c c c c c C       最小码间距离 min d 是衡量码的性能的重要参数，码的 min d 小，说明其中有些码字受干扰后容易变为 另一码字，译码时就会出错。因此，信道编码在选择码字时，应尽量使码的最小码间距离 min d 大一些为 好。 对于二元对称信道，设信源有 M 个消息 1 2 {, , , } M ss s  ，输入和输出符号集分别为 A {0,1}和 B {0,1}，其 N 次扩展信道的输入符号集 N A 和输出符号集 N B 中都含有 2N 个 N 长二元符号串，即 1 2 2 1 2 2 {, , , } {, , , } N N N N A B          从 N A 中选择 M 个符号串当作码字组成码C ： 1 2 {, , , } C cc c   M 按极大似然译码规则进行译码时，可以推导出等价于以下规则，称为最小（汉明）距离译码规则： * * () , : ( , ) min ( , ) , N jj j N jj ij i F cC B F Dc Dc c C A                 （5.9） 其含意是：将接收序列  j 译为与之最相似的输入序列（码字） * j c 。 5.2.5 有噪信道编码定理（香农第二定理） 5.2.5.1 有噪信道编码定理 若信道是离散、无记忆、平稳的，且信道容量为C ，只要待传送的信息率 R  C ，就一定能找到一 种信道编码方法，使得码长 N 足够大时，平均差错率 Pe 任意接近于零。 有噪信道编码定理实际上是一个存在性定理，它指出：在 R  C 时，肯定存在一种好的信道编码方 法，用这种好码来传送消息可使 Pe 逼近零。但香农并没有给出具体编码方法。 对有噪信道编码定理的证明要用到联合典型序列。所谓典型序列，是指那些平均自信息量逼近熵的 序列。联合 典型序列，是指那些平均联合自信息量逼近联合熵的序列。 离散无记忆信源 X 发出 N 长序列 1 2 N i ii i x  xx x  ，若 ( ) ( ) i I x H X N    （5.10） 则称 i x 为 X 的 典型序列，否则称为 X 的非 典型序列

若x和分别是X和Y的N长典型序列，且[(,)-H(XY)C，则肯定找不到信道编码方法，使得码长N足够大时，平均差错率P任意接近于零。对有噪信道编码逆定理的证明，要用到Fano不等式。Fano不等式：(5.12)H(X/Y)≤H(P,1-P)+P log(r-1)式中r是信道输入符号个数。5.2.6线性分组码5.2.6.1基本概念信道编码的目的是为了降低平均差错率。纠错编码理论几乎与信息论同时创立，创始人是汉明（R.W.Hamming），他与信息论创始人香农都在贝尔实验室工作。纠错编码的基本思路是在信息序列中引入可控余，或称校验码元，组成一个相关的码元序列-码字，译码时利用码元之间的相关性质来检测错误或纠正错误。分组码：先将信息序列分成K个符号一组，称为信息组，然后在信息组中加入一些校验码元组成N长码字，由此得到的码称为（N,K）分组码，校验位数目为r=N-K。线性码：线性码满足线性特性，即码中任意两个码字的和仍为码字。否则为非线性码。循环码：循环码是线性码的一个子集。循环码中任一码字循环移位后仍为该码的码字。否则为非循环码。5.2.6.2生成矩阵和校验矩阵编码函数可用矩阵表示成c=mG(5.13)其中m是K维信息组行矩阵，c是N维码字行矩阵，G是码的生成矩阵。m=[m m,... mk], m,e(0,1)(5.14)(5.15)c=[C C ... CN], C,e(0,1)169

169 若 i x 和 j y 分别是 X 和Y 的 N 长 典型序列，且 (, ) ( ) i j Ix y H XY N    （5.11） 则称序列对(, ) i j x y 为 X 与Y 的联合 典型序列，否则称为非联合 典型序列。 5.2.5.2 有噪信道编码逆定理 若信道是离散、无记忆、平稳的，且信道容量为C ，如果信息率 R  C ，则肯定找不到信道编码方 法，使得码长 N 足够大时，平均差错率 Pe 任意接近于零。 对有噪信道编码逆定理的证明，要用到 Fano 不等式。 Fano 不等式： ( | ) ( ,1 ) log( 1) HX Y HP P P r  e ee    （5.12） 式中 r 是信道输入符号个数。 5.2.6 线性分组码 5.2.6.1 基本概念 信道编码的目的是为了降低平均差错率。纠错编码理论几乎与信息论同时创立，创始人是汉明 （R.W.Hamming），他与信息论创始人香农都在贝尔实验室工作。 纠错编码的基本思路是在信息序列中引入可控冗余，或称校验码元，组成一个相关的码元序列—— 码字，译码时利用码元之间的相关性质来检测错误或纠正错误。 分组码：先将信息序列分成 K 个符号一组，称为信息组，然后在信息组中加入一些校验码元组成 N 长码字，由此得到的码称为(,) N K 分组码，校验位数目为 rNK   。 线性码：线性码满足线性特性，即码中任意两个码字的和仍为码字。否则为非线性码。 循环码：循环码是线性码的一个子集。循环码中任一码字循环移位后仍为该码的码字。否则为非循 环码。 5.2.6.2 生成矩阵和校验矩阵 编码函数 f 可用矩阵表示成 c mG  （5.13） 其中 m 是 K 维信息组行矩阵，c 是 N 维码字行矩阵，G 是码的生成矩阵。  1 2 , {0,1} m   mm m m  K i （5.14）  1 2 , {0,1} N i c   cc c c  （5.15）

通过生成矩阵，可将信息组变换为相应的码字。如果码字的前（或后）K位照搬信息组的K个信息元，这样形成的码称为系统码。对于前K位为信息元的系统码，生成矩阵G可分块成[10..0anara12..010a21a22a2rG=[IkxAkxr](5.16)：目:：100.1akrakiak2..校验方程的矩阵形式则为cH=0或Hc =0(5.17)式中H为r×N一致性校验矩阵，r=N-K为校验位数目。5.2.6.3汉明距离和码的纠检错能力的关系(1）一个码能够检测出ta个错误的充要条件是dmin≥ta+1；(2）一个码能够纠正t。个错误的充要条件是dmm≥2t。+1；(3）一个码能够纠正t。个错误，同时又能够检测出t.>t.个错误的充要条件是dmin≥t。+ta+1。其中，dmim表示码的最小汉明距离，是衡量其纠、检错能力的重要参数。5.2.6.4伴随式与伴随式译码用一致性校验矩阵H对接收序列y进行检验，检验结果记为S，则S= yH' =(c+e)H' =eH)(5.18)式中c为发送码字。如果s+0，则表明有错误存在。s是传输是否出错的标志，称为伴随式。e称为差错图样。当码字第i位发生错误时，e,=1，否则e,=0。通过接收序列y可以确定发送码字c的估计值℃：(5.19)c=y-e=ye170

170 通过生成矩阵，可将信息组变换为相应的码字。 如果码字的前（或后） K 位照搬信息组的 K 个信息元，这样形成的码称为系统码。 对于前 K 位为信息元的系统码，生成矩阵G 可分块成   11 12 1 21 22 2 1 2 10 0 01 0 00 1 r r KK Kr K K Kr aa a aa a aa a                              GI A （5.16） 校验方程的矩阵形式则为 T cH  0或 T Hc  0 （5.17） 式中 H 为 r N 一致性校验矩阵， rNK   为校验位数目。 5.2.6.3 汉明距离和码的纠检错能力的关系 (1) 一个码能够检测出 dt 个错误的充要条件是 min 1 d d t   ； (2) 一个码能够纠正 ct 个错误的充要条件是 min 2 1 c d t   ； (3) 一个码能够纠正 ct 个错误，同时又能够检测出 d c t t  个错误的充要条件是 min 1 c d d tt    。 其中， min d 表示码的最小汉明距离，是衡量其纠、检错能力的重要参数。 5.2.6.4 伴随式与伴随式译码 用一致性校验矩阵 H 对接收序列 y 进行检验，检验结果记为 s ，则 ( ) T TT s = yH c + e H eH   （5.18） 式中c 为发送码字。如果 s  0，则表明有错误存在。s 是传输是否出错的标志，称为伴随式。e 称 为差错图样。当码字第i 位发生错误时， 1 i e  ，否则 0 i e  。 通过接收序列 y 可以确定发送码字c 的估计值cˆ ： c= y e= y e ˆ   （5.19）