差错控制的基本概念

1、第九章差错控制的基本概念1本章内容提要差错控制系统及其理论基础纠错编码的基本概念及其本质纠错编码方法的性能评价、基于图形的编码2差错控制的理论基础主要是香农第二定理和近世代数。 （1）香农第二定理 这个抗干扰信道编码定理作为一个存在性定理，指出可以用任意接近信道容量的信息传输速率传送消息，且出错的概率可以任意小。引发了人们对纠错码的研究。纠错码理论的中心任务就是要针对具有不同干扰特性的各种信道设计出编码效率高、抗干扰性能好、而编译码设备又较简单的纠错码或检错码。 9.1.1差错控制的理论基础9.1 差错控制系统及其基础3 （2）近世代数经典代数学以数为主要的研究对象，而近世代数将研究对象由数扩

2、展到向量、矩阵等，以研究更为一般的代数运算的规律和性质为目标，推动了以讨论群、环、域、多项式、向量空间等性质和结构为主要内容的理论的发展。近世代数又称为抽象代数，在研究信道编码的许多具体构造规律时，发现用近世代数的理论能够对编码结构给予非常吻合的描述，因此成为信道编码的重要理论基础。 9.1.1差错控制的理论基础9.1 差错控制系统及其基础4差错控制系统根据它们的纠、检错能力；对信道的要求及适应性；编、译码器的复杂性；编、译码的实时性等性能指标可以分为如下4类自动请求重传系统前向纠错系统信息重复查询系统混合纠错系统9.1.2差错控制系统9.1 差错控制系统及其基础5图9.1 ARQ系统(1)自

3、动请求重传系统 通信系统在接收端检测到传输错误并自动告知发送方，请求发送方重发，称为自动请求重发，简称反馈重传。系统构成如图9.1所示。9.1.2差错控制系统9.1 差错控制系统及其基础6该系统接收端在收到的信码中检测出错码时，即设法通知发送端重发，直到正确收到为止。 所谓检测出错码，是指在若干接收码元中知道有一个或一些是错的，但不一定知道该错码的准确位置。图9.2列举了3种最流行的ARQ方式停止 等待式ARQ具有回拉功能的连续ARQ具有选择性重发功能的连续ARQ9.1.2差错控制系统9.1 差错控制系统及其基础7图9.2 自动请求重发（ARQ）8停止等待式ARQ只需要半双工连接，因为发射机在

4、接到确认信号后才进行下一个传送；具有回拉功能的连续ARQ需要全双工连接，通信双方的终端设备同时传输，发送方传送信息数据，接收方传送确认信号和非确认信号，在ARQ过程中，发送方被“拉回”到错误传送的消息处，从错误消息开始处重发所有的信息数据；具有选择性重发功能的连续ARQ也需要全双工连接，但它只要求错误的消息重发，然后发射机从先前停止的地方继续发送原序列而不重发已经正确接收的消息。 9.1.2差错控制系统9.1 差错控制系统及其基础9ARQ系统的优点是：纠错能力强；检错能力与信道干扰变化无关，适应性强；由于只要检测错误就可以了，因此编译码器比较简单。ARQ系统的缺点：必须有反向信道，否则只能检错

5、收、发两端必须互相配合信源能够被控制实时性较差因此它只适用于当发生错误需要重发的情况。9.1.2差错控制系统9.1 差错控制系统及其基础10 (2)前向纠错（FEC）系统系统的接收端不仅能在收到的消息序列中发现错误，还能够将其纠正。前向纠错系统的基本组成如图9.3所示。 图9.3 FEC系统9.1.2差错控制系统9.1 差错控制系统及其基础11纠错编码主要应用在数字通信中，根本目的是提高通信的可靠性。 根据香农第二定理，只要信道的信息传输速率小于信道容量，接近无差错传输的编码就是一定存在的，且信道容量C、信号带宽B和到达接收端的信噪比S/N满足香农公式。因此，可以把纠错编码看成这3个参量相互影

