第6章-有噪离散信道编码

第1页2023/2/2DepartmentofElectronicsandInformation,NCUTSongPeng第六章

──────────────

有噪离散信道编码6.1差错、差错控制系统分类6.2纠错码的基本概念6.3译码规则6.5香农第二定理第2页2023/2/2(1)数字通信系统工作原理数字通信系统模型信源：可以是人或机器（例如计算机、传感器）；信源编码器：将信源输出变换成信息序列；调制器：把输入的消息序列变换为适合于在实际信道中传输（存储）的信号波形；信道编码在通信系统中的地位和作用第3页2023/2/2(1)数字通信系统工作原理传输信道/存储媒介有线：实际的传输信道可能是光缆、电缆等有线信道；无线：高频无线线路、卫星中继等无线信道；存储媒介：媒介可以是磁带、磁盘、光盘等；无论何种传输媒介，都受到不同性质的干扰有线信道中的脉冲干扰；无线信道中的噪声和衰落；存储媒介的缺损也被看做是脉冲干扰。信道编码在通信系统中的地位和作用第4页2023/2/2数字通信系统工作原理解调器：其输入信号一般是受到干扰的混合波形，解调器的任务就是从有用信号和干扰的混合波形中恢复有用的信号，这个过程与调制器的过程相反。由于干扰的作用，解调器的输出信号不可避免地包含着差错，差错的多少不应超过系统所规定的数值。信源译码器：把解调器输出的序列变换成为信源输出的估值。信宿：用户。

信道编码在通信系统中的地位和作用第5页2023/2/2(2)通信系统的主要技术指标传输速率码元：携带数据信息的信号单元。码元传输速率（波特率、调制速率）：每秒钟通过信道传输的码元数。单位是波特（Bd）。比特率（比特传输速率）：每秒钟通过信道传输的信息量。单位是比特/秒（bit/s）。这两种传输速率的定义不同，它们都是衡量系统传输能力的主要指标.

二进制：每个码元的信息含量为1比特，二进制的波特率与比特率在数值上是相等的。

M进制：每一个码元的信息含量为log2M。如果码元传输速率为rs波特，相应的比特率rb为：rb=rslog2M(bit/s)信道编码在通信系统中的地位和作用第6页2023/2/2(2)通信系统的主要技术指标差错率：差错率是衡量传输质量的重要指标之一，有几种不同的定义码元差错率：指在传输的码元总数中发生差错的码元数所占的比例（平均值），简称误码率。比特差错率（误比特率）：指在传输的比特总数中发生差错的比特数所占的比例（平均值）。在二进制传输系统中，码元差错率就是比特差错率。码组差错率：指在传输的码组总数中发生差错的码组数所占的比例（平均值）。根据不同的应用场合对差错率有不同的要求。在电报传送时，允许的比特差错率约为10－4～10－5；计算机数据传输，一般要求比特差错率小于10－8～10－9；遥控指令和武器系统指令中，要求误比特率更小。信道编码在通信系统中的地位和作用第7页2023/2/2(2)通信系统的主要技术指标可靠性衡量传输系统质量的一项重要指标，工程中经常用平均无故障间隔时间来衡量。在数字通信系统中信息传输（存储）遇到的最主要的问题是在传输过程中出现差错的问题，也就是传输可靠性

的问题。在传输过程中产生不同差错的主要原因不同的传输系统有不同的性能；在传输过程中干扰不同。不同的用户或不同的传输系统对差错率的要求不同。有两种途径降低误码率以满足系统要求：降低信道（调制解调器/传输媒介）本身引起的误码率；采用信道编码，在数字通信系统中增加差错控制设备。信道编码在通信系统中的地位和作用第8页2023/2/2(2)通信系统的主要技术指标可靠性降低信道引起误码率的主要方法选择合适的传输线路：如有线线路中，电缆线路优于明线线路，光缆优于电缆；改进传输线路的传输特性或增加发送信号功率：如进行相位均衡和幅度均衡以改进线路的群延时特性和幅频特性，增加中继放大器。在无线信道中，可以增加发射机功率、利用高增益天线、低噪声放大器等方法改善信道；选用潜在抗干扰性较强的调制解调方案。信道编码在通信系统中的地位和作用第9页2023/2/2(3)采用信道编码的数字通信系统在某些情况下，信道的改善可能较困难或者不经济，可采用信道编码，以便满足系统差错率的技术指标要求。信道编码为系统设计者提供了一个降低系统差错率的措施。采用信道编码后的数字通信系统可用下图描述。信道编码在通信系统中的地位和作用第10页2023/2/26.1差错及差错控制系统分类(1)错误图样

