信道编码,纠错码基础

第6章信道编码本章内容：有扰离散信道的编码定理纠错编译码的基本原理与分析方法线性分组码卷积码1第六讲信道编码

PartI--有噪信道编码信道编码的意义译码规则信源编码提高数字信号有效性将信源的模拟信号转变为数字信号 降低数码率,压缩传输频带(数据压缩)信道编码提高数字通信可靠性

数字信号在信道的传输过程中,由于实际信道的传输特性不理想以及存在加性噪声,在接收端往往会产生误码。3编码有噪信道编码定理（香农第二定理）离散、无记忆、平稳信道，信道容量为C，只要待传送的信息率R<C，就一定能找到一种信道编码方法，使得码长N足够大时，平均差错率Pe任意接近于零。香农第二定理是存在性定理，它指出在R<C时，肯定存在一种好的信道编码方法，使Pe逼近零。但并没有给出编码的具体方法。

有噪信道编码逆定理离散、无记忆、平稳信道，信道容量为C，如果信息率R>C，则肯定找不到一种信道编码方法，使得码长N足够大时，平均差错率任意接近于零。1、香农信息论对信道编码的指导意义信道编码定理：每一个信道具有确定的信道容量C，对于任何小于C的信息传输率R，总存在一个码长为n，码率等于R的分组码，若采用最大似然译码，则其译码错误概率PE满足

PEAe-nE(R)

其中：A是常数，E（R)为误差函数错误概率PE越小，传输可靠性越高。增大码长n也可提高传输可靠性有噪信道编码定理（香农第二定理）

如一个离散无记忆信道，信道容量为C。当信息传输率R≤C时，只要码长足够长，总可以在输入符号集中找到M个码字组成的一组码和相应的译码准则，使信道输出端的平均错误译码概率达到任意小。有噪信道编码逆定理

如一个离散无记忆信道，信道容量为C。当信息传输率R>C时，则无论码长n多长，总找不到一种编码使信道输出端的平均错误译码概率达到任意小。信道编码的理论依据：当取信道容量C以下的信息传输率时，以指数趋进于0；当取分界点以下的信息传输率时，以指数趋进于1；因此在任何信道中，信道容量都是可达的、最大的可靠信息传输率。存在定理，它没有给出一个具体可构造的编码方法，但有助于指导各种通信系统的设计，有助于评价各种系统及编码的效率。差错符号、差错比特差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示；差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示；对于二进制传输系统，符号差错等效于比特差错；对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。10误码率/差错率根据不同的应用场合对差错率有不同的要求:在电报传送时,允许的比特差错率约为:10－4～10－5；计算机数据传输,一般要求比特差错率小于:10－8～10－9；在遥控指令和武器系统的指令系统中,要求有更小的误比特率或码组差错率11通常，降低误码率可采取两方面的措施：一是降低信道本身引起的误码率。二是采用差错控制、纠错编码技术。差错图样（errorpattern）为了定量地描述信号的差错，定义收、发码之“差”为： 差错图样E＝发码C－收码R

（模M）例：8进制(M=8)码元， 若发码 C=（0,2,5,4,7,5,2） 收码变为 R=（0,1,5,4,7,5,4） 差错图样 E=C－R=（0,1,0,0,0,0,6）（模8）12差错图样（errorpattern）二进制码：E=CR或

C=RE

，差错图样中的“１”既是符号差错也是比特差错，差错的个数叫汉明距离。13设发送的码字C1111111111

接收的码字R1001001111

差错的图样E0110110000差错图样中的“1”既是符号差错也是比特差错,差错的个数叫汉明距离。0:传输中无错1:传输中有错

差错类型随机差错：差错是相互独立的,不相关，以相等的概率独立发生于各码字、各码元、各比特存在这种差错的信道是无记忆信道或随机信道----(较多恒参信道)突发差错：指成串出现的错误,错误间有相关性,一个差错往往要影响到后面一串字----(随参信道)差错码元开头、以差错码元结尾，之间并不是每个码元都错，而是码元差错概率超过了某个额定值E:001001000000