6、响彼此权衡的结果。 在数字通信中，信噪比通常用Eb/N0来表示，其中Eb和 N0分别为信号的比特能量和噪声的功率谱密度，它们在数值上和S/N相等。9.1.2差错控制系统9.1 差错控制系统及其基础12通信系统误比特率与Eb/N0关系的曲线两者采用相同的调制方法和同样的信道，可见信道编码使得在同样信噪比情况下降低了误比特率，或者在更低的信噪比情况下也能达到误比特率的要求。 9.1.2差错控制系统9.1 差错控制系统及其基础图9.4 典型编码与未编码的差错性能比较13定义9.1 对于给定的误比特率，编码增益G是指通过编码所能实现的Eb/N0的减少量，即： (9.1) 其中 和 分别表示未编码及编码

7、后所需要的Eb/N0 。 例如，为了获得低于10 4 的误比特率，对于未编码情况必须使Eb/N0至少保持在12dB以上，而采用编码后仅需至少保持在8dB以上，在这种情况下获得了4dB的编码增益。9.1.2差错控制系统9.1 差错控制系统及其基础14 FEC系统的优点是：收端可自动发现错误、纠正错误；不需反向信道；能进行一点对多点的同播，可以是双向通信或单向通信；与ARQ相比，译码实时性好；控制电路比ARQ简单。 FEC系统的缺点主要有：译码比较复杂；所选用的纠错码要和信道的干扰情况相匹配，对信道的适应性较差，一般以最坏的信道条件来设计纠错码；通常是以注入冗余度为代价来换取编码增益，注入的冗余度

8、越大编码增益越高，一般情况下编码效率较低。 9.1.2差错控制系统9.1 差错控制系统及其基础15 (3)信息重复查询系统（ IRQ ）是指接收端将收到的消息原封不动地转发回发送端，在发送端与原发送消息相比较的系统。如果发现错误，则发送端再进行重发，直至正确为止。原理和设备都较简单，但需要有双向信道，因为相当于每一消息都至少传送了两次，所以传输效率较低。 (4)混合纠错系统（HEC）HEC系统将反馈重传技术与前向纠错技术相结合。当出现少量错码并在接收端能够纠正时，即用前向纠错方法纠正之；当错码较多超过其纠正能力但尚能检测时，就进行自动反馈重传。混合纠错结合了ARQ和FEC两者的优点。 9.1.

9、2差错控制系统9.1 差错控制系统及其基础161. 差错控制码的分类 不同的差错控制系统需要不同的差错控制码。从差错控制码功能的角度，可将常见的差错控制码分为以下3类： （1）检错码：只能发现错误，不能纠正错误。在一些仅需给出错误提示以及ARQ系统中使用这类码。 （2）纠错码：能够发现错误也能纠正错误。FEC和HEC系统都使用这类码。 （3）纠删码：能够发现并纠正或删除错误。纠错码的应用最为广泛。9.2.1纠错编码的分类9.2 纠错编码的基本概念及其本质172.纠错码的分类 图9.5 纠错码分类示意图9.2.1纠错编码的分类9.2 纠错编码的基本概念及其本质18(1)根据对信息元的处理方法分类

10、按照对信息元处理方法的不同，可以将纠错码分为分组码和卷积码。分组码的构成如图所示。 其码长为n = k + r，其中 k是信息元个数， r是监督（校验）元个数，监督元只与本组信息元有关。 通常将分组码写成码(n , k)，或称为(n , k)码。9.2.1纠错编码的分类9.2 纠错编码的基本概念及其本质19卷积码的构成如图所示，其中n0 k0 。 最主要特点是n0 k0个监督元不仅与本组的信息元有关，还与前m段的信息元有关。 类似于分组码，也称n0为卷积码的码长， k0为信息元个数，m为存储级数。通常将卷积码写成码(n0, k0 , m)，或称为(n0, k0 , m)码。 9.2.1纠错编码

11、的分类9.2 纠错编码的基本概念及其本质20（2）根据校验元与信息元之间的关系分类 根据校验元与信息元之间关系的不同，可以将纠错码分为线性码和非线性码。（3）根据纠正错误的类型分类纠随机错误码纠突发错误码纠同步错误码既纠随机又纠突发错误码。（4）根据每个码元的取值分类二进制码q进制码，其中q =pm，p为素数，m为正整数。（5）根据码的结构特点分类循环码、非循环码、系统码，完备码等。9.2.1纠错编码的分类9.2 纠错编码的基本概念及其本质219.2.2纠错编码的分类9.2 纠错编码的基本概念及其本质几个基本定义定义9.2 设码字v=(v0,v1, vn-1)C，令w(v)为码字v中那些不为0