在通信系统的接收端，若接收矢量R

和发送的原码字C不一样，例如C=(11000)，而R=(10001)，R与C不同，即出现了两个错误。这种错误是由信道中的噪声干扰所引起的。错误图样：设发送的码字为C=(v1,v2,…,vn)，接收矢量为R=(r1,r2,…,rn)；由于R=C+E，所以E=(e1,e2,…,en)=(c1+r1,c2+r2,…,cn+rn)；如ei=ci+ri，则表示码字的第i位受到干扰,也就是说R

的第i

位有错;

例如：C=(11000)，R=(10001)，根据上式可得：

E=(1+1,1+0,0+0,0+0,0+1)；可知接收矢量的第2位和第5位是错误的。第11页2023/2/2(2)错误种类随机错误：由随机噪声的干扰所引起。由于噪声的随机性，使得这种错误的特点为：各码元是否发生错误是相互独立的，通常不会成片地出现错误。突发错误：由突发噪声的干扰所引起。(3)检错码与纠错码检错码：有发现错误能力但没有纠正错误的能力。纠错码：有发现并纠正错误能力的码，是一种重要的抗干扰码。6.1差错及差错控制系统分类第12页2023/2/2(4)纠错编码的分类按校验位与信息位之间的约束关系来分分组码：编码的规则仅局限于本码组之内，本码组的监督元仅和本码组的信息元相关。卷积码：本码组的监督元不仅和本码组的信息元相关，而且还与本码组相邻的前n－1个码组的信息元相关。按校验位与信息位之间的关系来分线性码：编码规则可以用线性方程表示；非线性码：编码规则不能用线性方程表示；6.1差错及差错控制系统分类第13页2023/2/2(4)纠错编码的分类按码字的结构分系统码：前k个码元与信息码组一致；非系统码：没有系统码的特性。按纠正差错的类型分纠正随机错误的码；纠正突发错误的码。按码字中每个码元的取值分二进制码；多进制码。6.1差错及差错控制系统分类第14页2023/2/2

A.偶（或奇）校验方法偶校验位p和消息m之间的关系为

m0+m1+m2+…+mk－1+p=0(mod2)

则C=(m0,m1,m2,…,mk－1,p)为一个偶校验码字。

C中一定有偶数个“1”

所有可能的C的全体称为一个码率为k/(k+1)的(k+1,k)

偶校验码；确定校验位p的编码方程为：p=m0+m1+m2+…+mk－1

当差错图案E中有奇数个“1”，即R

中有奇数个位有错时，可以通过校验方程是否为0判断有无可能传输差错。校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错。（5）检错与纠错原理6.1差错及差错控制系统分类第15页2023/2/2

B.重复消息位方法

n重复码：码率为1/n，仅有两个码字C0和C1，传送1比特(k=1)消息；

C0=(00…0)，C1=(11…1)n重复码可以检测出任意小于n/2个差错的错误图案

BSC信道：pb≤1/2，n比特传输中发生差错数目越少，概率越大：

(1－pb)n>pb(1－pb)n－1>…

>pbt(1－pb)n－t>…

>pbn

总认为发生差错的图案是差错数目较少的图案，当接收到重复码的接收序列R

