（微电子学与固体电子学专业论文）数字视频广播系统中的可重构ldpc译码器研究.pdf

摘要 本文分析了基于置信度传播的软判决迭代算法及其若干种简化算法，并主要 针对带校诈因子的最小和软判决迭代算法的迭代步骤进行调整和简化，提出了一 种改进的软判决迭代译码算法。在该算法中，通过对迭代步骤的调整，消除了相 邻迭代过程中冗余的变量节点信息，减小了存储量需求；采用了一种高效率的压 缩策略对迭代产生的校验节点信息进行压缩，更进一步缩小了中间数据的存储 量；对算法中比较复杂的运算过程采用合理的近似，以减小算法的复杂度。实际 的性能测试表明，该算法简化后所引起的性能损失均在可接受的范围之内，即以 有限的代价实现了硬件复杂度的大幅减低。 基于上述的简化算法，本文提出了一种可重构准循环l d p c 码译码器硬件结 构。该结构利用了准循环l d p c 码的结构特点和简化算法的简洁特性，结构十分 的规整和高效；针对准循环l d p c 码矩阵的循环特性，采用了对数桶形移位器来 进行数据的交换，解决了l d p c 码译码器中连线过于复杂的问题。同时，该结构 借用了s i m d 处理器的架构，通过对准循环l d p c 码的矩阵规律进行归纳总结，提 取出矩阵的基本特性，并结合本文提出的算法，采用了微指令来表示某个准循环 l d p c 码的矩阵，使得译码过程可以用若干条简单的微指令组合成的程序段来控 制，让l d p c 码的结构独立于准循环l d p c 码的码率、码的规则性甚至整个校验 矩阵，从而实现了解码器的硬件可重构甚至于软件上的可重构。 本文针对中国数字电视地面传输国家标准( d t m b ) 和第二代欧洲数字视频 广播卫星传输标准( d s 2 ) ，实现了一个可重构准循环l d p c 码译码器，能够 支持两种数字视频广播标准的l d p c 码。综合结果表明，该译码器面积只比 d v b s 2 系统专用的l d p c 码译码器增加了不：至l j l ，- 其译码性能、吞吐率方面等 性能指标都达到了两种数字视频广播标准的要求，非常适用于多模数字视频广播 接收系统。 关键词：准循环l d p c 码最小和v l s i数字电视d v b s 2 中图分类号：t n 4 3 2 ；t n 9 1 3 8 ；t n 4 9 2 a bs t r a c t b ya n a l i z i n ga n dr e a r r a n g i n gd e c o d i n gs t e po fs o f t - d e c i s i o ni t e r a t i n gd e c o d i n g a l g o r i t h mb a s e do nb e l i e f e p r o p a g a t i o n ，t h i sp a p e rp r o p o s e d am o d i f i e di t e r a t i o n d e c o d i n ga l g o r i t h m i n t h i sm o d i f i e da l g o r i t h m ，t w ok i n d so fm e s s a g e sw e r e c o m p r e s s e dt os a v em e m o r yc a p a c i t a n c e ；s o m ec o m p l i c a t e df u n c t i o n sw e r es i m p l i f i e d t om a k ei m p l e m e n t a t i o ne a s y t h ef p g at e s tp r o v e st h a tt h i sm o d i f i e da l g o r i t h m s p e r f o r m a n c el o s e sa r ea c c e p t a b l e b a s e do nt h i sm o d i f i e da l g o r i t h m ，ar e c o n f i g u r a b l eq c - l d p cc o d e sd e c o d e r a r c h i t e c t u r ew a sp r o p o a s e d al o g - b a r r a ls h i f t e rw a si n t r o d u c e dt op a s s i n gm e s s a g e s t om a k ei n t e r c o n n e c t i o ns i m p l e ；b yi n t r o d u c i n gt h es i m da r c h i t e c t u r ea n dt h ei d e ao f m i c r o i n s t r u c t i o n ，d e c o d i n gp r o c e d u r ew a sa b s t r a c t e da sas e to fs o m eu s e r - d e f i n e d i n s t r u c t i o n s ，a n dt h ec o d er a t ea n dr e g u l a r i t yo fl d p cc o d e sc o u l db er e c o n f i g u r e d a n y t i m e t h i sp a p e rp r o p o s e da2 - m o d er e c o n f i g u r a b l eq c l d p cc o d e sd e c o d e rv l s i i m p l e m e m t a t i o nf o rd v b - s 2a n dd t m bs y s t e m s y n t h e s i z e dr e s u l t ss h o w st h a tt h i s d e c o d e rh a sag o o db a l a n c eb e t w e e nt h ed e c o d i n gp e r f o r m a n c ea n di t sh a r d w a r ec o s t s ， a n di sv e r ys u i t a b l ef o rm u l t i m o d ed i g i t a lv i d e ob r o a d c a s t i n gr e c e i v e rs y s t e m s k e yw o r d s ：q c l d p c m i n - s u mv l s i d i g i t a lt vd v b - s 2 c l cn u m b e r ：t n 4 3 2 ：t n 9 1 3 8 ；t n 4 9 2 a d c a s l c a t s c a w g n 心p b e r b f c n r d a c d s p d t m b d v b d v b c d v b s d v b s 2 d v b t d v b 亿 e t s i f e c f i f o f p g a h d t v i f i s d b t l d p c l 吣呵 l u t m l d m p e g m a p n t s c p s k q c - l d p c q a m q o s q p s k r a r a m r f r o m 主要英文缩略词表 a n a l o g - t o - d i g i t a lc o n v e r t e r a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t s a d v a n c e dt e l e v i s i o ns y s t e m sc o m m i t t e e a d d i t m s g v ew h i t eg a u s s i a nn o i s e ap o s t e r i o r ip r o b a b i l i t y b i te r r o rr a t e b i tf l i p p i n g c a r r i e r t o n o i s er a t i o n d i 西t 2 l l - t o - a n a l o gc o n v e r t e r d i g i t a ls i g n a lp r o c e s s i n g d i g i t a lt e r r e s t r i a lm u l t i m e d i ab r o a d c a s t i n g d i 西t a lv i d e ob r o a d c a s t i n g d 诤t a lv i d e ob r o a d c a s t i n g c a b l e d i g i t a lv i d e ob r o a d c a s t i n g s a t e l l i t e d i g i t a lv i d e ob r o a d c a s t i n g - s a t e l l i t e ，s e c o n dg e n e r a t i o n d i 百t a lv i d e ob r o a d c a s t i n g - t e r r e s t r i a l d i g i t a lv i d e ob r o a d c a s t i n g - t e r r e s t r i a l ，s e c o n dg e n e r a t i o n e u r o p e a nt e l e c o m m u n i c a t i o n ss t a n d a r d si n s t i t u t e f o r w a r de r r o rc o r r e c t f i r s t - i n ，f i r s t - o u ts h i f tr e g i s t e r f i e l dp r o g r a m m a b l eg a t ea r r a y h i g l ld e f i n i t i o nt e l e v i s i o n i n t e r m e d i a t ef r e q u e n c y i n t e g r a t e ds e r v i c ed i g i t a lb r o a d c a s t i n gf o rt e r r e s t r i a l l o wd e n s i t yp a r i t y c h e c k l o c a la r e an e t w o r k l o o k u pt a b l e m a x i m u ml i k e l i h o o dd e c o d i n g m o v i n gp i c t u r ee x p e r t sg r o u p m a x i m u ma p o s t e r i o f ip r o b a b i l i t y n a t i o n a lt e l e v i s i o ns y s t e m sc o m m i t t e e p h a s es h i f tk e y i n gm o d u l a t i o n q u a s i c y c l i cl o wd e n s i t yp a r i t y c h e c k q u a d r a t i ca m p l i t u d em o d u l m i o n q u a l i t yo fs e r v i c e q u a d r a t i cp h a s e - s h i f tk e y i n g r e p e a ta c c u m u l a t i o n r a n d o ma c c e s sm e m o r y r a d i of r e q u e n c y r e a do n l ym e m o r y r s r t l s i m d s n r t d s o f d m t m m b t d m p u w b v l s i w l a n w b f r e e d s o l o m o n r e g i s t e rt r a n s f e rl e v e l s i n g l ei n s t r u c t i o nm u l t i d a t a s i g n a lt on o i s er a t i o t i m e d o m a i ns y n c h r o n o u so f d m t e r r e s t r i a lm o b i l em u l t i m e d i ab r o a d c a s t i n g t u r b o l i k ed e c o d i n gm e s s a g ep a s s i n g u l t r aw i d eb a n d v e r yl a r g es c a l ei n t e g r a t e dc i r c u i t w i r e l e s sl o c a la r e an e t w o r k w e j g h t e db i tf l i p p i n g 图表索引 l 訇lt a n n e r 图6 图2 不同码长l d p c 码的最小环长分布7 图3 f ( x ) 函数曲线2 0 图4 示例矩阵以及校验式2 3 图5q c l d p c 码的校验矩阵示意图2 6 图6q c l d p c 码译码器结构图2 7 图7r c v 恢复操作示意图2 9 图8 子矩阵示意图3 0 图9 实现数据循环移位的数据交换网络3 l 图1 0 校验矩阵的扫描过程示意图3 1 图1 1 增加了使能信号的数据通路3 5 图1 2 循环数为k 的数据交换网络示意图3 5 图1 3 循环数为p 的移位示意图3 5 图1 4 非循环移位示意图3 6 图1 5 可重构循环移位器功能示意图3 7 图1 6 可重构的循环移位器结构示意图3 7 图1 7 增加了数据通路使能和改进的数据交换网络的l d p c 译码器结构3 7 图1 8 数据通路结构图，包括缓存一次行扫描符号的存储器。3 9 图1 9 低功耗设计4 1 图2 0d v b s 2 中u ) p c 矩阵示意图4 4 图2 1 h s 示意图一4 4 ， 图2 2h s 分解为若干个e j 矩阵示意图4 5 图2 3 子矩阵示意图4 6 图2 4 双模l d p c 解码器顶层原理图4 7 图2 5sm e m im e m 模块数据存放规律4 9 图2 6rm e m 模块数据存放规律5 0 图2 7 微指令存储器分区示意图5 1 图2 8 对数桶型移位器结构图5 3 图2 9f p g a 验证平台中模拟前端电路板5 4 图3 0d v b s 2 接收机的f p g a 验证环境5 4 图3 1d t m b 系统f p g a 测试方案原理图一5 6 图3 2f p g a 测试系统图5 6 表格1 每个变量节点对应的不正确的校验节点的个数1 2 表格2 两类算法复杂度的比较一2 3 表格3 微指令说明3 3 表格4d v b s 2 系统中的f e c 模块码率4 5 表格5d t m b 系统中的f e c 码参数4 7 表格6d v b s 2 系统中的l d p c 码译码器指令表5 1 表格7d v b s 2 系统性能仿真结果5 5 表格8 各种模式在高斯白噪声信道下的载噪比门限5 7 表格9d t m b 系统存储器使用对比表5 8 表格1 0l d p c 译码器的实现结果比较5 9 第一章0 l 毒 第一章引言 1 1 数字视频广播和差错控制 现代数字通信在v l s i 技术飞速发展的推动下，正在朝着高速、宽带以及可 移动的方向发展，如高清晰数字视频广播、3 g 甚至4 g 通讯、无线局域网和城域 网、超宽带无线通信u w b 、大容量高速存储系统等等。其中数字视频广播以其 覆盖面广、数据率大、与日常生活密切相关的特点，在过去的十年里获得了巨大 的发展，欧洲、美国、日本、韩国以及中国等都相继开展了数字视频广播的研究 以及相关标准的制定，形成了一条逐渐完整的产业链，并j 下在积极推动模拟视频 广播向全数字转换，促使数字视频广播消费市场的完善。 数字视频广播根据其传输方式可以大致分为卫星传输方式、有线传输方式、 地面无线传输方式三大类。这三类标准各有优缺点：有线传输方式信号质量好， 但是只限于固定接收，并且需要铺设电缆，不适用于城市移动接收和农村偏远地 区使用；地面方式则能够在移动和郊区不便铺设电缆设备的条件下使用，但是它 的覆盖范围比较小，通常采用组建多频( 或单频) 网的形式来扩展覆盖范围，对 于非常偏远的地方如边界和地形复杂的山区也不适用：卫星电视具有接收稳定、 覆盖面广等优点，但是需要同步卫星等巨大的前期投入。因此，各个国家一般都 采用三种方式来进行互补，以便节省成本和扩大覆盖范围。如中国就采用了卫星 进行中继后再采用有线或地面无线的方式送给城镇固定或移动接收，对于偏远的 农村则开展了“村村通”工程，进行卫星点对点传送节目。 在目前，国际上通行的卫星数字电视和有线数字电视标准是上世纪末欧洲电 信联盟制定的d v b s 和d v b c 标准；地面传输数字电视方面，各个组织和国家 根据自己的特点制定了若干个标准，主要有欧洲的d v b t 、d v b h ( 手持设备 标准本质上也是属于此类) ，美国的a t s c ，日本的i s d b t 以及中国目前颁布的 d t m b 、t m m b ( 手持设备) 等标准。从最早的d v b s 和d v b c 标准应用开始， 经过了大约十年的发展后，数字电视的需求不断被扩大，所传送的节目数量和质 量不断提高，导致原有的数字电视标准无法满足现实需要。为此，欧洲电信联盟 推出了第二代卫星数字电视标准d v b s 2 ，并且第二代地面传输标准d v b t 2 也在 加紧制定中。这些新的标准在数据带宽和可靠性上都有了不少的提高。 然而在数字通信系统中，可靠性和带宽( 或者发送数据的速度) 往往是一对 矛盾。若要求快速，在发送方的功率提高不大的前提下，必然使得每个数据码元 所占的时间缩短、波形变窄、能量减小，从而在受到干扰后产生错误的可能性增 加，传送消息的可靠性减低。若要求可靠，传送消息的速率就必须变慢。为了解 决这对矛盾，采用具有逼近香农极限的低密度奇偶校验码( l o wd e n s i t y 第一章，j i 高 p a r i t y c h e c kc o d e s 。l d p cc o d e s ) 是其中一个非常高效的解决办法。在d v b s 2 和d t m b 系统中就采用了l d p c 码，并且在d v b t 2 系统中也拟采用l d p c 码。 1 2 l d p c 译码器面临的技术挑战 l d p c 码具有逼近香农极限的非常优异的译码性能，同时它可以全并行译码， 能够提供非常高的译码速度。但是它的译码性能需要在码长较长、校验矩阵中的 非零元素随机性大的前提下才能够显示出来，并且需要使用迭代的软判决译码算 法，否则无法达到其优异的译码性能。 当l d p c 码的码长比较长时，迭代过程产生的中间数据非常大，并且存在大 量的非线性函数和复杂度大的乘法等运算操作，即使有若干学者提出了简化的算 法，基于迭代的译码过程本质没有改变，在校验矩阵随机性大的前提下，译码器 结构依然非常松散，不同码率的切换全部依靠节点计算单元之间的硬连线的选通 来实现，因此译码器的内部连线复杂度非常大。对于目前使用比较多的准循环 l d p c 码而言( 如d v b s 2 和d t m b 系统中的l d p c 码) ，不但码长达至l j l o s - 1 0 6 级 别，而且需要支持多达1 1 种码率( d v b s 2 ) 。在这种情况下，中间数据的存储量 达至u 2 3 m b 3 ，并且为了保证数据的存储带宽，这类存储器全部采用片上s r a m 实现，不仅导致译码器的硬件实现面积巨大( 接近4 0 m m 2 ) ，并且功耗也达到接 近瓦的数量级【1 】【2 】【3 】【4 】【5 】。因此，l d p c 码译码器的设计需要解决的是算法复 杂度的进一步降低、译码器结构规整化、能够灵活的支持多码率等问题。 此外，数字电视接收系统等消费类产品正朝着小型化、一体化的方向发展， 未来的电视接收系统需要能够接收不同传输标准的电视节目，这必然会导致接收 机系统的朝向多模多标准兼容的方向发展，因此提高接收机对不同标准的兼容性 将是未来的一个研究热点，而目前在采用l d p c 码的接收系统中，l d p c 码译码 器占据了一个非常大的比重，因此，设计一个具有好的译码性能、低复杂度和可 重构的l d p c 码译码器是一个非常重要和有意义的课题。 1 3 论文的主要工作 本文在分析基于置信度传播的软判决迭代算法及其若干种简化算法的基础 上，主要针对带校正因子的最小和软判决迭代算法的迭代步骤进行了调整和简 化，提出了一种改进的软判决迭代译码算法，并基于该算法提出了一中可重构的 q c l d p c 码译码器结构。 本文通过对迭代步骤的调整，消除了相邻迭代过程中冗余的变量节点信息， 减小了存储量需求；采用了一种高效率的压缩策略对迭代产生的校验节点信息进 行压缩，更进一步缩小了中间数据的存储量；对算法中比较复杂的运算过程采用 2 第一章，j l 。i 合理的近似，以减小算法的复杂度；同时，对算法中会严重影响译码性能的简化 步骤进行一定的补偿，以尽可能的减少因算法简化所带来的性能损失。 基于上述的简化算法，本文提出了一种可重构准循环l d p c 码译码器硬件结 构。针对准循环l d p c 码矩阵的循环特性，采用了对数桶形移位器来进行数据的 交换，解决了u ) p c 码译码器中连线过于复杂的问题；同时，该结构借用了s i m d 处理器的架构，通过对准循环l d p c 码的矩阵规律进行归纳总结，提取出矩阵的 基本特性，并结合本文提出的算法，采用了微指令来表示某个准循环l d p c 码的 矩阵，使得译码过程可以用若干条简单的微指令组合成的程序段来控制，让l d p c 码的结构独立于准循环l d p c 码的码率、码的规则性甚至整个校验矩阵，从而实 现了解码器的硬件可重构甚至于软件上的可重构。 本文针对中国数字电视地面传输国家标准( d t m b ) 和第二代欧洲数字视频 广播卫星传输标准( d v b s 2 ) ，实现了一个可重构准循环l d p c 码译码器，能够 支持两种数字视频广播标准的l d p c 码。综合结果表明，该译码器面积只比 d v b s 2 系统专用的l d p c 码译码器增加了不到1 ，其译码性能、吞吐率方面等 性能指标都达到了两种数字视频广播标准的要求，非常适用于多模数字视频广播 接收系统。 1 4 论文结构安排 第一章介绍了选题的意义和主要工作； 第二章介绍l d p c 码的基本概念，为第三章的译码算法介绍和推导做铺垫； 第三章中给出了若干种译码算法，主要介绍了对数域上基于置信度传播的软 判决迭代算法及其简化算法，提出了改进的最小和算法； 第四章主要基于所提出的算法提出了一种可重构q c l d p c 译码器结构： 第五章实现了一个可以支持两种数字视频广播系统的译码器，并给出了其性 能比较和v l s i 实现结果。 最后，对本文工作的一个总结以及后续工作的展望。 3 第- 二帝l d p c 码简介 第二章l d p c 码简介 低密度奇偶校验( l o wd e n s i t yp a r i t y c h e c k ，l d p c ) 码是一类具有逼近香农 极限的编码。l d p c 码g a l l a g e r 刁：1 9 6 2 年在其博士论文中首次提出f 6 】。然而， g a l l a g e r 的重大发现被编码界研究人员忽视了大约2 0 年，直到1 9 8 1 年t a n n e r 在他 的工作中从图论的观点出发，提供了一种对l d p c 码的全新解释。t a n n e r 的工作 又被编码理论家忽视了1 4 年，直到9 0 年代末期一些编码研究人员开始研究图论编 码和迭代译码。他们的研究工作导致了对g a l l a g e rl d p c 码的重新发现和进一步 推广。基于置信度传播迭代译码的长u ) p c 码已经被证明能够获得只距离香农极 限零点几个分贝的误码性能【7 9 1 。在很多要求高可靠性的通信和数字存储系统中 的差错控制方面，这个发现使得l d p c 码成为t u r b o 码的有力竞争者。相对于t u r b o 码，l d p c 码具有以下优点：1 ) 不需要深度交织以获得好的误码性能；2 ) 据具 有更好的分组误码性能；3 ) 误码平台处的误码率大大降低；4 ) 译码不需要基于 网格，译码并行度非常高，更适合需要高速吞吐率要求的系统。 尽管g a l l a g e r 提出了用于差错控制的l d p c 码，但是他没有代数的系统的提 供用于构造好的l d p c 码的特定方法，就像构造b c h 码、r s 码和有限几何码时 的那样；尽管如此，他提出了用于构造一类伪随机l d p c 码的通用构造方法。已 经发现的好的l d p c 码，特别是长码，大部分是计算机生成的。由于缺乏结构特 点，他们的编码过程非常复杂。k o u ，l i n 和f o r s s o r i e r 基于有限集合理论首次提 出了一种代数的、系统的l d p c 码构造方法 1 0 1 1 1 。有限集合l d p c 码这一大类 l d p c 码具有相对好的最小距离，并且他们的t a n n e r 图没有短环。这一类码可以 通过从低到高复杂度的各种方法译码，获得从可接受的到极好的误码性能。此外， 这些编码是循环或准循环的。因此，他们的编码过程简单并且可以通过线性移位 寄存器实现。一些长的有限几何l d p c 码的误码性能距离香农极限只有零点几个 分贝。 2 1l d p c 和t a n n e r 图 l d p c 码本质上是一种线性分组码。分组码编码器把信息序列分成每组k 个 比特( 符号) 的信息分组，一个信息分组可以用二进制的k 为向量 u = o ，u 1 ，u 2 ，u k - 1 ) 表示，称为一个消息( m e s s a g e ) 。在分组编码中符号；用来 表示k 比特信息而不是整个信息序列，因此每个信息分组可能有垆个不同的消 息。编码器把每个消息独立的变换成n 维的向量v 暑婶o ，h ，y 2 ，k 一1 ) ，即 码字( w o r d ) ，此处符号v 表示一个1 1 符号组而不是整个编码序列。因此，对应 于2 。个不同的消息，编码器的输出端就有2 k 个可能不同的分组码字。这2 0 个长 第二章l d p c 码简介 度为n 的码字的集合称为( n ，k ) 分组码。比值r = k n 称为码率( c o d er a t e ) ， 通俗一点说就是系统每发送一个符号所含有的进入编码器的有效信息比特数。由 于n 符号输出码字只取决于对应的k 比特输入消息，因此每个消息是独立编码的， 编码器也是无记忆的，可以用组合逻辑简单的实现。这种从k 维线性空间到n 维线性空i 白j 的映射可以通过一个矩阵g 来表示，即分组码的生成矩阵。对于某 一个固定的g ，完全等效的存在一个奇偶校验矩阵h ，即码字；要满足h 矩阵所 规定的所有校验式。换句话说，所有的码字序列；构成了矩阵h 的零空间，即 v 一0 。l d p c 码的奇偶校验矩阵h 是一个稀疏矩阵，现对于其行和列的长度 ( n ，m ) ，校验矩阵的每行和每列中的非零元素的个数( 即通常所说的行重( r o w w e i g h t ) 和列重( c o l u m ew e i g h t ) 非常小，l d p c 码也因此而得名。 对于任何一种线性分组码，t a n n e r 在【1 2 】中提出了一种简单的表示形式：编 码二分图( 或称之为t a n n e r 图) 。l d p c 码作为分组码，同样可以用二分图来表 示。二分图由两类节点组成：变量节点( v a r i a b l en o d e ) 和校验节点( c h e c kn o d e ) ， 分别对应于校验矩阵h 中的n 列和m 行。同一个集合内部的节点没有连线，只 有属于不同集合的两点之间可能会有连下，每一条连线对应于校验矩阵中的“1 ”。 为了方便，此处借用g a l l a g e r 对l d p c 码的表示方法：将码长为n ，行重、列重 分别为p 和r 的l d p c 码称为( ，y ，p ) l d p c 码。式1 是某个( 8 ，2 ，4 ) l d p c 码的校验矩阵和相应的校验方程，根据校验矩阵本文可以画出它的二分图( 图 1 ) 。图中变量节点结合( v l ，v 2 v 8 ) 和校验节点集合( c l ，c 2 ，c 4 ) 内部不存在相 连的边，但是两类节点之间存在连线。变量节点和校验节点之间存在连线意味着 该变量参与了此校验式，也就是校验矩阵某一行中1 的位置。本文将每个节 点上的连线数目称为该节点的次数( d e g r e e ) 。图1 中变量节点的次数( d v ) 为2 ， 校验节点的次数( d c ) 为4 。， h = 111o 0 01 10 o o110 0lol1o1 0 0ll010 v 10 9 v 20 9 v 30 v 7 ；0 h0 9 v s0 9 v 60 9 v s = 0 v 2o v 40 9 v 50 9 v 7 = 0 v 30 9 v 40 9 v 60 9 v 8 = 0 5 1 第一：章l d p c 玛简介 图1t a n n e r 图 图1 的二分图结构中，四条粗线构成了一个有向的闭合环路，由v 1 起始，经 过c l = v 3 = c 2 ，最后返回v l 。在一个l d p c 码的二分图中，每个节点都会存在许 多这样的闭合环路，其中长度最小的一个称为该节点的最小环长( s h o r t e s tc y c l c ) 。 二分图中所有节点的最小环长中，长度最小的称为二分图的最小圈长( g i r t h ) ， 上列的二分图中，g i n h 与变量节点l 的最小环长相等，都是4 。 l d p c 码二分图结构中g i r t h 的大小对l d p c 码的译码性能有很大影响。t a n n e r 认为g i n h 的长将直接关系到l d p c 码码字的最小码距，并给出了最小码距的下 界与西n h 的关系式： d 乏d ( d 1 - 了1 ) j ( y 沅- 1 二) t 百t - _ 2 y l - 1 + 争u 一1 ) 0 - 1 ) 1 t # - 2 ) 4 1 , g 2 为偶数；21 似一1 ) ( ，一1 ) 一7 ，、 l 冈舣； d 芝d ( d 历- = 1 ) 葫( r 7 - 1 j ) 】f 汀e q - 1 ，g ，2 为奇数； ( d 一1 ) ( ) ，一1 ) 一1 z 州司隽xo 其中，d 为l d p c 码的最小码距，g 为l d p c 码的g i r t h ，y 为变量节点的次 数，d 为二分图中子码( s u b c o d c ) 的最小码距。从公式中可以看出，西n h 的长 度越大，l d p c 码的最小码距越大，译码性能也就更好。仿真结果表明，如果二 分图中存在长度为4 的西r t h ，l d p c 码的误码率性能将会很差，所以本文在构造 l d p c 码的校验矩阵时，要尽量避免二分图中出现g i r t h 为4 的情况。 l d p c 码的译码算法主要是迭代译码算法，因为某些节点存在闭合环路，当 迭代次数较多时，到达这些节点的信息不再满足统计独立的特性，从而使得译码 性能与最大似然算法有一定的差距。因此，本文在设计l d p c 码时，在保证g i r t h 大于4 的情况下，各个节点的最小环长越大越好。令人惊奇的是，即使二分图中 存在不少这样的闭合环路，但只要g i r t h 大于4 ，l d p c 码应用迭代译码算法依然 可以取得较好的误码率性能。g a l l a g c r 6 认为造成这种现象的原因是：随着迭代 次数的增加，独立性产生的影响越来越小，而且趋向于相互抵消，当迭代次数到 达一定的次数，闭合环路影响译码结果的可能性很小。 6 第- 二帝l d p c 码简介 图2 是不同码长l d p c 码的最小环长分布，从图中可以看出，随着码长的增 加，拥有较短长度闭合坏路的节点越柬越少。例如，码长为1 1 5 2 的l d p c 码， 最小环长只有两种：6 和8 ，而长度为6 的节点占了3 9 。当码长增加到9 2 1 6 ， 二分图中已经没有长度为6 的闭合环路，最小环长为1 0 的节点有5 0 。最小环 长的分布状况可以作为衡量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 算法下的译码性能也就完全等效于最大似然译码。 囊羹 陵嚣惑谴 。e j黧 囊 鋈鬯一 菱三u 豇一 图2 不同码长l d p c 码的最小环长分布 2 2规则与非规则l d p c 码 在l d p c 码的校验矩阵中，如果行列重量固定为( p ，y ) ，即每个校验节点 有p 个变量节点参与校验，每个变量节点参与y 个校验节点，本文称之为规则 l d p c 码。g a l l a g e r 最初提出的g a l l a g e r 码就具有这种性质。从编码二分图的角 度来看，这种l d p c 码的变量节点次数全部为y ，而校验节点的次数都为p 。本 文还可以适当放宽上述规则l d p c 码的条件，行列重量的均值可以不是一个整 数，但行列重量尽量服从均匀分布。另外为了保证l d p c 码的二分图上不存在长 度为4 的圈，通常要求行与行以及列与列之间的交叠部分重量不超过1 ，所谓交 叠部分即任意两列或两行的相同部分。规则l d p c 码校验矩阵h 的特征概括如 下： 7 第二常l d p c 鸦简介 1 、h 的每行行重固定为p ，每列列重固定为y 。 2 、任意两行，两列之间交叠部分重量最多为1 。 3 、行重p 和列重y 相对于h 的行数m 、列数n 很小，h 是个稀疏矩阵。 4 、规则l d p c 码的最小码率r 可以通过下式计算： ，= ( n m ) n = 1 一m n = 1 一) ，p3 在规则l d p c 码的校验矩阵中，行重和列重的均值保持不变，所以校验矩阵 中1 的个数随着码长的增加而线性增长，整个校验矩阵的元素个数则成平方增 长。当码长达到一定长度时，校验矩阵h 是非常稀疏的低密度矩阵。对于规则 的l d p c 码，m a c k a y 在 1 3 1 中给出了以下两个结论： 1 ：给定列重大于3 的l d p c 码，存在某个小于信道传输容量且大于零的速率r ， 当码长足够长时，可以实现以小于r 且不为零的速率无差错的传输。也就是说任 意给定一个不为零的传输速率r ，存在一个小于相应香农限的噪声门限，当信道 噪声低于该门限且码长足够长的时候，可以实现以r 速率无差错的传输。 2 ：c 码的校验矩阵h 的列重y 不固定，而是根据信道特性和传输速率来确定 时，则一定可以找到一个最佳码，实现在任意小于信道传输容量的速率下无差错 的传输。 对于l d p c 码的每个变量节点来说，当它参与的校验式越多，即次数y 越大， 则它可以从更多的校验节点获取信息，也就可以更加准确的判断出它的正确值。 对于h 的每个校验节点来说，当它涉及的变量节点越少即次数p 越小，则它可 以更准确的估计相关变量节点的状态。这种情况对于规则l d p c 码来说是一对不 可克服的矛盾，于是l u b y ，m i t z e n m a c h e r 等人就引入了非规则l d p c 码的概念。 在非规则l d p c 码的编码二分图中，两个集合内部的节点次数不再保持相同， 即每个变量节点参与的校验式数目或每个校验式中含有的变量节点数目不再保 持均匀，而是有意设置部分突出的变量节点和校验节点。在译码过程中，那些参 与较多校验式的变量节点迅速得到它们的正确译码信息，这样它们就可以给相邻 的校验节点更加有效的概率信息，而这些校验节点又可以给与它们相邻的次数少 的变量节点更多的信息。整个译码的过程呈现出一种波状效应，次数越高的变量 节点首先获得j 下确信息，然后是次数较低的节点，然后依次往下，直到次数最低 的变量节点。j 下是这种波状效应，使得非规则l d p c 码获得比规则l d p c 更好 的译码性能。理论上的极限性能仅仅比香农限高0 0 0 4 5 d b 的非规则码次数分布 对已经找到f 1 4 1 。 为了描述非规则的l d p c 码，本文需要定义相应的次数分布，节点的次数分布 和边的次数分布是两种常用的次数分布。节点的次数分布n ( 辟) 定义为次数为 i 的变量( 校验) 节点在所有变量( 校验) 节点中所 f 的比例。边的次数分布( h ) 8 第二帝l d p c 码简介 定义为与次数为i 的变量( 校验) 节点相连的边数占总边数的比例。若( d v m 钔, , d 。m a x ) 为变量节点和校验节点中的最大次数，则有 一1 4 根据l d p c 码的编码二分图，每条边两端总对应一个变量节点和校验节点，所 以有5 式。 万；m 万，石= h 万= d 肛 5 对应的非规则l d p c 码的最小码率 ，= 1 一d ，d c 6 扎( n ) 和览( 黟) 存在如下的换算关系 f 以。石只i 肛；石目7 2 3二进制与多进制域上的l d p c 码 前面对l d p c 码的定义都是在二元域基础上的，m a c k a y 在【1 5 1 中对上述二元 域的l d p c 码又进行了推广。如果定义中的域不限于二元域就可以得到多元域 g f ( q ) 上的l d p c 码。多元域上的l d p c 码具有较二进制l d p c 码更好的性能， 而且实践表明在越大的域上构造的l d p c 码，译码性能就越好 1 6 】，比如在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 = 2 p ) 上构造的l d p c 码所对应的校验矩阵分别是 h 2 和h q 。h 2 中的元素是0 或1 ，而h q 是由元素0 ，1 ，q 1 构成，h q 中的每个元 素都是h 。中p 个元素的合成。设域g f ( q = 2 v ) 上的一个值a 与一个1x p 的二进 制向量相关联，那么把这个向量代入h q 中，就可以得到h 。的二进制表示。对于 二进制l d p c 码来说，如果它的校验矩阵h 的列重量足够大，那么它可以任意 地接近香农限，但是如果增加列重量会使得二分图中节点之间短圈的数目急剧增 加从而使b p 算法的性能下降。而在g f ( q ) 域上构造的l d p c 可以解决这个矛盾， 它的检验矩阵q h 可以增加与之对应的二进制校验矩阵2 h 中列的平均重量，且 它的：二分图结构并没有改变，不会造成节点之间短圈数目的增加，从而使得译码 性能得到显著的提高。这种多元域上的编码构造会增加译码复杂度，但是相对二f 9 肛 一v 智 d = h x 一孓智 d 第一章l d p c 码简介 译码性能的提高来说