（通信与信息系统专业论文）低密度奇偶校验码译码算法及应用研究.pdf

摘要 摘要 随着t u r b o 码的发明和迭代译码技术实现条件的成熟，低密度奇偶校验c l d p c ) 码这类 基于稀疏图形定义的纠错码也重新被发现并逐渐成为编解码领域研究的热点。由于l d p c 码构造方法灵活多变，同时具有多种可以高速并行实现的迭代译码算法，许多通信和存储系 统已经或计划将l d p c 码作为其核心纠错码方案。 l d p c 码的标准软判决译码算法称为和积算法或置信传播( b p ) 算法，是一种基于信息传 播机制的迭代译码算法。在实际应用中，由于码块长度的限制导致校验矩阵存在短圈，l d p c 码在标准b p 算法下的性能与最大似然译码性能相比还存在一定的差距。由于短圈对b p 算 法性能的影响，不同的遢火机制被应用于b p 算法的改进，我们提出一种适用于有限几何域 构造的l d p c 码的b p 算法改进。标准的b p 算法迭代机制称为流水机制，迭代过程中节点 问韵信息传递像流水般不问断的进行，对迭代杌制的改进也可以改善b p 算法的收敛性稚。 针对目前实际应用的l d p c 码结构，我们提出一种校验节点和变量节点之间同步并行的迭 代机制，在不增加硬件实现复杂度和译码延时的条件下，加快译码收敛速度，改善译码性能。 最小和算法是b p 算法的一种有效的简化算法，原本复杂的校验节点计算被简化成求最 小值的运算。由于最小值近似与标准的结果之间存在较大误差，有条件修正和无条件修正两 种修正方案被用于最小和算法的改进，修正因子的优化分别通过对单个校验式的近似或密度 演变算法来确定。我们结合上述两种修正方案的优点，提出一种自适应修正方法。对于中等 以上长度的l d p c 码，新修正方案有效地提高了译码性能，缩小了最小和算法和标准b p 算 法之间的性能差距。 比特翻转算法是l d p c 码所特有的一种硬判决译码算法，它具有计算复杂度低，硬件 实现简单，可快速并行译码等优势。加权比特翻转算法在比特翻转迭代译码的结构中引入部 分来自信道的接收信息，作为比特翻转判据的权重因子，提高了硬判决算法的纠错能力。目 前已有不少方案对加权比特翻转算法的加权因子或算法结构进行修正，在适当增加译码复杂 度的条件下改善译码性能。我们综合考虑l d p c 码校验式可靠度信息和置信传播机制，蹦 加权比特翻转算法做出修正，提出两种实用的改进算法，使得基于比特翻转的算法性能进一 步逼近软判决迭代译码算法。 b p 算法和其他译码方案相结合，可以有效地克服短圈的影响，提高中短长度l d p c 码 的纠错能力。迭代捧序统计译码算法将b p 算法输出的软信息和排序统计译码算法相结合； 改善了l d p c 码的译码性能。但由于排序统计译码算法复杂度接近码长的j 次方，较多的 i 糸南，、学博七学位论文 排序统计译码处理会给b p 迭代算法带来比较长的译码时延。利用迭代过程中的累积对数似 然比信息我们提出一种改进的低复杂使送代排j 孚统计译码算法。在此基础上，排序统计译 码算法可以和b p 算法并行处理，在b p 算法译码结束的同时给出排序统计译码算法的译码 结果。在不增加译码延时的条件下提高译码性能。 由于l d p c 码具有较强的自检错能力，结合l d p c 码编码的混合自动重传请求机制得 到了广泛的关注和研究。针对递增冗余或数据打孔这些不同的重传机制，如何设计l d p c 码的校验矩阵是提高系统吞吐量的关键问题。我们对数据打孔方式下的l d p c 码的校验矩 阵做了相应的优化。在不增加编译码复杂度的条件下，新的校验矩阵结合混合自动重传请求 协议明显提高了数据通过率。 关键词：低密度奇偶校验码，置信传播算法，最小和算法，比特翻转算法，排序统计译码 i l 竺竺! ! a b s t r a c t w i t ht h em v t i o no f t u r b oc o d e sa n dt h ed e v e l o p m e n to fi t e r a t i v ed e c o d i n gt e c h n i q u e s ， 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 sw h i c ha t ed e f i n e di nt e r m so f t h es p a r s er a n d o mg r a p h s h a v eb e r e d i s c o v e r e da n db e c o m ef o c a lp o i n to fr e s e a r c hi ne r r o r - c o n t r o lc o d i n g d u et ot h e v a r i o u sc o n s t r u c t i o nm e t h o d sa n dh i g i is p e e dp a r a l l e la r c h i t e c t u r e sf o r i t e r a t i v ed e c o d i n g ，t h e l d p cc o d e sh a v e b e e no rw i l lb et h ec o r ct e c h n i q u eo fc o d i n gi nm a n ym o d e mc o m m u n i c a t i o n a n ds t o r a g es y s t e m s t h es o f t - d e c i s i o nd e c o d i n ga l g o r i t h mf o rl d p cc o d e s ，c a l l e dt h eb e l i e fp r o p a g a t i o n p ) a l g o r i t h mo rb x l n l p r o d u c ta l g o r i t h m ，i sac l a s so fi t e r a t i v ed e c o d i n gb a s e do nm e s s a g ep s i n g s c h e d u l e f o rp r a c t i c a la p p l i c a t i o n s ，t h el i m i t a t i o no fb l o c kl e n g t hw i l ll e a dt os h o r t - c y c l ei n t a n n e rg r a p h , t h ei t e r a t i v eb pa l g o r i t h mf o rl d p cc o d e si n c u r sm u c hp e r f o r m a n c ed e g r a d a t i o n r e l a t i v et ot h em a x i m u ml i k e l i h o dd e c o d i n g d i f f e r e n tm m e a l i n gs t r a t e 西e s 目ea p p l i e di nt h e m o d i f i c a t i o n so fb pa l g o r i t h mt oo v e r c o m et h ei n f l u e n c eo fs h o r t - c y c l e w ep r e s e n ta l l i m p r o v e m e n to nt h eb pd e c o d i n gf o rt h ef i n i t eg e o m e t r y 口g ) l d p cc o d e s i nt h es t a n d a r db p a l g o r i t h m , t h ep a s s i n go ft h em e s s a g eb 咖e d i f f e r e n tn o d e si sl i k et h eu n i n t e r r u p t e df l o o d i n g ， i ti sc a l l e df l o o d i n gs c h e d u l e t h ei m p r o v e m e n to nt h ei t e r a t i v es c h e d u l ew i l la l s os p e e d 呷n l e c o n v e r g e n c eo f b pa l g o r i t h m a c c o r d i n gt ot h ei m p l e m e n t a t i o na r c h i t e c t u r e so f l d p cc o d e s ，w e p r o p o s eap a r a l l e li t e r a t i v es c h e d u l eb e t w e e nt h ev a r i a b l en o d e $ a n dc h e e kn o d e s ，w h i c hi m p r o v e s t h ep e r f o r m a n c eo f b pd o d i n gw i t h o u ta n yh a r d w a r er e s o u r c ei n c r e a s e t h em i n - s u m 叫s ) a l g o r i t h n ai s e f f e c t i v es i m p l i f i c a t i o no fb pa l g o r i t h m 。w h e r et h e c o m p l e xt a n h - b a s o d p a l a t e o fc h e e k - n o d ei s s i m p l i f i e d t ot h es e l e c t i o no fm i n i m u ma n d s u b - m i n i m u ml l rm a g n i t u d e s s i n c et h e r ei ss e v e rd e g r a d a t i o nd u et 0t h em sa p p r o x i m a t i o n 。 t w om o d i f w , a t i u ns c h e m e sma p p l i e df o rt h ei m g r o v e m e n to i lm sa l g o r i t h m o n ei st h e c o n d i t i o n a lc o r r e c t i o ns c h e m ea n dm eo t h e ri su n c o n d i t i o n a lc o l l e t i o ns c h e m e t h ec o r r g c t i o n f a c t o r si nb o t hs c h e m e sa r ed e t e r m i n e db yt h ea p p r o x i m a t i o no f t a n h - b a s e dc h e c k - n o d eu p d a t eo r d e n s i t ye v o l u t i o na l g o r i t h m ，r e s p e c t i v e l y c o m b i n i n gt h ea d v a n t a g e s o fd i f f e r e n tc o r r e c t i o n s c h e m e s , w ep r e s e n t 趾a d a p t i v em o d i f i c a t i o nt ot h em sa l g o r i t h m f o rt h em o d e r a t eo fl o n g b l o c kl e n g t hl d p cc o d e s ，t h ep r o p o s e da l g o r i t h ma c h i e v e san o t i c e a b l ep e r f o r m a n c eg a i na n d r e d u c e st h ep e r f , m a a n c eg a pt ot h eb pd e c o d i n g i l l 东南丈学博士学位论文 t h eb i t - f l i p p i n g ( b f ) a l g o r i t h mi sad i s t i n c th a r d - d e c i s i o nd e c o d i n go fl d p cc o d e s ，w h i c h h a st h ea d v a n t a g e si nt e r m so ft h el o wc o m p u t a t i o nc o m p l e x i t y ，s i m p l ei m p l e m e n t a t i o ni n h a r d w a r ea n dh i g h s p e e dp a r a l l e ld e c o d i n ga r c h i t e c t u r e s w e i g h t e db i t - f l i p p i n g ( w b f ) a l g o r i t h m g i v e ss i g n i f i c a n tp e r f o r m a n c eg a mo v e rt h eb fd e c o d i n g ，w h e r es o m er e c e i v e di n f o r m a t i o nl y o m t h ec h a n n e li su t i l i z e da st h ew e i g h t e df a c t o ro ff l i p p i n gf u n c t i o ni nt h ei t e r a t i v ep r o c e s s t h e r ea r e m a n yi m p r o v e m e n t so i lt h ew e i g h t e df a c t o ro rd e c o d i n ga r c h i t e c t u r eo fw b fa l g o r i t h mt h e s e m o d i f i c a t i o ns c h e m e sa c h i e v ec o n s i d e r a b l ep e r f o r m a n c eg a i na n dr e q u i r eo n l yam o d e r a t e i n c r e a s ei n c o m p u t a t i o nc o m p l e x i t ya n ds t o r a g e b a s e do nt h er e l i a b i l 时i n f o r m a t i o n o f c h e c k n o d ea n dt h em e c h a n i s mo fm e s s a g ep a s s i n g ，w ep r o p o s et w oi m p r o v e m e n t so nt h ew b f a l g o r i t h ma n dm a k et h ed e c o d i n gp e r f o r m a n c ec l o s e rt ot h ei t e r a t i v es o f c d e c i s i o na l g o r i t h m t h ec o n c a t e n a t i o no fb pd e c o d i n gw i t ho t h e ra l g o r i t h m sw i l le f f e c t i v e l yo v e r c o m et h e i n f l u e n c eo fs h o r t c y c l ei nt a n n e rg r a p ha n ds i g n i f i c a n t l yi n c r e a s et h ep e r f o r m a n c eo fl d p c c o d e sw i t hs h o r tb l o c kl e n g t h ，u t i l i z i n gt h es o f to u t p u to fi t e r a t i v ed e c o d i n ga st h er e l i a b i l i t i e so f o r d e rs t a t i s t i c d e c o d i n g ( o s d ) ，b p o s da l g o r i t h mm a k e sf m - m e ri m p r o v e m e n to f ft h e p e r f o r m a n c eo fb o t hb pa n do s da l g o r i t h ms i n c et h ec o m p l e x i t yo fo s da l g o r i t h mi s a p p r o x i m a t e l yp r o p o r t i o n a t et ot h ec u b eo f b l o c kl e n g t h , t h ed e c o d i n gs p e e do f b pa l g o r i t h mw i l l b es i g n i f i c a n t l yd e c r e a s e dw i t ht h eo s dp r o c e s sp e r f o r m e dm a n yt i m e s i nt e r m so ft h e a c c u m u l a t i o no f l o g l i k e l i h o o dr a t i o ( l l 鼬i nt h e i t e r a t i v e d e c o d i n g , w ep r o p o s e a l l i m p r o v e m e n to nt h eb p - o s da l g o r i t h mw i t hl o wc o m p l e x i t y ，f u r t h e r m o r e ，t h eo s da n db p a l g o r i t h m s c a nb ep e r f o r m e dp a r a l l e l ，w h i c hi m p r o v et h ep e r f o r m a n c ea n dd on o tb r i n g a n y a d d i t i o n a ld e c o d i n gd e l a y d u e t o t h ee r r o r d e t e c t i o nc a p a b i l i t i e s o f l d p c c o d e s 。a l o t o f r e s e a r c h w o r kh a s b e e n c a r r i e d o u tf o c u s i n go nt h el d p cc o d e dh y b r i da u t o m a t i cr e p e a tr e q u e s t ( h a r q ) t h ed e s i g no f p a n t y c h e e km a t r i c e so fl d p cc o d e sa c c o r d i n gt oi n c r e m e n t a lr e d u n d a n c y ( 1 r ) o rd a t a p u n c t u r i n g ( d p ) r e t r a n s m i s s i o nm e c h a n i s mi sak e yi s s u r et oi n c r e a s et h es y s t e mt h r o u g h p u t w e p r o p o s eam e t h o dt oo p t i m i z et h ea r c h i t e c t u r ea n dd e g r e ed i s t r i b u t i n n s o ft h ep a r i t y - c h e c km a t r i x f b rt h el d p cc o d e dd p h a r qa n di m p r o v et h et h r o u g h p u tw i t h o u ti n c r e a s ei nc o m p l e x i t 3 , o f e n c o d i n ga n dd e c o d i n g k e yw o r d ：l o w - d e n s i t y p a r i t y c h e c kc o d e s ，b e l i e fp r o p a g a t i o na l g o r i t h m ，m i r a s u m a l g o r i t h m ，b i t - f l i p p i n ga l g o r i t h m ，o r d e r e ds t a t i s t i cd e c o d i n g a o m s a r q ： a d a p t i v eo f f s e tm i n s u m a u t o m a t i cr e p e a tr e ( c s t 自适应的偏移修正最小和； 自动重传请求： a w g n ：a d d i t i v ew h i t e ng a u s s i o nc h a n n e l 加性高斯白噪声信道： b f ： b p ： b s c c i u 啦： c r s p ： d e ： b i tf l i p p i n g b e l i e f p r o p a g a t i o n b i n a r ys y m m e t r i cc h a n n e l 比特翻转： 置信传播； 二进制对称信道； 固定速率随机打孔： c o n s tr a t es e q u e n t i a lp u n c t u r e 固定速率顺序打孔； d e n s i t ye v o l u t i o n 密度演变； d m - m s ：d e g r e em a t c hm i n - s u m 度数匹配的最小和 d p ： d v b ： e x i t ： f e c ： f g ： l d p c ： l l r ： h a r q ： l r ： l i r ： 数据打孔： d i s t a lv i d e ob r o a d c a s t i n g 数字电视广播； 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 外信息转移； f i n i t eg e o m e t r y l o w - d e n s i t yp a r i t y - c h e c k l o g - l i k e l i h o o dr a t i o 前向差错控制 有限域几何； 低密度奇偶校验； 对数似然比； h y b r i d a u t o m a t i c r e p e a tr e q u e s t混合自动重传请求 i n c r e m e n t a lr e d u n d a n c y 递增冗余： i n f i n i t ei m p u l s ef i l t e r 无限冲激响应滤波器： i m w b f ： i m p r o v e dm o d i f i e dw e i g h t e db i tf l i p p i n g 改进的修正加权比特翻转 v 东南大学博士学位论文 m a p ： m l d ： m s ： m a x i m u map o s t e r i o r ip r o b a b i l i t y 最大后验概率 m a x i m u ml i k e l i h o o dd e c o d i n g最大似然译码： m i n - s u m 最小和； m w b f ：m o d i f i e dw e i g h t e db i tf l i p p i n g 修正加权比特翻转 n m s ： o m s ： o s d ： p e g ： p p b p ： r c ： q c ； s h b p ： s i s o ： s p b p ： s p c ： s s 。b p ： n o r m a l i z e dm i n s u m 归一化的最小和 o 丘e tm i n - s u m 偏移修正的最小和 o r d e r e ds t a t i s t i c sd e c o d i n g排序统计译码； p r o g r e s se d g eg r o w t h 渐进边增长； p a r t i a lp a r a l l e lb e l i e f p r o p a g a t i o n部分并行的置信传播 r a t ec o m p a t i b l e q u a s ic y c l i c 速率适配 准循环； s h f f u l e ds c h e d u l eb e l i e f p r o p a g a t i o n 混合顺序的置信传播 s o f ti n p u ts o f to u t p u t软输入软输出 s y n c h r o n o u sp a r a l l e lb e l i e f p r o p a g a t i o n 同步并行置信传播； s i n g l ep a r i t ) - c h e c k 单比特奇偶校验码； s e f i f ls c h e d u l eb e l i e f p r o p a g a t i o n 串行机制的置信传播 t a n n e r 图：校验矩阵对应的变量节点和校验节点的双层连接图 w b f ： w e i g h t e db i tf l i p p i n g 加权比特翻转 w s w b f ： w e i g h t e d s u mw e i g h t e db i tf l i p p i n g 校验和加权比特翻转 v 1 1 1 符号和变量说明 符号和变量说明 h ：l d p c 码的校验； ，m ，k ： 校验矩阵列与行的长度，以及高斯消去系统化后的信息比特长度 a a ： r ： 规则l d p c 码校验矩阵的行重和列重 l d p c 码的码率： 校验节点集合c = ，所【1 ，m 】 ； 变量节点集合y = 匕，疗【1 ， ，】 ； 校验式序列s = = o ，1 ，m 【1 ，m 】) ； 全零行向量，维数膨； 与变量节点相连接的校验节点集合； 与校验节点相连接的变量节点集合； l d p c 码校验矩阵对应的t a n n e r 图中连接变量节点和校验节点的总边数 - - i n ，甩【1 ， ，】 b p s k 调制后的序列，x = 矗= l - 2 w ，n e 1 ，】 ； a w n g 信道噪声信号； 噪声方差； 信道的输出序列】，= 以= 矗+ u n ，甩【l ，】) ； 迭代次数，最大迭代次数； 信道接收初始的对数似然比信息； 第k 次迭代，变量节点输出的对数似然比信息； 第k 次迭代，变量节点向校验节点传递的似然比信息； 第七次迭代，校验节点向变量节点传递的似然比信息； i x )，：、 “ ： ： ： ； ； o“、 ； ： ： - ： ： 屠 却。m_g 已 n 乳 叭 小跏几 肌 “ ”以 n 眠珞办厶 东南大学博士学位论文 分块矩阵构造中子矩阵的维数，及部分并行迭代中每次迭代的节拍 s p b p 迭代算法中，变量节点和校验节点初始的位置向量 校验节点c 。输入对数似然比信息中最小幅值 a o m s 算法的最小值分段间隔； a o m s 算法的查表索引； b f 类算法中变量节点的翻转函数； b f 类算法中校验节点豹权重信息； o s d 算法中对矩阵和输出序列的排序置换 o s d 算法处理的迭代间隔； 变量节点上的累积对数似然比信息； a r q 重传次数； 编码序列中的信息比特段和校验比特段 d p h a r q 中，c p s r 打孔模式相邻数据打孔段的重合长度 d p h a r q 重传打孔率； 非规则l d p c 码矩阵中最大列重和行重； p ( x ) ，五( x ) ：按照t a n n e r 图中边的连接节点重量分布，得到的非规则分布 p ( z ) ，互( x ) ：按照节点重量分布的得到的非规则分布； 7 4 ： 第口次重传的打孔序列： d ： 二进制序列的汉明重量； x ： n ： t 幻 “ 缸 “ 小 钻 出 k 玑 叭 以 咖 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：卸日期：业矿 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：蔓1 4 导师签名期：堋，矿 第一章绪论 第一章绪论 自香依创立信息理论以来，如何构造逼近香侬限的好码以及如何有效的译码直是纠错 码理论研究中的重要课题。同时纠错码的编解码技术在各种实际的数字通信系统和计算机系 统中都起到了举足轻重的作用。伴随着世界范围内的信息科技革命，特别是通信技术，计算 机理论以及网络技术的互相融合，纠错编码技术正以前所未有的速度在发展和更新。 i i 论文的研究背景 2 0 世纪6 0 年代初期由g a l l a g e r 提出的低密度奇偶校验( l d p c ，l o w - d e n s i t y p a r i t y - c h e c k ) 码 h 1 2 ，在最近的十年里，因为其渐近香依限的译码性能被m a c k a y 等在文献【3 冲重新发 现，而越来越受到人们的关注，成为纠错编码领域的一个研究热点。目前与l d p c 码编解 码技术相关的研究已取得了长足的进步，随着非规则l d p c 码构造【4 】和密度演变理论【5 】【6 1 的提出，已有的研究结果表明精心设计的非规则l d p c 码长码【7 】【8 】能逼近信道容量极限， 性能要优于t u r b o 码【9 】。而如何在有限长度和硬件可实现的条件下，设计性能优越的l d p c 码及改进编解码算法已经逐步成为移动通信、卫星通信、深空通信等领域中一个重要的研究 方向。 对于有限长度的l d p c 码。由于校验矩阵对应的二分图或t a n n e r 图 1 0 l 中不可避免的存 在短圈，l d p c 码的在置信传播( b p b e l i e f p r o p a g a t i o n ) 算法 i l l 1 2 下的迭代译码性能会有较 大的损失。对于不同的l d p c 码矩阵结构，如何改进b p 算法，抵消短圈在迭代算法中带来 的正反馈效应，提高译码性能也是一个重要的研究方向。b p 算法虽然本身具有较好的并行 处理结构，但矩阵的伪随机构造使得完全并行的译码算法难以实现，同时串行译码等适合 d s p 处理的算法又不可避免的会带来很大的处理时延。如何面向适合并行译码处理的硬件 实现，在不影响译码性能的条件下，构造设计合适的矩阵结构和迭代处理方案一直是l d p c 码编解码技术中一个研究热点。 l d p c 码的b p 算法是一种迭代译码算法，在校验节点和变量节点的迭代处理过程中， 校验节点处理的复杂度和时延要远大于变量节点的处理。文献【1 3 】研究了校验节点单元运算 的简化处理方案最小和( m s ，m i n - s u m ) 算法，该算法将校验节点的复杂处理简化成为选 取最小值的计算，其运算复杂度和变量节点处理几乎相同。正由于m s 算法中校验节点处理 的计算简单，实际的l d p c 码硬件设计和应用中大多采用m s 算法，但该近似算法的性能与 b p 算法相比还存在一定的差距。为此许多文献对m s 算法给出了各种修正方案，减少由最 1 东南大学博士学位论文 小值近似带来的性能损失，在适当增加复杂度的基础上逼近标准的b p 算法性能。不同的修 正处理对l d p c 码的译码性能改善与码字长度及校验矩阵的结构有关，所以如何设计一种 适合各类型l d p c 码的低复杂度修正算法，也是一个很有意义的研究方向。特别是针对长 度较长的非规则l d p c 码，目前的修正处理与b p 算法相比始终有较大的性能差距，如何针 对这一类型的l d p c 码设计合适的译码算法是个值得关注的问题。 l d p c 码的译码算法中还有一类是基于比特翻转( bf ，b i tf l i p p i n g ) 1 4 】【1 5 】的硬判决或混 合判决算法。这类算法译码复杂度低，实现简单，适合超高速译码的要求，但是比特翻转算 法的性能相比软判决算法，如b p 算法和m s 算法，有很大差距。文献 1 5 1 给出了一种加权 的比特翻转算法( w b f ，w b i g h t e db i tf t i p p i n g ) 以及一些改迸处理方案，这类算法和用了各个 变量节点上接收信号的可靠度信息，增加了翻转判决处理的可靠性。如何利用l d p c 码中 其他信息改进翻转判决的处理策略，是进一步改善这类混合判决算法性能的一个研究方向。 在许多应用中，系统采用中短长度的l d p c 码，对应的t a n n e r 图不满足渐进无圈的条 件，b p 译码算法和最大似然译码( m l d 。m a x i m u ml i k e l i h o o dd e c o d i n g ) 算法相比，在性能上 仍然有较大差距。文献 1 6 1 给出一种迭代排序统计译码算法将迭代译码处理和( o s d ，o r d e r e d s t a t i s t i c sd e c o d i n g ) 算法相结合，在b p 算法无法给出合理的译码结果时，通过o s d 处理适 当改善l d p c 码的译码性能，逼近最大似然译码。但是o s d 算法复杂度和码长的三次方成 正比，远大于线性复杂度的b p 算法，因此o s d 处理会给b p 算法带来很大的译码时延。如 何改进b p 算法和o s d 算法的结合方案，提高o s d 算法处理效率，减少译码时延，是b p - o s d 算法实际应用所必需考虑的关键问题。 未来的数字移动通信系统为了保证数据业务的传输质量，除了要使用纠错编码之类的技 术以外，必须采用有效的差错控制协议，例如自动重发请求( a r q ，a u t o m a t i c r e p e a tr e q u e s t ) 。 由于信道编码和a r q 协议两种技术各有乖j 弊，将a r q 协议和编码纠检错特性结合使用的 混合重传请求机$ 1 ( h a r q h y b r i da u t o m a t i cr e p e a tr e q u e s t ) ，可以保证较高的系统传输效 率。由于l d p c 码具有渐近香侬限的译码性能以及较好的检错能力，l d p c 码和h a r q 技 术的结合已经成为一个研究热点。目前已有相当多的研究工作致力于设计适合h a r q ，具 有递增冗余( i r ，i n c r e m e n t a lr e d u n d a n c y ) 结构的l d p c 码，及相应的重传打孔方案和接收处 理算法。如何结合给定的h a r q 协议设计合适的l d p c 码也是目前l d p c 码技术研究的 一个热点问题。 本文主要是针对上述几个问题，以l d p c 码的译码算法为主要研究方向，将l d p c 码 的具体实现作为切入点，研究和探讨l d p c 码的译码算法及其与h a r q 的结合方案。论文 2 第一章绪论 将对l d p c 码已有的各种主要算法及我们提出的一些改进算法给出相应的描述，分析比较 各种算法的复杂度，并通过仿真验证不同算法间的性能差异。 1 2l d p c 码相关的一些基本定义和内容 本文主要的研究对象为二进制l d p c 码，包括规则l d p c 码和非规则l d p c 码，首先 本节将简单介绍l d p c 码的定义和基本结构。 l d p c 码是一种线性分组码，线性分组码总是通过一个生成矩阵将信息序列映射成码字 序列。对于给定的一个生成矩阵，完全等效的存在一个奇偶校验矩阵日，所有的码字序列 矽 构成了日的零空间，日形1m o d 2 = o 。l d f c 码的特点完全取决于它的奇偶校验矩阵 日。相对于行与列的长度( m ，) ，l d p c 码校验矩阵的行列重量( b 乃非常小，是一个非 常稀疏的矩阵，所以称为低密度。校验矩阵h 的稀疏性再加上构造中所使用的不同规则， 使得l d p c 码校验矩阵对应的t a n n e r 图具有不同的闭合环路分布。l d p c 码不同的t a n n e r 图结构，使褥l d p c 码在如b p 算法这一类迭代译码算法下，表现出完全不同的译码性能， 当日的行重p 和列重a 保持不变或尽可能保持均匀的时候，这样的编码称之为规则l d p c 码( ，m ，a ，p ) ，反之如果行重列重变化差异较大，则称为非规则l d p c 码 任意一种线性分组码都可以表示成t a n n e r 图的结构，即是将节点分为两个不同的集合， 同一个集合内部的节点问没有连线，只有属于不同集合的两点之间可能有连线。对于l d p c 码，可以通过它的校验矩阵日 “的m 个校验方程和n 个比特位置，确定两个节点集合； 变量节点集合y = v i ，吃，h 和校验节点集合c = q ，c 2 ，c m ) 。如果某个变量节点参 与了某个校验方程，则这两个属于不同集合的节点问有一条边相连，同时定义与变量节点 相连的所有校验节点集合为彳( n ) ，而参与校验节点的变量节点集合为口( 坍) 。 日= 例如一个( 6 ，4 ，2 ，3 ) 的规则l d p c 码，它的校验矩阵和相应的方程组如式( 1 1 ) 所示。根 据这些校验方程组，可画出对应的t a n n e r 图，如图1 1 所示- 图中变量节点集合( v 1 ，b k ) 和检验节点集合( q ，乞) 内部不存在相连的边，但两个集合之间有边相连，符合t a n n e r 图的定义。定义某个节点相连接的边的数目为该节点的次数图1 1 中，每个变量节点吒与 两条边相连接，每个校验节点与三条边相连，所以有a = 2 ，p = 3 在一个包含边和节点 3 o o o o l l l i i i = n 如咋 o o o o 吃h 吩 o o o o h b h 吃 ，、l、， 0 o l 1 o l l o l 1 o o o l o l l o o 1 l o 1 o ，。l 东南大学博士学位论文 的图形中，节点的次数分布很大程度上决定了该图形的一些基本性质。 在图1 1 显示的t a n n e r 图结构当中，六条粗体连线构成了一个有向的闭合环路，由v 。起 始，最后返回v ，长度为6 。在一个l d p c 码的t a n n e r 图中，会存在许多这样的闭合环路， 其中晟短的闭合环路长度，称之为最小i 蟊长( g i r t h ) ，上例的t a n n e r 图中，g i r t h 即为6 图1 1 ( 6 a ，2 ，3 ) 码字的t a n n e r 图，咋为变量节点，c 卅为校验节点 通常一个二迸制规则l d p c 码可以由( ，m ，五，p ) 四个参数确定校验矩阵的基本特性 但是描述非规则矩阵还需要进一步引入边或节点度数分布的概念 4 】。定义多项式 4 a ( x ) = 4 x 一，p ( x ) = p , x 1 ( 1 2 ) 分别为非规则l d p c 码的t a n n e r 图中对应的边重量分布，其中 ( 尼) 别为连接重量为f 的 变量(