中“1”的个数少于一半时，认为发送的是C0，否则认为是C1。（5）检错与纠错原理6.1差错及差错控制系统分类第16页2023/2/2B.重复消息位方法（5）检错与纠错原理6.1差错及差错控制系统分类图示纠1个任意差错的3重码第17页2023/2/2C.等重码（定比码）设计码字中的非0符号个数恒为常数，即C由全体重量恒等于m的n重向量组成。5中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错。（5）检错与纠错原理6.1差错及差错控制系统分类第18页2023/2/2

(6)差错控制的基本方式前向纠错(FEC)

发送端发送能够被纠错的码；接收端收到这些码后，通过纠错译码器不仅能自动发现错误，而且能自动纠正接收码字传输中的错误。6.1差错及差错控制系统分类第19页2023/2/2

(6)差错控制的基本方式自动请求重发(ARQ):重传反馈方式

发送端发出能够发现（检测）错误的码；接收端收到通过信道传来的码后，译码器根据该码的编码规则，判决收到的码序列中有无错误产生；通过反馈信道把判决信号告诉发端；发端根据这判决信号，把接收端认为有错的消息再次传送，直到接收端认为正确接收为止。6.1差错及差错控制系统分类第20页2023/2/2

(6)差错控制的基本方式自动请求重发(ARQ)ARQ方式对系统的要求必须有一反馈信道；适用于一个用户对一个用户的通信；信源能够控制；系统收发两端必须互相配合，控制电路比较复杂。前向信息反馈(IRQ)：也称回程校验方式。收端把收到的数据,原封不动地通过反馈信道送回到发端;

发端比较发的数据与反馈来的数据，从而发现错误，并且把错误的消息再次传送，直到发端没有发现错误为止。6.1差错及差错控制系统分类第21页2023/2/2(6)差错控制的基本方式混合纠错(HEC)：是FEC与ARQ方式的结合发端发送同时具有自动纠错和检测能力的码组；收端收到码组后，检查差错情况，如果差错在码的纠错能力以内，则自动进行纠正；如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。这种方式在一定程度上避免了FEC方式要求用复杂的译码设备和ARQ方式信息连贯性差的缺点，并能达到较低的误码率，因此在实际中的应用越来越广。6.1差错及差错控制系统分类第22页2023/2/2(6)差错控制的基本方式6.1差错及差错控制系统分类第23页2023/2/26.2纠错码的基本概念分组码：就是对每个k位长的信息组，按照一定规则增加r=n－k位校验码元，构成长度为n的序列(cn－1，cn－2，…，c1，c0)，该序列称为码字(或者码组、码矢)。如果采用二进制码，则信息组共有2k种组合，经过编码后相应码字只有2k种，称这2k个码字集合为(n，k)分组码。每个长度为n的序列称为n重，(n，k)分组码的码字集合数量只有2k个，所以，分组码就是确定某种规则，从2n个n重中筛选出2k个不同的码字。被选中的2k个n重为许用码组，其余的2n－2k个码字为禁用码组。码率：表示信息位在码字中所占的比例。(n，k)分组码的码率为R=k/n。第24页2023/2/2卷积码(n0，k0，m)：是对每段长度为k0的信息组，按照一定的规则增加r0=n0－k0个校验元，构成长度为n0的码段，而r0个校验元不仅与当前本段的信息元有关，而且与前m段的信息元也有关，当信息元不断输入时，输出码序列为半无限长。上图是一个(2，1，2)卷积码编码器，其中k0=1，即每次输入一位信息到移位寄存器，而输出码元组的个数为n0=2，即每输入一个信息位，编码器输出两个码元。6.2纠错码的基本概念第25页2023/2/2(n0，k0，m)卷积码的码率为R=k0/n0，与m无关。在卷积码中，称n0(m+1)为编码约束码长，说明k0个信息从输入编码器到移出移寄存器时对编码输出影响的码元数。汉明距离：两个n重x、y之间对应码元取值不同的个数，称为这两个n重之间的汉明距离，用d(x、y)表示。n重x中非零码元的个数称为汉明重量，简称重量，用w(x)表示。(n，k)分组码中，任意两个码字x、y之间的汉明距离的最小值，称为该分组码的最小汉明距离，简称为最小距离，表示为最小汉明距离表明该分组码抗干扰能力的大小。它与码字的检错、纠错能力有关，d0越大，码的抗干扰能力越强，在相同的译码规则下，错误译码的概率越小。6.2纠错码的基本概念第26页2023/2/2例6.1(3，2)码共有四个码字，分别为000，011，101，110，