12、的码元的个数，即(9.2)则w(v)是码字v的汉明重量，简称重量。定义9.3 码C中所有那些不等于0的码字的重量的最小值称为码C的最小重量。即(9.3)22根据最小汉明距离的定义，(n，k)码的最小汉明距离d为该种编码中任两个码字间距离的最小值，即 (9.4)定义9.4 设发码C: (cn-1, c1,c0) 或(c0, c1, ,cn-1) ，收码R: (rn-1, r1,r0)或(r0, r1, ,rn-1) ，则定义信道的错误图样为E: (en-1, e1,e0)或(e0, e1, ,en-1) ，其中(9.5)由定义可知R=C+E (9.6) E=CR (9.7) 9.2.2纠错编码的

13、分类9.2 纠错编码的基本概念及其本质23定义9.5 在错误图样中，若“1”集中于某个长度b内，则称该种错误为长度为b的突发错误，其中b称为突发错误长度，该图样称为突发错误图样。 典型的突发错误图样为：00111100，中间含有b个连续的1。对于一些编码（例如循环码），突发错误图样也包括首尾相接的错误，其错误图样为： 11000011，其中两段分别连续的1的个数共为b。9.2.2纠错编码的分类9.2 纠错编码的基本概念及其本质24定义9.6 分组码是对每段k位长的信息组，以一定规则增加r =nk个监督(校验)元，组成长为n的序列(cn 1, cn 2, c1, c0)，称这个序列为码字或码组、

14、码矢。在二进制的情况下，k位长的信息组共2k个，通过编码器后，码字还是2k个，称这2k个码字的集合为(n，k)分组码。n长序列的可能排列共有2n种，其中只有2k个n重构成了(n, k)分组码，称它们为许用码组，其余的2n2k个n重为禁用码组。9.2.2纠错编码的分类9.2 纠错编码的基本概念及其本质25定义9.7 (n0, k0, m)卷积码是对每段k0长的信息组以一定的规则增加r0 = n0k0个监督(校验)元，组成长为n0的码段；n0 k0个校验元不仅与本段的信息元有关，且与前m段的信息元有关；编码约束长度nc=n0 (m+1)，它表示k0个信息元从输入编码器到离开时，在码序列中影响的码元

15、数目。定义9.8 将信息位在码字中所占的比例称为编码效率，也称为码字效率，通常也用R表示。对于分组码，有R = k/n (9.8) 对于卷积码，有R = k0 / n0 (9.9) 编码效率是衡量编码有效性的基本参数。 9.2.2纠错编码的分类9.2 纠错编码的基本概念及其本质262. 纠错码举例 （1） 重复码重复码是k =1的分组码 (n, 1), 它的(n 1)个校验元是信息元的重复。对二进制系统，只有两个码字：00.0，11.1，其中1和0的个数均为n。重复码的译码采用大数判决方法，也称为大数准则，或最大似然准则、最小距离准则，即译码时以大于n/2的最小整数作为判决门限。若n是奇数，可

16、以实现完全的译码，称为完备译码；若n是偶数，则会出现1、0个数相等的情况，将导致译码失败，称为不完备译码，但由于检出了错误，可作删除处理或结合ARQ进行译码。9.2.2纠错编码的分类9.2 纠错编码的基本概念及其本质27重复码特点：d = n，随着n的增大，抗干扰能力越来越强，但R = 1/n随之下降，编码效率越来越低；检错能力大于或等于纠错能力，距离d 越大，纠错能力越强。若未编码时接收的错误概率为 ，经过n次重复编码后，如果结合ARQ技术，其接收的错误概率可降低到 。9.2.2纠错编码的分类9.2 纠错编码的基本概念及其本质28 （2）奇偶校验码 奇偶校检码是只有一个校验元的分组码(n,

17、n1)，即k = n1，其组成和方法如图9.8所示。 若每个码字中1的个数为偶数，则为偶校验；若每个码字中1的个数为奇数，则为奇校验。图9.8 奇偶校检码的组成和编码方法9.2.2纠错编码的分类9.2 纠错编码的基本概念及其本质29由于每个码字均按同一规则构成，所以奇偶校验码是一种致校验码。码的性能在接收端，译码过程包括检验码字的各比特的模2和是否为0，如果结果是1，则代表码字中存在错误。它是一种检错码且只能检测奇数个错。假设所有比特发生错误的可能性是相同的，且相互独立，则一个n比特长的符号发生j位错误的可能性为 (9.10)9.2.2纠错编码的分类9.2 纠错编码的基本概念及其本质30设无法

