武汉理工大学第二章辅导信息理论编码 下载本文

第5章 有噪信道编码

5.1 基本要求

通过本章学习,了解信道编码的目的,了解译码规则对错误概率的影响,掌握两种典型的译码规则:最佳译码规则和极大似然译码规则。掌握信息率与平均差错率的关系,掌握最小汉明距离译码规则,掌握有噪信道编码定理(香农第二定理)的基本思想,了解典型序列的概念,了解定理的证明方法,掌握线性分组码的生成和校验。

5.2 学习要点

5.2.1 信道译码函数与平均差错率

5.2.1.1 信道译码模型

从数学角度讲,信道译码是一个变换或函数,称为译码函数,记为F。信道译码模型如图5.1所示。

?XYX信道译码 DMC F

A?{a1,a2,,ar}A?{a1,a2,,ar}B?{b,b,,b}12s

N图5.1 信道译码模型

5.2.1.2 信道译码函数

信道译码函数F是从输出符号集合B到输入符号集合A的映射:

F(bj)?a*j?A,j?1,2,...s

其含义是:将接收符号bj?B译为某个输入符号aj?A。译码函数又称译码规则。 5.2.1.3 平均差错率

在信道输出端接收到符号bj时,按译码规则F(bj)?aj?A将bj译为a*j,若此时信道输入刚好是

**a*j,则称为译码正确,否则称为译码错误。

bj的译码正确概率是后验概率:

??P(X?a*j|Y?bj)?P?F(bj)|bj? (5.1)

bj的译码错误概率:

P(e|bj)?P??X?F(bj)|Y?bj???1?P??F(bj)|bj?? (5.2)

平均差错率是译码错误概率的统计平均,记为Pe:

Pe??P(bj)P(e|bj)??P(bj)1?P??F(bj)|bj??j?1j?1ssss?? (5.3)

?1??P??F(bj),bj???1??P??F(bj)??P??bj|F(bj)??j?1j?15.2.2 两种典型的译码规则

两种典型的译码规则是最佳译码规则和极大似然译码规则。 5.2.2.1 最佳译码规则

使Pe达到最小的译码规则称为最佳译码规则。这种规则是按后验概率最大原则定出的,所以又称最大后验概率译码规则。

*??F(bj)?aj?A,bj?B (5.4) F:?*??P(aj|bj)?P(ai|bj),ai?A上式中最大后验概率条件可等价成最大联合概率条件。

*将P(a*j|bj)?P(ai|bj)两边乘以P(bj),变换为P(aj,bj??P(ai,bj)。

因此,最佳译码规则又可表示成:

*??F(bj)?aj?A,bj?B (5.5) F:?*??P(aj,bj)?P(ai,bj),ai?A因为使用最大联合概率条件,所以又称为最大联合概率译码规则。 5.2.2.2 极大似然译码规则

按最大转移概率条件来确定的译码规则,称为极大似然译码规则:

*?F(b)?abj?Bjj?A,? (5.6) F:?*??P(bj|aj)?P(bj|ai),ai?A虽然极大似然译码规则的平均差错率不是最小,不是最佳的,但最易找出。

可以证明,当信道输入等概时,极大似然译码规则与最大联合概率译码规则等价,此时极大似然译码规则也是最佳的。

5.2.3 信道编码对平均差错率和信息率的影响

信道编码(或称纠错编码)是靠增加冗余码元来克服或减轻噪声影响的。冗余是相对于信息的表示而言,但是对提高传送可靠性来说,冗余码元却提供了极宝贵的可靠性信息。

以下以两种简单信道编码方法来说明信道编码对平均差错率和信息率的影响。 5.2.3.1 “简单重复”编码

日常中人们可以通过重复某句话使别人听得更清楚。数字通信中,将符号重复传几次,也会提高传送可靠性。例如,“重复2次”编码,如图5.2所示。

?3Y3X3XU信道译码 信道译码 PY3|X3 f F {?1,?8} {?1,?2,,?8}{u1,u2}{?1,?2,,?8}

fu1?0????1?000 000??1 ?2?001001??2

?3?010010??3

F?1?000?4?011011??4

?2?111?5?100 100??5 ?6?101101??6

?7?110110??7

fu2?1????8?111111??8

图5.2 “重复2次”编码

编码规则为

?0?000 f:??1?111扩展信道的转移矩阵为

?1?p3[P]??3Y3|X3??p按极大似然译码规则得译码函数:

?2p2ppp2?3p2ppp2?4pp2p2p?5p2ppp2?6pp2p2p?7pp2p2p?8p3??1

?3p???8

F(?1)??1F(?5)??1即

F(?2)??1F(?6)??8F(?3)??1F(?7)??8F(?4)??8F(?8)??8?1?000??2?001??F??1?000????3?010??5?100??信道编码之后的信息率为

?4?011??6?101??F??8?111 ????7?110???8?111?H(U) bit/码元 (5.7) NlogM bit/码元 (5.8) NR?若信源等概率分布,则

R?其中M代表信源消息(符号)个数。

log2?2?1 bit/码元 Pe?10 1log21?4R?? bit/码元 P“重复2次”编码 N?3e?3?10

331?5N?5R? bit/码元 Pe?10

51?7N?7R? bit/码元 Pe?4?10

7R也跟着下降。即信息传输的有效性和可靠性是矛盾的。 随着“重复”次数的增加,Pe下降,但

无编码 N?1R?5.2.3.2 对符号串编码

对信源的符号串进行编码,即增多消息个数M,同时增大码长N,有可能使平均差错率Pe降低到要求的范围以内,而又能使信息率R降低得不多。

例如,取M?4(2次扩展信源)、N?5。4个消息记为s1?00,s2?01,s3?10,s4?11 编码函数为

f:si?mi1mi2??i?ai1ai2ai3ai4ai5i?1,2,3,4

?ai1??ai2??ai3??ai4?a?i1?mi1?mi2?mi1?mi2 ?mi1?mi1?mi2译码采用极大似然规则。编译码示意图见图5.3所示。

0000000001F0001000100 000000100010000 1000100011

0110101100F f011110100100???00000011015次扩展信道 0010111101

f111000111001?? ?011011011110110 f?1011110??F1010110011 f10111111110011111???110100011010100

1101011011F1100011110 110101001001010 0101111001

图5.3 M?4 、n?5 的编译码示意图

编码后的信息率R和平均差错率Pe分别为

log42? bit/码元 551Pe?1?(4p5?20p4p?8p3p2)?7.86?10?4

4N和适当增多消息与“重复2次”编码相比,R略有增加,Pe处在同一数量级。因此,增大码长

R(有效性)的要求是有效的。 个数M,对兼顾Pe(可靠性)和

R?5.2.4 最小汉明距离译码规则

5.2.4.1汉明距离

两个等长符号序列x和y之间的汉明距离,记为D(x,y),是x与y之间对应位置上不同符号的个

数,用来定量描述符号序列之间的“相似”程度。 5.2.4.2汉明距离与信道编码性能的关系

码是码字的集合,码字则是由码元组成的符号序列。假如C?{c1,c2,意两个不同码字之间的汉明距离或码间距离为

,cq}是等长码,则C中任

D(ci,cj),ci?cj,ci,cj?C

码C的最小码间距离定义为

dmin?min??D(ci,cj)??ci?cjci,cj?C

最小码间距离dmin是衡量码的性能的重要参数,码的dmin小,说明其中有些码字受干扰后容易变为另一码字,译码时就会出错。因此,信道编码在选择码字时,应尽量使码的最小码间距离dmin大一些为好。