10011100000

14突发长度=4突发长度=6纠错码分类15从功能角度讲,差错码分为检错码和纠错码检错码：用于发现差错纠错码：能自动纠正差错纠错码与检错码在理论上没有本质区别,只是应用场合不同,而侧重的性能参数也不同。纠错码分类对信息序列的处理方法：分组码、卷积码码元与原始信息位的关系：线性码、非线性码差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论：代数码、几何码、算术码、组合码等16检错与纠错举例0:晴,1:雨若1→0,0→1。收端无法发现错误1700晴1001110011雨能发现一个错误禁用码组插入1位监督码后具有检出1位错码的能力,但不能予以纠正。检错与纠错举例18000晴010001111000111雨晴在只有1位错码的情况下,可以判决哪位是错码并予以纠正,可以检出2位或2位以下的错码，但纠错能力有限，比如111000。100011101110雨择多译码纠错编码的基本思路纠错能力的获取归结为两条：一条是利用冗余度，另一条是噪声均化（随机化、概率化）19冗余度就是在信息流中插入冗余比特。例：3bit表示4种意义。1、增加码长N例：设某BSC信道误码率Pe=0.01，假如编码后的纠错能力是10%。先设码长N=10，码字中多于1位误码时就会产生译码差错，差错概率为：纠错编码的基本思路2、噪声均化就是让差错随机化，就是设法将危害较大的、较为集中的噪声干扰分摊开来。卷积：卷积码在一定约束长度内的若干码字之间加进了相关性，译码时不是根据单个码字，而是一串码字，这样就可以将噪声分摊到码字序列而不是一个码字上。交错：交错是对付突发差错的有效措施。如果保持码率不变，将码长增加到N=40，那么当码字中多于4位误码时，会产生译码差错，差错的概率为信道编码（纠错编码）在被传输信息中附加一些冗余码,即监督码元,利用附加码元与信息码元间的约束关系加以校验,以检测和纠正错误。信源编码减少了冗余度冗余度是随机的、无规律的信道（纠错）编码增加了冗余度冗余度是特定的、有规律的,故可利用其在接收端进行检错和纠错。21传输冗余比特必然要占用更多的资源。时间：比如一个比特重复发几次,或一段消息重复发几遍,或根据收端的反馈重发受损信息组。频带：插入冗余比特后传输效率下降,若要保持有用信息的速率不变,方法之一是增大符号传递速率(波特率),结果就占用了更大的带宽。功率：采用多进制符号,用8进制ASK符号代替4进制ASK符号来传送2比特信息,可腾出位置另传1冗余比特。8进制ASK符号的平均功率肯定比4进制时要大,这就是动用冗余的功率资源来传输冗余比特。设备复杂度：加大码长,采用网格编码调制,是在功率、带宽受限信道中实施纠错编码的有效方法,代价是算法复杂度的提高,需动用设备资源。22差错控制系统分类前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力231.前向纠错方式前向纠错方式：FEC(ForwardError-Correction)。利用纠错码自动纠正收端检出的错误。

FEC方式的优点是：无需反馈信道，传信率恒定，译码延时恒定，有利于实时处理和同步。

FEC方式的缺点是：如果纠大量的错误，必须插入较多的监督码元，编码效率低，需增加相应的信道容量，或使用高效码，对于高可靠性通信，选择适用的纠错码及其译码算法往往比较困难。自动请求重传系统有三种：停发等侯重发返回重发选择重发停发等候重发