d0=2。例6.2讨论(n，1)重复码的检错能力和错误译码概率，假设码元错误概率为pe=0.1。

(1)(2，1)重复码。只有两个码字(00)和(11)，d0=2，R=1/2。只有当发送端发送码字为(00)而接收端接收码字错成(11)，或(11)错译码为(00)时，才造成错误译码。

若用不完备译码(并与ARQ结合)，只有当两个码元同时出错时，才会造成无法识别的错误，所以错误译码概率为p2e=10－2。这种码能发现传输中的一个错误，但不能自动纠正。6.2纠错码的基本概念第27页2023/2/2(2)(3，1)重复码。它的两个码字是(000)和(111)，d0=3，R=1/3。

设发送端发送码字是(000)，若收到的是(001)或(010)或(100)，则根据大数译码准则判断为(000)，信息组为0；若收到的是(011)，(101)，(110)，(111)中之一，则造成错误译码，错判为信息组是1。所以正确译码的概率为

Q=1－［(1－pe)3+3pe(1－pe)2］同理，当发送端发送码字(111)时，正确译码的概率与上述结果相同。所以不管发送端发送码字(000)、(111)的先验概率如何分布，正确译码概率都为Q。因此，该码能纠正序列中的一个错误，此时错误译码概率

p=1－Q=1－［(1－pe)3+3pe(1－pe)2］=2.8×10－26.2纠错码的基本概念第28页2023/2/2(3)(4，1)重复码。显然，该码的d0=4，R=1/4。由于n是偶数，故只能采用不完备译码。它的纠错能力如下：

①能纠正一个错误的同时发现两个错误。

若发送的是(0000)，则错一个时，根据大数准则可正确判断发送的是0的信息组。若错两个变成(0011)，(1100)，(1010)，(0101)，(1001)，(0110)之一时，则译码器无法做出判决，而指出发生了两个错误。仅在变成(1110)，(0111)，(1011)，(1101)和(1111)时，译码器才做出错误译码。这时的错误译码概率

②若仅用来检错，则可检测e=d0－1=3个错误。若发送的是(0000)，则仅在变成(1111)时，才产生错误译码，而其他情况均能正确译码或发现错误。因此，这时的错误译码概率

p=p4e=10－4

6.2纠错码的基本概念第29页2023/2/2(4)(5，1)重复码。(5，1)码的d0=5，R=1/5。它的纠错能力如下：①能纠正两个随机错误，这时的错误译码概率传送信息组0、1的错误概率从0.1降至0.7%，约降低了两个量级。

②若仅用来检错，则能发现e=d0－1=4个错误。

若与ARQ系统结合进行纠错，则错误译码概率大约为

p=p5e=10－5

随着码长n的增加，重复码的d0=n越来越大，抗干扰能力越来越强。6.2纠错码的基本概念第30页2023/2/2通过上面这些例子可看出，(n，k)分组码的最小距离d0与纠错能力和检错能力之间有如下关系。

任意(n，k)分组码，如果要在码字内检测e个随机错误，则要求码的最小距离满足d0≥e+1；纠正t个随机错误，则要求d0≥2t+1；纠正t个随机错误，并且检测e(≥t)个错误，则要求d0≥e+t+1；纠正t个随机错误和ρ个删除，则d0≥e+ρ+1。最小距离为d0，至多能够检测e=d0－1个错误，能够纠正

个错误。该定理确定了分组码纠错能力、检错能力与汉明距离之间的关系，是纠错理论中的基本定理之一。6.2纠错码的基本概念第31页2023/2/2(n，k)分组码的最小汉明距离d0与n、k之间满足下列关系：

