（通信与信息系统专业论文）ieee80216e系统中的ldpc编解码器算法研究及硬件设计.pdf

东南大学硕士学位论文 摘要 低密度奇偶校验码( l d p c ) 码是由g a l l a g e r 在1 9 6 2 年首先提出的一种纠错码，在沉寂 了多年之后，最近又重新成为通信技术研究的热点。l d p c 码是一种具有稀疏校验矩阵的线 性分组码，采用迭代的概率译码算法，l d p c 码可以达到接近香农极限的性能。本论文首先 给出了一种高效、经济的q c u ) p c 码的编码方案，然后针对o c l d p c 码的特点重点研 究了快速译码算法和它的硬件实现。 编码方面，针对i e e e8 0 2 1 6 e 协议中给出的l d p c 码的校验矩阵具有准循环阵的特点， 本文给出了一种利用移位寄存器来大量节省器件消耗量的编码方案。解码方面，本文研究了 在白高斯噪声信道下，基于软判决迭代译码算法的一种具有很高并行度的快速译码算法一 t m b os u m 算法。文章给出了这种算法与b p 算法和m i ns u m 算法的性能对比以及算法在迭 代次数等问题上的仿真结果。之后，文章研究了这种快速译码算法的诸多定点化问题，在权 衡了性能和复杂度后，给出了较为合理的量化方案。 在论文的最后部分，文章给出了这种快速译码算法的硬件实现方案，并详细介绍了译码 器的总体结构和工作时序。此外，本文对每一个子模块的接口、内部结构和工作时序也进行 了详细的解释和说明。最后，文章分析了这种硬件实现方案的器件消耗量以及运算量。利用 这种硬件实现方案，在1 0 0 m 的时钟下，l ，2 码率码字的译码速率可以达到5 0 m 以上，同时 误码率和误帧率的性能也能保持较好的水平。 关键词：低密度奇偶校验码，b p 算法，m 访s u m 算法，髓e8 0 2 1 6 ；e 东南大学硕工学垃论史 a b s t r a c t l o wd e n s i t yp a r i t y c h e c k ( l d p c ) c o d e sw e r ef i r s td i s c o v e r e db yg a l l a g e ri nt h ee a r l y 19 6 0 sa n dr e c e n t l yh a v eb e e nr e d i s c o v e r e da n dg e n e r a l i z e d ，t h i sc l a s so fc o d e sd e c o d e dw i t h s o f t i ns o f t o u t ( s i s o ) i t e r a t i v ed e c o d i n gp e r f o r m sa m a z i n g l yw e l l t h er e s e a r c ho fh i 曲e f f i c i e n t e n c o d e ra n dh i g hs p e e dd e c o d e ri st h ef o c u so f t h i st h e s i s ， t h el d p cc o d e sg i v e ni nt h ep r o t o c o li e e e8 0 2 1 6 3 ea r eq u a s i - c y c l e ( q c ) l d p cc o d e s 。 a c c o r d i n gt ot h i sc h a r a c t e r i s t i c ，w ed e s i g n e dak i n do fe c o n o m i c a le n c o d e rw i t hs i m p l es h i f t r e g i s t e t s i nt h i st h e s i s ，s e v e r a li t e r a t i v em e s s a g ep a s s i n ga l g o r i t h m sf o rl d p cc o d e s ，s u c ha s b e l i e fp r o p a g a t i o n ( b p ) a l g o r i t h m ，m i ns u ma l g o r i t h ma n dn o r m a l i z e dm i ns u ma l g o r i t h me t c ， a r ec o n s i d e r e d a so n eo f c o n t r i b u t i o n so f t h i st h e s i s ，a l li m p r o v e dd e c o d i n ga l g o r i t h m ( t u r b os u m a l g o r i t h m ) b a s e do nt h en o r m a l i z e dm i n - s u ma l g o r i t h mi sp r o p o s e d w i t ht h i sn o v e lh a l f - p a r a l l e l a l g o r i t h m ，t od e c o d el o n gl d p cc o d e si nh i 曲- s p e e di sp o s s i b l e a tt h es a m et i m e ，s o m ek e y p a r a m e t e r sa n df i n i t ep r e c i s i o na n a l y s i sf o rt h eh a r d w a r ei m p l e m e n t a t i o no fl d p cd e c o d e rh a v e b e e np e r f o r m e dc o n s i d e r i n gt h et r a d e o f f b e t w e e nh a r d w a r ec o m p l e x i t ya n ds y s t e mp e r f o r m a n c e e v e n l u a l l y , t h ea f c h i t e c t o r e so f t h e i m p l e m e n t a t i o no f l d p cd e c o d e ro nf p g a ，i n c l u d i n gt h e i n t e r n a l - a r c h i t e c t u r ea n dt i m es c h e d u l i n gh a v eb e e na n a l y z e d b e s i d e s ，t h ei n t e r f a c e ，a r c h i t e c t u r e a n dt i m es c h e d u l i n go fe v e r ys u b - m o d e la r ea l s oi n t r o d u c e d f i n a l l y , w ea n a l i z e dt h ec o m p l e x i t y o ft h eh a r d w a r ed e s i g n w i t ht h i sa r c h i t e c t u r e w ec a l la c h i e v et h ed e c o d i n gr a t eo fm o r et h a n 5 0 m b i t s ，w h e ns y s t e mc l o c ki s1 0 0 m h z s k e y w o r d s ：l d p cc o d e s ，b e l i e fp r o p a g a t i o n ( b p ) a l g o r i t h m ，m i ns u ma l g o r i t h m ，p r o t o c o li e e e 8 0 2 1 6e 东南大学硕士学位论文 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：到嵫盛。日期：笠j 业f 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名： 第一章绪论 第一章绪论 衡量通信系统质量的重要指标之一是可靠性，即系统对抗噪声干扰和信道衰落的能力。 信道编码技术是目前被广泛采用的，并被证明是非常有效的提高系统可靠性的一种技术。近 年来，随着无线数字通信的发展及各种高速率、突发性强的新业务的出现，研究并利用好纠 错编码技术就显得越来越重要。 1 1 纠错编码的早期发展 1 9 4 8 年，香农建立的信息论l l 】是现代纠错码的理论基础。香农定理中指出了纠错编码能 够有效纠错所需的最小比特信噪比，我们称之为香农限，这为我们提供了评价一种编码方案 和译码算法性能的一个重要标准。 早期的研究主要集中在以代数理论为基础的线性分组码，出现了汉明码、循环码等一系 列码字，它们的译码算法主要采用大数逻辑和捕错译码。由于这些码字的纠错译码算法的复 杂度随着码长的增加呈指数速率增长，实现起来十分困难，所以授入使用的码字都是短码， 而这些短码离香农限的距离又很远，所以这些码是不理想的。 在上世纪5 0 年代有人提出了卷积码。卷积码在编码过程中引入了寄存器，从而增加了 码元之间的相关性，在相同复杂度的条件下可以获得比分组码更高的编码增益，但也增加了 分析和设计的复杂性。随着各种卷积码的译码方法，尤其是维特比( x ，i t e r b i ) 译码算法的出现， 使得卷积码逐渐得以广泛应用，8 0 年代出现的t c m ( 格栅编码调制) 技术，更加促进了卷积 码的发展。 纠错编码从很大意义上来说就分为上述的线性分组码和卷积码两大类，它们各有优缺 点虽然它们都离理想的性能有不小的距离，不过却为今后的发展提供了重要的参考和理论 基础。 1 2 近香农极限的纠错编码 1 9 9 3 年。法国的c b e r r o u 等人在卷积码和级联码的基础上，提出了一种全新的编码方 案一t l l r b o 码口j ，在信道编码的理论和应用中取得了突破性的进展。这种编码能够随着码长 的增加而逼近香农的理论极限，同时译码复杂度也可以接受。t u r b o 码采用并行级联递归的 编码器结构，是一种系统的卷积码。其译码算法主要有m a p 算法、l o g - m a p 算法、 m a x - l o g - m a p 算法、s o v a 算法等。t u r b o 码具有独特的编码结构和译码思想：在子编码器 中采用了反馈型的系统卷积码，且在子编码器间引入交织器，减少了子编码器间信息的相关 性，模仿了随机编码的形式：同时在译码中采用了软输入、软输出的译码信息和信息反馈的 译码器形式，并引入了迭代译码的思想。 在获得巨大成功的t u r b o 码的启发下，另一类具有相似特征和性能的编码重新得到人们 东南大学碗了学位论文 的重视，这就是l d p c 码( l o wd e n s i t yp a r i t yc h e c kc o d e s ) 。l d p c 码的理论最早出现在 g a l l a g e r 在1 3 1 中描述的一种编码，现在通常称之为g a l l a g e r 码，这种码因为校验矩阵的稀疏 性，使得译码的复杂度和码长保持线性关系，从而使得长码的应用成为可能。不过由于肖时 人们的注意力集中在级联编码上，以及当时技术条件的限制，这种编码方案遭到了忽视。 d j c m a c k a y 、m n e a l 和n w i b e r g 等人对g a l l a g e r 码重新进行了研究，发现g a l l a g e r 码虽然性能较t u r b o 码略有差距，但它同样具有逼近香农限的性能【4 】。在g a l l a 叠e r 码的基础 上，他们进一步研究了多元域上的l d p c 码”j ，发现多元域上的g a l l a g e r 码较二元域上的码 的性能有较大提高，且域的阶数越高编码的性能越好。m g l u b y 和m m i t z e n m a c h e r 等人从 另一个角度对g a l l a g e r 码进行了推广，提出非正则l d p c 码【6 j ，这种纠错码的性能能够赶 上甚至超过t u r b o 码。 l d p c 码具有巨大的应用潜力，目前基于l d p c 码在各通信领域应用的研究正方兴未艾， 如在移动和固定无线通信、深空通信、光纤通信、卫星数字视频和声频广播、磁，光全息存 储、电缆调制解调器和数字户线s l ) 等领域的应用。本文的工作主要集中于l d p c 码在无 线城域网中的应用。 1 3 8 0 2 1 6 e 系统中的l d p c 码及以及译码算法的研究简介 近年来。无线城域网吸引了越来越多的人的关注，尤其是在世界微波接入互操作性论坛 ( w i m a x ：w o r l d w i d e i j l t e r o p e m b i l 埘f o r m i c r o w a v e a c c e s s ) 于2 0 0 1 年4 月成立之后，更是取 得了很大的进展。而且，随着d s p 芯片技术的发展，快速傅立叶变换反变换技术的引入， o f d m 的应用变得更加实际，这更加大了无线城域网的应用。在无线城域网系统中，纠错 编码是必不可少的。目前，l d p c 码由于其优蘸的性能而得到了广泛的关注。 i e e e 8 0 2 1 6 e 系统中采用的是一种结构化的非规则的q c l d p c 码，其校验矩阵由很多大 小相同的方阵构成，这些方阵包括全零阵，单位阵和各种单位循环移位阵。校验矩阵照此可 以彼分为( n r ) x 2 4 块，其中r 代表码率。i e e e 8 0 2 1 6 e 系统共有四种码率的码字，分别为1 ，2 、 2 3 、3 f 4 和5 6 。 以码率为1 2 的某个码字的校验矩阵为例，这种的l d p c 码的校验矩阵的结构具体如图1 1 所示，其中标有p 的是单位阵的循环移位阵，标有i 的是单位阵，其余全是全零阵。 2 - 第一章绪论 ppp ppi pp p ppii pppppii ppp p ii ppp p ii pppp i ii pp ppii ppp pii pppppii p pppil p pppi i p p pppi 图i i 某个1 2 码率码字的校验矩阵结构匿 这种结构的l d p c 码给编解码器的硬件实现带来了很大方便。例如，在设计编码器时， 我们只需要存储生成矩阵中各个循环阵的首列( 而不是整个生成矩阵) ，然后用按顺序载入 移位寄存器就可以完成编码了；同样的。在解码时校验矩阵也可以采用相似的存储策略来节 省存储器的消耗。此外，这种校验矩阵具有分块循环的特性也为半并行的解码算法提供了可 能，本文给出的一种解码算法就属于这个范畴。利用设计良好的半并行解码算法，我们完全 可以在保证性能的前提下。达到正e e s 0 2 1 6 e 中规定的甚至是更高传输速率，这为将来可能 的业务扩展提供了良好的基础。 任何事物都有两面性，虽然这种结构的l d p c 码具有上述的优点，不过它在性能上会比 按照最优方法设计出来到l d p c 码差一些，主要体现在e r r o r - - f l o o r 出现的比较早以及 w a t e r f a l l 区不是非常陡峭。不过考虑到i e e e 8 0 2 1 6 e 系统的工作环境以及系统性能要求，只 要采用设计良好的解码算法，这种结构l d p c 的码基本上还是能够满足要求的。 目f l - u l d p c 码的译码算法可以分为硬判决译码和软判决译码。硬判决算法计算复杂度很 低，只需要模二运算，但是译码性能不够理想；软判决译码算法的译码性能要远远好于硬判 决译码算法，但是运算复杂度也大为提高。在软判决译码算法方面，首先有b p ( b e l i e l - p r o p a g a t i o n ) 算法，也称为s u m - p r o d u c t 算法，其译码性能比硬判决算法好的多，而相应的 运算复杂度也不大。为了进一步减少复杂度，h ”1 4 2 1 中提出了一类简化的b p 算法m i n s u m 算法( n o r m a l i z e dm i n s u m 算法) ，以及它们的各种变型算法。目前软判决译码算法是研究 的重点，工作主要集中在如何降低算法的运算量同时又能保持良好的译码性能上。本章主要 研究一种基于n o r m a l i z e dm i n s u m 算法的快速译码算法，这种算法改变了以往算法中接收符 号和校验式之间串行的信息交换方式，将这个过程改为了并行执行，从而大大加快了迭代计 算的速度，同时性能也有不小的改善。 东南大学硕士学位论土 1 4 本文的主要内容 本文主要讨论i e e e 8 0 21 6 e 中给出的l d p c 码的编解码方法，重点是高速率的译码算法 及其硬件实现。 文章共分六章，本章为绪论，简单介绍了l d p c 码以及城域网的发展历程。第二章详细 介绍了l d p c 码的二分图结构和基于不同结构的l d p c 码的分类，最后介绍了l d p c 码的 最小码重分布。第三章介绍了基本的以及本系统所使用的l d p c 码的编码方法，同时给出一 种适合本系统的编码器硬件实现方案。第四章详细论述了l d p c 码的几种主要的软判决译码 算法，并以此为基础给出了一种并行度很高的快速软判决译码算法t 1 1 r b os u m 算法。文章 给出了算法的原理、步骤，两种不同的实现方法和这种算法的性能仿真结果。第五章给出了 译码算法的定点仿真结果，并给出了定点化方案。第六章给出了译码器详细的硬件实现方案， 包括了总体时序，模块划分，以及各个模块的接口、结构和时序，最后文章分析了这个方案 的复杂度问题。 本人在研究生阶段还参加过与东大通信公司的合作项目( h s d p a 的系统仿真。在项目 研究期间，我主要负责信道模型和信道估计两个模块( 重点是信道估计模块) 的c 程序的编 写与调试。我先后编写过滑动窗模式、车速自适应滑动窗模式两种信道估计算法。经仿真发 现。后者的应用使得系统在3 k m h 车速下的吞吐量要比使用前者时高出o 5 个d b 以上。 4 第二章l d p c 码的简介 第二章l d p c 码的简介 低密度奇偶校验码是一种线性分组码，它通过一个生成矩阵g 将信息序列映射成发送 序列，也就是码字序列。对于生成矩阵6 ，完全等效的存在一个奇偶校验矩阵胁所有的码 字序列矿构成了的零空间，即h v t = o 。 l d p c 码的奇偶校验矩阵日是一个稀疏矩阵，相对于行与列的长度( ，校验矩阵 每行、每列中非零元素的数目( 我们习惯称作行重、列重) 非常小，这也是l d p c 码之所以 称为低密度码的原因。当日的行重p 和列重，保持不变或尽可能的保持均匀时，我们称这 样的l d p c 码为正则l d p c 码，反之如果列、行重变化差异较大时，称为非正则的l d p c 码。正确设计的非正则l d p c 码的性能要优于正则l d p c 码。根据校验矩阵日中的元素是 属于g f ( 2 ) 还是g f ( q ) ( 口= 2 9 ) ，我们还可以将l d f c 码分为二元域或多元域的l d p c 码 文献1 7 j 的研究结果表明，多元域l d p c 码的性能要比二元域的好，这是由于它进一步增加了 码间距离的原因。下面我们分别讨论u ) p c 码的上述几个重要特性。 2 1 l d p c 码的二分图结构 l d p c 码可以用二分图来表示，它的二分图由两类节点组成：变量节点( v 抓a b l e n o d e ) 和校验节点( c h e c k n o d e ) ，分别对应于校验矩阵胃中的列和m 行。同一个集合内部的节 点没有连线，只有属于不同集合的两点之间可能有连线，每一条连线对应于校验矩阵中的 1 。式2 1 是某个( 8 ，2 ，4 ) l d p c 码的校验矩阵和相应的校验方程，根据校验矩阵我们可 以画出它的二分图( 图2 1 ) 。图中变量节点集合“，v 2 。) 和校验节点集合( q c 2 c 4 ) 内部不存在相连的边，但两类节点之间存在着连线。我们将每个节点上的连线数目称为该节 点的次数( d e g r e e ) ，图2 1 中，变量节点的次数( 以) 为2 ，校验节点的次数( 以) 为4 。 心 0 0 0 10 1 1 0ll0l i 110l0l l010 i j ( 2 1 ) 图2 1 的二分图结构中，四条粗线构成了一个有向的闭合环路，由v l 起始，经过 乌 v 3 寸c 2 ，最后返回。在一个l d p c 码的二分图中，每个节点都会存在许多这样的 闭合环路，我们将其中长度最小的一个称为该节点的最小环长( s h o r t e s t c y c l e ) 。二分图中所 有节点的最小环长中，长度最小的称为二分图的最小圈长( g i r t h ) ，上例的二分图中，g i r t h 与变量节点l 的最小环长相等，都是4 。 - 5 0 o o o = i i i | l l 吩吒叶唯 o o o o 匕吒匕吒 o 0 0 0 屹竹n n 0 0 o o h h 也b ，lfifil，、_，t-l 末南丈学颤上学位论文 图2 1( 8 ，2 ，4 ) l d p c 码的二分图 l d p c 码二分图结构中g i r t h 的大小对l d p c 码的译码性能有很大影响。g i r t h 的长度将 直接关系到l d p c 码码字的最小码距，g i r t h 的长度越大，l d p c 码的最小码距越大，译码性 能也就更好。如果二分图中存在长度为4 的g i r t h ，l d p c 码的误码率性能将会很差，所以我 们在构造l d p c 码的校验矩阵时，要尽量避免二分图中出现g i r t h 为4 的情况。 因为某些节点存在闭合环路，当迭代次数较多时，到达这些节点的信息不再满足统计独 立的特性，从而使得译码性能与最大似然算法有一定的差距。因此，我们在设计l d p c 码时， 在保证g i r t h 大于4 的情况下，各个节点的最小环长越大越好。 最小环长的分布状况是衡量l d p c 码结构好坏的一个准则，二分图结构，中、短长度的 环所占的比重越少，l d p c 码的译码就越接近理想中无圈( c y c l ef r e e ) 的假设。当l d p c 码 的码长趋向于无穷，其编码二分图结构可以看作近似无圈，l d p c 码在b p 算法下的译码性 能也就完全等效于最大似然译码。 2 2 正则与非正则l d p c 码 在l d p c 码的校验矩阵中，如果行列重量固定为( p ，y ) ，我们称之为正则l d p c 码。 我们还可以适当放宽上述正则l d p c 码的条件，只要行列重量尽量服从均匀分布，行列重量 的均值可以不是一个整数。此外为了保证二分图上不存在长度为4 的圈，我们通常要求行与 行以及列与列之间的交叠部分重量不超过1 ，即任意两列或两行的相同部分不超过1 。 正则l d p c 码校验矩阵h 的特征可以概括如下： 1 、疗的每行行重固定为p ，每列列重固定为y 2 、任意两行，两列之间交叠部分重量最多为1 3 、行重p 和列重y 相对于h 的行数m 、列数很小，是个稀疏矩阵 4 、正则l d p c 码的最小码率r 可以通过下式计算： ，= ( 一m ) n = 1 一m n = 1 一，p( 2 3 ) 在正则l d p c 码的校验矩阵中，行重和列重的均值保持不变，所以校验矩阵中1的 6 第二章l d p c 码的简介 个数随着码长的增加而线性增长，整个校验矩阵的元素个数则成平方增长。当码长达到一定 长度时，校验矩阵日是非常稀疏的低密度矩阵。对于正则的l d p c 码，m a c k a y 在1 4 l 中给出 了以下两个结论： l 、对于任意给定列重大于3 的l d p c 码，存在某个小于信道传输容量且大于零的速率r ， 当码长足够长时，可以实现以小于r 且不为零的速率无差错的传输。也就是说任意给定一个 不为零的传输速率，存在一个小于相应香农限的噪声门限，当信道噪声低于该门限且码长 足够长的时候，可以实现咀，速率无差错的传输。 2 当l d p c 码的校验矩阵的列重，不固定，而是根据信道特性和传输速率来确定时， 则一定可以找到一个最佳码，实现在任意小于信道传输容量的速率下无差错的传输。 对于l d p c 码的每个变量节点来说，当它参与的校验式越多，即次数，越大，则它可以 从更多的校验节点获取信息，也就可以更加准确的判断出它的正确值。对于日的每个校验 节点来说，当它涉及的变量节点越少即次数p 越小，则它可以更准确的估计相关变董节点 的状态。这种情况对于正则l d p c 码来说是一对不可克服的矛盾，于是l u b y ，m i t z c n m a c h e r 等人就引入了非正则l d p c 码的概念。 在非正则l d p c 码的编码二分图中，两个集合内部的节点次数不再保持相同，即每个交 量节点参与的校验式数目或每个校验式中含有的变量节点数目不再保持均匀，而是有意设置 部分突出的变量节点和校验节点。在译码过程中，那些参与较多校验式的变量节点迅速得到 它们的正确译码信息，这样它们就可以给相邻的校验节点更加有效的概率信息，而这些校验 节点又可以给与它们相邻的次数少的变量节点更多的信息。整个译码的过程呈现出一种波状 效应，次数越高的变量节点首先获得正确信息，然后是次数较低的节点，然后依次往下，直 到次数最低的变量节点。正是这种波状效应，使得非正则l d p c 码获得比正则l d p c 更好 的译码性能。理论上的极限性能仅仅比香农限高0 0 0 4 5 d b 的非正则码次数分布对已经找到 嘲。 2 3 二元域与多元域的l d p c 码 如果定义中的域不限于二元域就可以得到多元域g f ( g ) 上的l d p c 码。多元域上的 l d p c 码具有较二进制l d p c 码更好的性能，而且实践表明在越大的域上构造的l d p c 码， 译码性能就越好【9 】。比如在g f ( 1 6 ) 上构造的正则码性能已经和t u r b o 码相差无几。多元域 l d p c 码之所以拥有如此优异的性能，是因为它有比二元域l d p c 码更重的列重，同时还有 和二元域l d p c 码相似的二分圈结构。 假设在域g f ( 2 ) 和域g f ( q ) ( q = 2 9 ) 上构造的l d p c 码所对应的校验矩阵分别是也 和h q 峨中的元素是0 或i ，而h q 是由元素o 1 ，q 一1 构成，h q 中的每个元素都是何2 中p 个元索的合成。如果设域g f ( q 1 ( q = 2 ) 上的一个值口与一个l p 的二进制向量相 一， 东南大学硕士学位论文 关联，那么把这个向量代入矾中，就可以得到h 。的二进锄表示。对于二进制l d p c 码来 说，如果它的校验矩阵h 的列重量足够大，那么它可以任意地接近香农限，但是如果增加 列重量会使得二分图中节点之间短圈的数目急剧增加从而使b p 算法的性能下降。而在 g f ( q ) 域上构造的l d p c 可以解决这个矛盾，它的校验矩阵。可以增加与之对应的二迸制 校验矩阵，中列的平均重量，且它的二分图结构并没有改变，不会造成节点之间短圈数目 的增加，从而使得译码性能得到显著的提高。这种多元域上的编码构造会增加译码复杂度， 但是相对于译码性能的提高来说这种增加是值得的。 2 3l d p c 码的最小码重分布 l d p c 码的性能可以根据各个码字之间的最小码距，即最小码重来衡量，码重越大，则 它的纠错能力越强。但随着码长的增加，直接分析l d p c 码的最小码重很难实现。g a t l a g e r 在1 3 1 中提出将特征类似的l d p c 码归为一类，对该集合分析其中码字的最小码重就比较简 单。在集合的最小码重分布特性已经得到的情况下，我们更有可能从集合中随机拶l 选出具有 较好码重分布特性的l d p c 码。 若某个l d p c 码中，码重为珀q 码字数目为职| ) ，则表示对于该码中任意一个码字，与 它距离为f 的码字数目为w ( 0 。因为少数重量较轻的码字主导了整个码组的译码性能，因此 对于给定码长a - 码率为，的l d p c 码，我们总是希望它的最小码重d 尽可能的大，并且 码重等于或稍大于d 的码字数量尽可能的少。e i l i a s 在【l6 j 中分析了在随机产生校验矩阵的情 况下，获得的一般奇偶校验分组码的码重分布界。对于码长码率为r 的奇偶校验码，当 它的所有码字等概分布时，最小码重分布有如下的不等式： 丽= ( 2 叫”) 【2 枷硼埘r e 冲佃( 俨( h 灿z 】 附螂，高i 压焉唧h h m z ， 其中，6 = j ，日( 艿) = 一占1 n 一( 1 一占) l i l ( 1 一艿) 。式2 9 说明，当h ( 6 ) - ( i - r ) l n 2 o 5 ) ，t h e n = 1 ，e l s e v ：= 0 ，如果该序列使得所有校验式满足，则将 之作为译码输出，并结束迭代，否则k = k + l ，跳转到步骤2 4 1 3 对数域上的b p 算法 在概率域的算法中需要做大量的乘法运算，这不仅需要大量的硬件资源，而且当码长变 长，迭代次数加大后，计算概率的次数越多，数值稳定性越差。如果用对数似然比作为b p 算法中节点之间传递的信息，连乘的运算就被转化为加法和查表的计算。 上( z ) = 2 y o 2 定义驴( 工) = - i n t a n h ( 1 x ) = k ：i ：害三, t , o - l ( = 妒( x ) ，则 三( 艺) = ( 兀d ( g 篇) 弦 妒( 声白二) ) 】 j e b ( m ) tj 口( m ) 、f 其中d ( g 名) = s 堙 ( g 二) ，( g 篇) = | 吐 相应的式( 4 1 0 ) 和( 4 】1 ) 也写成对数似然比后的形式为 三( 露) = 工( 群) + 三( k - 1 ) 3 e a ( n ) 上( g 胛k ，= l t p 。k ) 一上 m a x ，结束这帧的译码，否则继续 2 4 ( 4 1 2 ) ( 4 1 4 ) ( 4 1 5 ) ( 4 1 6 ) 第四章译码算法 3 根据式( 4 1 4 ) 和q “求每一个工( _ k ，- 1 ) ，即更新r 阵 4 通过式( 4 1 5 ) 计算每个变量节点的l i ：一) 5 根据式( 4 1 6 ) 和r “1 ，更新每一个三( 以) ，即更新q 阵 6 根据步骤4 的结果做硬判，得到一个输出序列y ， 矿( z ( 1 ) o 5 ) ，t h e nt = 1 ，e l s e v ：= 0 ，如果该序列使得所有校验式满足，则将 之作为译码输出，并结束迭代，否则k = k + l ，跳转到步骤2 4 1 3 最小和( m i ns u m ) 算法 在对数域的b p 算法中，我们用了函数烈x ) = 一l i l t a 】【】l l ( 三力由于它具有这样一个特 性，就是矿1 ( x ) = 矿( 曲，也就是说烈妒( x ) ) = x ，所以式( 4 1 4 ) 中的讧矿( 国二) ) 】 可以简化计算；另外，当h 很小时，妒( 力上升得很快，所以缈( 国二) ) 几乎为( g 二) 中的最小值左右，所以d 。妒( 眩) ) 】* ，嚣留k ( 靠) l e b ( m 、 一一7 ” 所以式( 4 1 4 ) 被简化为 工( t ) = ( 兀口( g 名) ) ，躲。( 靠) j e b ( m ) v 。7 工( j k k j 删u g j k 。) 的计算和b p 算法一样只是三( z ) 可以简化为 工( z ) = ，彳0 ) ( 4 1 7 ) ( 4 1 8 ) 很明显。该算法在迭代运算中只有加减法和比较大小的运算，运算量和存储量都比b p 算法小了很多，很适合硬件实现。 但是它的译码性能要比b p 差很多，这主要是由于简化妒( ( g 篇) ) 时，( g 名) 中 j e b ( m 1 h 的最小值和次小值相差不大时近似算法就会出现不小的误差。为了解决这一问题，有人提出 了下面一种算法。 4 1 4 修正的最小和( n o r m a l i z e dm i ns u m ) 算法 该算法只是在式( 4 1 7 ) 的基础上增加了一个归一化因子r 来加以修正 2 5 末南丈学硕七学位硷文 t ( o 。7 ( 兀。口( q 砂璺现、，p ( q 名) b f m l u 其他方面该算法和m i ns u m 算法完全一致。 如果这个归一化园子取得合适的话，可以使算法的性能非常逼进b p 算法。 ( 4 1 9 ) 到此，软判决译码算法进入了实用阶段，也就是到了可以用较少的硬件资源实现的阶段。 该算法的实现步骤如下： 1 初始化 a 、用式( 4 1 2 ) 计算每个变量节点上的( p ：) b 、对q 阵赋初值，q 。( f ，) = ( g ：) = ( p ；) ，i 口( j ) c 、k = - i ；初始化迭代次数 d 、设置卵的初始值 2 如果k m a x 结束这帧的译码，否则继续 3 根据式( 4 1 9 ) 和9 “1 求每一个三( ，奢1 ) ，即更新r 阵 4 通过式( 4 1 5 ) 计算每个变量节点的上( 露) 5 根据式( 4 1 6 ) 和r “，更新每一个工( g ) ，即更新q 阵 6 根据4 步骤的结果做硬判，得到一个输出序列v f ( p k ( 1 ) o 5 ) ，t h e ne = 1 ，p b p t = 0 ，如果该序列使得所有校验式满足，则将 之作为译码输出，并结束迭代，否则k = k + l ，跳转到步骤2 4 2t u r b os m 译码算法 如果直接按照n o r m a l i z e dm i ns u m 算法来安排硬件的工作时序难以达到很高的译码速 率，为了解决这个问题，下面一种基于n o r m a l i z e dm i ns u m 算法的改进算法被给出，这就 是t u r b os u m 译码算法。 4 2 1t u r b os u m 译码算法原理 以上介绍的各种算法都是按照：更新r 阵，接着更新q 阵，再更新r 阵这样循环 2 6 第四章 译码算法 的顺序来进行迭代的。这样做的好处是：更新r 阵时用的是最新的o 阵信息，更新o 阵时 也是如此。但是这样做增加了很多的等待时间。 t u r b os u m 译码算法的主要思想就是同时更新r 阵和q 阵，其他方面和n o r m a l i z e dm i n s u m 算法是几乎一致的，可以说它就是n o r m a l i z e dm i ns u m 算法的一种t u r b o 变型。它的 优势很明显，如果r 阵的内部数据逐行更新，q 阵的内部数据逐列更新，那么该算法迭代 一次的时间仅仅是n o r m a l i z e dm i ns u m 算法的一半。虽然r 阵和q 阵的更新无法利用全新 的q 阵和r 阵信息，以致单纯地从迭代次数上看，该算法的收敛速率低于n o r m a l i z e dm i n s u m 算法。不过在相同的时间里，该算法可以比n o r m a l i z e dm i ns u m 算法获得多一倍的迭 代次数，这足以弥补它收敛速度慢的缺点。 它的粗略实现步骤如下所示 1 初始化 a 、用式( 4 1 2 ) 计算每个变量节点上的( 钟) b 、对q 阵赋初值，q 。( f ，j ) = 工( g ：) = l ( p d ，f 丑( j ) c 、k = - i ；初始化迭代次数 d 、设置叩的初始值 2 如果k m a x ，结束这帧的译码，否则继续 3 根据式( 4 1 9 ) 和矿- 1 求每一个工( ，：) ，即更新r 阵 同时根据式( 4 1 6 ) 和r “，更新每一个工( g 盖) ，即更新q 阵 4 通过式( 4 1 5 ) 计算每个变量节点的工( z ) 5 根据步骤4 的结果做硬判，得到一个输出序列v ， 矿( z ( 1 ) o 5 ) ，t h e nt = 1 ，p 厶嘭= o ，如果该序列使得所有校验式满足，则将 之作为译码输出，并结束迭代，否则k = k + t ，跳转到步骤2 4 2 2t u r b os u m 译码算法的半并行实现形式 首先介绍一下“串行”解码和“并行”m i n s u m 解码算法的概念。m i ns u m 算法是“串 行”还是“并行”包含两层意思： 1 r 阵和o 阵的计算是交替进行还是同时进行，或者说是否是先计算完r 阵再计算q 2 7 东上学硕士学位论文 阵，然后再计算r 阵，依次类推。 2 r 阵内部的数据是逐行更新还是同时更新：q 阵的数据是逐列更新还是同时更新 一个完全意义上的并行m i ns u m 算法是在这两个层面上都必须属于并行的算法。这种 算法虽然运算速度非常快，但是它的器件消耗量也是非常惊人的。实际当中，为了在运算速 度和器件消耗量上取得平衡，我们一股采用半并行的译码算法。 在上一节中我们介绍的t u r b os u m 算法在第一个层面上已经是并行的了，那么它的半并 行实现只能在第二个层面上进行安排了。下面我们就来看看如何按排r 阵和q 阵内部数据 的更新。 根据前面介绍过的1 e e e 8 0 2 1 6 e 中采用的l d p c 码的校验矩阵的特点，我们对r 阵和q 阵进行如下分割：r 阵按行均匀分块，每一块包含的行数为z ；q 阵按照列均匀分块，每 块包含的列数也为z 。例如对于码长5 7 6 码率1 ，2 的l d p c 码，可以将r 阵按行分为1 2 块， 每块包含2 4 行，q 阵则按列分为2 4 块，每块有2 4 列。 运算的时候，r 阵的各块中每次选出一行进行更新，q 阵的各块中每次选出一列进行更 新。这样z 个计算周期以后r 阵和q 阵的数据就都被更新了一次。这种安排所需要的运算 单元仅仅是全并行算法的l z ，运算速度也足以满足系统的要求了，另外在后面的章节里我 们发现这种安排对于硬件存储器的设计也是非常有利的。 下面我们通过一个简单的例子来形象地说明一下这种半并行实现方法：如果把一个 l d p c 码的r 阵分为3 块，q 阵分为5 块，各块中的起始位置都为l ，即在第一个计算周期 里，更新q 阵中每块的第l 列和r 中每块的第1 行；在下一个计算周期里，更新3 块r 阵 中每块的第2 行和5 块q 阵中每块的第2 列；依此类推。该算法的一次迭代可以用下 图来加以说明。 1 s tc y c l e2 n dc y c l e 图4 4 半并行t u r b os u m 算法示意图 8888l 8888 8 888l z t hc y c l e 通常。为了取得较好的性能，r 阵各块不一定从第一行开始更新，q 阵也是一样。经过 仿真发现，当r 阵的各块从第一行开始更新，q 阵的各块从第二列开始更新时可以取得相 对较好的性能。 这种算法的具体步骤如下： 2 8 第四章译码算法 1 初始化 a 、用式( 4 1 2 ) 计算每个变量节点上的l ( p ：) b 、对q 阵赋初值，q 。( f ，j ) = ( g ：) = 工( p ；) ，f 矗( ，) c 、将r 阵清零，r o ( f ，j ) = 0 ，j a ( o d 、k = l ；初始化迭代次数 e 、设置7 7 的初始值 2 如果k m a x ，结束这帧的译码，否则继续 3 f o r ( i = 0 i z ；i + + ) ( 其中z 表示每一块的大小) 根据式( 4 1 9 ) 和矿_ 1 ，计算各块r 阵中的第i 列： 同时根据式( 4 1 6 ) 和r “，计算各块q 阵中第i 行； 更新各块r 阵中的第i ( 模z ) 列； 更新各块q 阵中第i + 1 ( 模z ) 行； 4 通过式( 4 1 5 ) 计算每个变量节点的三( 露) 5 根据步骤4 的结果做硬判，得到一个输出序列矿， 矿( ( 1 ) o 5 ) ，t h e n 砖= 1 ，e l s e t = 0 ，如果该序列使得所有校验式满足，则将