信道编码定理

信道编码定理错误概率译码准则信道编码定理1噪声信道的编码问题在二进制数字通信系统中，编码器的编码过程分为两步：信源编码：把信源的消息数据序列编成二进制数字构成的码序列；信道编码：把二进制数据序列编成具有纠检错能力的二进制序列。由于信源编码在构造上并未考虑抗干扰，如果把信源编码器的输出直接接入信道，由于信道中存在噪声干扰，将引起误码，降低通信可靠性。因此提出了以提高通信可靠性为主要目的的信道编码，它是对信源编码器输出的最佳码再进行一次编码，以提高其抗干扰能力的一种编码形式。2信道编译码的理论基础信道的特征是由信道传递概率p(Y|X)来描述的。由p(Y|X)可以算出信道容量C，只要在信道中实际传送的信息率R’<C，在接收端就能够无差错地译出发端所输送的信息。信道输入符号序列X代表M种信源符号，信源符号也可以是已经经过信源编码的M种码字，使从信道输出符号序列Y能正确地译出这M种码字，问题就在于如何用X组成这M种码字，才能达到无差错地传送，这就要编码。这种编码实质上是希望信源与信道特性相匹配，所以称为信道编码。

3信道编译码的基本思想信道编码的编码对象是信源编码器输出的数字序列M，又称为信息序列。通常是由二元符号0，1构成的序列，而且符号0和1是独立等概的。信道编码，就是按一定的规则给数字序列M增加一些多余的码元，使不具有规律性的信息序列M变换为具有某种规律性的数字序列C，又称为码序列。码序列中信息序列的诸码元与多余码元之间是相关的。在接收端，信道译码器利用这种预知的编码规则来译码，或者检错(检验接收到的数字序列R中是否有错)，或者纠错(纠正其中的差错)。信道编码的基本思想是就是根据相关性来检测和纠正传输过程中产生的差错。4通信的可靠性问题通信的可靠性问题，即消息通过信道传输时如何选择编码方案以减少差错。首先，通信的可靠性显然与信道的统计特性有关，因为杂噪干扰是造成错误的主要因素。其次，编码方法和译码方法也将影响信息传输的可靠性。在有噪信道中传输信息是会发生错误的，错误概率和信道统计特性、编译码过程以及译码规则有关。5编码信道的概念信道编码研究的对象是编码信道，如上图所示，它是由信道编码器、信道译码器和实际信道一起形成的一个新的信道。编码信道是研究信道纠错编码和译码的一种模型。它可以是：无线通信中的如发射机、天线、自由空间、接收机等全体；有线通信中的如调制解调器、电缆等全体；互联网的多个路由器、节点、电缆、低层协议等全体；计算机的存储器如磁盘等的全体；……。接收向量

Y码字X编码信道信源编码信源译码消息m消息m’6错误概率和译码规则考虑一个二元对称信道，单符号错误传递概率是pb=0.9，其输入符号为等概率分布。如果规定在信道输出端接收到符号0时，译码器把它译成0；接收到1时译成1，那么译码错误概率为0.9。反之，如果规定在接收到符号0时译成1；接收到1时译成0，则译码错误概率为0.1。可见，错误概率既与信道统计特性有关，也与译码规则有关。00111-pb1-pbpbpb二元对称信道7无记忆二进制对称信道（BSC）假定数字通信系统的编码信道是无记忆二进制对称信道：二进制信道是指码字和接收向量均由二元序列表示的信道，即c=(c0,c1,…,cn-1)ci{0,1}、

r=(r0,r1,…,rn-1)ri{0,1}。二进制信道可用转移概率p(r/c)描述输入输出关系；满足以下公式的二进制信道称为无记忆二进制信道：

p(r/c)=p(ri

/ci

)i=0…n-1满足以下对称特性的无记忆二进制信道称为无记忆二进制对称信道，简称BSC：p(0/1)=

p(1/0)=pb接收向量rri{0,1}

码字cci{0,1}二进制信道p(r/c)信源编码信源译码消息m消息m’8BSC的信道模型只要噪声是白噪声，大多数二进制传输信道的模型可等效为一个BSC，其信道模型如下图所示。+cer二进制无记忆00111-pb1-pbpbpbBSC转移概率BSC编码信道9可将BSC的输入输出关系等效为代数关系：r=c+emod2e=(e0,e1,…,en-1)差错图案：随机序列(ei)随机错误：ei

=1,i位突发错误：第i至第j位之间有很多错误。BSC的输入输出关系描述+cer10译码规则译码规则的定义11译码规则-例设有一离散无记忆信道，其信道矩阵为则以下A和B是两个不同的译码规则：由于n=3，m=3，m个输出符号中的每一个都可以译成n个输入符号中的任何一个，故按此信道矩阵总共可设计出33=27种译码规则。在所有的译码规则中，不是每一种译码规则都是合理的，因此要讨论选择译码规则的准则，这些准则总的原则是使译码平均错误概率最小。

