（通信与信息系统专业论文）基于ems算法的多元ldpc码译码器设计与fpga实现.pdf

摘要 摘要 低密度校验( l d p c ) 码被证明是一类纠错性能逼近s h a n n o n 限的好码。多元 l d p c 码与二元l d p c 码相比性能更好，然而，这是以高译码复杂度为代价的。 本文作者结合国家8 6 3 计划项目( 2 0 0 6 a a 0 1 2 2 6 7 ) ，对多元l d p c 码译码器 的设计与实现问题进行了研究。主要完成的工作有以下几个方面。 分析了基于有限域的多元l d p c 码的译码算法，通过分析发现，多元l d p c 码的译码复杂度主要集中在校验节点更新的计算。扩展最小和( e m s ) 算法能够 降低校验节点更新的计算复杂度。 结合仿真，对e m s 算法的性能和复杂度做了进一步研究，并对e m s 算法的 特点进行深入分析。 通过对e m s 算法特点的分析，对一个g f ( 6 4 ) 上码长1 0 4 4 b i t s 、码率1 2 的多 元l d p c 码，采用x i l i n xv i r t e x - 4 系列x c 4 v l x 6 0f p g a 芯片设计并完成译码器， 对该译码器中各模块的结构和功能做了详细说明，并对译码器功能做了验证仿真。 关键词：多元l d p c 码e m s译码器 f p g a a b s t r a c t a b s t r a c t l o w - d e n s i t yp a r i t y - c h e c k ( l d p c ) c o d e sh a v es h o w nt oh a v eg o o de r r o r c o r r e c t i n gp e r f o r m a n c et h a ta p p r o a c h e st h es h a n n o nl i m i t n o n - b i n a r yl d p cc o d e s s h o ws i g n i f i c a n t l y h i g h e rp e r f o r m a n c e st h a nb i n a r yl d p cc o d e s h o w e v e r , t h i s i m p r o v e m e n ti sa c h i e v e da tt h ee x p e n s eo fi n c r e a s e dd e c o d i n gc o m p l e x i t y t h i st h e s i si n v e s t i g a t e ss o m ek e yp r o b l e m so fd e s i g na n df i e l dp r o g r a m m a b l eg a t e a r r a y ( f p g a ) i m p l e m e n t a t i o no fn o n - b i n a r yl d p cd e c o d e r ，n l ed e c o d i n ga l g o r i t h m sf o rn o n - b i n a r yl d p cc o d e so v e rf i n i t ef i e l d sg f ( q ) ， s u c ha st h eb 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 ，f f t o b pa l g o r i t h ma n de x t e n d e dm i n - s u m ( e m s ) a l g o r i t h m ，a les t u d i e d t h ee m sa l g o r i t h mi ss u b o p t i m a l ，a n dn a t u r a l l y i n t r o d u c e sap e r f o r m a n c ed e g r a d a t i o nc o m p a r e dw i t ht h eb pa l g o r i t h m t or e d u c et h e d e c o d i n gc o m p l e x i t y , w eh a v et of o c u so nal o c a ls i m p l i f i c a t i o no ft h ec h e c kn o d e p r o c e s s i n g b yt h e o r e t i c a la n a l y s i s a n ds i m u l a t i o n , t h ep e r f o r m a n c e sa n dc o m p u t a t i o n a l c o m p l e x i t yo fe m sd e c o d i n ga l g o r i t h ma l es t u d i e d 1 1 1 ee m sd e c o d i n ga l g o r i t h m g r e a t l yr e d u c e st h ec o m p u t a t i o n a lc o m p l e x i t yo fp r o c e s s i n gu n i t s n ee m sa l g o r i t h m i sag o o dc a n d i d a t eo fh a r d w a l ei m p l e m e n t a t i o no fn o n b i n a r yl d p cd e c o d e r s ，s i n c ei t s c o m p l e x i t yh a sb e e ng r e a t l yr e d u c e dc o m p a r e dw i 也t h a to fo t h e rd e c o d i n ga l g o r i t h m s f o rn o n b i n a r yl d p cc o d e sa n dt h ep e r f o r m a n c ed e g r a d a t i o ni ss m a l lo rn e g l i g i b l e b a s e do np r i n c i p l e so fe m sd e c o d i n ga l g o r i t h m ，t h ef p g ai m p l e m e n t a t i o n m e t h o da n ds t r u c t u r ea l ep r o p o s e d ，a10 4 4 b i t sr a t e1 2n o n b i n a r yl d p cc o d eo v e r g f ( 6 4 ) d e c o d e ri si m p l e m e n t e do nx i l i n xf p g av i r t e x - 4x c 4 v l x 6 0 ，a n da l lt h e m o d u l e si nt h ef p g ad e s i g na n dt h eh a r d w a r es i m u l a t i o nr e s u l t sa r ea l s oi n t r o d u c e d k e y w o r d s ：n o n b i n a r yl d p cc o d e s e m sd e c o d e r f p g a 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说 明并表示了谢意。 申请学位 本人签名 不实之处，本人承担一切的法律责任。 日期趔聋缉哆 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密质遵守此规定) 本人签名：缝 导师签名：立支啦 日期型叠笸困趁 日期之虚：么：2 第一章绪论 第一章绪论 本章首先介绍了信道编码在数字通信系统中的作用，然后回顾了信道编码发 展的几个阶段，接着分别介绍了二元l d p c 码和多元l d p c 码的发展现状，最后 对本文内容作总体安排。 1 1 数字通信与信道编码 1 9 4 8 年，美国贝尔实验室的c l a u d ee s h a n n o n 在他的开创性论文通信的数 学理论【l 】中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著名的信道 编码定理，由此奠定了纠错码的基础。s h a n n o n 证明：只要传输的信息速率小于信 道容量，就可以通过编码的方式实现信息的可靠传输。 根据s h a n n o n 的信息理论，数字通信系统的模型如图1 1 所示。 编码信道 广一一一一一一一一一一一一一一一一一一一一- 1 图1 1 数字通信系统模型 从s h a n n o n 信道编码定理可知，随着分组码的码长或卷积码的约束长度的增 加，系统可以取得更好的性能( 即更大的保护能力或编码增益) ，而译码应该采用 最大似然( m l ) 译码。但是，众所周知，最大似然译码算法( m l d a ) 的复杂性 随码长1 1 指数增加，当n 较大时，m l d a 几乎物理不可实现。因此，必须研究新 的编码方案。几十年来，寻找好码及其有效译码算法一直是信道编码理论与技术 研究的中心任务。 迄今，信道编码已有6 0 年的历史，其发展经历了几个重要的阶段。 5 0 年代至6 0 年代，主要研究各种有效的编、译码方法，奠定了线性分组码的 理论基础；提出了著名的b c h 码编、译码方法；给出了纠错码的基本码限。这是 纠错码从无到有得到迅速发展的年代。自6 0 年代至7 0 年代初，不仅提出了许多 有效的编译码方法，如软判决译码和卷积码的维特比( v i t e r b i ) 译码等，而且注意 到了信道编码的实际化问题，为信道编码的实用化打下了坚实的基础。7 0 年代初 2 基于e m s 算法的多元l d p c 码译码器设计及f p g a 实现 至8 0 年代，这是纠错码发展史中具有极其重要意义的时期。在理论上以戈帕 ( g o p p a ) 为首的一批学者，构造了一类g o p p a 码，其中一类子码能够达到s h a n n o n 在信道编码定理中提出的码。8 0 年代以来，科学家们从几何观点讨论分析码，利 用代数曲线构造了一类代数几何码。这些码中，某些码的性能逼近香农限，在理 论上证明具有优越的性能【2 】。 s h a n n o n 理论证明，随机码是好码，但是它的译码却太复杂。因此，多少年来 随机编码理论一直是作为分析与证明编码定理的主要方法，而如何在构造码上发 挥作用却并未引起人们的足够重视。直到1 9 9 3 年，t u r b o 码的发现，才较好地解 决了这一问题，为s h a n n o n 随机码理论的应用研究奠定了基础。 t u r b o 码，又称并行级连卷积码( p c c c ) ，是由c b e r r o u 等在i c c 9 3 会议上 提出的【3 】。它巧妙地将卷积码和随机交织器结合在一起，实现了随机编码的思想， 同时，采用软输出迭代译码来逼近最大似然译码。文 3 】中的模拟结果表明，如果 采用大小为6 5 5 3 5 的随机交织器，并且进行1 8 次迭代，则在e 0 0 7 d b 时， 码率为1 2 的t u r b o 码在a w g n 信道上的误比特率( b e r ) 1 0 ，达到了逼近 s h a n n o n 限的性能( i 2 码率的s h a n n o n 限是0 d b ) 。因此，这一超乎寻常的优异性 能，立即引起信息与编码理论界的轰动。 1 9 9 5 年被重新发现的l d p c 码，被证明具有比t u r b o 码更优异的性能，而成 为近年来研究的热点。 总之，到现在为止，s h a n n o n 创建的信息理论已经诞生6 0 多年了，在这半个 多世纪的发展过程中，经过各国学者的不懈努力，信道编码理论与技术这一研究 领域取得了辉煌的成就，今天它己成为一门标准技术而广泛应用于通信、计算机 等各个领域中【4 j 。 1 2l d p c 码的发展 1 2 1 二元l d p c 码的发展与应用 l d p c ( l o w - d e n s i t yp a r i t y c h e c k ) 码是一类校验矩阵为稀疏矩阵的线性分组码， 最早由g a l l a g e r 于1 9 6 2 年提出【5 】，它是一类逼近s h a n n o n 限的好码。然而，由于 受到当时计算机能力的限制，l d p c 码曾一度被认为是一种不实用码，很长的一段 时间内被人们所忽视。直到1 9 8 1 年t a n n e r 在他的工作中从图的角度提供了一种对 l d p c 的全新解释【6 j 。但是，t a n n e r 的工作又被忽视。到了上世纪9 0 年代初t u r b o 码的问世，特别是随着硬件水平的飞速发展，l d p c 码的优异性能才重新为人们所 认识。1 9 9 6 年，m a c k a y 和n e a l 指出具有线性译码复杂度的随机构造的l d p c 长 码可以与t u r b o 码匹敌i ，j 。1 9 9 7 年l u b y 等扩展了g a l l a g e r 的规则l d p c 码，提出 了性能更优越的非规则l d p c 码 s l 。这些先期工作在编码界掀起了进一步研究 第一章绪论 l d p c 码的浪潮。与t u r b o 码相比，l d p c 码具有与t u r b o 码相近( 甚至在长码上 超越t u r b o 码) 的译码性能，同时它还具有译码速度快、易于v l s i ( 超大规模集 成电路) 实现和错误平层低等优点。此外，可以借助r i c h a r d s o n 和u r b a n k e 等提 出的密度进化理论优化设计l d p c 长码并分析其极限性能【9 】。 近年来，编码理论界关于二元l d p c 码的构造方面取得了许多研究成果，大 致分为随机构造方法和代数构造方法。随机构造方面比较著名的有x i a o y uh u 的 p r o g r e s s i v ee d g eg r o w t h ( p e g ) 0 0 】以及近年来t a ot i a n 等人提出的降低错误平层的 a c e 算法【1 2 1 。在代数构造方面，差集、循环移位矩阵、有限几何等都被用来构造 l d p c 码校验矩阵。r y a n 等学者设计了可以快速编码的中等码长高码率的非规则 l d p c 列1 2 】，这类码实质上是一种非规则r a 码。最近，s h ul i n 等将代数编码与 随机编码方法相结合，提出了基于有限几何和有限域的l d p c 码代数构造方法， 所构造的l d p c 码具有较低的错误平层【”】【1 4 】。 l d p c 码是当今信道编码领域的研究热点。随着通信质量要求和硬件水平的提 高，以及理论研究的日趋成熟，l d p c 码已经走进实用化进程。近几年国际上对 l d p c 码的理论研究以及工程应用和v l s i 实现方面的研究都已取得重要进展。 目前l d p c 码已被广泛应用在包括通信、广播、h d d 硬盘等领域。 2 0 0 2 年，美国f l a r i o nt e c h n o l o g i e s 公司率先将l d p c 码应用于基带l s i 。2 0 0 3 年，英特尔公司提议在1 0 g b a s e t 中采用该方式。测定该规格的i e e e8 0 2 3 a n 工作小组在2 0 0 4 年8 月一致通过采用l d p c 码。日本n t tc o m m u n i c a t i o n 在2 0 0 4 年1 2 月开始导入实时的图像配信服务“o c nt h e a t e r 同样也采用l d p c 码。 一般的l d p c 码编码器实现非常复杂，r i c h a r d s o n 和u r b a n k e 提出的r u 算法 ( 2 0 0 1 年) 实现对非规则l d p c 的快速编码，很大程度上降低了编码复杂度，但 是其复杂度仍然较高。另外，通过构造有一定规律的校验矩阵，可以降低编码复 杂度，如非规则重复累积( i r a ) 码及扩展i r a ( e l r a ) 码，两者都能够实现线性 时间编码。这种结构的l d p c 码已经在2 0 0 4 年发布的d v b s 2 标准中得到应用。 2 0 0 4 年6 月确定的h d t v 卫星电视放送规格标准d v b s 2 也采用了l d p c 码。 i e e ep 8 0 2 1 6 e 中则给出一种基于矩阵分块的构造方法，其编译码实现简单且性能 优异。 除了通信范畴外，硬盘h d d 保存装置也让l d p c 码有所发挥。现代硬盘的纪 录密度的年增率约3 0 ，早已挥别以往一年两倍的增加速度。虽然厂商也努力在 导入垂直纪录的新方法，但能否大幅度改善并不被看好，人们更期待高水平的纠 错编码来提高纪录密度。 可见，由于l d p c 编码具有接近s h a n n o n 限的性能、抗衰落性能突出、译码 速度快、易于v l s i 实现和错误平层低等优点使之成为研究热点。l d p c 结合o f d m 调制、c d m a 技术在3 g 、b 3 g 和第四代移动通信中将得到广泛应用。在磁盘存贮 4 基于e m s 算法的多元l d p c 码译码器设计及f p g a 实现 系统中，l d p c 码的纠错性能要好于磁盘存储系统高码率短帧码工业标准之一的 r s 码的性能。除此之外，l d p c 码的编译码技术、l d p c 码与多天线系统相结合， 都可以极大地提高移动通信系统中的用户容量。l d p c 码在磁盘存储系统、下一代 a d s l 系统以及深空通信、无线通信方面是取代r s 码的强有力的候选者，有极其 重要的应用价值。这些技术都将成为各大研究机构和通信公司的研究热点。未来 移动通信标准也都将l d p c 码作为信道编码方式之一。 1 2 2 多元l d p c 码的发展 多元l d p c 最早由g a l l a g e r 提出【5 j ，1 9 9 8 年，d a v e y 和m a c k a y 研究了基于 有限域的多元l d p c 码【l5 1 ，结果表明其性能要优于二元l d p c 码，但这是以更大 的编译码复杂度换取的。2 0 0 5 年，s h ul i n 等人提出了几种基于有限域构造多元准 循环l d p c 码的方法，其编码增益超过采用代数译码算法下相同码长和码率的r s 码【1 6 1 。 目前关于l d p c 码的研究主要集中在二元码上，只有极少数涉及多元l d p c 码。然而，已有研究表明，在中、短码长时，多元l d p c 码比二元l d p c 码具有 更强的纠错性能【l 7 1 9 1 ；这种优越性在高阶调制系统中表现的更为显著。 与二元l d p c 码相比，多元l d p c 码的优势主要体现在： 1 ) 更好的纠错性能：和积迭代译码在无环图中等效于最大后验概率译码，而 在有环图中大量小环的存在会严重恶化和积迭代译码性能，消除小环( 特别是4 环) 对迭代译码的正确收敛至关重要。由于多元l d p c 码将多个比特合并成一个 多元符号，从而具有消除l d p c 码二部图表示中小环的潜力，有望能获得更好的 纠错性能。 2 ) 抗突发错误能力强：实际信道中产生的错误往往是突发错误或突发错误与 随机错误并存，如在无线信道和网络信道中，由于信号衰落或数据包丢失等原因， 信道产生的错误往往是突发的，而二元l d p c 码并不具有很强的抗突发错误能力， 在实际系统中往往需要同r s 码或b c h 码级联。多元l d p c 码由于可以将多个突 发比特错误合并成较少的多元符号错误，因而纠错性能优于二元l d p c 码。研究 结果已经验证了这一点。 3 ) 适合高速率传输：多元l d p c 码是基于高阶有限域设计的，因此非常适宜 与高阶调制方案及多天线系统结合，从而提供更高的数据传输速率和频谱效率。 采用多元l d p c 码，可以设计高效的单多层编码调制系统。多元l d p c 码也很容 易与多天线系统相结合以获得更高的频谱效率。 但是，多元l d p c 码也有其缺点。设l d p c 符号所在的域是g f ( q ) ，其中q = 2 ，。 由于l d p c 码译码算法是在符号级上的，所以标准的和积算法的实现复杂度会随 着p 的增加而迅速增加。另一方面，为提高多元l d p c 码的纠突发错误能力，我 第一章绪论 们又希望增大p 。这个矛盾表明，降低多元l d p c 码的编译码复杂度是一个非常 值得研究的问题。目前关于这方面已经有了一些研究成果，如文献 2 0 从理论上证 明了在多元l d p c 码的译码过程中，由校验节点传往变量节点的信息可以通过f a s t h a d a m a r dt r a n s f o 加( f h t ) 来计算，从而降低了译码复杂度；文献【2 1 提出了一 种置信传播算法的改进方法，使和积译码算法可以用于高达g f ( 2 5 6 ) 上的l d p c 码 的译码；文献 2 2 1 提出了一种用于多元l d p c 码的广义最小和译码算法，该算法的 译码复杂度要远远低于o ( q 2 ) ，从而可以应用于更高阶域上的l d p c 码，而同时性 能损失却很小。但是在实际应用系统中，在性能损失不大的前提下，多元l d p c 码的译码的低复杂度的译码算法以及相应的量化实现也是一个很值得研究的问 题。 多元l d p c 码的译码复杂度随着域增大而指数增加。文献 2 3 】提出了一种g f ( 8 ) 上的多元l d p c 码译码器的硬件实现结构。但是在实际系统中，高阶域上的多元 l d p c 码能更好的与高阶调制相结合，其硬件实现也更具研究价值。 总之，在多元l d p c 码的研究中，机遇与挑战并存。值得相信的是，多元l d p c 码将成为未来高速无线通信中编码方案的极具竞争力的候选者，有着良好的应用 前景。 1 3 本文研究工作及内容安排 本文作者结合国家8 6 3 计划项目( 2 0 0 6 a a 0 1 2 2 6 7 ) ，研究了多元l d p c 码的译 码算法，并采用e m s 算法实现了一个g f ( 6 4 ) 上码长1 0 4 4 b i t s 、码率1 2 的多元l d p c 码译码器。本文共分为五章，其余章节内容安排如下： 第二章介绍多元l d p c 码的译码算法，主要包括b p 算法、f f t - b p 算法、对 数域的f f t o b p 算法以及e m s 算法，阐述了多元l d p c 码译码算法的具体步骤， 并对算法复杂度问题进行了讨论。 第三章介绍e m s 译码算法参数的设定与量化性能，详细阐述了e m s 算法实 现的具体设计，主要介绍了实现中涉及参数的设定和各主要计算步骤的设计。详 细说明了初始消息向量的计算、校验节点更新和变量节点更新中需要处理的数据 及相应的处理操作。 第四章详细介绍了多元l d p c 码译码器的f p g a 实现，对其中的各个模块的 功能以及各模块之间的相互关系做了说明，并通过硬件平台仿真对该译码器的性 能进行验证测试。 第五章对全文进行总结，并提出下一步的研究方向。 第二章多元l d p c 码及其译码算法 第二章多元l d p c 码及其译码算法 本章简要介绍了有限域和多元l d p c 码的概念，阐述了多元l d p c 码译码算 法及其具体步骤，主要包括b p 算法、f f t - b p 算法、对数域的f f t - b p 算法以及 e m s 算法，讨论了多元l d p c 码译码算法的复杂度问题，最后给出了算法性能仿 真和分析。 2 1 有限域介绍 基于有限域的多元l d p c 码中的符号是有限域o f ( q ) 中的域元素，其编译码都 涉及有限域上的运算。为此，我们先简要介绍有限域的概念。 对于任何质数p ，存在一个有限域，表示为o f ( p ) ，其中包含有p 个元素。可 以将o f ( p ) 延伸为一个含有p 肼个元素的域，称为o f ( p ) 的扩展域，表示为o f ( p 肘) ， m 是非零整数，g f ( p ) 是o f ( p ”) 的子集。 一般提到的多元l d p c 码都是基于扩展域o f ( 2 ”) 中的元素构造的，所以我们 需要简要介绍扩展域g f ( 2 ”) 的概念。 g f ( 2 ”) 中任何非零元素都可由a 的幂次表示，a 也被称作o f ( 2 ”) 的本原元。 o f ( 2 ”) 上元素的无限集f ，就是根据元素集 o ，1 ，a ) 而形成的，后一个元素通过前 一项乘以口得到： f = o ，1 ，a ，a 2 ，a 7 ，) = o ，a 0a 1 ，口2 ，a 7 ， ( 2 1 ) 为了从f 中得到有限元素的集合o f ( 2 ”) ，必须对f 域施加一个条件，使它只 能含有2 肘个元素并且对乘法封闭。域元素集对乘法封闭的条件可由下面的不可约 多项式表示： a ( 2 。- l + 1 = 0 即a ( 2 - - 1 ) ：1 = a o( 2 2 ) 根据这个多项式限制条件，任何幂次等于或超过2 珊一1 的域元素都可降阶为如 下所示的幂次小于2 ”一1 的元素： a ( 2 - + ”) = a ( 2 一1 a ( 肿1 ) = a ( ”+ 1 ( 2 3 ) 由此，集合f 可转化为： o f ( 2 册) = o ，口o ，a 1 ，口2 ，a 但。- 2 ( 2 - 4 ) 、， 在有限域o f ( 2 ”) 中，2 ”个元素中的任意一个都可由阶数小于或等于聊一1 的不 同多项式来表示。多项式的阶数是它的最高幂指数。将o f ( 2 ”) 中每个非零元素用 多项式口f ( x ) 表示，其系数至少有一个不为o 。对于f - o ，1 ，2 ，2 肘一2 ，有： a 。= 口j ( 义) = 口l o + q ，l x + 口f ，2 x 2 + + a i j ，l l x 加1 ( 2 5 ) 以m = 4 即g f ( 2 4 ) 为例，表2 1 为域元素及其多项式表示。 基于e m s 算法的多元l d p c 码译码器设计及f p g a 实现 x 3x 2z 1x o ooo00 a o 000l a 1 00lo a 2 0l00 口3 1oo0 a 4 00ll a 5 o11o a 61l 0o 口71ol1 a 8 010l 口9 10l 0 a l o 01ll a l l 111o a 1 2 1lll 口1 3 11o1 仅1 4 100l 有限域中两个元素的加法定义为两个多项式中同幂次项系数进行模2 加，即： a + a = ( q ，o + a j ，o ) + ( q ，l + 吩。1 ) x + + ( q ，朋- 1 + a j ，m 1 1 ) x 脚一1 ( 2 6 ) 而有限域上的乘法则定义为： a 。a 。= a “7 - - a 。= a k , 0 + a k j r + + 吱，m l x 所1 ( 2 - 7 ) 其中k = i + j m o d ( 2 胂- 1 ) 。 2 2l d p c 码的概念 l d p c 码是一种线性分组码，它的名字来源于其校验矩阵的稀疏性，即校验矩 阵中只有数量很少的非零元素，其它大部分都是零元素。 一个码长为、信息位长度为k 的l d p c 码由生成矩阵g r 。定义或校验矩阵 日唯一确定。对于任意的信息序列焉。r ，通过对其进行编码得到对应的码字 x ：s g 。若l d p c 码是由校验矩阵嘞x 确定的，其所有码字x 都满足h z r = 0 r ， 即码字集合为日肌的零空间。校验矩阵的每一行表示一个校验约束，m 个校验约 第二章多元l d p c 码及其译码算法 9 束构成伴随式向量。校验矩阵的每- - y i j 中的非零元表示一个码元符号参与非零元 所在行的校验约束。 根据校验矩阵中的元素取自域的不同，l d p c 码可以分为二元l d p c 码和多元 l d p c 码。 从概念上来看，二元l d p c 码与多元l d p c 码的不同在于其校验矩阵中的元 素取自不同的域。二元l d p c 码校验矩阵中的元素取自有限域g f ( 2 ) ，而多元l d p c 码校验矩阵中的元素取自g f ( q ) 。二元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 码是一种线性分组码，它可以用因子图表示。l d p c 码的因子图由两类 节点组成：变量节点( v a r i a b l en o d e ) 和校验节点( c h e c kn o d e ) 。 图2 1 给出了一个二元l d p c 码的校验矩阵及其对应的因子图，在因子图中， 变量节点集合( 五，而，矗) 和校验节点集合( 毛，z 2 ，乙) 内部不存在相连的边，但两 类节点之间存在着连线，仅当| l l 盯= 1 时，其对应的变量节点和校验节点之间由一条 边连接。每个变量节点具有d ，条入射边，即度数为d ，；每个校验节点具有d 。条入 射边，即度数为d ，。 h = 1lo0 o0 0 10o1o1 0 ol10 o0 1 l0o0 0l0 o10110 0 图2 1 a 二元l d p c 码的校验矩阵 校验节点 翻 z 2z 3z 4 规 娩 溉 知趣 变量节点 图2 1 b 二元l d p c 码的因子图表示 l o 基于e m s 算法的多元l d p c 码译码器设计及f p g a 实现 若由因子图中的某个节点出发，经过不同的连续的节点，最后可返回所选的 起始节点，则该闭合路径即构成因子图中的一个环( c y c l e ) ，环上的节点数或边数 称为环长，图中所有环的最小长度称为围长( g i r t h ) 。 在l d p c 码的设计过程中，需要兼顾码结构本身和迭代译码解决环的问题。 一般码长较长时消除4 环即可获得较好的性能，而对于短码，环的影响更大一些。 所以在对l d p c 码进行构造时，要尽量消除小环【z 4 j 。 基于有限域的多元l d p c 码由d a v e y 和m a c k a y 在1 9 9 8 年首次提出。在中、 短码长时，多元l d p c 码比二元l d p c 码具有更强的纠错性能。 设多元l d p c 码所在的域是g f ( q ) ，其中q = 2 p 。g f ( q ) 上的多元l d p c 码由 一个稀疏矩阵乩。表示，矩阵中的值均是g f ( q ) 上的域元素。我们可以用因子图 来表示多元l d p c 码。 变量节点 校验节点 图2 2 多元l d p c 码的因子图 如图2 2 所示，即为多元l d p c 码的因子图。多元l d p c 码的因子图和二元 l d p c 码没有本质不同。但是，由于多元l d p c 码将多个比特合并成一个多元符号， 其因子图一般比二元l d p c 码小，因此，构造能够消除环的多元l d p c 码较为容 易。 2 3 基于有限域的多元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 码与随机构造的规 则l d p c 码的性能相当，当码长较长时，略差于随机构造的码，但是随机构造的 码往往成功率不搞，即码的性能差异较大。 构造多元l d p c 码时，不管采用随机构造方法，还是基于一定准则的多元准 循环l d p c 码构造，其校验矩阵中域元素的选取，可以用随机选取的方法，也可 第二章多元l d p c 码及其译码算法 以基于一定的准则进行选取。随机方法比较简单，但是一般性能不如后者好；此 外还有有限几何的方法。m a c k a y 熵准则和二进制图最小距离准则是两种主要的算 法。 对于系统形式的准循环l d p c 码，可以通过校验矩阵进行直接编码，而且编 码的方法很多，大致分为并行编码和串行编码两大类，它们各具特点。并行编码 可以有效降低时延，但是相比串行编码，需要额外的存储单元。具体实现时，要 在编码速度和复杂度之间进行取舍。 多元l d p c 码的编码已经不是其实用化进程中的瓶颈，但是多元l d p c 码的 译码复杂度问题一直没有得到很好的解决。 设l d p c 符号所在的域是g f ( q ) ，其中q = 2 p 。由于l d p c 码译码算法是在符 号级上的，所以标准的和积算法的实现复杂度会随着p 的增加而迅速增加。另一 方面，为提高多元l d p c 码的纠突发错误能力，我们又希望增大p 。这个矛盾表 明，降低多元l d p c 码的编译码复杂度是一个非常值得研究的问题。 多元l d p c 码的译码算法主要用于g f ( 2 p ) 上的多元l d p c 码。本文提到的多 元l d p c 码也指的是g f ( 2 p ) 上的多元l d p c 码，以后不再赘述。 现有的多元l d p c 码的译码算法都较为复杂。基于图模型的b p 译码算法是多 元l d p c 码最基本的译码算法。多元l d p c 码译码器和二元l d p c 码的b p 译码器 的最大区别就在于其节点之间传递的消息是g 个概率度量值或g 一1 个对数似然比 度量值。因此，每一个校验节点的计算复杂度与g 值成指数关系，这在有限域的阶 数g 很大时译码完成的计算量相当大。所以，b p 译码器只能应用在g 不是很大的 场合( q 6 4 ) 。采用基于快速傅里叶变换( f f t ) 的b p 算法能将校验节点的计算 复杂度减小到o ( ql o gq ) ，虽然已经大大降低了算法复杂度，但是采用此快速算法 要用到指数运算和实数的乘法运算，不利于硬件实现。基于对数域的f f t - b p 算法 能够进一步降低译码复杂度，而基于对数似然比的e m s 算法对b p 算法作了简化， 复杂度降低较多，而且需要存储的空间也极为降低，非常便于硬件实现，但性能 有一定的损失。 2 3 1b p 译码算法 多元l d p c 码的b p 算法并不是直接从二元的情况直接得到，因为多元l d p c 码的校验矩阵中的元素不是二元的。变量节点和校验节点之间不能直接传递消息， 而必须经过置换节点。从图2 3 中可以看到，图中左方的二元l d p c 码的变量节点 和校验节点之间可以直接传递消息，而具有相同连接关系的多元l d p c 码中，多 元l d p c 码的变量节点和校验节点之间消息的传递需要经过一个置换节点，置换 节点与校验矩阵中的非零元一对应，它需要完成消息中的域元素与校验矩阵中 非零元的乘法或者除法运算，其具体运算过程将在算法中说明。 1 2 基于e m s 算法的多元l d p c 码译码器设计及f p g a 实现 变量节点 校验节点 变量节点 置换节点 校验节点 图2 3 校验矩阵中的非零元在因子图中的转换 在表示多元l d p c 码的因子图中，变量节点属于有限域g f ( q ) ，而且，这些变 量节点都与校验节点相连。在连接变量节点和校验节点的边上，译码过程中的消 息不断的来回传递。由于码字符号是g f ( q ) 上随机的一个符号，因此在边上传递的 消息的数量也是鸟，即这些消息是g 长的向量。 g f ( q ) 上的l d p c 码的因子图中，边上传递的消息是长度为g 的向量，记为u 。 根据2 1 节的介绍，g f ( 2 p ) 上的元素可以表示为一个多项式。对向量u 中的元素 可以用p 维的张量来表示，记为口l ，a 2 ，口口】，其中a k o ，1 ) 。设a g f ( 2 p ) ， 口( x ) 为其对应的多项式表示，则有 上 a ( x ) = a k x 卜1 鲰 o ，1 ) ，v k 1 ，p ( 2 - 8 ) k = l q ，a 2 ，a q 】在因子图中表示与口对应的一个消息。在译码过程中，变量节 点和校验节点之间传递的消息向量u 包含g 个消息，分别对应g f ( q ) 上的g 个域元 素，例如g f ( 2 3 ) 上的l d p c 码的因子图中，其消息向量u = q ，a 2 ，口3 】) 。 假定信道为二进制输入高斯信道。对于一个g f ( 2 p ) 上的l d p c 码的码字 c q “r ，需要将其转换成二进制序列b 【6 l 。r ，其中钆 - 1 ，1 ) 。经过该信道 后，信道输出为以= 魂+ n k ，其中体为加性高斯噪声且体一n ( o ，仃2 ) 。 信道输出的似然值计算如下： ! 丝兰2 三 p ( 儿i 以= 1 ) o c p 幻2v k 【1 q n 】 ! 盐兰! 三 p ( 以i 钆= - 1 ) 芘口2 ，v k 【1 习】 ( 2 - 9 ) ( 2 - 1 0 ) 由于译码算法的初始化需要的是符号似然值，因此需要将比特似然值转化成 g f ( 2 p ) 上的符号似然值。初始化符号似然值记为三= 三 q ，a 2 ，口p 】) ，其计算如下： 【q ，a 2 ，口p 】= p ( 只l 【q l 。r p 】= 【q 口p 】) = 兀p ( 咒i 气= q ) ( 2 1 1 ) k = l 其中a e g f ( 2 p ) ，口( x ) = z 。 k = l 每个变量节点在初始化时对应的初始化消息向量包含q 个符号的似然值，记为 第二章多元l d p c 码及其译码算法 z 。 对算法中涉及的符号做定义如下： 州4 表示传入度为瓯的变量节点消息集合； ) 吼越表示传出度为矾的 变量节点消息集合；下标“p v ”表明消息由置换节点发送至变量节点；下标是“甲 表明消息由变量节点发送至置换节点。 吆 。丸4 、 ) 砒4 、下标“p c 和“c p 的含义与前面的类似。 译码算法可以分解成如下的步骤： 1 ) 变量节点更新计算 乩 q ，a 2 ，】= 三 口l ，a 2 ， 兀【q ，口2 ，】 ( 2 - 1 2 ) v = 1 v 耐 由于传递的消息是概率值，因此在计算出 q ，a 2 ，a ， 之后，需要对向 量做归一化处理，以保证满足 ，炳吲口l ，a 2 ，】= 1 ( 2 1 3 ) 2 ) 置换 q ，口2 ，a p = 石，五，厶】 ( 2 - 1 4 ) 其中，口( x ) = h ( x ) j ( x ) 。 3 ) 校验节点更新计算 以 m q 。，口f ：，】=兀 a c 。，q ：，】 ( 2 1 5 ) d l ( 善卜一+ 口而( 工) 暑0c = l ，c 耐 由于传递的消息是概率值，因此需要对运算结果圪做归一化处理，以保证 满足 怖埘，【q a 2 ，口p 】- 1 ( 2 - 1 6 ) 4 ) 逆置换 q ，口2 ， - 【 ，五，厶】 ( 2 - 1 7 ) 其中，a ( x ) = h - i ( x ) ( x ) 。 5 ) 译码判决 r 或、 安= a r g m a x t l a l ，a 2 ，】兀吼q ，a 2 ，口，】 ( 2 - i s ) a e g f ( 2 p ) i v 篁l i 从b p 译码算法的过程可以看出，其译码复杂度高的原因在于校验节点更新的 计算非常复杂，计算圪需要的操作数随着域的大小g 和校验节点的度数吐指数增 长，其复杂度为o ( d 。q 2 ) 。基于高阶域的多元l d p c 码很难采用b p 译码算法。 2 3 2 基于快速傅里叶变换的b p ( f f t - b p ) 算法 b p 算法的主要复杂度集中在校验节点的更新计算。为了降低b p 算法的复杂 1 4 基于e m s 算法的多元l d p c 码译码器设计及f p g a 实现 度，必须简化b p 算法中校验节点更新的计算。m a c k a y 等提出基于快速傅里叶变 换的f f t - b p 算法【2 5 】， b a m a u l t 、d e c l e r c q 和f o s s o