北工大信息论第六章 有噪信道编码14

第六章有噪信道编码需要掌握的内容：译码规则与错误概率的关系平均差错率与信道编码的关系汉明距离有噪信道编码定理线性分组码第一节译码规则与错误译码概率0011信源（信源编码，信道编码）译码（信源译码，信道译码）信道信宿一.译码规则译码函数又称译码规则

注意:

译码规则是人为定的,对于同一个信道可有多个不同的译码规则

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

例如：对于二元信道就可制定若干不同译码规则，如图所示。“好”的译码规则的标准是：错误译码概率小译码正确---如果接收到bj，按

译成aj*

，而输入的刚好是aj*bj的译码正确概率为：

bj的译码错误概率为：二.错误译码概率

译码错误概率的统计平均称为平均译码错误概率或平均差错率，记为PePe与译码规则F有关

使Pe小的译码规则F是好的译码规则简化Pe式为下面的形式：当输入等概:上式可化为：例6-1：

参见下图，假设P(a1)=0.4,分别求出4种译码规则所对应的平均差错率。0.80.20.10.9a1a2b1b2解：信道输入概率矩阵和转移矩阵分别为：

转移矩阵各行元素乘以对应的输入概率，得联合概率矩阵

译码规则F1对应的平均差错率为

其它译码规则对应的平均差错率分别为Pe(F2)=0.4 Pe(F3)=0.14 Pe(F4)=0.86四种规则相比，F3最好，F4最差第二节两种典型的译码规则

一.最佳译码规则

平均差错率Pe与译码规则有关，使Pe达到最小的译码规则——最佳译码规则。

可以看出：要减小Pe

，必须减小各个接收符号的译码错误概率，或者增大各个接收符号的译码正确概率。确定最佳译码规则的方法：该最佳译码规则称为最大后验概率译码规则最大后验概率条件可等价为最大联合概率条件,为什么呢?则最佳译码规则又可表示为：最佳译码规则又称为最大联合概率译码规则例6-2

参见下图，假设P(a1)=0.4，求最佳译码规则。

0.80.20.10.9a1a2b1b2解：例6-1已经求出联合概率矩阵，重写为则最大联合概率译码规则为：对应的平均差错概率：

——按最大转移概率条件确定的译码规则例6-3：已知信道转移矩阵，试确定译码规则。解：按转移概率最大原则确定极大似然译码规则如下：

二、极大似然译码规则原因是：极大似然译码规则是按最大转移概率条件确定的，即如果输入等概，则

所以当信道输入等概率时，极大似然译码规则是最佳的。提问:为什么?第三节信道编码的编码原则二元信源和二元对称信道的模型如下图所示

DMCX{a1,a2}Y{b1,b2}a1=0a2=1b1=0b2=11-p1-pp=0.01p=0.01DMSU{u1,u2}信源的熵为：H（U）=logM=1比特/符号信道容量为：C=log2-H(0.99,0.01)=0.92比特/符号由图可知：信源与信道之间不加信道编码，则由于信道输入等概分布，则极大似然译码规则就是最佳译码规则，根据信道转移矩阵确定极大似然译码规则为：平均差错率为：提问：传输系统的Pe要求控制在10-6以下，而利用译码规则的Pe太高，如何降低平均差错率呢？－－－信道编码一.简单重复编码

对信源符号进行“重复2次”编码:信道编码f信道译码F“重复2次”编码规则为

求出3次扩展信道的转移矩阵按极大似然译码规则得译码函数

即：

译码差错率为：结论：信道编码降低平均错误率提问：信道编码对信息传输速率有什么影响呢？

信道编码，或称为纠错编码，就是靠增加“冗余”码元来克服或减轻噪声影响的。结论：信道编码降低了信道的信息传输率信道编码之后的信息率或信道待传的信息率为无信道编码的信息率或信道待传的信息率为