121、译码平均错误概率若译码规则为，则信道输出端接收到符号yj时，一定译成xi。如果发送端发的就是xi，这就是正确译码，因此条件正确概率为反之，如果发送端发的是，则是错误译码，因此条件错误概率为

经过译码后，平均到一个符号所产生的错误的大小，也就是译码平均错误概率为

13译码平均错误概率的其它表达式译码平均错误概率还可以写成若用条件概率表示，则可以写成平均正确概率则可以写成

14等概率分布时的译码平均错误概率若输入为等概率分布，则上式意味着，在输入为等概率分布的条件下，译码错误概率可用信道矩阵中元素的求和来求。这种求和是除去信道矩阵中每列中对应于的那一项后，求矩阵中其余元素之和。

152、译码规则选择译码规则总的原则应是使译码平均错误概率pE最小。

译码平均错误概率

为非负项之和，欲使译码平均错误概率最小，那么应使每一项为最小。由于p(yj)

与译码规则无关，故欲使译码平均错误概率最小，即为使最小，或者使为最大，于是引出最大后验概率准则。

16最大后验概率译码准则-定义17最大后验概率准则-例题18最大后验概率准则-例题（续）19后验概率与最大似然-译码准则从最大后验概率译码规则可以很容易推出极大似然译码规则。20最大似然译码准则-定义

当信道输入符号为等概分布时，应用极大似然译码准则是很方便的，即将yj译成信道矩阵中第j列最大的那个元素。式中的条件概率即为信道矩阵中的元素。21最大似然译码准则-例题当输入为等概率分布时，译码规则A就是依据最大似然译码准则而得的。22最大似然译码准则-例题（续）输入为等概率分布时，两种译码规则所对应的平均错误概率分别为

在输入为等概率分布时，最大似然译码准则是最优的。23费诺不等式译码时发生错误是由信道中噪声引起，因此平均错误概率与信道疑义度H(X|Y)有关，其关系由费诺不等式表示。引理6.1.1译码平均错误概率与信道疑义度H(X|Y)间满足以下关系这个不等式称为费诺不等式。

24费诺不等式的物理意义虽然PE与译码规则有关，但不管采用什么译码规则费诺不等式均成立。费诺不等式表示，当作了一次译码判决后所保留的关于信元的不确定性可以分成两部分：H(PE)和PE

log(n-1)。第二部分是当判决是错误的，其错误概率为PE

时，到底是n-1个输入符号中哪一个引起错误的最大不确定性，它是(n-1)个符号不确定性的最大值log(n-1)与PE

的乘积。

第一部分是接收到Y后，判决是否发生错误的不确定性H(PE)，其中H(PE

)是译码平均错误概率PE

的熵，表示产生错误概率PE

的不确定性。25费诺不等式的几何含义信道疑义度是信源熵H(X)超过平均互信息I(X;Y)的部分。若以H(X|Y)为纵坐标，PE为横坐标，则函数H(PE)+PE

log(n-1)随PE变化的曲线如图所示。由图可知，当信源、信道给定时，信道疑义度H(X|Y)就给定了译码平均错误概率PE的下限。

26错误概率与编码方法

前面讨论了平均错误概率与译码规则的关系。选择最佳译码规则只能使错误概率有限地减小，无法使其任意地小。要想进一步减小错误概率，必须优选信道编码方法。现在讨论不同的编码方法对译码平均错误概率和信息传输率的影响。

27错误概率与编码方法1简单重复编码2消息符号个数3（5,2）线性码4汉明距离281简单重复编码与错误概率

本节举例说明在采用简单重复编码时重复次数对译码平均错误概率和信息传输率的影响。设有二元对称信道如图其信道矩阵为未编码时：选择最佳译码规则为

在输入为等概率分布时，译码平均错误概率为29简单重复编码举例（续1）采用简单重复编码，规定信源符号为0（或1）时重复发送三个0（或1）。输入符号和输出符号的关系如图：

30简单重复编码举例（续2）31简单重复编码举例（续3）在简单重复编码时，采用“择多译码”的译码规则等效于最大似然译码准则。择多译码是根据接收序列中“0”和“1”的个数，如果是“0”多，则译码器就判决为“0”，如果是“1”多，就判决为“1”。采用简单重复编码方法，如果增大重复次数n，则会降低译码平均错误概率，但信息传输率也要减小。信息传输率表示平均每个码符号所携带的信息量，其中M为消息符号个数。32简单重复编码举例（续4）重复次数对信息传输率和错误概率的影响如下能否找到一种编码方法，使平均错误概率充分小，而信息传输率R’又可以保持在一定水平上，这就是香农第二定理所要回答的问题。

332消息符号个数M本节讨论消息符号个数M对错误概率和信息传输率的影响。在一个二元信道的n次无记忆扩展信道中，输入端共有2n个符号序列可能作为消息符号，现仅选其中M个作为消息符号传递。

34消息符号个数M的影响（续1）设n=3，那么可供选择的消息符号数共有8个，发送端只选择其中M个作为输入消息符号传递，而接收端会接收到所有8个输出符号，然后从中译出M个消息符号。