18、检测的错误概率为Pnd，则有 (9.12)如果是奇校验，则求和的上限值为(n 1)/2。奇偶校验码特点： （1）d = 2，能检1个错，也能检奇数个错； （2）R = (n 1)/n，编码效率很高。随着n的增大，编码效率趋近于1，但d /n 则趋近于0，即抗干扰能力随之下降。 9.2.2纠错编码的分类9.2 纠错编码的基本概念及其本质31纠错编码的本质是通过在发端的码字中引入可控的冗余度换取传输可靠性的提高。以分组码为例，它获得纠、检错能力的本质，是由于加入了(n k)个监督码元。k个码元的消息集合最多具有2k个消息组合，同样，n个码元的码字集合最多具有2n个消息组合许用码组的个数为2k而禁用

19、码组的个数为 (2n 2k) 。若由于错误使接收到的码字落到了禁用码组里，就必然可被检测出来，同时也给纠正提供了可能，这取决于编码的结构。如果由于错误而使接收到的码字落到了许用码组里，则无无法判别是无错还是有错，从而造成不可检测的错误。 9.2.3纠错编码的本质9.2 纠错编码的基本概念及其本质32这种以注入冗余度来获取可靠性提高的方法，必然带来信息传输速率的降低。但根据香农第二定理，信息传输速率接近于信道容量且具有任意小错误概率的通信是存在的，即编码效率接近于1 且又能使错误概率任意小的信道编码是存在的，这就给编码工作者提出了严峻的课题。在后面几章将会看到，人们发现的所谓“好码”，主要是在同

20、样的编码效率下具有更高的纠错或检错功能。9.2 纠错编码的基本概念及其本质9.2.3纠错编码的本质33编码性能优劣可以用最小码距d的大小来表征。定理9.1 任一(n，k)分组码，若要在码字内： (1) 检测a 个随机错误，则要求d a+1； (2) 纠正 t 个随机错误，则要求d 2t+1； (3) 检测a个并纠正t (t a )个随机错误，则要求da+t+1。证明（1）可以由图9.9(a)简单证明： 9.3 纠错编码方法的性能评价图9.9(a)34设一码组A位于0点。若码组A中发生一位错码，则可以认为A的位置将移动至以0点为圆心、以1为半径的圆上某点，但其位置不会超出此圆；若码组A中发生两位

21、错码，则其位置不会超出以0点为圆心、以2为半径的圆。因此，只要最小码距不小于3（如图中B点），在此半径为2的圆上及圆内就不会有其它码组。这就是说，码组A发生两位以下错码时，不可能变成另一任何许用码组，因而能检测错码的位数等于2。同理，如果一种编码的最小距离为d，则将能检测 (d 1)个错码；反之，若要求检测a个错码，则最小码距d至少应不小于(a +1)。9.3 纠错编码方法的性能评价35 （2）可以图9.9 (b)来加以说明。 9.3 纠错编码方法的性能评价图9.9 码距与检错和纠错能力的关系（b）36图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出以原位置为圆

22、心，以2为半径的圆。若接收码组落于以A为圆心的圆上，就判决收到的是码组A；若落于以B为圆心的圆上，就判决为码组B。这样，就能够纠正两位错码。若这种编码中除码组A和B外，还有许多种不同码组，但任两码组之间的码距均不小于5，则以各码组的位置为中心、以2为半径画出的圆都不会互相重叠。每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距d = 5时，能够纠正两个错码，且最多能纠正两个。若错码达到3个，就将落于另一圆上，从而发生错判。为纠正t个错码，最小码距d应不小于(2 t +1)。9.3 纠错编码方法的性能评价379.3 纠错编码方法的性能评价(3)先说明什么是“检测a个并纠正t (t a)

