（信息与通信工程专业论文）低复杂度的ldpc码快速译码算法研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 l d p c 码( 低密度校验码) 是一类可以用非常稀疏的奇偶校验矩阵定义的线性 分组纠错码，具有逼近香农限的性能。通常地，评估一种l d p + 6 吗c 码译码算法 的指标有三个：译码速度、计算复杂度、译码性能。那么，如何从这三个方面着 手，对当前常用的l d p c 码译码算法- b p 算法进行改进，以得到一种低复杂度、 性能优异的快速l d p c 码译码算法是一个非常有意义的课题。 本文的工作可概括为以下五个方面： 1 、阐述分析了l d p c 码中环对译码性能的影响，在用一个简单的范例说明了 消息传递的本质之后，详细描述了基于常用的几种不同消息传递机制的l l r b p 译码算法，利用密度进化分析方法对它们的收敛性进行了分析比较。 2 、鉴于洪水译码算法实现复杂度高、串行译码算法译码速度慢的缺点，本文 深入研究了一种介于全并行消息传递与串行消息传递之间的混合消息传递机制 分组串行消息传递机制，通过对校验节点分组，在不同分组之间串行地进行 消息传递和更新，同一分组内部并行地进行消息传递和更新，从而在串行译码算 法基础上提高了译码的速度，在洪水译码算法的基础上降低了实现复杂度，在译 码速度和复杂度之间取得了很好的折衷。 3 、研究了q c l d p c 码的码结构，通过研究发现其独特的结构特点使其非常 适合采用分组串行译码算法进行译码，从而提出了一种快速的q c - l d p c 码译码算 法，它能在串行译码算法的基础上成倍地提高译码速度。 4 、分析了变量节点e x l l r 值发生振荡的原因，并提出了两种基于变量节点 e x l l r 值振荡的改进的b p 译码算法，i o bb pi 和i o bb pi i ，这两种算法都是通 过修正变量节点发生振荡的e x l l r 值，来降低振荡带来的性能恶化程度。在基本 不增加译码复杂度的情况下，能改善传统的b p 译码算法的性能。 5 、借鉴强迫收敛的思想，对i o bb pi i 算法进行改进，使得改进算法能够在 b p 算法基础上提高性能的同时，进一步降低译码复杂度，很好地兼顾了译码性能 和计算复杂度。针对在采用b p 译码算法译码收敛到错误码字时各变量节点判决消 息绝对值均值趋于平稳的现象，提出了一种新的迭代停止判决准则，将其应用到 i o bb p i i 算法，从另外一个角度达到了提高译码算法性能的同时降低译码复杂度 的目的。 主题词：l d p c 码环b p 译码算法消息传递机制q c l d p c 码外信 息振荡强迫收敛迭代停止判决准则 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t l o wd e n s i t yp a r i t yc h e c kc o d e sa r eac l a s so fl i n e a rb l o c ke r r o r - c o r r e c t i n gc o d e s t h a tc a i lb ed e f i n e db yt h ev e r ys p a r s ep a r i t y c h e c km a t r i x t h e i re r r o rp e r f o r m a n c e a p p r o a c hs h a n n o nl i m i t s t h e r e a r et h r e ei n d e x e st oa s s e s sad e c o d i n ga l g o r i t h m ， i n c l u d i n gt h ed e c o d i n gc o n v e r g e n c er a t e ，t h ec o m p u t a t i o nc o m p l e x i t ya n d t h ed e c o d i n g p e r f o r m a n c e h o wt of i n daf a s tl d p cc o d e sd e c o d i n gm e t h o dw i t i ll o wc o m p l e x i t y a n dg o o dp e r f o r m a n c et u r n st ob ev e r yi m p o r t a n ta n dm e a n i n g f u l t h i sw o r ki nt h i sp a p e rm a i n l yc o n t a i n st h ef o l l o w i n gf i v ea s p e c t s ： ( 1 ) t h ee f f e c t st od e c o d i n gp e r f o r m a n c eb r o u g h tb yt h ec y c l e si nt h el d p cc o d e s t a n n e rg - r a p h yw e r es t u d i e d a f t e ri l l u s t r a t i n gt h ee s s e n c eo fm e s s a g ep a s s i n g ，t h et h e s i s d e s c r i b e ss e v e r a ll l r b pd e c o d i n gm e t h o d sb a s e do nd i f f e r e n tm e s s a g ep a s s i n g s c h e d u l e 。t h e nt h ec o n v e n g e c er a t eo ft h ed i f f e r e n td e c o d i n gm e t h o d sw e r ec o m p a r e d t h r o u g hd e n s i t ye v o l u t i o na n a l y s et 0 0 1 ( 2 ) c o n s i d e r i n gt h ed r a w b a c k so ff l o o d i n ga n ds e r i a lm e s s a g ep a s s i n gs c h e d u l e s ，a n e ws c h e d u l en a m e dg r o u p i n gs e r i a lw e r ep r e s e n t e d f o rt h ea l g o r i t h m ，t h em e s s a g ew a s u p d a t e di nas e r i a ls e q u e n c eo fms u b s e t so fc h e c kn o d e s ( o rv a r i a b l en o d e s ) ，w h i l et h e c h e c kn o d e s ( o rv a r i a b l en o d e s ) i nt h es a m es u b s e tw e r eu p d a t e ds i m u l t a n e o u s l y i nt h i s w a y ，t h ed e c o d i n gs p e e dw o u l db ef a s t e rt h a nt h ec o m m o ns e r i a ld e c o d i n ga l g o r i t h m s e v e r a lt i m e s a n dt h ec o m p l e x i t yw a sl o w e rt h a nt h ef l o o d i n gd e c o d i n ga l g o r i t h m ( 3 ) b ys t u d y i n gt h es t r u c t u r eo fq u a s i - c y c l i cl d p cc o d e s ，w ef i n dt h a ta ne f f i c i e n t g r o u p i n gm e t h o ds u i t a b l ef o r t h eq u a s i - c y c l i cl d p cc o d e sb a s e do nt h ec i r c u l a n t a r c h i t e c t u r e h e n c e ，t h eg r o u p i n gs e r i a ld e c o d i n ga l g o r i t h mw a sf i t f o rq u a s i c y c l i c l d p cc o d e s ，w h o s es p e e dw a sa tl e a s tpt i m e st h a nt h a to ft h es e r i a lo n e ( pi st h e d i m e n s i o no ft h ec y c l i cp e r m u t a t i o nm a t r i xi nt h ep a r i t yc h e c km a t r i xo fq u a s i - c y c l i c l d p cc o d e s ) ( 4 ) w ee x p l a i n e dw h yt h em a g n i t u d e so fap o s t e r i o rl l r sa n de x - l l r so fs o m e b i t so s c i l l a t e de v e r yi t e r a t i o n s t w oi m p r o v e da l g o r i t h m sw e r ep r o p o s e d ，i o bb pia n d i o bb pi i ，w h i c hc o u l di m p r o v et h ed e c o d i n gp e r f o r m a n c ed e t e r i o r a t e db ye x l l r o s c i l l a t i o n f r o mt h ec o m p u t e rs i m u l a t i o n ，w ef o u n dt h a tf o rs h o r ta n dm i d d l el e n g t h l d p cc o d e s ，谢t i las i m p l em o d i f i c a t i o n ，o u rp r o p o s e da l g o r i t h m sc o u l dl o w e rt h ee r r o r f l o o r 丽t t ll o wc o m p l e x i t y ，s ot h e yc a l la c h i e v eb e t t e rb e ra n db l e rt h a nt h e c o n v e n t i o n a ll l r b pd e c o d i n ga l g o r i t h m ( 5 ) t w oi m p r o v e dd e c o d i n ga l g o r i t h m sw e r es e tf 0 r t ht ol o wt h ec o m p l e x i t yo f i o bb pi ia l g o r i t h mf r o mt w od i f f e r e n ta s p e c t s f i r s t l y ，w ed e c r e a s e dt h em e s s a g e s c o m p u t a t i o no fi o bb pi i 州mf o r c e dc o n v e r g e n c es c h e d u l ei ne a c hi t e r a t i o n s ，s ow e c o u l dr e d u c et h eo v e r a l ld e c o d i n gc o m p u t a t i o nt ol o w e rt h ed e d o d i n gc o m p l e x i t y s e c o n d l y ，an e w i t e r a t i o ns t o p p i n gd e t e m i n er u l ew a sp u tf o r w a r d w ec o u l dd e t e c tt h e 第i i 页 国防科学技术大学研究生院硕士学位论文 m e a l lo fa ut h ev a r i a b l e s a b s o l u t elu d y i n gm e s s a g ew h e t h e rb es t a b l eo rn o tt od e c i d e t os t o pt h ec u r r e n ti t e r a t i o no rt ol e ti tc o n t i n u e b yd o i n gs o ，w em i g h tr e d u c et h em e a n d e c o d i n gi t e r a t i o n st ol o w e rt h ea l g o r i t h m sc o m p l e x i t y t h et w oi m p r o v e dd e c o d i n g a l g o r i t h m sa l lb e t t e rp e r f o r m a n c ea n d l o w e rc o m p l e x i t yt h a nb pa l g o r i t h m k e yw o r d s ：l d p cc o d e sc y c l e b e l i e f p r o p a g a t i o na l g o r i t h m m e s s a g e p a s s i n gs c h e d u l eq u a s i c y c l i cl d p cc o d e s e x - l l ro s c i l l a t i o n f o r c e dc o n v e r g e n c ei t e r a t i o ns t o p p i n gd e t e r m i n a t i o nr u l e 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表2 1基于对数似然测度的洪水消息传递译码算法基本流程1 5 表2 2 基于校验节点的串行消息传递译码算法基本流程1 6 表2 3基于校验节点的分组串行码算法基本流程1 7 表3 1基于校验节点的分组串行码算法基本流程2 3 表3 2 基于校验节点分组的半串行译码算法流程3 0 表5 1收敛所需平均迭代次数和e x l l r 值平均更新次数4 5 表5 2 检测确u 是否平稳的具体流程4 9 第1 i i 页 国防科学技术大学研究生院硕士学位论文 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图3 1 图3 2 图3 3 图3 4 图4 1 图4 。2 图4 3 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 1 图5 1 2 图5 1 3 图5 1 4 图目录 ( 1 0 ，2 ，4 ) 规则l d p c 码的校验矩阵及t a n n e r 图表示9 二分图存在长度为4 的环1 1 二分图存在长度为6 的环11 校验矩阵存在长度为4 的环1 1 校验矩阵存在长度为6 的环1 l 采用消息传递计算士兵人数1 2 计算士兵人数过程中消息传递过程的图形表示1 3 t a n n e r 图上的译码消息流的迭代传递。1 4 检验节点分组方法示意图2 0 不同消息传递机制下的准循环l d p c 码译码算法性能仿真图2 4 几种算法收敛性比较仿真图2 4 洪水译码算法和半串行译码算法收敛性比较仿真图。3 1 变量节点的多环结构引起判决消息值振荡3 6 四种不同译码算法的误比特率3 9 四种不同译码算法的误帧率3 9 x 0 时，c , o ( x ) 函数特性曲线4 2 两种译码算法在a w g n 信道中的性能比较4 3 基于强迫收敛机制的i o bb pi i 算法译码算法性能仿真图4 5 成功译码时每次迭代后各变量节点判决消息绝对值均值分布图4 6 收敛至错误码时每次迭代后各变量节点判决消息绝对值均值分布图4 7 不收敛时每次迭代后各变量节点判决消息绝对值均值分布图4 7 码长为9 6 的( 6 ，3 ) 规则l d p c 码的性能仿真图5 0 码长为6 0 0 的非规则l d p c 码的性能仿真图5l 码长为4 0 0 0 的( 6 ，3 ) 规则l d p c 码的性能仿真图5 1 码长为9 6 的( 6 ，3 ) 规则l d p c 码译码平均迭代次数仿真图5 1 码长为6 0 0 、码率为1 2 的非规则l d p c 码平均迭代次数仿真图5 2 码长为4 0 0 0 的( 6 ，3 ) 规则l d p c 码平均迭代次数仿真图5 2 口取值不同时，( 4 0 0 0 ，6 ，3 ) 的l d p c 码的性能仿真图5 2 口取值不同时，( 4 0 0 0 ，6 ，3 ) 的l d p c 码平均迭代次数仿真图5 3 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 学位论文题卧一垡熏釜盘盟兰里2 堕! i 塑童叠圣缮这圣刍超 学位论文作者签名：三蝗4 ：翌垒日期：以盯姥，年f 月， 7 p 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阋和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 坠复玺庭! 三望芝! 歪鱼立塾婆丝薄盗缉! 童 学位论文作者擀：j 垂必进日期：文。文辂1 1 月，归 作者指导教师签名： 壹羞 日期：硝年r f 月乒日 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 引言 1 9 4 8 年，香农在一篇具有里程碑意义的论文l l j 中证明，只要信息传输速率低 于信道容量，通过适当的信息编码，可以在不损失信息传输速率或存储速率的条 件下，将有噪信道或存储介质引起的差错降至任意低的程度。这就是著名的信道 编码定理，它明确地指出了实现有效而可靠通信的必由之路和信道编码的方向， 奠定了现代通信的理论基础。 自从香农的著作发表以来，研究者们为了在噪声环境下控制差错而在设计有 效的逼近香农限的编译码系统方面做出了大量的努力。经过他们的不懈努力，各 种信道编码方案不断涌现。1 9 5 0 年代，人们在信道编码发展早期发现了汉明码【2 】、 格雷码【3 】和里德米勒码【4 1 【5 】等几类重要的线性分组码和卷积码 6 1 。1 9 6 0 年代出现了 诸如b c h 7 8 】和r s l 9 等多种好的分组码结构和构造级联码的思想f 嘲。1 9 6 2 年 g a l l a g e r 提出了接近香农限的低密度奇偶校验码( l o w d e n s i t yp a r i t yc h e c kc o d e s ， l d p cc o d e s ) 【1 1 1 ，但限于当时技术和认识水平，未能引起人们的重视。1 9 7 0 8 0 年代，卷积码软判决译码算法不断完善、级联码技术的成熟以及编码调制技术的 提出和发展，使编码系统性能向香农限更近了一步，但始终还是存在2 - 3 d b 的差 距。直到1 9 9 3 年t u r b o 码的出现【1 2 l 和1 9 9 6 年l d p c 码的重新发现【1 3 】，标志着现 代纠错编码技术的出现，人们再次看到了逼近香农限的可能性。 l d p c 码是目前人们发现的单发单收信道中纠错能力最好且没有误码平层的 一种码，相对于性能相近但具有明显错误平层的t u r b o 码，除了在编译码复杂度 以及成功译码所需迭代次数方面稍逊之外，l d p c 码具有一系列1 、曲o 码难以匹敌 的特性：l 、译码算法描述简单，对严格的理论分析具有可验证性，能够在硬件平 台上并行运算，吞吐量大，具有实现高速译码的潜力；2 、具有随机码的特性，在 与信源或信道级联时，不需要额外增加交织器，使得通信系统的复杂度和译码延 时比t u r b o 码要低；3 、译码判决简单，l d p c 码字的正确性是由校验矩阵计算伴 随式的方法来确认的，不管译码正确与否，译码器几乎都能检测得出来，随时退 出不必要的迭代，而t u r b o 码需要额外的运算并使用依赖于某个门限的终止准则 来退出迭代，即便如此最终还是不能判断是否正确译码；4 、构造灵活，通过变换 校验矩阵的形状，我们可以比较简单地构造出满足各种码率和码长要求的l d p c 码，而t u r b o 码主要依靠打孔法来得到不同码率的码，必须通过精心的设计才能 得以实现；5 、从商业角度来说，l d p c 码不受专利保护，而t u r b o 码不享有此优 惠。 第l 页 国防科学技术大学研究生院硕士学位论文 基于l d p c 码上述种种优势，人们对l d p c 码研究不断深入，其应用也越来 越广泛。2 0 0 4 年6 月正式颁布的d v b s 2 标准中，作为该标准的核心技术，前向 纠错编码系统中的l d p c 码采用规则码和非规则码混合的编码结构，从而获得了 很好的性能。同年8 月，基于双绞线的1 0 g b p s 以太网标准草案i e e e 8 0 2 3 a n 也决 定采用l d p c 码，并于2 0 0 6 年7 月批准为正式标准。遵循d v b s 2 的机顶盒在我 国地面数字电视传输标准建设各选的方案中，广电总局广科院的t i m i 方案性能较 好，该方案最大的技术亮点就是采用了l d p c 码信道编码技术。由于l d p c 码提 出较晚和3 g 移动通信标准失之交臂，但基于l d p c 编码的方案极有可能成为4 g 移动通信系统的应用方案。此外，人们还把l d p c 码应用于卫星通信、深空通信、 高速与甚高速率数字用户线、光和磁记录存储系统等。 l d p c 码的研究掀起了继t m b o 码之后编译码领域的又一高潮，设计并实现低 复杂度的l d p c 码快速译码算法很自然地成为了一个研究热点。 1 2 纠错编码的译码算法研究 1 ，2 1 译码算法分类 对于任何的纠错码而言，译码问题始终是其理论与实际中最关键、最有吸引 力的问题之一。译码器的运算速度及其实现的复杂性，往往成为纠错码是否实用 的关键。研究出快速、简单、经济和译码错误概率小的译码方法，仍是当今纠错 码理论和实际中最重要的研究课题之一。 如果把码字看成是时间域或频率域上的信号，则纠错码的译码可以分为利用 d f t 和信号处理的频域译码以及时域译码。时域译码是频域译码的基础。而在时 域译码中，一般分为两类：一是利用码的代数结构的代数译码，在译码过程中传 送的消息是比特值，也称为硬判决译码算法；二是不仅利用码的代数结构，而且 还利用信道干扰统计特性的概率译码，在译码过程中传送的消息是与后验概率相 关的消息，也称为软判决译码。硬判决译码计算比较简单，但性能稍差；软判决 译码计算比较复杂，但性能较好。常用的硬判决译码有捕错译码、大数逻辑译码 以及比特翻转译码等，而软判决译码算法有广义最小距离译码、契斯( c h a s e ) 译 码、维特比译码、序列译码等。为了平衡性能和计算复杂度，可以将两者结合使 用，称为混合译码算法。 对于l d p c 码而言，通常采用时域译码方法，它包含有多种译码算法。这些 算法本质上大都是基于t a n n e r 图的消息传递并迭代的译码算法。根据消息迭代过 程中传送消息的不同形式，l d p c 的译码方法也可以分为硬判决译码和软判决译 码。常用的硬判决译码算法主要有大数逻辑译码算法 4 并且只能为偶数。特别地，如果t a n n e r 图中没有环( c y c l ef r e e ) ，则定义其围长为无穷大。例如：某个t a n n e r 图有长度 为6 、8 、1 0 、1 2 和长度更长的环，则该t a n n e r 图的围长为6 。 l d p c 码中环的存在会对码的性能产生重要影响 3 7 】。根据图2 2 粗实线所示 为某校验矩阵的t a n n e r 图中一个经过变量节点h 、吃和校验节点c l 、c 2 的长度为4 的环，校验约束c l 和c 2 对于( v l ，屹) 是( o ，0 ) 或者( 1 ，1 ) 是无法区分的。同样，图2 3 中粗实线所示，为某校验矩阵的t a n n e r 图中一个经过变量节点m 、吃、屹和校验 节点c l 、c 2 、c 3 的长度为6 的环，校验约束q 、乞、巳对于( m ，屹，k ) 是( o ，0 ，0 ) 或 者( 1 ，1 ，1 ) 也是无法区分的。由此可以看出，短环的存在降低了校验约束正常的检错 和纠错能力。 l d p c 码一般采用基于消息传递的迭代算法进行译码，该类算法在无环的 t a n n e r 图上是最优的。在消息传递的迭代译码算法中，假定了变量节点是相互独 立，短环的存在必然破坏了独立性的假设，造成变量节点自身信息的叠加，从而 降低判决的可靠性，给译码性能带来了损失。环的长度越短，变量节点自身信息 被重复计算的程度越大，给译码性能带来的损失也越大。因此，在设计码的一致 校验矩阵h 时，应尽量避免短环，尤其是长为4 的环。 l d p c 码的校验矩阵与t a n n e r 存在者一一对应的关系，那么t a n n e r 图中的 环体现在校验矩阵中将是什么样的情况，它们彼此之间存在着什么样的关系，这 就是我们下面将要讨论的问题。 图2 4 给出了环长为4 的短环在l d p c 码校验矩阵中出现的一般形式，由带箭 头的实线可以清楚地看到变量节点m 、v ，和校验节点c ，、q 构成了长度为4 的短 环，对于图2 2 和图2 4 而言，如果m = h ，1 ，= v 2 ，c p = q 和c q = 1 7 2 ，图2 2 中的 短环就可以和图2 4 校验矩阵中的短环对应起来。同样地，图2 5 给出了环长为6 的短环在l d p c 码校验矩阵中出现的一般形式，由带箭头的实线可以清楚地看到 变量节点v j 、v ，、k 和校验节点1 7 p 、c ，构成了长度为6 的短环，对于图2 3 和图2 5 而言，如果m = 1 1 ，吩= v 2 ，唯= 心，c p = e l ，= c 2 和q = 巳，图2 3 中的 短环就可以和图2 5 校验矩阵中的短环对应起来。 t a n n e r 图中的一条边对应到校验矩阵中，代表了校验矩阵中的一个非零元素。 而校验矩阵中连接两个非零元素的边，只代表了一种连接，并且这种连接只能是 水平方向的或者垂直方向的，其中水平方向的边表示两个变量节点通过一个校验 节点连接起来，如图2 5 ，变量节点m 和v ，通过校验节点c 。连接起来。同理，垂直 第l o 页 国防科学技术大学研究生院硕士学位论文 校验节点 变量节点 校验节点 变量节点 謦g瞄 图2 2 二分图存在长度为4 的环 q乞 qc 4 哆学巧辔 图2 3 二分图存在长度为6 的环 厂 f- h _ l 1c 一 图2 4 校验矩阵存在长度为4 的环图2 5 校验矩阵存在长度为6 的环 方向的边表示两个校验节点通过一个变量节点连接起来。校验矩阵图中某些边按 照一条水平边连一条垂直边，再连一条水平边，再连一条垂直边的方式连接，如 此下去若能够构成一个闭合路径，则所有的水平边不同行，所有垂直边不同列。 那么该闭合回路就是校验矩阵中的一个环，所构成的环的长度则由该环包含的非 零元素个数确定。同时，l d p c 码校验矩阵中的非零元素对应t a n n e r 图中的边， 根据校验矩阵的特点发现，非零元素的个数正好与环中边的条数相等，所以环的 长度恰好又等于矩阵图中环包含的边的总数。图2 4 中环有四个非零元素，所以该 环的长度为4 ，包含4 条边；图2 5 中环有六个非零元素，该环的长度为6 ，包含 6 条边。根据以上描述可知，对于特定的任意的l d p c 码，其t a n n e r 图中的环和 校验矩阵的环是一一对应的。 第1 1 页 国防科学技术大学研究生院硕士学位论文 下面从不同于消息传递的另一个角度出发来分析环的存在对l d p c 码性能的 影响。图2 4 中，根据l d p c 码校验矩阵与t a n n e r 图的对应关系可知，由变量节 点v 和v ，对应校验矩阵中的的两列之间重叠的1 数至少为2 。校验矩阵中两列的重 叠的l 数为0 意味着这两列是相互正交的，相关性最小。如果两列的重叠的1 数 越大，则这两列的相关性就越大。所以，如果校验矩阵两列之间两列的重叠的1 数为2 的情况出现比较频繁，必然增强了校验矩阵的列的相关性，这样会减少校 验矩阵的秩，从而使得该校验矩阵确定的分组码的自由距离减少。对于图2 5 ，长 度为6 的环增强了三列之间的相关性，如果长度为6 的短环出现得比较频繁，也 会影响校验矩阵的秩，从而减小自由距离，导致码性能的下降。 综上所述，校验矩阵中的短环的存在，可能会导致校验矩阵列的相关性增强， 从而减小校验矩阵的秩，减小码的自由距离，降低码性能。事实上高围长的l d p c 码的校验矩阵更可能是满秩的，其中高围长的l d p c 码是指对应t a n n e r 图最短环 的环长比较大的l d p c 码。 2 3 1 消息传递的本质 2 3 消息传递机制 消息传递( m e s s a g ep a s s i n g ) 是现代纠错编码系统中的一个重要概念。以计算一 列士兵人数来说明这个问题。如图2 6 ，士兵排成一条直线，每个士兵只能与其相 邻的前、后士兵通信。现在的问题是：计算士兵总数，并把这个信息传达给每个 士兵。士兵之间通信规则是：站在末端的士兵把数l 传达给其邻居；任何时候一 个士兵从一个邻居接收到一个数时，把这个数加1 后传达给另一个邻居。如此从 左到右、从右到左各进行一次，每个士兵接收到两个数三和r ，那么每个士兵能够 计算士兵总人数为：三+ 足+ l 。 下面采用图2 7 说明计算士兵人数过程中的消息传递原理。如图2 7 ( a ) 所示， 一个节点代表一个士兵，消息传递规则是：如果图中一个节点有k + i 条边，那么 沿着任意一条边的输出消息是其它k 条边的输入消息之和。图2 7 ( b ) 中沿着垂直边 为每个节点输入先验消息或内在消息1 ，表示每个士兵本身；图2 7 ( c ) 表示各个节 点之间消息传递过程；图2 7 ( d ) 中每个节点沿着垂直边输出按照消息传递规则得到 厂、一厂、 德删山 u 、 r 尺+ 1 图2 6 采用消息传递计算士兵人数 第1 2 页 国防科学技术大学研究生院硕士学位论文 的输出消息或外部消息，表示每个士兵通过消息传递得到的额外信息。每个士兵 把内部消息与外部消息相加就得知本列士兵总数为6 。稍加观察可知，整个过程中 只对各个节点进行“本地( 1 0 c a l ) ”计算，而最后得到了士兵总人数这个全局问题的答 案。这就是消息传递的功能所在，把复杂的全局问题通过各个简单单元之间的消 息传递，转换成简单本地计算。这在现代纠错编码的迭代译码算法中得到了充分 的应用。 但是只有在图中没有环时这种消息传递规则才能完美地运行。如果图中存在 环，相当于一群士兵站成了一个圈，利用消息传递规则计算人数时将得到无穷大 的结果。 ( a ) ：消息传递规则 ：输入每个节点的先验消息或 内部消息( i n t r i n s i cm e s s a g e ) ( c ) ：消息传递过程 g 卜_ ) - g 卜_ w( d ) ：每个节点输出消息或外部 1 5 1 5 1 5 1 5 1 5 1 5 消息( e x t r i n s i cm e s s a g e ) 图2 7 计算士兵人数过程中消息传递过程的图形表示 事实上，l d p c 码译码算法的整个迭代过程可以看成在由校验矩阵决定的 t a n n e r 图上进行消息传递的过程。g a l l a g e r 在其论文中提出了l d p c 码基于概率的 迭代译码方案，这是消息传递算法的雏形。消息传递算法必须给定一种消息传递 与更新秩序的法则，称该法则为消息传递机带l j ( m e s s a g e p a s s i n gs c h e d u l e ) 。研究表 明，对有环图而言，消息传递机制是影响译码性能的一个重要因素，f o m e y 提出 一个发人深省的问题：“能否通过改变译码算法基于的消息传递机制以改进译码性 能? ” 3 8 】。研究表明答案是肯定的，比如y o n g y im a o 和a n m i rh b a n i h a s h e a u 提出 了基于概率方案的消息传递机制【3 9 】，考虑了码的t a n n e r 图的结构，特别是变量节 点的围长分布，使得变量节点输出消息的平均更新频率与通过该变量节点的最短 环的长度成正比，该算法本质上减少了节点信息的正反馈，从而改善译码的性能。 e r a ns h r o n 提出了基于串行方案的消息传递机制【4 0 】。在l d p c 码的译码算法研究 中，消息传递机制是一个重要的研究方向。 第1 3 页 国防科学技术大学研究生院硕士学位论文 2 3 2 洪水消息传递机制 洪水消息传递机件j 1 ( f l o o d i n gs c h e d u l e ，f s ) 是目前普遍采用的，基于并行处理的 消息传递机制。基于该机制的l d p c 码译码算法由于采用全并行处理，译码速度 很快。b p 译码算法就是一种最常用的洪水消息传递机制下的译码算法，以对数似 然比准则下的b p 译码算法为例进行说明。 l l r - b p 是一种迭代s i s o 译码算法，可用由校验矩阵决定的t a n n e r 图来描述， 如图2 8 所示。每轮迭代过程中，所有变量节点同时接收并处理校验信息上( 如) ， 向与其相连的变量节点传送变量消息( 瓯) ；随后所有校验节点同时接收并处理变 量信息( 瓯) ，向与其相连的变量节点传送校验消息( 如) 。其具体译码过程如表 2 1 所示。 图2 8t a n n e r 图上的译码消思沉的迭代传递 假设我们用( 1 ，) 表示与变量节点相连的校验节点集合，( c ) 表示与校验节点 相连的变量节点集合，那么三( 瓯) ( 对二元码而言) 是在已知与变量节点v 相连的除 c 外其它校验节点所发送的校验消息 上( r ，) ，c ( 1 ，) c ) 前提下，变量节点为o 和为l 的条件概率的对数似然比值，计算式见表2 1 式( 2 2 ) ；同理，三( 如) 是 在假设已知变量节点取值为o 或为1 ，与校验节点c 相连的其它变量消息 三( q v 。) ，1 ，( c ) ，) 也已知前提下，校验关系成立的两个条件概率的对数似然比 值，计算式见表2 1 式( 2 1 ) 。 由表2 1 式( 2 1 ) 和( 2 2 ) 可以看出，在每一轮迭代中，校验消息三( 瓯) 和 变量消息三( 如) 的计算都是利用上一轮迭代的结果，每个校验节点和变量节点在本 轮迭代中已更新的消息只能在下一轮迭代计算中被使用，这就导致译码收敛速度 较慢，为了获得期望的性能就需要大量的迭代；同时对本轮迭代中更新的消息变 量必须进行存储，占用大量的硬件资源，不便于硬件实现。为克服这些缺陷和不 足，e r a ns h r o n 等人提出了基于校验节点( 变量节点) 的串行方案的消息传递机制。 第1 4 页 国防科学技术大学研究生院硕士学位论文 表2 1 基于对数似然测度的洪水消息传递译码算法基本流程 i n i t i a l i z a t i o n ： f o r a l l ，e v ，c c ( 如) 卜0 f o r a l lv 矿，c c ( 瓯) 卜 i t e r a t i o n ： f o r a l ic c 三( 如) 卜俐畎l ( q 。) ) ( 2 1 ) e n do f l o o p f o ra l i v v 三( 瓯) 卜( ) + 。i ( 小工( 足，) ( 2 2 ) e n do f l o o p f o ra i l l ，矿 工( q ) 卜三( ) + 。帅ll ( 凡) ( 2 3 ) e n do f l o o p 2 3 3 串行消息传递机制 基于串行消息传递机制译码算法分为基于校验节点和基于变量节点两种，本 文只对基于校验节点的串行消息传递译码算法进行简要叙述，基于变量节点的串 行消息传递译码算法可做类似处理。 基于校验节点的串行译码算法在每一轮迭代过程中，按照校验节点一定的顺 序( 比如( q ，c ：，) ) 进行消息处理和传递，对每个校验节点同时接收变量消息 三( 既) 并向与之相连的消息节点发送校验消息三( 如) ，这样就能保证更新的消息马 上用到后面校验节点消息的处理，从而改进了译码算法的收敛特性。 基于校验节点的串行消息传递译码算法的具体译码过程如表2 2 所示。 与洪水消息传递译码算法相比，串行消息传递译码算法有以下几个优点：( 1 ) 由于在每轮迭代过程中，本节点更新的消息三( 凡) 在后面节点消息更新的时候被用 到，而不像洪水消息传递译码算法那样，更新的消息只能等到下次迭代才能传送 出去，从而提高了译码的收敛速度，其收敛要求的迭代次数约为洪水消息传递译 码算法的一半左右 4 1 j ，这样就减少了译码延时，便于硬件实现；( 2 ) 在没有限制 迭代次数的时候，串行消息传递译码算法性能和洪水消息传递译码算法相近，在 低迭代次数要求的情况下，串行消息传递译码算法性能比洪水消息传递译码算法 更优越1 4 2 j ；( 3 ) 对照表2 1 和表2 2 可知，串行消息传递译码算法迭代过程中不 用存储n ( v ) 和三( 线) ，这样在硬件实现时可以节省大量的存储空间。 但由于在每轮迭代过程中，串行消息传递译码算法对节点消息是顺序更新的， 这样每次译码所需时间就会增长，导致译码速度的降低。而分组串行译码可以较 好地解决这一问题。 第1 5 页 国防科学技术大学研究生院硕士学位论文 表2 2基于校验节点的串行消息传递译码算法基本流程 i n i t i a l i z a t i o n ： f o ra l l ，e 矿，c cl ( r 。) 卜0 f o ra l l ，y 工( q ，) 卜三( 只) i t e r a t i o n ： f o ra l lc c s 卜刚伊( 三( q ) 一l ( r 。) ) f o ra l lv ( c ) ( q ，。) 4 - l ( q ，) 一三( r ，) ( r ，) 一缈叫( s 一9 ( 从瓯。) ) ) 三( g ) 6 - - 工( q ，。) + 上( 8 。) e n do f l o o p e n do f l o o p 2 3 4 分组串行消息传递机制 2 3 4 1 基于校验节点的分组串行传递译码算法 分组串行译码算法也可以分为基于校验节点和基于变量节点两种译码算法， 本文只对基于校验节点的分组串行传递译码算法进行分析。 基于校验节点的分组串行译码算法是在串行译码算法中，加入校验节点集合 分组处理，以实现局部并行操作。即先将校验节点集合c 按一定规则划分成m 个 子集 b 1 ，b 2 ，b 册) ，消息的更新以子集为顺序依次进行( 即按串行方式完成消息 传递) ，而位于同一子集内的校验节点同时进行消息的更新( 即并行操作) 。具 体译码过程如表2 3 所示。每一轮迭代过程中，首先对子集b l 中的所有校验节点 并行地进行变量消息( 瓯) 的接收和校验消息三( 凡) 的发送( 即表2 3 虚框