线性分组码最佳软判决译码原理研究

武汉理工大学硕士研究生课程论文 课程：《现代信息理论与传输技术》 开课学院：信息工程学院 学期：2010-2011年度第2学期

成绩

《现代信息理论与传输技术》

姓 名 宋 黎 学 号 104972103129 院 系 信息工程学院 专 业 信号与信息处理 班 级 信研9班

提交时间： 2011 年 6 月 13 日

线性分组码的最佳软判决译码原理研究

宋 黎

（武汉理工大学，湖北 武汉430063）

摘要：首先介绍线性分组码提出的背景，概述了主要几类线性分组码发展过程，它们的优点。讨论了线性分组码和软判决的基本原理，介绍了线性分组码的最佳软判决译码的原理， 关键字：线性分组码；软判决；最大似然译码

Research on The Best Soft-Decision Decoding

for Linear Block Codes

Song Li

（ Wuhan University of Technology,Wuhan 430063,China ）

Abstract: The background of linear block codes are introduced briefly at first.we discuss its advantage, and future trends., discuss the theory of linear block codes and soft-decision decoding and also discuss the theory of it that the best soft-decision decoding of linear block codes Keywords: linear block codes; soft-decision decoding;MLD

引言：近年来，对高效可靠的数字传输和存储系统的需求日益增长。这种需求随着在商业、政府和军事领域面向数字信息的交换、处理和存储的大规模高速数据网的出现而变得更加的迫切。这类系统的设计要求通信与计算机技术的融合，系统设计者所关心的一个主要问题就是：如何控制差错以使得数据能够可靠重现。线性分组码在信息的的传输中具有重要的作用，在早期，科学家汉明就发现了线性分组码中的一个特例：汉明码。它是一种完备码，可简单地通过查表机制来译码。适当地缩短汉明码，可以得到最小的距离为4、纠单个差错并检测两个差错的好码。由于码率高并且译码简单，汉明码及其缩短码在近几年广泛应用于数字通信和数据存储系统中的差错控制。在早期构造的用于纠错检错的第二类线性分组码是里德—穆勒码。里德—穆勒码是穆勒为交换电路设计和差错检测而提出的。里德—穆勒码构成了一大类能够纠正多个随机错误的码。这些码构造简单并且具有丰富的结构特性，可以采用各种软判决算法进行译码。里德—穆勒码的一些软判决译码算法也已经被设计出来，它们能够在很低的译码复杂度条件下得到很好的误码性能。线性分组码可以说在现代通信中有着极其广泛的应用。

1 线性分组码的基本原理

差错控制编码的基本作法是：在发送端被传输的信息序列上附加一些监督码元，这些多余的码元与信息之间以某种确定的规则建立校验关系。接收端按照既定的规则检验信息码元与监督码元之间的关系，一旦传输过程中发生差错，则信息码元与监督码元之间的校验关系将受到破坏，从而可以发现错误，乃至纠正错误。

对于（n，k）线性分组码编码器，输出的n比特码字包含k比特信息码元和nk比特监督码元。如图1所示。

消息比特

mk1,mk2,,m0 bnk1,bnk2,,b0 监督比特

图1 系统码的码字结构

根据图1的表示法，码字最右边的nk比特为监督比特，最左边k比特与相应的信息比特相同。因此有

 bi, i0,1,,nk1 ci （1）

mink , ink,,n1 nk个监督比特是k个信息比特的线性和，可以用一般的多项式表示：

bip0im0p1im1p(k1)imk1 （2） 系数的定义如下

1, 如果bj依赖于mipij （3）

0, 如果b不依赖于mji系数pij的选择要是生成矩阵的各行线性独立，且校验式唯一。

式（1）和式（2）给出了（n，k）线性分组码的数学结构。这两个等式可以用矩阵表示法重新表示为一种紧凑的形式。为此，我们定义1k的信息矢量m，1nk监督矢量b和1n的码矢量c，其形式分别为

m[mk1,mk2,,m0] （4）

b[bnk1,bnk2,,b0] c[cn1,cn2,,c0]

（5）

（6）

注意，这三个都是行矢量。这样就可以用紧凑的矩阵形式将定义监督比特的联立等式写为

cmP （7） 其中，P为knk的系数矩阵，其定义如下：

pk1,nk1 pk1,nk2  pk1,0pk2,nk1 pk2,nk2  pk2,0 P （8）   p p  p0,nk20,00,nk1其中，pij取值1或0。

由式（4）~式（6）可知，c可以表示为由矢量m和b组成的分块矢量：

cbm （9） 将式（7）代入式（9），并提出公因子m，得

cmPIk （10）

Ik为kk的单位矩阵。定义kn的生成矩阵为

GPIk （11） 上式给出的生成矩阵的k行之间是线性独立的，也就是说，G中任意一行都不能表示为其它各行的线性组合。利用生成矩阵的定义，可将式（10）简化为

cmG （12）