23、个错误”（简称“纠检结合”）。在某些情况下，要求对于出现较频繁但错码数很少的码组，按前向纠错方式工作，以节省反馈重发时间；同时又希望对一些错码数较多的码组，在超过该码的纠错能力后，能自动按检错重发方式工作，以降低系统的总误码率。这种工作方式就是“纠检结合”。在上述“纠检结合”系统中，差错控制设备按照接收码组与许用码组的距离自动改变工作方式。若接收码组与某一许用码组间的距离在纠错能力t范围内，则按纠错方式工作；若与任何许用码组间的距离都超过t，则按检错方式工作。 38以图9.9(c)来加以说明。设码的检错能力为a，则当码组A中存在a个错码时，该码组与任一许用码组（例如图中码组B）的距离应至少为t

24、+1，否则将进入许用码组B的纠错能力范围内，而被错纠为B。这样就要求最小码距d至少为a + t +1。9.3 纠错编码方法的性能评价（c）图9.9 码距与检错和纠错能力的关系399.4 基于图形的编码编码的主要挑战是设计接近信道容量同时具备合理的译码复杂度的编码方案。Turbo码、低密度奇偶校验码（LDPC）等专门的Turbo类编码采用简单的迭代译码算法，在许多重要的信道上都能非常接近香农极限，它们的共同特征是都可作为基于图形的编码来理解。图形编码方案在保持合理的译码复杂度的同时接近信道容量。低密度奇偶校验码、Turbo码和大部分可译的接近香农极限的纠错码都可以理解成图形编码。图形能构造出用于

25、迭代译码的和积译码算法。因式（因子）图用来描述编码以及在译码时必须处理的联合概率分布。409.4 基于图形的编码9.4.1编码的图形建模（1）Tanner图Tanner定义了一种称为Tanner图的二次分裂图，将码字的符号与这些符号必须满足的限制联系起来.Tanner还介绍了两种基于图形的译码算法，即和积算法和最小和算法。图9.10给出（7，4）汉明码的两种Tanner图 。41图9.10 （7，4）汉明码的两种Tanner图：a)局部校验;b)全局校验9.4 基于图形的编码9.4.1编码的图形建模429.4 基于图形的编码9.4.1编码的图形建模图9.10(a) 有7个变量顶点，用圆圈表示，

26、对应每个码字中的7个符号x1, x2, , x7。三个校验顶点，表示每个码字必须满足的二进制线性方程。一个有效码字，它每个校验顶点的邻点（即与校验顶点相连的变量）都必须形成模二和为零（即有偶数个1）的构造。 例如(x1, x2, , x7)=(1, 1, 1, 0, 0, 0, 0)和(x1, x2, , x7)=(0, 1, 1, 1, 0, 1, 0)是有效码字，(x1, x2, , x7)=(1, 1, 1, 0, 1, 1, 0)则不是，因为不是每个校验式都满足上述关系。可以将Tanner图中的多个校验顶点聚合成一个，如图9.10(b)所示，称为全局校验，而将图9.10(a)的形式称为

27、局部校验。439.4 基于图形的编码9.4.1编码的图形建模（2）因式图通常将含有状态变量的Tanner图称为因式图。图9.11(a)是(7, 4)汉明码的格图，图9.11(b)是对应的因式图。格图中从最左边顶点出发向右一系列路径上的标示代表汉明码的16个码字。辅助变量s0, s1, s7不直接表示码字符。第i个格区约束了(si-1, xi, si)的可能的组合；事实上，在此线性格图的例子里，这些三元组总能形成线性码。 44图9.11 (a)（7，4）汉明码的trellis图；(b)对应的因式图 459.4 基于图形的编码9.4.1编码的图形建模例如，第3个格区由（00, 1, 01），（01

28、, 0, 10）等8个线性组合构成了局部编码。这码可以认为是二进制（5, 3）码，如图9.11(b)所示。注意到状态变量通常并不是二进制的，图9.11(b)的因式图用并行线的数量对应构成每个状态变量的比特数。两端的状态s0和s7规定总为0，因此实际上它们是零比特变量或常量，于是它们与图9.11(b)因式图的连接用虚线表示。469.4 基于图形的编码9.4.1编码的图形建模因式图可用于建模许多编码结构。例如Turbo码便是根据图9.12(a)所示编码原理构成的。此编码器输入k信息比特x=(x1, , xk)，产生两个不同的奇偶校验比特流p=(p1, , pk)和q=(q1, , qk)，选择(x

29、, p)对和(x, q)对，使其分别是(2k, k)码C1和C2中的码字，通常选择C1和C2为同样的编码器，图中代表信息比特的置换，即用于计算q的信息比特与p的相同，但顺序不同。图9.12(b)是对应的因式图，其组成码均由单个校验顶点建模而成。在图9.12(c)中，这些全局校验被分解为与C1和C2的格图表示相对应的链状图。47图9.12 (a)并行链接码的编码；(b)对应的因式图；(c)格图结构码的因式图 489.4 基于图形的编码9.4.2 采用和积算法译码当考虑到译码问题时，基于图形建模的编码的作用就显现出来了。译码本质上是一个统计推导问题：给定一系列的观察（噪声信道输出对发送的码字的响应