d0≤n－k+1例如，(7，4)线性分组码的最小汉明距离为d0=n－k+1=4，最多可以检测3个错误，而只能够纠正1个错误。奇偶校验码是只有一个检验元的(n，n－1)分组码，其最小汉明距离为2，所以只能检测一个错误，而没有纠错能力。奇偶校验码随着n的增加，码率接近1，而错误译码概率接近误码元率pe。也就是说，随着码长的增加，该码的抗干扰能力接近0。6.2纠错码的基本概念第32页2023/2/26.3译码规则译码器的任务就是根据已知的编译码规则，从接收到的序列中尽可能正确地恢复信源发送的信息。

对于译码器来说，编译码规则是已知的，即发送端所采用的编码算法及其对应的码集合是已知的。其任务就是根据接收到的码字序列确定发送端发送的码字，所以接收到的码字序列也是已知的。第33页2023/2/26.3.1两种译码规则先讨论单个符号传输情况。对于二元对称信道，信道输入为x，输出为y，如图所示。译码应当根据接收到的符号y确定输入符号是x=a1=0还是x=a2=1。信道的特性及其参数为，信道错误传输的概率为pe，正确传输概率为1－pe，信源输入的先验分布为p(x=0)=p，则p(x=1)=1－p。信道译码就是根据接收到的符号、信道特性及信道输入的先验分布找到信道输入的估值

，即最有可能发送该消息的输入符号。从统计角度而言，信道输入的估值应当满足称为最佳译码，即错误译码的概率最小。6.3译码规则第34页2023/2/26.3.1两种译码规则由于概率P(xi|y)是后验概率，因此该方法称为最大概率译码(MAP)。后验概率P(xi|y)应当根据贝叶斯公式进行计算。得到后验概率为于是得到最大后验译码规则为：如果P(0|y)>P(1|y)，则；否则，。6.3译码规则第35页2023/2/26.3.1两种译码规则将上述分析方法推广到矢量情况中。假设接收的码字序列为r=(r1，r2，…，rn)，而码字集合为C，其中元素ci满足ci=(ci1，ci2，…，cin)。译码的主要任务是如何尽可能正确地再现码字ci。在已知接收符号序列r的条件下，译码器需要从码集合中找到一个码字ci作为译码估值，满足这就是最大后验译码。后验概率可根据先验概率P(ci)和信道转移矩阵，再据贝叶斯公式得到6.3译码规则第36页2023/2/26.3.1两种译码规则在实际中，为了便于译码，通常可以做出下列假设：

(1)构成码字集合的各个码字的先验概率是相等的，即P(ci)=P(cj)，对所有的i，j；(2)P(r)对于任何序列都有相同的概率取值。根据上述两种假设，P(ci|r)最大等价于P(r|ci)最大，于是最大后验概率译码等效于最大先验概率译码，即最佳译码等价于最大似然译码(MLD)。对于无记忆信道而言，码字的似然函数P(r|ci)就是构成该码字的联合概率，等于各个码元的似然函数的乘积，即其中，n为码字的序列长度。所以最大似然译码为6.3译码规则第37页2023/2/26.3.1两种译码规则信道为二元对称信道时，根据汉明距离的定义，序列r中如果有d个码元与ci的码元不同，则对应的汉明距离为d，所以对于二元码，d就是发送码的码元与接收码的码元中不同码元的数量，此时的似然函数为在实际通信系统中，码元错误概率p总是很小，即p/(1－p)<<1，而(1－p)n为常数，所以汉明距离d越小，则P(r|ci)越大；反之，汉明距离d越大，则P(r|ci)越小，这样最大似然函数对应于最小汉明距离，于是最大似然译码转化为汉明距离译码。汉明距离译码是一种硬判决译码，逐个比较接收码字r与各种可能码字ci的对应码元，选择汉明距离最小的码字作为译码估值。6.3译码规则第38页2023/2/26.3.2错误译码概率在信道特性一定的情况下，各种可能码字ck产生某一接收序列rj的概率为如果接收序列rj确实是由码字ci产生，对于特定序列rj，正确译码概率Pc(rj)为Pc(rj)=P(rj|ci)P(ci)相应错误译码的概率Pe(rj)为