使信息矢量m在2k个二进制k元组的范围内变化，并利用式（12）即可生成全部码字集合。且其中任意两个码字的和为另一个码字。线性分组码的这种特性称为封闭性。

线性分组码的信息比特和监督比特的关系可以用另一种方法来表示。以H表示一个nkn的矩阵，其定义为

HInkPT （13）

其中，PT是一个nkk的矩阵，表示系数矩阵P的转置，Ink为nknk的单位矩阵。因此分块矩阵的乘法运算如下：

PT HGTInkPT PTPT （14）

Ik在模2运算中，有PTPT0，0表示nkk的空矩阵（所以因素都等于零的矩阵）。所以 HGT0 （15） 同样地，由GHT0，此处0是一个新的空矩阵。将式（12）右乘H的转置矩阵HT，根据式（15），可得

cHTmGHT0 （16） 矩阵H称为线性分组码的监督矩阵，式（16）所列的等式称为监督方程。

生成方程式（12）和监督方程式（16）是描述和运算线性分组码的基本方程。这两个方程可用框图的形式来描述，分别如图2（a）和2（b）所示。

码矢量 消息矢量

生成矩阵 码矢量

m

G c

（a）

监督矩阵 零矢量

c

H 0

（b）

图2 生成方程和监督方程的框图

生成矩阵G应用于发射机的编码，而监督矩阵H则用于接收机的译码。对于后者，我们引入一

个1n的接收矢量r，该矢量由发送的码矢量c经过噪声信道得到。将矢量r表示为原始码矢量c与另一个矢量e的和，如下所示：

rce （17） 矢量e称为错误图样。如果r中第i个元素c中第i个元素相同，则e中相应的元素为0；另一方面，如果r中第i个元素c中第i个元素不相同，则e中相应的元素为1，这种情况就可以认为是i位产生的误码。也就是说，对于i1,2,,n，有

ei1, 如果在第i位产生了误码0, 其它 （18）

接收机的任务就是从接收矢量r中译出码矢量。通常，译码算法始于对一个称为误码校正子的

1nk的矢量计算，误码校正子也可简称为校正子。校正子的重要之处在于它仅取决于错误图样。

假设有1n的接收矢量r，则与之对应的校正子定义为

srHT （19） 校正子有如下重要性质：首先，校正子仅与错误图样有关，而与发送的码字无关。

srHTceHTmGHTeHTeHT （20） 因此，只要知道了监督矩阵H，就可以计算出校正子s。s仅与错误图样e有关，并且s的nk个元素是错误图样e的n个元素的线性组合。其次，不同码字的所有错误图样都有相同的校正子。式（20）包含nk方程，但具有n个未知数（e0,e1,,en1），因此，错误图样没有唯一解。满足式（20）的错误图样有2n个，但它们都对于于与性质（2）相符的同一个校正子。特别地，虽然有2nk个可能出现的校正子矢量，但包含在校正子s中的关于错误图样e的信息，还不足以使译码器准确地计算出发射端发出的码矢量。但是校正子s使真实错误图样的搜索范围由原来的2n种减少到2nk种可能。这样，译码器的任务就是从对应于s的陪集中得出最佳选择。

下面将线性分组码的译码过程描述为：对于接收矢量r，计算校正子srHT；在以校正子s作为表征的陪集中，鉴别出陪集首（具有最大发生概率的错误图样）e0。陪集首e0与校正子的对应关系为se0HT，而e0为所有可能出现的，且能够被纠正的错误图样；计算码矢量cre0，作为接收矢量r的译码输出。

2 线性分组码的最佳软判决译码

基于接收解调器的匹配滤波器硬判决输出的算法称之为硬判决译码算法，它是在每一个信号间隔内，匹配滤波器输出都量化为两个电平，即0和1，由于硬判决译码算法在匹配滤波器输出时采用了两电平量化，从而对信息造成了很大的损失，这样就会降低译码性能。 2.1软判决译码算法

如果匹配滤波器的输出不经过量化或者量化多于两个电平，我们称解调输出为软判决。匹配滤波器软判决输出软判决序列，而基于软判决序列的译码就称之为软判决译码。软判决译码能够提供比硬判决译码更好的译码性能，一般来说，软判决最大似然译码比硬判决译码多提供3分贝的编码增益，但是软判决译码能够获得更好的误码性能是以增强译码复杂度为代价的，软判决译码一般分为基于可靠性的译码算法和基于码结构的译码算法两大类。

软判决译码的最大似然译码也可称为最佳译码虽然有最优的译码性能，然而，在实际中实现它却很困难，主要是因为运算复杂度太高，对于长码尤其如此，如果使用暴力译码，对每一个码字都需要2次最佳量度运算和2-1比较才能找到最佳的译码码字。当k很大时，由于需要计算和比较的次数太多而实现困难。为了克服复杂度的问题，人们已经提出了多种非最优或次优的软判决译码算法，这些算法在误码性能和译码复杂度之间进行了良好的折中。 2.2 线性分组码的最佳软判决译码