以下假设输入为等概率分布p(x)=1/M，信道错误传递概率p=0.01，采用简单重复编码和最大似然译码准则。当n=3，M=2时，有：

35消息符号个数M的影响（续2）当n=3，M=4时，有比特/码符号

M=4有不同的选取方法，代表不同的编码方法，其平均错误概率是不同的。

36结论：输入信息符号个数M增大时，平均错误概率显然是增大了，但信息传输率也增大了。反之，亦然。

输入信息符号个数M不变时，即信息传输率不变时，不同的编码方法，其平均错误概率是不同的。

37错误概率与编码方法1简单重复编码2消息符号个数3（5,2）线性码4汉明距离383（5，2）线性码从以上讨论看出：增大简单重复编码次数n，虽然使平均错误概率pE下降，但信息传输率R’也降低了。增大输入消息符号个数M，尽管可使信息传输率R’增大，但又增大了平均错误概率pE。当采用好的编码方法时，可以使平均错误概率pE和信息传输率R’两个指标得到较好的折衷。39（5，2）线性码的编码设M=4，n=5则输入符号有M=4种，由的4个不同取值决定。采用以下编码方法将输入符号编码成为5位码：40（5,2）线性码的编码（续）由上述编码方法得到一种(5,2)线性码，如图所示:41（5,2）线性码的译码效果采用最大似然译码准则，当p=0.01时正确译码概率为平均错误译码概率为信息传输率为前述n=3，M=4的一种简单重复编码平均错误译码概率为信息传输率为42结论与n=3，M=4的简单重复编码比较，（5,2）线性码的信息传输率R’略有降低，但平均错误概率却好得多。说明好的编码方法可以在错误概率和信息传输率两个性能上达到最佳折衷。43离散信道编码定理信道编码定理是一个理想编码的存在性定理。信道容量是一个临界值，信息传输率不超过这个值，信道就可几乎无失真地把信息传过去，否则就会产生失真。44纠错码分类

检纠错码的种类繁多，其分类也有多种方式，主要依据使用的信道、纠错类型和码的数学结构分类。以下首先简要介绍干扰类型和对应的信道类型、检纠错工作方式，再介绍检纠错码的不同分类方法。45干扰类型信道中的干扰一般分为两种形式：随机噪声，它主要来源于设备的热噪声和散弹噪声以及传播媒介的热噪声，它是通信系统中的主要噪声；脉冲干扰，它的特点是突发出现，主要来源于雷电、通电开关、负荷突变或设备故障等。46检纠错的工作方式

反馈重传纠错当发现有错时，通过反馈系统向发出端发出询问信号要求重新发送。发送端收到信号后，重发已发生错误的那部分信息，直至接收端认为无错误为止。前向纠错当在传输中出现差错，且错误个数在码的纠错能力范围内时，系统的接收端根据编码规则进行解码，并自动纠正错误。这种纠错方式不需要反馈，故称其为前向纠错。混合纠错当错误在码的纠错能力之内时，采用自动纠错。当超出码的纠错能力，且能发现错误，则发出询问信号，反馈到发送端要求重发。47线性码和非线性码根据码的数学结构，可以有不同的分类。按校验元与信息元的关系，可分为线性码和非线性码。线性码的校检位是若干信息位的线性组合，而非线性码的校检位与信息位不满足线性关系。线性码的编译码都优于相同纠错能力的非线性码。48分组码和卷积码按对信息序列处理方式分类，可分为分组码和卷积码分组码:对于某组码字，其信息序列划分为一组k位码元，将其编成n（n>k）位的码字。重点讨论线性分组码。根据分组码的结构，又可分为循环码和非循环码。卷积码:是将整个信息序列编成一个码序列，码与码之间相互影响，不能分开。卷积码又称为树码或链码。494汉明距离

定义：设为两个n长的二元码字，则码字X和Y之间的汉明距离为其中，代表模二和运算。上式的含义是，两个码字之间的汉明距离就是它们在相同位上不同码符号的数目的总和。

举例：设X=(101111)，Y=(111100)，则D(X,Y)=350汉明距离满足的性质1、非负性D(X,Y)≥0当且仅当X=Y式等号成立。2、对称性D(X,Y)=D(Y,X)3、三角不等式D(X,Z)+D(Y,Z)≥D(X,Y)51最小码距Dmin定义：在二元码C中，任意两个码字的汉明距离的最小值，称为码C的最小码距，即举例：设有n=3的两组码对于码C1有对于码C2有52最小码距对错误概率的影响显然，最小码距Dmin越大，则平均错误概率pE越小。码本中最小码距Dmin越大，受干扰后，越不容易把一个码字错译成另一个码字，因而平均错误概率pE小。如果码本中最小码距Dmin小，受干扰后很容易把一个码字错译成另一个码字，因而平均错误概率pE大。因此，在选择编码规则时，应使码字之间的距离Dmin越大越好，这样的准则即为最小