Pe(rj)=P(rj)－Pc(rj)对于选择好的译码规则，错误译码的概率PE应当为所有接收序列rj对应的错误译码概率Pe(rj)之和，即6.3译码规则第39页2023/2/26.3.2错误译码概率平均错误译码概率为设rj译码时选择的输入码字编号为irj，则错误译码概率可以表示为平均错误译码的概率取决于译码规则。对于最大后验概率译码，译码规则是根据规则选择的。对于最大似然译码而言，译码规则是maxP(rj|ci)。当先验概率分布P(ci)满足等概率分布，且P(r)对于任何序列都有相同的概率取值时，平均错误译码的概率是最小的，此时最大似然译码与最大后验概率译码相当。6.3译码规则第40页2023/2/26.3.2错误译码概率举例：设信道输入、输出符号集合分别为{a1，a2，a3}和{b1，b2，b3}，而且信道转移矩阵为6.3译码规则选择两种译码规则分别计算输入为等概率分布和p(a1)=0.25、p(a2)=0.25、p(a3)=0.5时，两种译码规则对应的平均错误译码概率。解(1)当输入为等概率分布时，两种译码规则的平均错误译码概率分别为由于译码规则A就是最大似然译码，当输入等概率时，p(bj)(j=1，2，3)都相等，所以最大译码是最优的，平均错误译码概率最小。第41页2023/2/26.3.2错误译码概率举例：6.3译码规则(2)当输入分布为p(a1)=0.25、

p(a2)=0.25、p(a3)=0.5时，两种规则的平均错误译码概率分别为从结果可以看出PE′(B)>PE′(A)，尽管概率转移矩阵是对称的，但是由于输入不是等概分布的，因此最大似然译码并不是最优的，即其对应的平均错误译码概率不是最小的。第42页2023/2/26.3.2错误译码概率举例：6.3译码规则已知信道的转移矩阵为采用最大似然译码，当输入为等先验分布，求平均错误译码概率PE；如果先验分布为(0.4，0.4，0.2)，重新计算PE。解:最大似然译码规则就是选择转移矩阵中的每列元素最大值作为译码输出的估值，所以错误译码概率为当先验分布为(0.4，0.4，0.2)时,由此可见，尽管输入为等概率分布，但是当接收的各个符号概率不相等时，最大似然估计的错误译码概率也不是最小的。第43页2023/2/26.3.2错误译码概率举例：6.3译码规则设离散无记忆信道的误码元率为pe=0.1，现有两个码字(000，111)通过信道传输，假设码字是等概率分布的，采用最大似然规则译码，计算译码平均错误概率PE。解由于码字长度n=3，信道输出端接收的码字共有23=8种组合，将其表示为b0~b7，并将输入两种码字表示为{a0，a1}。由于两个码字中每个码元都可能出错，根据误码元率可以得出条件转移为p(b0|a0)=(1－pe)3=0.729

p(b0|a1)=p3e=10－3

p(b1|a0)=(1－pe)2pe=8.1×10－2

p(b1|a1)=(1－pe)p2e=9×10－3

p(b2|a0)=(1－pe)2pe=8.1×10－2

p(b2|a1)=(1－pe)p2e=9×10－3

p(b3|a0)=(1－pe)p2e=9×10－3

p(b3|a1)=(1－pe)2pe=8.1×10－2

p(b4|a0)=(1－pe)2pe=8.1×10－2

p(b4|a1)=(1－pe)p2e=9×10－3

p(b5|a0)=(1－pe)p2e=9×10－3

p(b5|a1)=(1－pe)2pe=8.1×10－2

p(b6|a0)=(1－pe)p2e=9×10－3

p(b6|a1)=(1－pe)2pe=8.1×10－2

p(b7|a0)=p3e=10－3

p(b7|a1)=(1－pe)3=0.729第44页2023/2/26.3.2错误译码概率举例：6.3