由于线性分组码的种类很多，在这里就在加性白噪声信道上接收机使用最佳软判决译码时，二进制线性分组码的性能。

k

k

令E表示传输一个码字的信号能量，令Ec表示传输码字的一个元素（比特）所需的信号能量。由于每个码字有n个比特，所以E=nEc；又因为每个码字只传递k位信息比特，所以每个信息比特所需的能量为：EbEkEcEkcRrn。这里假定各个码字等概率发生，具有相同的先验概率1/M。

假设码字的各比特用二进制PSK发送，那么每个码字的波形必然取自M个传输信号波形之一。而高斯白噪声信道的最佳接收，也就是要使码字的平均差错概率最小。可以用一组（M个）并行的滤波器分别与M个可能的发送波形匹配来实现。在每个信号传输间隔的尾部（完成码字中n个比特的传输），要对各匹配滤波器的输出进行比较，送出输出值最大的匹配滤波器对应的码字。换一种方法，也可以使用M个互相关器。不管哪一种方法，接收机在实现是还可简化。也就是说，只要用一个滤波器（或互相关器）与传输码字每一比特的二进制PSK波形匹配，就可以构成一个等效的最佳接收机，后接一个译码器，用来生成与M种码字对应的M各判决变量。

具体的讲，令rjj1,2,......n表示发送任一指定码字后匹配滤波器的n个输出取样。由于信号是

用相干二进制PSK传输的，所以输出可用下列两式之一表示：

当码字的第j比特是1时，表示为

当码字的第j比特是0时，表示为

rEcn jjrjEcnj （1）

（2）

变量nj表示取样瞬间的加性高斯白噪声。每个nj的均值为0，方差为N0/2。根据已知的M种可能发送的码字和接收到的值，最佳译码器形成M个相关度

CMjCr,Cj(2Cij1)rj, i=1,2,….M （3）

j1尽管在软判决译码中根据式（3）计算相关度相对比较简单，但当码字数量巨大，比如M大于2

10

n时，当一个码用于二进制输入的对称信道，如加性高斯白噪声信道，并用最佳软判决译码时，第m个码字的传送差错概率对于所有m都是相同的。所以。为了简化起见，假定传送的是全零码字C1。要对C1正确译码，相关度CM1必须超过其余M-1个相关度CMm（m=2,……M）,所有这些CM都是高斯分布的，CM1的平均值是Ecn，CMm（m=2,……M）的平均值是Ecn（1-2m/n）。每个判决变量的方差是N0/2，正确译码概率（或零效于计算码字差错概率）的精确表达式涉及M个相关度之间的互相关性，C1和其余M-1个码字之间的互相关系数为：

m12m/n,，m=2,……M （4）

式中，m表示第m个码字的重量。

如果在加性高斯白噪声信道中用二进制正交FSK传送码字的每个比特，那么最佳接收机可用两

个匹配滤波器实现，一个滤波器与发送“0”的频率匹配，另一个滤波器与发送“1”的频率匹配。再接一个译码器，用来计算与M个可能的发送波形相对应的M个相关度，接收机的检测可以是相干的，也可以是非相干的。当然如果是相干检测，则相干PSK对信噪比的要求小3分贝。因为即使不编码的PSK也比二进制正交FSK好3分贝，由此看来，PSK对于FSK的优点在采用编码波形后仍然存在。当然，如果采用非相干检测，由于非相干组合的损失，性能将变得更差。 3 结束语

至此我们概述了线性分组码的基本原理以及线性分组码最佳软判决译码的原理，以及采用各种检测对差错性能的影响。可以看到，由于微处理机的飞速发展和广泛应用，以及由于软判决译码在信道中有很高的软判决增益，可以预料它将更加广泛的应用。

个别观点认为，由于集成电路的飞速发展，今后可以用数字式的最大似然译码代替软判决译码，因而断定软判决译码仅是一种过渡性的技术。但是事实上是最大似然译码的复杂性随码长指数增长，而其性能仅比软判决译码好零点几分贝。因此在性能成本比上，软判决译码无疑比最大似然译码要好。另一方面，从本质上讲软判决译码其实就是利用数字技术实现最佳的一种译码方法，一个设计的巧妙的软判决译码器，其实也就是一个最大似然译码器，而且可以快速译码，因此可以肯定，软判决译码有着极其广阔的前景。

参考文献

[1]杨莉芸，杜健，张白愚.基于可靠性的线性分组码软判决译码算法研究.信息工程大学学报，2009 [2]王新梅.软判决译码综述.通信学报，1985

[3]Shu Lin,Daniel J Costello,Error Control Coding[M].北京：机械工业出版社，2007 [4]John G.Proakis.Digital Communications[M].北京：电子工业出版社，2001

[5] Proakis J G. Digital Communications[M」.3rd ed. NewYork ; McGraw-Hill ,1995. 6.