30、），推测最有可能发送的是哪一个码字（ML译码），或者各码元最可能的取值（逐码元MAP译码）。和积算法试图通过沿着因式图的边线传递消息的方式来解决逐码元MAP译码问题。499.4 基于图形的编码9.4.2 采用和积算法译码（1）概率质量函数的因式图表示因式图可用来建模编码，也可用于表示一个含许多变量的函数的因式分解结构。例如，设函数g(x1, , x7)可因式分解为3个函数f1(x1, x2, x4, x5)、f2(x2, x3, x4, x6)和f3(x4, x5, x6, x7)的乘积，则g的因式图同图9.11(b)所示汉明码因式图的结构一样，只是校验顶点由对应于f1、 f2和 f3的因式顶

31、点代替。设g是自变量x1, , xn,的某种全局函数，且g = ，其中各个fj是以x1, , xn的某个子集为自变量的局部函数。因式图表示g的因式分解具有n个变量顶点和m个因式顶点。当且仅当xi是fj的一个自变量时，变量顶点xi和因式顶点fj之间有一条边连接。509.4 基于图形的编码9.4.2 采用和积算法译码标识函数是因式图应用中的重要函数。若P(x1, , xn)是对变量x1, , xn的某种预测，则P的标识函数记作P，当P在x1, , xn构造上判为真时就取值1，反之为0。例如x1 x2 xn = 0判为1，当且仅当二进制变量x1, , xn构成偶校验式。仅当所有的标识函数都判为1时它

32、们的积判为1。由此，如果g(x1, , x7)是f1 、f2 和f3 的乘积，g判为1当且仅当f1 、f2 和f3都判为1时，即当且仅当变量x1, , xn满足定义(7, 4)汉明码的3个奇偶校验方程时。因此g可看作是码成员关系的标识函数g = (x1, x7 ) C，其中C表示(7,4)汉明码。由此，图9.10(a) 一是理解为汉明码的Tanner图，另一个是理解为汉明码成员关系标识函数的因式图。519.4 基于图形的编码9.4.2 采用和积算法译码 码成员关系标识函数还可看作是概率质量函数，表示在二进制n元组上的分布，在码字上是均匀分布的，而非码字上的分布为0。假设据此选出一码字x=(x1

33、, , xn) C，将它在无记忆信道上发送，接收到的矢量为y = (y1, , yn)。无记忆性表明其联合概率密度函数p(y,x)可分解因式成p(y,x)= p(x) ，其中p(x)是xC的标量形式。对任何给定的接收y，后验概率质量函数p(x|y)由函数g(x1, xn )= (x1, xn ) C 乘以一个比例因子给定，其中x1, , xn是的g的自变量，且给定的y1, , yn作为固定参数使用。 529.4 基于图形的编码9.4.2 采用和积算法译码当然，g(x1, , xn)具有较好的因式分解结构，所以可用因式图表示。这样的因式图具有和C一样的因式图结构，除了与变量顶点xi相连的是表示p

34、(yi|xi)的待定因式顶点。此待定顶点表示在任何给定的译码问题中必须处理的确证。这样的确证顶点如图9.13所示，图中(a)所示的方向表示左至右消息mxf，概括了左边子图中收集的确证， (a)所示的方向表示右至左消息mf x ，概括了右边子图中收集的确证。 53图9.13树图中的和积算法运算过程549.4 基于图形的编码9.4.2 采用和积算法译码（2）非循环因式图中的和积算法计算码元xi的后验概率质量函数p(xi|y)时，逐码元最大后验（MAP）译码要求能够选择出与xi最相似的值。显然函数g(x1, , xn)表示标乘一个比例因子后的联合后验概率质量函数。计算p(xi|y)需进行边界化运算，