停发等候重发方式在两个码组之间有停顿时间（T1），使传输效率受到影响，但由于工作原理简单，在计算机数据通信中仍得到应用过程演示即停等候重发系统中：1发送端1接收端TW发送端在TW时间内送出一个码组给接收端接收端进行检验即停等候重发系统中：1发送端1接收端TWACKT1接收端未发现错误，则发回一个认可信号（ACK）给发送端两码组之间有停顿时间T1即停等候重发系统中：1发送端1接收端TW发送端收到信号ACK后再发出下一个码组ACKT12233即停等候重发系统中：1发送端1接收端TWACKT1223如果接收端检测出错误，则发回一个否认信号NAK发现错误3NAK发送端收到信号后重发前一个码组即停等候重发系统中：1发送端1接收端TWACKT12233发现错误NAK3返回返回重发

返回重发系统比停发等候重发系统有很大改进，在许多数据传输系统中得到应用过程演示1发送端接收端发送端无停顿地送出一个又一个码组给接收端不再等候ACK信号123411发送端接收端234发现错误一旦接收端发现错误便发回NAK信号34253NAK6TW11发送端接收端2234发现错误34NAK34562TW发送端重发下一个码组时先重发前N段码组11接收端2234发现错误34NAK34562TW2345645623789101145678从码组2开始重发发送端返回11发送端接收端2234发现错误34NAK34562TW2345645623789101145678从码组2开始重发N=5选择重发

选择重发系统传输效率最高，但另一方面价格也最贵，应为它要求较为复杂的控制,在发送、接收端都要求数据缓存器。

此外，重发系统和返回重发系统都需要全双工的链路，而停发等後系统只要求半双工的链路。过程演示1发送端接收端发送端无停顿的送出一个又一个码组给接收端不再等候ACK信号123411发送端接收端234发现错误一旦接收端发现错误便发回NAK信号。这几步和返回重发是一样的。34253NAK6TW11发送端接收端234发现错误34253NAK6TW发送端重发有错误的一组。（而返回重发要重发前面所有的码组）4211接收端2234发现错误34NAK34562TW27891045627111213141589101112只重发码组2发送端返回43混合纠错(HEC)：是FEC与ARQ方式的结合。发端发送同时具有自动纠错和检测能力的码组,收端收到码组后,检查差错情况,如果差错在码的纠错能力以内,则自动进行纠正。如果信道干扰很严重,错误很多,超过了码的纠错能力,但能检测出来,则经反馈信道请求发端重发这组数据。信息反馈(IRQ)：收端把收到的数据,原封不动地通过反馈信道送回到发端,发端比较发的数据与反馈来的数据,从而发现错误,并且把错误的消息再次传送,直到发端没有发现错误为止。有噪信道编码的译码准则实际的信道传输过程中，差错的发生往往不可避免；错误概率和信道统计特性等相关；选择合适的译码规则能降低差错。

[例]错误概率与译码规则有关01XY01二元对称信道错误概率不仅与信道的统计特征有关，而且也与译码规则有关。信道编码以及译码将信道用图5-1所示的模型表示。信道编码器信道信道译码器uxy信道模型

信源输出序列u，经信道编码器编成码字x=f(u)并输入信道，由于干扰，信道输出y，信道译码器对y估值得

=F(y)

。

译码器的任务是从受损的信息序列中尽可能正确地恢复出原信息。两种常用译码规则信道总不可避免会搀杂噪声，所以信息在信道传输过程中，差错是不可避免的。选择合适的译码规则可以弥补信道的不足。1．最大后验概率译码准则发送码矢xk，其发送概率为q(xk)，通过信道转移概率为p(y︱xk)的信道传输，接收到矢量y，信道译码器输出

通信过程可用图5－5所示框图表示。信源信道编码器信道信道译码器信宿干扰{xk}{y}图5－5通信过程框图

当估值≠xk时，就产生了误码，用（x︱y）表示后验概率，则收到y估错的概率为

（5-2）

通信总希望错误概率最小，由式(5-2)可看出错误概率pe

(xk)最小等同于后验概率（xk︱y）最大，这就是最大后验概率译码准则。

根据概率关系式

（5-3）