二.对符号串编码(矢量编码）例6-4：二元信源U，若取二元符号串“00，01，10，11”作为消息，则消息个数增加为M=4。提问：此时平均差错率又发生怎样的变化呢？结论：增加信源消息个数，可提高信道的信息传输率取码长N=3，则编码后的信息率为

R=(log4)/3=2/3比特/码元码长N=3，可供选择的码字为选择以下编码函数：

根据信道转移矩阵确定极大似然译码规则为

则平均差错率为：

结论：增加消息个数M与重复编码相比，在提高信息率的同时会使平均差错率增大。第四节汉明距离两个等长符号序列x和y之间的汉明距离，记为D(x,y)，是x与y之间对应位置上不同符号的个数。解：求汉明距离：

D(x,z)=2;D(y,z)=3因此，z与x的相似程度高于与y的相似程度一.定义例6-5：

x=100111,y=111000,z=111111,比较z与x和y的相似程度。X和Y是二元序列，记为

是等长码，则C中任意两个不同码字之间的汉明距离或码间距离为码C的最小码间距离定义为二元对称信道，可以根据汉明距离来决定译码规则

假如有一个信源有M个消息二元对称信道的输入符号集和输出符号集分别为A={0，1}和B={0，1}。其N次扩展信道的输入符号集和输出符号集分别为：经N次扩展信道传送之后，按极大似然译码规则进行译码记N长二元符号串为

由信道无记忆可知转移概率为码元错误概率为p，正确概率为

则有：极大似然译码规则等价为最小汉明距离译码规则

最小距离译码规则可在一般信道中采用，但不一定与极大似然译码规则等价，只有对于二元对称信道，它才与极大似然译码规则等价，并且当输入等概时是最佳的。

对于二元对称信道，若输入等概，无论用什么规则确定译码函数，与之对应的平均差错率都可用汉明距离表示：

结论：第五节有噪信道编码定理一.正定理（香农第二定理）若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R<C，就一定能找到一种信道编码方法，使得码长足够大时，平均差错率任意接近于零。二.逆定理若信道是离散、无记忆、平稳的，且信道容量为C，只要待传送的信息率R>C，就一定找不到一种信道编码方法，使得码长足够大时，平均差错率任意接近于零。

信道编码定理告诉我们：R<C时，通过编码可使平均差错率逼近零；逆定理则说明：R>C时，无论如何编码，都不可能使平均差错绿逼近零。因此，信道容量C是确保可靠性传输的信息传输率的上限。第六节纠错编码

一.纠错码分类（1）根据信道中的干扰类型，纠错码分为：

反向重传纠错检错编码检错译码信道CmR反馈前向纠错纠错编码纠错译码信道CmR混合纠错（2）根据不同的分组方式及随后的映射关系，纠错码分为：分组码:先将信息序列分成K个符号一组，称为信息组，然后在信息组中加入一些校验码元组成N长码字，该码称为（N，K）分组码。（N，K）分组码中的任一码字的码长为N，信息位数为K，校验位数为n-k。树码:信息序列以每K个码元分段，编码器输出该段的校验码元不仅与本段的K个信息码元有关，而且还与前面若干段的信息码元有关(3)根据信息码元与校验码元之间是否存在线性关系，纠错码分为：

线性码:非线性码:线性码的校验码元是若干信息码元的线性组合。线性码具有很好的数学结构，编译码比较简单，性能优于具有同样纠错能力的非线性码非线性码的校验码元与信息码元不满足线性关系1.生成矩阵和校验矩阵

二.线性分组码有（5，2）分组码,设

,其中为信息码元，为校验码元假设校验码元由下列方程组得到,其中表示模2加.

方程组改写成矩阵形式有:

令则:式中H称为一致校验矩阵

为维的单位阵维的一般矩阵为校验矩阵与码字具有正交性

可知:由校验方程可改写为:

令，则上述方程组可用矩阵表示：为维矢量，为维矢量，表示信息码元为维矢量，称为的生成矩阵

式中为维的单位阵，为维的一般矩阵

写成分块矩阵，即生成矩阵与校验矩阵H的关系为：则有:例6-6：已知一个线性分组码的生成矩阵为求生成的线性分组码以及校验矩阵H.解：由生成矩阵可知信息位有3位，则线性分组码为（7，3）分组码，生成矩阵生成的码字为：由知由知，2.线性分组码的纠、检错能力

检错:

译码器能检测到是否有错误发生。码的检错能力用检测到的错误位数描述。纠错:译码器不但能检测是否有错误发生，并能纠正错误。码的纠错能力用纠正错误的位数描述。码的纠检错能力与码的最小汉明距离密切相关，具体结论如下：解：因为dmin=3=2+1，所以能检出td=2个错误译码方法为：

000译为0，111译为1，其他置为“错误”标志因为dmin=3=2*1+1，所以能纠正tc=1个错误译码方法为：

000，001，010，100译为0；011，101，110，111译为1但该码不能在纠正tc=1个错误的同时又能检出td=2个错误例6-7：简单重复2次编码，编码规则为0→000，1→111，码C={c1,c2}={000,111},dmin=3。试问该码纠检错能力如何？例6-8：简单重复3次编码，编码规则为0→0000，1→1111码C={c1,c2}={0000,1111},dmin=4。试问该码纠检错能力如何？接收序列译码接收序列译码0000010000000101001Error001001010Error0011Error10111010001100Error0101Error110110110Error111010111111111解：由dmin=4=3+1，知能检出td=3个错误

译码方法为：0000译为0，1111译为1，其他置为“错误”标志由dmin=4>2*1+1和dmin=4=1+2+1，知能纠正tc=1个错误，同时能检出td=2个错误，译码方法为：例6-9：比较（5，2）线性码和“重复2次”码的纠、检错能力和信息率。解：由例6-6和第三节的“简单重复编码”可知：“重复2次”码的纠、检错能力和信息率为：（1）dmin=3，能检出td=2个错误或纠正tc=1个错误。（2）R=1/3(比特/码元)由码字生成式求出与各信息组对应的码字：

信息组码字c0000000010110110101111111010（5，2）线性码的生成矩阵为结论：（5，2）的信息率比“重复2次”码提高了一倍。码C={c}的最小汉明距离为dmin=3，纠、检错能力与“重复2次”码相同，能检出td=2个错误或纠正tc=1个错误。由第三节的“简单重复编码”可知:R=2/3(比特/码元)两者的平均差错率处于同一数量级，原因是它们的最小汉明距离相同3.伴随式和伴随式译码若发送码字为,则由于在传输过程中受到各种干扰，接收序列不一定等于发送的码字两者之间的差异即是出现的差错。差错是多样化的，定义差错的式样为差错图样则有对于二元序列情形，模2减等同模2加，则有：以及S是传输是否出错的标志,称为伴随式.译码时，需由来确定发送码字,若能确定差错