35、即计算：和积算法用于同时计算各个边界值，只要所需处理的因式是非循环的，就可以得到有效和精确的计算结果。和积算法可以理解成沿着因式图的边线传递消息的运算。 559.4 基于图形的编码9.4.2 采用和积算法译码消息的本质首先，消息就是函数。因式图的边线总是连着变量顶点x和函数顶点f，如图9.13所示。消息可以沿这条边线以任何方向通过（xf 或fx）。在与变量x相连的边线上传递的消息总是定义x的符号集上的函数。例如设x是定义在符号集0，1上的二进制变量，则在与x相连的任何边线上传递的消息都是形如(x)的函数。此函数可由矢量(0), (1)或比率(0)/(1)及lb(0)/(1)表示。由此，消息就是

36、一个一系列值所指定的函数。我们将从变量顶点x到因式顶点f的消息记为x f (x)，而从因式顶点f到变量顶点x的消息记为f x (x)。 569.4 基于图形的编码9.4.2 采用和积算法译码 因为消息就是函数，因此可像函数一样作乘积运算。由此，如果1(x)和2(y)分别是x和y的函数，则它们的积1(x)2(y)是（x ,y）的函数。和积算法由两个更新准则和一个终止准则定义。用N(v)表示因式图中顶点v的邻点集合。如果wN(v)，则v和w有公共边线，且集合N(v)w表示除w外与v相邻的点。变量顶点的更新准则：由变量顶点x到相邻的因式顶点fN(x)的消息xf表示为(9.13)即由变量顶点x发送到相

37、邻的因式顶点fN(x)的消息，可由在x处收到的来自除f外所有邻点的消息的乘积得到。579.4 基于图形的编码9.4.2 采用和积算法译码因式顶点的更新准则：从因式顶点f到相邻的变量顶点xN(f)= x, y1, y2, , ym的消息f x 由下式得到：(9.14)即由f到相邻的变量顶点x的消息得到：先将f处来自除x外其他邻点的消息与f相乘，再对得到的函数关于x边界化。终止准则： x的边界函数由下式得到：(9.15)即x的边界函数是x收到的所有消息的乘积。 589.4 基于图形的编码9.4.2 采用和积算法译码 在非循环因式图中，由任何顶点v发出的消息都可以计算并沿边线e送出，只要能得到沿除e

38、外其他所有边线到达v的消息。由此可知，消息传递始于叶状顶点，因为这些点能在一开始时提供所有需要的信息。 一旦每个变量顶点都已收到所有邻点的消息，则算法终止。对于一个含E条边线的有限非循环因式图，不超过2E步便可满足终止条件（即一条边线上不再需要发送超过两条消息，每个消息一个方向）。定理9.2 在一个表示函数g(x1, , xn)的有限非循环因式图中，由和积算法根据式(9.15)计算得的函数(xi)是xi.的边界函数。599.4 基于图形的编码9.4.2 采用和积算法译码当g(x1, , xn)表示在给定某个观察确证点e下n个随机变量的条件概率质量函数p(x1, , xn| e)时，非循环因式图

39、中和积算法运算过程中所传递的消息具有特定的含义。非循环因式图的每条边线都促使图形划分为两个子图，即左子图和右子图，且将确证分为左确证el和右确证er，分别和左、右子图相连。消息x f (x)是给定左确证条件下x的条件概率质量函数。消息f x (x)是给定右确证条件下x的条件概率质量函数。这些消息的乘积就是给定所有确证时x的条件概率质量函数。 60 非循环因子图的一个重要例子就是格图。在描述格图的链形因式图中，和积算法的运算导致了消息沿因式图边线的前向和后向传播(如图9.12(b)所示)，从而得到了著名的前向/后向算法或称BCJR算法。前向传播消息常用符号表示，后向传播消息用表示。从非循环因式图中对消息的一般阐述的观点看来，消息代表给定过去确证情况下状态变量的条件概率质量函数，而消息代表给定将来确证情况下状态变量的条件概率质量函数。因此，著名的BCJR算法是和积算法的特例，且由于因式图是非循环的，定理9.2保证了计算的结果是真实的边界函数（即每个符号的后验概率质量函数）。 9.4 基于图形的编码9.4.2 采