根据式（5-3）后验概率（x︱y）最的就意味着p（x

y）全概率最大，因此最大后验概率译码准则也称为最大联合概率译码准则。【例5.5】信源分布，信道转移概率矩阵,信道输出符号Y={y1,y2,y3}，按最大后验概率准则译码。(1)根据p(xy)=p(y︱x)q(x)算出全概率，用矩阵表示

(2)根据，算出[（y）]=[0.380.340.28]

(3)再由算出后验概率，用矩阵表示

(4)按最大后验概率准则译码，在后验概率矩阵中，每列选一最大值（矩阵中带下划线的值），译为

(5)若按最大联合概率译码准则译码，在全概率矩阵[p(xy)]中每列选一最大值（矩阵中带下划线的值），也可译出

最大后验概率译码准则存在问题：

不易实现,对于信道，可以获知统计特性P（y/x）,但难以获得信源分布p（x），因此无法求得全概率p（xy）；

而获得后验概率（收发）也很困难。

在实际应用中，一般按最大信道转移概率来确定估值，即在收到矢量y后，在所有的xm(m=1,2,…,M)中,选一个转移概率p(y︱xm)最大的xm值，作为对y的估值=xk，这一译码规则称为极大似然译码规则。2．极大似然译码准则---退而求其次已知接收序列的条件下使先验概率最大的译码算法实际应用中，能够获知信道的统计特性p(y/x)，所以可根据信道转移概率来确定码字估值。3．平均错误概率

（5-4）

【例5.6】计算[例5.5]的平均错误概率，若信源等概分布，对其译码，并求平均错误概率。

