（通信与信息系统专业论文）多元ldpc码编译码器的设计与实现.pdf

摘要 摘要 近些年来，低密度奇偶校验码( l o wd e n s i 够p a r i t yc h e c kc o d e s ，l d p c ) 因 为其优异的纠错性能和高度并行的译码方案而受到极大的关注，被广泛考虑为下 一代通信系统中的纠错码标准，而多元l d p c 码作为二元l d p c 码的延伸，并没 有被人们深入的研究。但是，相对二元l d p c 码，多元l d p c 码有更好的译码性 能，其应用前景潜力巨大。 多元l d p c 码的实现复杂度和译码器的资源消耗很大是制约其发展的重要原 因，至今没有重要的硬件研究结果问世。本文，把编码和译码协同起来考虑，提 出一种基于准循环r a 结构编码算法，扩展最小和( e x t e n d e dm i l l s u m ，e m s ) 译 码算法的多元l d p c 码的编译码实现方案。系统详细的阐述其内部结构，功能， 工作原理，设计细节。准循环的校验矩阵结构有利于高速的并行编译码，r a 结构 大大的简化了编码复杂度，而e m s 译码算法很大程度上简化了译码实现复杂度和 资源消耗。本文采用4 元l d p c 码为例在x i l i n xf p g a 上做了实际验证，综合后的 编码器时钟频率为1 2 3 2 7 7 m h z ，折算成编码器输出端的数据率为2 4 6 5 5 4 m b i t s ， 译码器工作时钟频率为1 7 5 3 5 2 m h z ，折合成译码器输入端的数据率最大为 8 7 6 7 6 m b i t s s ，并进行相关分析和对比，证明其可用性。本文提出一种双进双出信 息调度算法，有效地提高了时钟利用率和吞吐量，译码速率增加到原来的1 9 3 倍。 针对这些情况，本文的主要研究内容包括： 首先，对多元l d p c 码的校验矩阵构造方法，编码方案，几种常见的译码算 法做了简单介绍，详细介绍了基于r a 结构的构造方法和e m s 译码算法。 其次，便于对比，详细阐述了r u 编码方法和本文采用的r a 结构编码方法的 硬件实现具体过程，并对二者的性能进行分析，给出了相关仿真结果。 再次，系统阐述了基于e m s 译码算法的译码器硬件实现方案，包括各模块功 能，结构，工作原理，着重对译码器资源占用、速度、性能进行详细分析，对比， 并提出一种优化的信息调度算法，证明了其可行性。 最后，作者对上述内容做以总结，并提出了下一步工作安排。 关键词：多元l d p c 码，扩展最小和，硬件实现，f p g a a b s t r a c t a b s t r a c t r e c e n t l y ，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 ea t t r a c t e dm u c ha t t e n t i o n b e c a u s eo ft h e i re x c e l l e n te r r o r - c o r r e c t i n gp e r f o r m e n c ea n dh i g h l y p a r a l l e l i z a b l e d e c o d i n gs c h e m e ，t h e yw i l lb e c o n s i d e r e d a s e r r o r c o r r e c t i n gc o d e sf o r n e x t g e n e r a t i o nc o m m u n i c a t i o ns y s t e m s l d p cc o d e so v e rg f ( q ) a r e a l le x t e n s i o no fb i n a r y l d p cc o d e st h a th a v en o tb e e ns t u d i e de x t e n s i v e l y h o w e v e r ，p e r f o r m a n c eo fg f ( q ) l d p cc o d e sh a v eb e e ns h o w nt ob eh i g h e rt h a nb i n a r yl d p cc o d e s ，a n dt h e yh a v e g r e a tp o t e n t i a lo f t h e i ra p p l i c a t i o np r o s p e c t s t h eh i g h l yh a r d w a r ec o m p l e x i t ya n da r e ao ft h ed e c o d e ra r et h ei m p o r t a n tr e a s o n f o rr e s t r i c t i n gt h e i rd e v e l o p m e n t i nt h i sp a p e r , p u t t i n gt h ec o d ea n dd e c o d e rd e s i g n t o g e t h e rt oc o n s i d e r , w ep r o p o s eaf p g ai m p l e m e n t a t i o nb a s e do nt h eq u a s i c y c l i cr a c o d i n ga l g o r i t h m ，e x t e n d e dm i n s u m ( e m s ) d e c o d i n ga l g o r i t h mf o rl d p cc o d e so v e r g f ( q ) f u n c t i o n ，s t r u c t u r e ，w o r k i n gp r i n c i p l ea n dd e s i g nd e t a i l sa r es y s t e m i c a l l y d i s c u s s e d q u a s i c y c l i cc o d e sc a nf a c i l i t a t ee f f i c i e n th i g h s p e e dp a r a l l e ld e c o d i n g r a s t r u c t u r el a r g e l yr e d u c e st h ec o d i n gc o m p l e x i t y , a n dt h ee m sa l g o r i t h mg r e a t l y s i m p l i f i e s t h e d e c o d i n gc o m p l e x i t y a n dr e s o u r c ec o n s u m p t i o n b a s e do nt h i s a r c h i t e c t u r e s t h el d p cc o d e so v e rg f ( 4 ) d e c o d e ri s i m p l e m e n t e do nx i l i n xf i e l d p r o g r a m m a b l eg a t ea r r a y ( f p g a ) t h er e s u l ts h o w st h em a x i m u me n c o d i n gc l o c k 丘e q u e n c yi s 12 3 2 7 7 m h z ，a n dt h e t h r o u t h p u ti s2 4 6 5 5 4 m b i f f s ，t h em a x i m u m d e c o c o d i n gc l o c kf r e q u e n c yi s1 7 5 3 5 2 m h za n dt h et h r o u g h p u ti s8 7 6 7 6 m b i t s s s o m e c o r r e l a t i o na n a l y s i sa n dc o m p a r i s o n sp r o v ei t s a v a i l a b i l i t y t h i sp a p e rp r e s e n t s s c h e d u l i n ga l g o r i t h me f f e c t i v e l yi m p r o v i n gt h eu t i l i z a t i o no ft h ec l o c ka n dt h r o u g h p u t a b o u t1 9 3t i m e sm o r et h a nb e f o r e a c c o r d i n gt ot h e s e ，t h em a i nr e s e a r c hc o n t e n t si n c l u d e ： f i r s t ，ab r i e fi n t r o d u c t i o na b o u tc o n s t r u c t i o nm e t h o d so fl d p cc o d e sa n ds e v e r a l c o i t l l t l o nd e c o d i n ga l g o r i t h m sh a sb e e nd o n e t h es t r u c t u r eo fr ac o n s t r u c t i o nm e t h o d s a n de m sd e c o d i n ga l g o r i t h mi nd e t a i l sa r ed e s c r i b e d s e c o n d , s e v e r a lc o d i n ga l g o r i t h m sa r ei n t r o d u c e d ，t oc o m p a r e ，w eg i v et h ed e t a i l h a r d w a r ei m p l e m e n t a t i o nd e s c r i p t i o no fr u c o d i n ga n dr ac o d i n ga l g o r i t h m s ，a l s ot h e u a b s t r a c t r e l e v a n ts i m u l a t i o nr e s u l t sa l eg i v e n t h i r d ，w eg i v et h ed e c o d e rh a l d w a l ei m p e n m e n t a t i o np r o g r a mb a s e d0 1 1e m s d e c o d i n ga l g o r i t h m ，i n c l u d i n ge a c hm o d u l ef u n c t i o n , s t r u c t u r e ，w o r k i n gp r i n c i p l e ，a n d t h ep e r f o r m a n c e t h ec o m p a r i s o nh a sb e e nm a d et op r o v ei t sf e a s i b i l i t y f i n a l l y , t h ea u t h o rg i v e st h es u m m a r yo ft h ec o n t e n tr i g h ta b o v ea n df u t u r ew o r k k e y w o r d s ：q - a r cl d p c ，e m s ，h a l d w a r ei m p l e m e n t a t i o n ，f p g a i i i 图目录 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 1 图2 1 2 图3 1 图3 2 图3 3 图3 4 图3 5 图3 - 6 图3 7 图3 8 图3 - 9 图3 1 0 图3 1 1 图3 1 2 图3 图3 图3 图4 3 4 5 图目录 ( 6 ，2 ，4 ) 码对应的因子图6 多元系统r a 编码结构图8 交织器结构图9 不同码长对应的r a 结构多元q c l d p c 码性能仿真曲线1 0 不同码率下r a 结构的q c l d p c 码的性能一1 0 类似下三角结构的校验矩阵1 2 信息位长k - - 4 8 6 ，码率i 净1 2 时，h l 的结构1 5 信息位长k - - 4 8 6 ，码率r - l 2 时，h 2 的结构1 5 利用张量表示的因子图的变换操作1 8 行度数为4 ，列度数为2 规则l d p c 码的傅里叶变换原理示意图2 l 4 元l d p c 在a w g n 信道下不同译码算法性能比较2 7 4 元l d p c 在瑞利衰落信道下不同译码算法性能比较2 7 r u 算法编码器结构图2 9 向量加法单元的电路结构图3 0 m v m 存储器r a m 中存放的x 矩阵的信息结构图3 1 矩阵向量乘法单元的实现电路结构图3 2 4 元域中相乘，相加运算的查找表结构图3 2 f s 前向迭代储存器r a m 中存储矩阵x 的信息结构图3 3 f s 前向迭代具体的实现电路结构图3 4 r u 算法编码器资源使用情况图一3 5 r a 算法编码器结构框图3 5 r a 算法编码器控制单元示意图3 6 r a 算法编码器输入模块的结构图3 7 r a 编码器输入模块中r a m 群的结构图3 8 r a 结构编码器输出模块结构图3 9 r a 结构编码器编码模块结构示意图一4 0 r a 结构编码器资源占用情况4 l 译码器整体结构图4 4 v i i 图目录 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 。l l 图4 1 2 图4 1 3 图5 1 图5 2 图5 3 图5 4 图5 5 图5 - 6 图5 7 图5 8 图5 - 9 l d p c 码完全串行译码结构4 5 l d p c 码完全并行译码结构4 6 l d p c 码部分并行译码结构一4 7 4 元l d p c 码校验节点模块设计结构框图一4 9 4 元l d p c 码校验节点排序器的结构框图5 0 4 元l d p c 码校验节点选择器的结构框图5 l 4 元l d p c 码校验节点分离器的原理框图5 2 4 元l d p c 码校验节点分离器中数据选择器的结构图5 3 2 4 输入l 输出的求最大值模块结构图5 5 4 输入，l 输出的m a x 模块结构图5 5 变量节点更新与输入输出i o w 模块的原理结构图5 6 变量节点更新和判决结构图5 7 4 元l d p c 码基于e m s 译码算法c n u 模块资源占用图5 9 4 元l d p c 码基于e m s 译码算法v n u 模块资源占用图5 9 4 元l d p c 码基于e m s 译码算法整体模块资源占用图6 0 e m s 译码器硬件实现与软件仿真对比图6 2 信息交叠调度算法6 3 标准信息调度算法原理图，6 3 交叠信息调度算法原理图6 4 双进双出信息调度算法原理图6 5 双进双出信息调度算法译码器资源占用示意图6 6 v i i i 表目录 表目录 表2 - i四进制加法与乘法运算表7 表2 - 2p 1 计算分解步骤1 3 表2 - 3p 2 计算分解步骤1 4 表2 - 4不同译码算法的计算复杂度2 6 表5 - il o g f f t - b p 译码算法c n u 计算模块6 0 表5 - 2l o g f f t - b p 译码算法v n u 计算模块6 0 表5 3l o g f f t - b p 译码算法整体模块6 0 表5 - 4本文译码器整体模块折算资源对比6 1 缩略语说明表 各n q 淑 b e r b p c n u e m s f p g a f f t i o l d r l d p c l u t m i m o 0 f d m p e g q c q p s k s t b c v n u 缩略语说明表 a d d i t i v ew m t eg a u s s i a nn o i s e b i te r r o rr a t e b e l i e fp r o p a g a t i o n c h e c kn o d eu n i t e x t e n d e dm i n - s u m f i e l dp r o g r a m m a b l eg a t ea r r a y f a s tf o u r i e rt r a n s f o r i l l i no u t p u t l o gd e n s i t yr a t i o l o wd e n s i t yp a r i t yc h e c k l o o ku pt a b l e m u l t i p l ei n p u tm u l t i p l eo u t p u t o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g p r o g r e s s i v ee d g eg r o w t h q u a s ic y c l i c q u a t e m a r yp h a s es h i f tk e y i n g s p a c e t i m eb l o c kc o d e v a a b l en o d eu n i t x 加性高斯白噪声 误码率 置信传播 校验节点 扩展最小和 现场可编程门阵列 快速傅立叶变换 输入输出 对数似然比 低密度奇偶校验 查找表 多输入多输出 正交频分复用 渐进边增长 准循环 四相相移键控 空时分组码 变量节点 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：一塑l 盟一 日期：劢1 1 7 年午月加日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：到：垒 导师签名：鍪碰 日期：k f 汐年( p 月1 , oe t 第一章绪论 第一章绪论 l d p c ( 低密度奇偶校验) 码是由g a l l a g e r 【1 】【2 】在1 9 6 2 年首次提出来的一类非 常高效的纠错码，是一种具有稀疏校验矩阵的线性分组码，然而可惜的是在接下 来的3 0 年里受计算机运算能力和集成电路规模的限制，一直被人忽略。直到1 9 9 6 年d j c m a c k a y 和r m n e d 等人1 3 j 【4 j 对它重新进行了研究，发现l d p c 码具 有逼近香农限的优异性能，在二进制a w g n 加性高斯白噪声信道下，码率为1 2 的最好的不规则l d p c 码的门限值距香农限只有0 0 0 4 5 d b ，码长为1 07 时其仿真 结果显示，在误比特率为1 0 击的情况下，离香农限的距离低于0 0 4 d b ，这超过了 t u r b o 码。并且具有译码复杂度低、可并行译码以及译码错误的可检测性等特点， 从而成了信道编码理论新的研究特点。目前l d p c 码的研究主要集中在2 个方面， 其中一个是非规则的2 进制l d p c 码，在码长大于1 0 0 0 0 时，性能非常接近香农 限【5 j ，另一个就是中短码长的多元l d p c 码【6 j 。文献 6 中说明多元l d p c 码的性能 要好于2 元l d p c 码，最好的l d p c 码是非规则的多元l d p c 码p j 。 1 1 多元l d p c 码的应用前景和发展方向 基于l d p c 码的编码调制系统已经成为目前l d p c 码的研究热点瞵儿引。基于多 元l d p c 码的高阶调制系统的研究更加有前景。文献 1 0 中，作者提出了一个新映 射机制，应用于多元l d p c 码编码调制系统，基于平衡保护的原则，对于星座图 中的最高有效位分配较少的比特，可以获得0 1 d b 0 5 d b 的性能优势。 多元l d p c 码可以应用于s t p c s p 系统中，实现基于符号的预编码和l d p c 码迭代检测功能，使之获得很高的系统增益【1 1 1 。 l d p c 码成功应用于第二代数字视频广播系统，作为其信道编码方案。c c s d s 组织也建议l d p c 码作为空间通信系统的信道编码方案。 为了减小衰落影响和提供更好的频谱利用率，快速调频多址接入多维频率调 制系统( f f hm a m f s k ) 被人们广泛的关注，文献 1 2 中，作者提出了一种应用 多元l d p c 码的f f hm a m f s k 软多用户解调方法，结果显示，无论是高斯信道， 还是瑞利衰落信道，性能都有很大改善。 电子科技大学硕士学位论文 文献 1 3 1 0 0 ，作者把多元l d p c 码应用到s i s o 和m i m o 系统中，采用的p e g 构造方法，准循环结构，l o g s p a 译码算法，高阶调制，衰落信道，相对于2 进制 l d p c 码在1 0 。5 次方误码率时有0 2 d b 的增益。 最近几年，促使传感器网络发展进化的几种可能技术之一就是分布式源编码 ( d i s t r i b u t e ds o u r c ec o d i n g ，d s c ) 。d s c 要求低复杂度的编码器，把复杂度转移到 译码器中。文献 1 4 】中，作者采用多元l d p c 码作为d s c ，结果显示，相比于同等 的二进制压缩机制要好，非常使用于传感器网络 另外，多元l d p c 码也可以应用到磁介质存储中，被证明性能上可以替代r s 码【1 5 】【1 6 1 。 一般的f l a s h 存储介质通常使用简单的差错控制码，比如汉明码，b c h 码，在 未来高密度多级单元( m u l t i l e v e lc e l l ，m l c ) f l a s h 存储器中，随着级数的增加， 误码率也会高涨，因此，常规的纠错码是满足不了需求的，文献 1 7 】中，作者采用 多元l d p c 码作为其纠错码应用，是m l c 重要的候选码字之一。另外，多元l d p c 码也可以应用于媒体存储系统中，作为纠错码部分【l 引。 矢量脏纸编码( v e c t o rd i r t yp a p e rc o d i n g ，d p c ) 技术应用于多点协同系统， 但是一般的d p c 实现由于量化而造成性能损失，文献 1 9 】中，作者提出一种新的 矢量d p c 传输机制，把多元l d p c 码与基于低密度生成矩阵的量化器结合起来， 结果显示会带来1 4 9 0 6 d b 的增益。文献 2 0 】中，作者提出了一种基于多元l d p c 码的编码协同机制，可以使多用户环境达到全传输分集。 目前光纤通信系统是采用b c h r s 码和他们的级联形式，文献 2 1 中，作者认 为多元l d p c 码是光线信道中4 0 g b s 传输率的纠错码选择之一，结果显示，b e r 在l o 以2 时，增益达到1 0 5 d b ，而冗余度只有1 2 5 9 。 多载波码分复用技术最近几年在4 g 通信系统比如无线宽带多媒体应用方面 受到广泛关注，其囊括了多种技术优势，高频谱利用率，量化简单，窄带干扰消 除，多点接入，文献 2 2 q u ，作者提出一种多点接入检测的新机制，其中把p i c l i k e 检测和联合多元l d p c 译码结合起来，用于上行链路架构。 f h 调频技术是常见的抗干扰技术，在突发噪声信道中，常用的纠错码为r s 码，文献f 2 3 】中，作者采用多元l d p c 码为纠错码，应用于f h 系统。结果显示其 性能要好的多。 最近，多载波调制采用o f d m 的形式被应用于水下通信，可是o f d m 在衰落 信道中的性能较差，而且o f d m 传输要求有较高的峰平功率比。文献 2 4 】中，作 者采用多元l d p c 码来解决上述问题，提出新的构造方法，具有高性能，可线性 第一章绪论 并行编码，p a p r 大大降低，试验证明采用该类多元l d p c 码水下通信系统非常好。 1 2 多元l d p c 码的主要研究内容 目前，多元l d p c 码的研究大部分集中在两个方向，其中一个是研究l d p c 码的校验矩阵的构造方法和译码算法优化的角度来提高l d p c 码的性能。另外一 类是通过构造特殊的l d p c 码校验矩阵，从简化硬件资源需求的角度，实现性能 和资源利用率的平衡。 文献 2 4 】中，作者采用欧几里德有限几何法构造多元l d p c 码，特征为支持固 定码长下多码率，并且成功应用于m i m o 系统中。这些码字可以支持相同的译码 结构，因此，采用这些码字的m i m o 系统也可以支持不同的数据传输率，而且相 比i e e e s 0 2 1 6 e 二进制l d p c 码有较低的复杂度和更好的性能。文献 2 5 】中，作者 基于欧几里德几何学的超平面法来构造高效编码和高性能多元准循环l d p c 码。 文献 2 6 1 中，作者基于欧几里德几何学的2 种不同的特性循环置换矩阵和超平面来 构造性能非常好多元l d p c 码。 文献 2 7 】中，作者提出了多元r c l d p c 码的构造方法，是基于二进制映像代 数特性比特缩短方法。结果显示相对于传统方式，在码率为1 5 时，会有l d b 的 增益。文献【2 8 中作者也是利用多元l d p c 码的二进制映像，代数特性来构造其校 验矩阵。 文献 2 9 3 0 】 3 1 m ，作者提出了多种多元l d p c 码的代数构造方法，结果表 示他们都能在相同码长情况下性能超过r s 码。可以替代r s 码应用于某些存储和 通信系统。 文献 3 2 中，作者提出了一种基于外信息转移图( e x t r i n s i ci n f o r m a t i o nt r a n s f e r ， e x i tc h a r t s ) 的方法来设计多元l d p c 码，并用于高斯信道。 文献 3 3 中，作者把二进制l d p c 码高斯近似的密度进化理论扩展到多元域 上，文献【3 4 】中，作者给出了多元l d p c 码的密度进化，门限，稳定条件。 文献 3 5 1 中，作者提出了一个简化的多元l d p c 码的s p a 译码算法，核心是 采用e t 变换，使译码迭代形式类似与2 进制形式，相对于规则的s p a 算法有0 5 d b 的下降。 我们知道有很多译码算法可以简化译码复杂度，但是迭代次数是固定不变的， 然而，有些信息因为过大的噪声是无法进行译码的，这样就会浪费不必要的迭代 电子科技大学硕士学位论文 次数去译码，希望译码停止规则可以灵活一些，文献 3 6 q u 作者给出了一个新的多 元l d p c 码译码停止规则，基于分析变量节点外信息的方差。可以在忽略不计的 性能损失的情况下有效的降低平均迭代次数 文献 3 7 1 q u ，作者提出了一种新的简单的译码算法，把比特翻转方法和标准的 傅里叶变换结合起来，结果显示，在高性噪比区域，译码复杂度大大简化，性能 增益很大。 文献 3 8 中，作者提出了一种新的具有低复杂度，准循环特性迭代译码算法 m i n m a x 算法，采用蒙特卡罗法仿真显示，相比b p 译码算法有0 2 d b 的性能损失， 非常适合于实际应用。 实现方面，文献 3 9 中，作者给出了一个多元l d p c 码译码器实现方案，结果 显示译码的吞吐量为4 4 4 m b s 时钟频率为15 0 m h z 。 文献 4 0 中，作者提出了一个对数域上的多元l d p c 译码器实现方案，其复杂 度为o ( q l o g q ) ，选用的译码算法为m a x l o g ，准循环矩阵，码长5 1 2 ，行重为6 ， 列重为3 。结果显示在g f ( 1 6 ) q u ，在e b n 0 为6 3 d b 时，误码率在1 0 。 文献 4 1 1 中，作者把多元准循环l d p c 码和相干检测结合起来应用于光纤路由 网络，能够适应可变的信道环境，支持的数据率达到1 0 0 g b s 文献 4 2 中，作者首次提出了一个高效的多元l d p c 码的v l s i 结构方案，译 码算法为m i n m a x ，5 比特量化，o 18 u m c m o s 工艺，工作频率2 0 0 m h z ，m m c u 消耗5 5 k 。 本文通过对多元l d p c 码的编码，译码算法分析，找到一种适宜于硬件实现 的多进制l d p c 码编译码方案。并且利用m a t l a b 语言验证其链路性能，同时在 x i l i n xv 4f p g a 上对其设计进行实现并调试验证。 1 3 论文结构及内容安排 本文重点研究了多进制l d p c 码译码的设计与硬件实现，首先对几种常用的 多元l d p c 码的编码、译码算法进行比较分析，最终采用r a 结构的编码方式， e m s 扩展最小和译码算法，其次，详细系统的阐述了编、译码的实现方案和设计 过程，最后采用a w g n 信进行链路仿真。并利用硬件平台，以4 元l d p c 码为例 对所做的设计进行仿真调试验证。具体内容安排见下： 本章节介绍了多元l d p c 码的研究现状和研究意义，阐述了多元l d p c 码的 4 第章绪论 主要研究内容。并对本文的研究方向和范围进行概括，给出了全文的内容纲要。 第二章着重介绍了多元l d p c 码的理论基础、基本的编码构造方法，编码方 案，几种常见的译码算法，并进行性能比较分析。 第三章提出基于r a 编码方式的硬件设计和实现结构，并进行性能分析和对 比。 第四章主要论述基于e m s 译码算法的多元l d p c 码的译码器的设计与硬件实 现结构。 第五章主要是以4 元l d p c 码为例对译码器进行链路验证仿真测试。包括译 码器资源占用分析，性能分析，速度分析，信息调度算法的改进优化。 最后，第六章对全文进行总结，并对下一步研究工作进行展望。 电子科技大学硕士学位论文 第二章多元l d p c 码的编码和译码算法 2 1 多元l d p c 码的基本知识 1 9 6 2 年， r o b e r tg a l l a g e r 1 】博士提出一种具有稀疏校验矩阵的分组纠错码。 我们常用因子副4 3 】来表示l d p c 码。因子图中包含的节点可以分为信息节点和校 验节点，相互之间的连接关系与奇偶校验矩阵h 对应，即变量节点对应矩阵h 的 列向量，校验节点对应其行向量，而矩阵中非零元素对应因子图上的一条边。便 于理解，举例：一个码长为n = 6 ，码率r = l 3 ，列重为2 ，行重为3 的校验矩阵h 是： h = 1o 0l o o 11 1o o o 1l 01 上面矩阵其对应的因子图如下： 校验节点 o1 ll 1o o o 变量节点 图2 - 1 ( 6 ，2 ，4 ) e - 马对应的因子图 对l d p c 码的定义m a k c a y 又进行了推广【6 1 。多元域上的l d p c 码比二进制 l d p c 码有更好的性能，而且实践表明在越大的域上构造的l d p c 码译码性能就越 好，比如在g f ( 1 6 ) 上构造的规则码性能已经和t u r b o 码相差无几。 编、解码的功能体现在对码字实行乘、加运算，运算的规则服从元素所在字 符集代数域的惯例。般的，在元素集合构成的域f 中，对元素定义的两种算术 运算：加法和乘法。它们要满足以下特性 删： 6 第二章多元l d p c 码的编码和译码算法 加法 1 ) 集合f 要满足加法是封闭的。 2 ) 满足加法结合律：如果口，b ，c f ，那么口+ ( 6 + c ) = ( 口+ b ) + c 。 3 1 满足加法交换律：口+ 6 = b + 口。 4 、口+ 0 = a 。 5 ) 每个元素对应的逆元素记为一b 。两个元素相减定义为口- b = 口+ ( 一6 ) 。 乘法 1 ) 集合f 要满足乘法是封闭的。 2 ) 满足乘法结合律：a ( b c ) = a ( b c ) 。 3 ) 满足乘法交换律：a b = b a 。 4 ) 满足乘法分配律：( c t + 6 弦= a c + b c 。 5 )口( 1 ) = 口。 6 ) 除零外，每个元素对应的逆元素记为b 。两个元素相除定义为 口b = a b 。 如上面所述，码是由有限个元素的域构成的，用g f ( q ) 表示。每个域必须有一 个零元素和一个单位元，最简单的是二元域g f ( 2 ) ，一般地，若q 是素数，可构成 一个由元素f o ，1 ，q 一1 ) 组成的q 元域g f ( c o 。在域g f ( q ) 中的加、乘运算定义为 摸q 运算。 本文采用的多元域为四元域口( 4 ) ，由四个元素( o ，1 ，2 ，3 ) 构成，其对应的加 法与乘法运算规则如表2 1 所示。 表2 1 四进制加法与乘法运算表 + o 12 3 oo123 11o32 223o l 332lo 0123 o0ooo 1 0123 2o23 l 3 0312 通常，有限域只有当q 是素数或素数的幂数时才能构成。当q 是素数时，乘 法和加法基于上述模q 运算，如果，q = p ”( p 是素数，m 为任意正整数) ，有可 能将g f ( q ) 域扩展为g f ( q ”) 。扩域中的乘、加运算也基于模q 运算。 7 电子科技大学硕士学位论文 2 2 多元l d p c 码的构造方法 目前l d p c 码的构造方法通常会划分成两类：随机或伪随机法和代数法。随 机或伪随机法侧重考虑码的性能，而代数法则更多的是考虑如何降低编译码复杂 度，优势在码长较短时更明显。其中比较常见的构造方法有g a l l a g e r 的构造方法【l j ， m a c k a y 的随机构造方法【4 5 】，p e o ( p r o g r e s s i v ee d g e g r o w t l l ) 构造方法【4 引，b i t - f i l l i n g 构造方法 4 7 1 ，e x t e n d e db i t f i l l i n g 算法【4 8 1 ，还有欧几里德有限几何构造方法 4 9 】【5 0 】， 这些构造方法用于硬件实现比较复杂，不利于并行的流水处理，本文采用的是下 一节介绍的基于r a 结构的多元准循环码构造方法。 2 2 1r a 结构多元准循环码构造法 本文采用的r a 结构的多元准循环l d p c 码构造方法如下： 次系统r a 码是由重复器、交织器、组合器和累加器( 5 l 】【5 2 】组成如图2 2 所示。 长为k 的信息序列m = ，m ：，m k ，经重复器重复p 次后得： m 1 = m 2 l = m p = m 1 ，聊2 ，m 】 图2 2 多元系统r a 编码结构图 在交织器如图2 3 所示中，由p 个内交织序列n ，幢，p 分别对信息 序列m o ，m 扪，”r e ( p ) 进行交织，其中r l “= 防：，) ，万黔，万印，i = i ，2 ，p 。交织后 的输出序列为：b ，b ，b 川，其中b 7 是m n 经o 交织后的输出。交织过程 由公式表示为： b 噱刚，b 2 0 ) ( ，) 】= i r a ；一聊。，聊。小扛1 2 ，p 将交织后的p 个输出序列复合，得 a = q ，口2 ，a k 。p 】= b ，b ，b p 】= 6 1 f ，磷，研轴，磷扪，：研川，磷】 第二章多元l d p c 码的编码和译码算法 交织器( 1 k 行q y u 交织器( 2 复 i l l l 用 行列交织器 器 一 交织器( p 1 图2 3 交织器结构图 复合后的序列a 输入加权器，组合器。设加权序列w = ( m ，w 2 ，w k 。p ) ， w ( 1 ，2 ，q - i ) ，组合器参数为a ，则经过加权、组合后的输出为： ，；= ) 口+ l w h ) 州+ + a c f _ l m 口w c ) 口+ 4 = a f i _ 1 ) a + l w ( f - 1 ) 口+ ，i = 1 2 k p a ( 2 1 ) ，- l 然后经累加器计算k xp a 个校验位p ，设累加因子口，g f ( q ) ，累加运算 表达式为1 ( a + f l d ) ，则 p l = 口一1 只= ( 只一l + ，；) 口一1f = 2 , 3 ，k p a ( 2 2 ) 该码字是c = 【m l ，p i , - - , n 州。】，对应码长n = 尼+ 印a ，码率r = k ( k + k p a ) = a ( 咖) 。当重复次数p 、组合参数a 给定时，可以编码得到( p ，a ) 规则l d p c 码。改变k 、p 和a 值，可以构造不同码长，不同码率的r a 结构的l d p c 码。 与上述编码过程相对应，该l d p c 码奇偶校验矩阵h 可以分为两部分 h = 【i ：1 ，l r l ：】。1 ：i ，是列重为p ，行重为a 的稀疏矩阵，其非零元素的分布由交织器 参数c 决定，非零元素的值由加权器的加权序列决定；h ，是一个由累加器决定的 双斜对角矩阵。最后根据h 进行b p 译码。在这种方法，交织器和加权的设计是非 常重要的，它关系校验矩阵h 的准循环结构【5 ”，及其环、度的分布。 为了与实现统一，在g f ( 4 ) 域上，基于r a 码结构的多元准循环l d p c 码经过 a w g n 信道，采用q p s k 调制和b p 译码算法，最大的译码迭代次数设定为4 0 次， 针对不同的码长、码率分别进行了性能仿真。 9 州觥删滞多元q c - l d p c 码竺竺 慧霪； 蟊唾墨萋誊委萋! = ! 竺 舻擘譬囊攀攀攀攀! 攀 第二章多元l d p c 码的编码和译码算法 图2 4 所示为码率1 2 ，码长分别为1 6 2 、4 8 6 、9 7 2 和1 9 4 4 时r a 结构的多元 q c l d p c 码的b e r 性能比较。图2 5 所示为码长9 7 2 ，码率分别为3 4 、2 3 、1 2 、 l 3 时r a 结构的多元q c l d p c 码的b e r 性能比较。 从图2 - 4 和图2 5 可以看出，本文采用r a 构造方法的q c l d p c 码，随着码 率的降低或者是码长的增长，误码率在1 0 刁时，性能增加l d b 到1 5 d b 。 2 3 多元l d p c 码编码基本原理 2 3 1 基于高斯消去的直接编码 为了便于说明，我们假设校验矩阵h 的大小为小