()å=-=Mjkj1)(1yxyfw（1）求平均错误概率pe根据式（6-4）得=0.01+0.12+0.07+0.12+0.1+0.02=0.44(2)当信源等概分布，按最大似然函数译码准则译码，[例5.5]已给出信道转移概率矩阵在矩阵的每列中选一最大值(矩阵中带下划线的值)，译码为平均错误概率最优译码与最大似然译码译码器的任务是从受损的信息序列中尽可能正确地恢复出原信息。译码算法的已知条件是：实际接收到的码字序列{r},r=(r1,r2,…,rN)发端所采用的编码算法和该算法产生的码集XN，满足信道模型及信道参数。55最优译码：最大后验概率译码准则最佳译码，也叫最大后验概率译码(MAP:Maximumaposteriori)已知r的条件下找出可能性最大的发码作为译码估值,通过经验与归纳推测发码的方法56

消息组mi

码字ci

接收码r

估值

消息编码器信道译码消息还原最大后验概率译码准则等同于最小传输错误概率准则57

消息组mi

码字ci

接收码r

估值

消息编码器信道译码消息还原存在问题：

不易实现,对于信道，可以获知统计特性P（y/x）,但难以获得信源分布p（x），因此无法求得全概率p（xy）；

而获得后验概率（收发）也很困难。

已收到码为条件的条件概率全概率、联合概率，也等同于最大联合概率译码准则次最优：最大似然译码准则最大似然译码(MLD:MaximumLikelihoodDecoding)已知r的条件下使先验概率最大的译码算法实际应用中，能够获知信道的统计特性p(y/x)，但很难获得信源分布P(x),无法求得全概率p(xy)所以根据信道转移概率来确定码字估值。58最优译码与最大似然译码的关系如果构成码集的2K个码字以相同概率发送，满足P(ci)=1/2K

，i=1,2,…,2K

P(r)对于任何r都有相同的值，满足P(r)=1/2K

则P(ci/r)最大等效于P(r/ci)的最大，在此前提下最佳译码等效于最大似然译码。59最优译码与最大似然译码对于无记忆信道，

[例]：BSC信道的最大似然译码可以简化为最小汉明距离译码。汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等概率，汉明距离译码也就是最佳译码。

60[例]已知信道矩阵并设p(x1)=1/2,p(x2)=p(x3)=1/4,分别用最小错误概率准则和最大似然译码准则确定相应的译码规则，并计算平均错误概率。解：由于输入符号不是等概率分布，所以对于最小错误概率准则必须根据联合概率的大小来选择。p(x1y1)=1/4,p(x2y1)=1/24,p(x3y1)=1/12p(x1y2)=1/6,p(x2y2)=1/8,p(x3y2)=1/24p(x1y3)=1/12,p(x2y3)=1/12,p(x3y3)=1/8故译码规则是F(y1)=x1,F(y2)=x1,F(y3)=x3对于最大似然译码准则，可以直接从信道矩阵的传递概率来选择，译码规则是F(y1)=x1,F(y2)=x2,F(y3)=x3平均错误概率为pE=1/24+1/12+1/6+1/24+1/12+1/12=12/24p’E=1/24+1/12+1/8+1/24+1/12+1/12=11/24<pE64选择最佳译码规则只能使错误概率pE有限地减小，无法使其任意的小。要想进一步减小错误概率，必须优选信道编码方法。[例]已知信道转移矩阵如下，试确定译码规则。解只知转移概率，无法找出最佳译码规则，只能采用最大似然译码规则。将转移概率矩阵各列最大的值标出，重写转移矩阵如下：

按转移概率最大原则确定最大似然译码规则如下：

尽管一般情况下并不知道这样译码的差错率。但可以证明，当信道输入等概时，最大似然译码规则也是最佳的。纠错码的数学基础：

矢量空间与码空间基本的纠错码为（n,k）分组码（块码）每块为k个符号由n个码元组成码字码字可视为n重矢量（n个矢量元素）67矢量空间与码空间F表示码元所在的数域(对于二进制码，F代表二元域{0,1})设n重有序元素的集合V={Vi

},若满足条件：V中矢量元素在矢量加运算下构成加群；V中矢量元素与数域F元素的标乘封闭在V中；分配律、结合律成立，则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。68矢量空间中矢量的关系

对于域F上的若干矢量线性组合：

线性相关：

其中任一矢量可表示为其它矢量的线性组合线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替.69矢量空间与基底一组线性无关的矢量，其线性组合的集合就构成了一个矢量空间V，这组矢量就是这个矢量空间的基底。n维矢量空间应包含n个基底基底不是唯一的，例：线性无关的两个矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可张成同一个两维空间。70二元域GF(2)上三重矢量空间以（100）为基底可张成一维三重子空间V1，含21=2个元素，即以(010)(001)为基底可张成二维三重子空间V2，含22=4个元素，即以(100)(010)(001)为基底可张成三维三重空间V,含23=8个元素，V1和V2都是V的子空间。71概念重数构成矢量的有序元素的个数维数构成矢量空间的基底的个数72矢量空间每个矢量空间或子空间中必然包含零矢量两个矢量正交：V1V2＝0两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交正交的两个子空间V1、V2互为对偶空间

(DualSpace)，其中一个空间是另一个空间的零空间（nullspace，也称零化空间）。73码空间

74

消息k长 (n,k)码字n长

qk

种分组编码器qn种

k维k重矢量n维n重矢量

通常qn>>qk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。分组编码的任务选择一个ｋ维n重子空间作为码空间。确定由k维k重信息空间到ｋ维n重码空间的映射方法。码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。75随机编码编码的分析设计途径：1.数学解析途径，即将代数、几何、数论等理论运用到编解码，如分组码，卷积码。2.运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作随机码界。用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。76随机编码对于一个(N,K)分组编码器对K个q进制组成的消息组m=(m0,m1,…,mk-1)编码；生成N个q进制符号组成的码字c=(c0,c1,…cN-1)；在(N,K)分组编码器中随机选定的码集有qNM种一个消息组的编码有qN种选择（N个码元，q进制）qK个消息组共有种选择令M=qK，可得上式77随机编码在(N,K)分组编码器中随机选定的码集有