（通信与信息系统专业论文）ldpc码的构造及译码研究.pdf

摘要 低密度奇偶校验码( 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 s ) 是一种基于 图模型和迭代译码的纠错编码方案，性能非常接近s h a n n o n 容量限，目译码算法 复杂度较低，近年来逐渐成为人们的研究热点。 本文对l d p c 码的代数构造及其迭代译码算法进行了深入研究，在以下几个方 面获得了关键性研究成果： 1 引入模g o l o m b 尺子概念构造了一类准循环l d p c 码。推导了t a n n e r 图的 围长全少是1 0 的必要条件。利用两个模g o l o m b 尺子给出了一种代数构造。结合 计算机搜搜，获得了具有大围长的短码长的准循环l d p c 码。对列重为2 的准循环 码，利用s i n g e r 完备差集给出了围长为1 2 的具有最短码长的l d p c 码。实验结果 表明我们构造的码性能优于p e g 算法构造的码。 2 对一些几何以及组合学构造的l d p c 码从不相交差集的角度作了统一描 述。这类码的特点是校验矩阵含有一个循环矩阵，或一列或一行校验矩阵。推导 了这类码对应的t a n n e r 图无4 环的充分必要条件。进一步利用w i l s o n 差族给出 了一类新的构造。仿真结果表明新构造的码在和积算法下性能良好。 3 基于二维最大距离可分码提出了构造准循环l d p c 码的一个一般性框架。 定义了两类码，它们的校验矩阵互为转置。然后利用二维广义r s 码给出了一种具 体构造。译码校验矩阵含有大量冗余行，而t a n n e r 图的围长至少是6 。就l d p c 码 而言，这类码具有相当客观的最小距离。我们进一步证明了现有文献中基于有限 域构造的多种准循环l d p c 码可以统一到上述框架中。实验结果表明新构造的码在 和积算法下性能良好。 4 基于大数投票的思想，提出了有限域上非二元l d p c 码的三种低复杂译码 算法。前两种是硬判决算法；第三种是基于可靠性的算法。这三种算法的一个关 键特征是t a n n e r 图传递的消息是一个域元素，这样致使校验节点的处理非常简单。 这些算法仅仅需要整数及有限域运算。复杂度分析和仿真结果联合表明，同 f f t q s p a 算法相比，所提出的算法针对基于有限几何，有限域和分圆陪集构造的 非二元l d p c 码取得了非常好的性能和复杂度之间的折衷。 关键词：低密度奇偶校验码准循环码迭代译码 a b s t r a c t b e i n gap o w e r f u lc l a s so fe r r o r - c o r r e c t i n gc o d e sb a s e do ng r a p h i c a lm o d e l sa n d i t e r a t i v ed e c o d i n ga l g o r i t h m 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 sh a v er e c e n t l y r e c e i v e dm u c ha u e n t i o nd u et ot h e i rc a p a c i t ya p p r o a c h i n gp e r f o r m a n c ea n dr e l a t i v e l y l o w d e c o d i n gc o m p l e x i t y t h i sd i s s e r t a t i o ni si n t e n d e dt oi n v e s t i g a t et h ea l g e b r a i cc o n s t r u c t i o na n dt h e i t e r a t i v ed e c o d i n ga l g o r i t h mo fl d p cc o d e s t h em a i nr e s u l t sa r es u m m a r i z e da s f o l l o w s 1 t h ec o n c e p to fm o d u l a rg o l o m br u l e ri si n t r o d u c e dt oc o n s t r u c tac l a s so f q u a s i c y c l i cl o w - d e n s i t yp a r i t y c h e c k ( q c l d p c ) c o d e s an e c e s s a r yc o n d i t i o nf o r t h e i rt a n n e rg r a p h st oh a v eag i r t ho fa tl e a s t10i sd e r i v e d w et h e np r o p o s ea c o n s t r u c t i o nm e t h o ds a t i s f y i n gt h ec o n d i t i o n ，w h o s ep a r i t y c h e c km a t r i xi ss p e c i f i e db y t w om o d u l a rg o l o m br u l e r s f o rj = 2 ，g i r t h - 12c o d e sw h o s el e n g t h sa c h i e v et h e m i n i m u ma r ec o n s t r u c t e db a s e do ns i n g e rp e r f e c td i f f e r e n c es e t s i m u l a t i o nr e s u l t s s h o wt h a tc o d e sc o n s t r u c t e d 2 w ep r e s e n tau n i f i e dv i e wo fs o m eg e o m e t r i c a l l yo rc o m b i n a t o r i a l l yc o n s t r u c t e d c y c l i ca n dq u a s i - c y c l i c ( q c ) l d p cc o d e si nt e r m so fd i s j o i n td i f f e r e n c es e t s ( d d s ) a c o m m o nf e a t u r eo ft h e s ec o d e si st h a tt h e i rp a r i t y - c h e c km a t r i c e sc o n s i s to fas i n g l e s p a r s ec i r c u l a n tm a t r i x ，o rac o l u m no rar o wo fs p a r s ec i r c u l a n tm a t r i c e s as u f f i c i e n t a n dn e c e s s a r yc o n d i t i o nf o rt h e i rt a n n e rg r a p h st oh a v en ol e n g t h 一4c y c l e si sd e r i v e d n e wc o n s t r u c t i o n sa r ef u r t h e rp r o p o s e db a s e do nw i l s o nd i f f e r e n c ef a m i l y ( d f ) ，a s p e c i a ld d s s i m u l a t i o nr e s u l t ss h o wt h a tt h en e w l yc o n s t r u c t e dc o d e sp e r f o r mw e l l u n d e rt h es u m - p r o d u c ta l g o r i t h m ( s p a ) 3 a g e n e r a l f r a m e w o r kf o r c o n s t r u c t i n gq c l d p c c o d e s b a s e do n t w o d i m e n s i o n a l ( 2 - d ) m a x i m u md i s t a n c es e p a r a b l e ( m d s ) c o d e si sp r o p o s e d t w o c l a s s e so fq c - l d p cc o d e sa r ed e f i n e d ，w h o s ep a r i t y c h e c km a t r i c e sa r et r a n s p o s e so f e a c ho t h e lw et h e nu s e2 一dg e n e r a l i z e dr e e d s o l o m o n ( g r s ) c o d e st og i v eac o n c r e t e c o n s t r u c t i o n t h ed e c o d i n gp a r i t y c h e c km a t r i c e sh a v eal a r g en u m b e ro fr e d u n d a n t p a r i t y c h e c ke q u a t i o n sw h i l et h e i rt a n n e rg r a p h sh a v e ag i r t ho fa tl e a s t6 t h e m i n i m u md i s t a n c e so ft h ec o d e sa r ev e r yr e s p e c t a b l ea sf a ra sl d p cc o d e sa r e c o n c e r n e d w ef u r t h e rs h o wt h a tm a n ye x i s t i n gc o n s t r u c t i o n so fq c - l d p cc o d e sb a s e d o nf i n i t ef i e l d si nt h el i t e r a t u r ec a nb eu n i f i e du n d e rt h i sc o n s t r u c t i o n 4 b a s e do nt h ei d e ao fp l u r a l i t y v o t i n g ，w ed e v e l o pt h r e el o w c o m p l e x i t y d 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 s t h ef i r s tt w o a l g o r i t h m sa r eh a r d - d e c i s i o nd e c o d i n ga l g o r i t h m s ；t h et h i r di sar e l i a b i l i t y b a s e d d e c o d i n ga l g o r i t h m ak e yf e a t u r eo ft h e s ea l g o r i t h m si st h a tt h em e s s a g ep a s s e di nt h e t a n n e rg r a p hi saf i e l de l e m e n t ，w h i c hl e a d st oa v e r ys i m p l ec h e c kn o d eu p d a t e t h e y r e q u i r eo n l yf i n i t ef i e l da n di n t e g e ro p e r a t i o n s c o m p l e x i t ya n a l y s i sa n ds i m u l a t i o n r e s u l t sj o i n t l ys h o wt h a t , c o m p a r e dt ot h e f a s tf o u r i e rt r a n s f o n nb a s e dq a r y s u m p r o d u c ta l g o r i t h m ( f f t - q s p a ) ，t h ep r o p o s e dd e c o d i n ga l g o r i t h m so f f e rg o o d t r a d e o f f sb e t w e e n p e r f o r m a n c ea n dc o m p l e x i t yf o rt h en o n b i n a r yl d p cc o d e s c o n s t r u c t e db a s e do nf i n i t eg e o m e t r i e s ，f i n i t ef i e l d sa n dc y c l o t o m i cc o s e t s k e y w o r d s ：l o w - d e n s i t yp a r i t y c h e c kc o d e s q u a s i - c y c l i cc o d e s i t e r a t i v e d e c o d i n g c h a p t e r 1 i n t r o d u c t i o n c h a p t e r1 i n t r o d u c t i o n 1 1t h eh i s t o r yo fc h a n n e lc o d i n g t h ef i e l do fc h a n n e lc o d i n gs t a r t e dw i t hc l a u d es h a n n o n s1 9 4 8l a n d m a r k p a p e r ”i nt h i sp a p e r ，s h a n n o ne s t a b l i s h e dt h ef a m o u sc h a n n e lc o d i n g t h e o r e m t h et h e o r e mi ss oc e n t r a lt h a ti th a sb e e nd i r e c t i n gt h ed e v e l o p m e n t o fc h a n n e lc o d i n g t h et h e o r e mi ss t a t e da sf o l l o w s f o rag i v e nn o i s yc h a n n e l ，t h e r ei saq u a n t i t ycc a l l e dc a p a c i t y ，i ft h e i n f o r m a t i o nr a t ers a t i s f i e st h a tr c a na r b i t r a r i l ys m a l fe r r o rr a t ei sn o ta c h i e v a b l e u n f o r t u n a t e l y ，t h ep r o o fo ft h ea b o v er e s u l ti sn o n c o n s t r u c t i v e ，m e a n i n g t h a ti tp r o v e so n l yt h ee x i s t e n c eo fs u c hac h a n n e lc o d ea n dad e c o d i n ga l - g o r i t h m t h e r e f o r e ，s i n c et h ea p p e a r a n c eo fs h a n n o n st h e o r e m ，t h eq u e s t h a sb e e no nf o rc o d e st h a th a v eac e r t a i ns t r u c t u r ea se g 1 i n e a r i t y m o r e - o v e r ，f i n d i n gp r a c t i c a ld e c o d i n ga l g o r i t h m sm a t c h e dt ot h e s ec o d e si se q u a l l y i m p o r t a n t t h ec h a n n e lc o d e sc a nb eb r o a d l yc l a s s i f i e di n t ot w oc a t e g o r i e s ：b l o e k c o d e sa n dc o n v o l u t i o n a lc o d e s t h ef i r s tl i n e a rb l o c kc o d e sw e r ed i s c o v e r e d b yh a m m i n gi nt h el a t e1 9 4 0 s ，w h i c hc a nc o r r e c ts i n g l ee r r o r s u b s e q u e n t l y , g o l a yc o d e s ，r e e d m u l l e r ( r m ) c o d e sw e r ed i s c o v e r e di nt h e1 9 5 0 s t h e “b i gb a n g ”w a st h ei n v e n t i o no fb o s e - c h a u d h u r i h o c q u e n g h e m ( b c h ) a n d r e e d s o l o m o n ( r s ) c o d e si nt h r e ei n d e p e n d e n tp a p e r si n1 9 5 9a n d1 9 6 0 t h e nt h ef a m o u sb e r l e k a m p - m e s s a yd e c o d i n ga l g o r i t h mf o rt h e s ec o d e sw a s d e v e l o p e di nt h el a t e1 9 6 0 s f u r t h e rd e v e l o p m e n t si na l g e b r a i cc o d e si n c l u d et h ea l g e b r a i cg e o m e t r y ( a g ) c o d e si nt h e1 9 7 0 s ，a n dn e wd e c o d i n g a l g o r i t h m sf o rr sc o d e sp r o p o s e db ys u d a na n dg u r u s w a m ia n dk o e t t e r 2c o n s t r u c t i o na n dd e c o d i n go fl d p cc o d e s a n dv a r d y 0 nt h eo t h e rh a n d c o n v o l u t i o n a lc o d e sw e r ei n v e n t e db ve l i a s i n1 9 5 5 t h ef i r s td e c o d i n ga l g o r i t h mw a si n v e n t e db yw b z e n c r a f ti n1 9 6 1 c a l l e ds e q u e n t i a ld e c o d i n g l a t e ri n1 9 6 3 f a n op r o p o s e da ni m p r o v e ds e - q u e n t i a ld e c o d i n g s u b s e q u e n t l y , m a s s e yp r o p o s e dav e r ys i m p l ed e c o d i n g m e t h o d c a l l e dt h r e s h o l dd e c o d i n g 1 9 6 7 v i t e r b ii n v e n t e dt h ef a m o u sv i t e r b i a l g o r i t h m ( v a ) i tw a sq u i c k l yr e c o g n i z e db yf o r n e yt h a tt h ev aw a sa c - t u a l l ya no p t i m u md e c o d i n ga l g o r i t h m i n1 9 7 4 ，b a h l ，c o c k e ，j e l i n e k ，a n d r a v i vp u b l i s h e da na l g o r i t h mn o wc a l l e dt h eb c j ra l g o r i t h m i n1 9 9 3 ，a tt h ei e e ei n t e r n a t i o n a lc o n f e r e n c eo nc o m m u n i c a t i o n sf i c c ) i ng e n e v a ，s w i t z e r l a n d ，b e r r o u ，g l a v i e u x ，a n dt h i t i m a i s h i m as t u n n e dt h e c o d i n gr e s e a t d lc o m m u n i t yb yi n t r o d u c i n gan e wc l a s so f t u r b oc o d e s ” c o m m e n t st ot h ee f f e c to f “i tc a n tb et r u e ；t h e ym u s th a v em a x t ca3d b e r r o r w e r ew i d e s p r e a d h o w e v e r ，w i t h i nt h en e x t y e a rv a r i o u sl a b o r a t o r i e s c o n f i r m e dt h e s ea s t o n i s h i n gr e s u l t s a n dt h e “t u r b or e v o l u t i o n ”w a sl a u n c h e d s h o r t l yt h e r e a f t e r ，g a l l a g e r sl 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 e r er e - d i s c o v e r e di n d e p e n d e n t l yb vm a c k a ya n ds p i e l m a n t u r b oc o d e sa n dl d p c c o d e sh a v eb e e ns h o w nt ob et w oc l a s s e so fc a p a c i t y - a p p r o a c h i n gc o d e s a s c o s t e l l oa n df o r n e yp o i n t e do u ti n 2 】) f i f t yy e a r so fe f f o r ta n di n v e n t i o n h a v ef i n a l l yp r o d u c e dc o d i n gs c h e m e st h a tc l o s e l ya p p r o a c hs h a n n o n ，sc h a n n e l c a p a c i t yl i m i to nm e m o r y l e s sc o m m u n i c a t i o nc h a n n e l s 1 2 l o w - d e n s i t yp a r i t y - c h e c kc od e s l d p cc o d e sw e r ei n v e n t e di n1 9 6 0b yr g a l l a g e r t h e yw e r el a r g e l yi g n o r e d o v e r3 0d e c a d e su n t i lt h ed i s c o v e r yo ft u r b oc o d e si n1 9 9 3 s i n c et h e n ，l d p c c o d e sh a v ee x p e r i e n c e dar e n a i s s a n c ea n da r en o wo n eo ft h em o s ti n t e n s e l y s t u d i e da r e a si nc o d i n g l d p cc o d e sa r ed e f i n e db yas p a r s ep a r i t y - c h e c km a t r i x i nt e r m so f d e c o d i n g ，i ti sm o r ec o n v e n i e n tt od e s c r i b et h ec o d e sb yt h et a n n e rg r a p h t a n n e rg r a p h so fl d p cc o d e sa r eb i p a r t i t eg r a p h sw i t hv a r i a b l en o d e so n o n es i d ea n dc o n s t r a i n tn o d e so nt h eo t h e r e a c hv a r i a b l en o d ec o r r e s p o n d s t oab i t ，a n de a c hc o n s t r a i n tn o d ec o r r e s p o n d st oo n ep a r i t y - c h e c kc o n s t r a i n t o nt h eb i t sd e f i n i n gac o d e w o r d t h ed e c o d i n g so fl d p cc o d e sc a nb e i n t e r p r e t e da st h em e s s a g ep a s s i n gi nt h et a n n e rg r a p h s b a s e do nt h e i rc o n s t r u c t i o nm e t h o d s ，l d p cc o d e sc a nb er o u g h l yc l a s s i - f l e di n t ot w oc a t e g o r i e s ：r a n d o ml d p cc o d e sa n ds t r u c t u r e dl d p cc o d e s w e i i k n o w nc o n s t r u c t i o n so fr a n d o ml d p cc o d e si n c l u d ep r o g r e s s i v e - e d g e g r o w t h ( p e g ) a l g o r i t h ma n da p p r o x i m a t ec y c l ee x t r i n s i cm e s s a g ed e g r e e ( a c e ) a l g o r i t h m w r e l l - k n o w nc o n s t r u c t i o n so fs t r u c t u r e dl d p cc o d e si n c l u d ef i n i t eg e o m e t r ym e t h o d ，f i n i t ef i e l dm e t h o da n db a l a n c e di n c o m p l e t e c h a p t e r l i n t r o d u c t i o n 3 b l o c kd e s i g n ( b i b d ) m e t h o d ，e t c f o rl a r g ec o d el e n g t h s ，i ti sw i t hh i g h p r o b a b i l i t yt h a tr a n d o ml d p cc o d e sp e r f o r mv e r yw e l l h o w e v e r ，t h e yh a v e s o m ed e f i c i e n c i e si nt e r m so fe n c o d i n ga n dd e c o d i n g 0 dt h eo t h e rh a n d f o r s m a l l t o - m o d e r a t el e n g t h s w e l l d e s i g n e ds t r u c t u r e dl d p cc o d e sc a np e r - f o r ma sw e l la so re v e nb e t t e rt h a nr a n d o ml d p cc o d e s t h ei n h e r e n t s t r u c t u r a lp r o p e r t i e sl e n dt h e m s e l v e st of r i e n d l yi m p l e m e n t a t i o n s 1 3o u t l i n eo ft h et h e s i s t h et h e s i sm a i n l yc o n c e r n st h ec o n s t r u c t i o n so fb i n a r ys t r u c t u r e dl d p c c o d e sa n dt h ed e c o d i n g so fn o n b i n a r yl d p cc o d e s t h er e s tc h a p t e r sa r e o r g a n i z e da sf o l l o w s i nc h a p t e r2 ，w ei n t r o d u c ean e wc o n c e p t ，m o d u l a rg o l o m br u l e r ，t o c o n s t r u c tl a r g eg i r t hq u a s i c y c l i c ( q c ) 一l d p cc o d e s s o m en e c e s s a r ya n d o r s u f f i c i e n tc o n d i t i o n sa b o u tg i r t ha r ed e r i v e d i nc h a p t e r3 ，w eu s ed i s j o i n td i f f e r e n c es e tt og i v eau n i f i e dv i e wo fs o m e g e o m e t r i c a l l yo rc o m b i n a t o r i a l l yc o n s t r u c t e dc y c l i ca n dq cl d p cc o d e s a v a i l a b l ei nt h el i t e r a t u r e t h ew i l s o nd i f f e r e n c ef a m i l yi si n t r o d u c e dt og i v e an e wc o n s t r u c t i o n i nc h a p t e r4 ，w ep r o p o s ea g e n e r a lf r a m e w o r kf o rc o n s t r u c t i n gq c l d p c c o d e sb a s e do nt w o - d i m e n s i o n a l ( 2 一d ) m a x i m u md i s t a n c es e p a r a b l e ( m d s ) c o d e s w bf u r t h e rs h o wt h a tm a n ye x i s t i n gc o n s t r u c t i o n so fq c l d p cc o d e s b a s e do nf i n i t ef i e l d si nt h el i t ( u a t u r ec a nb eu n i f i e du n d e rt h i sc o n s t r u ( ：t i ( ) n i nc h a p t e r5 ，w ed e v e l o pt h r e el o w - c o m p l e x i t yd e c o d i n ga l g o r i t h m sf o r n o n b i n a r yl d p cc o d e sb a s e do nt h ei d e ao fp l u r a l i t yv o t i n g t h e ye x h i b i t g o o dt r a d e - o f f sb e t w e e np e r f o r m a n c ea n dc o m p l e x i t y 4c o n s t r u c t i o na n dd e c o d i n go fl d p cc o d e s c h a p t e r 2 q c l d p cc o d e sb a s e do nm o d u l a rg o l o m br u l e r s 5 c h a p t e r2 q c - l d p cc o d e sb a s e do n m od u l a rg o l o m br u l e r s t h i sc h a p t e ra i m st oc o n s t r u c tq u a s i c y c l i c ( q c ) 一l d p cc o d e sw i t hl a r g e g i r t h t h ec o n c e p to fm o d u l a rg o l o m br u l e ri si n t r o d u c e dt oc o n s t r u c ta c l a s so fq c l d p cc o d e s ，w h o s ep a r i t y - c h e c km a t r i c e sc o n s i s to faj l a r r a y o fc i r c u l a n tp e r m u t a t i o nm a t r i c e s t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s a n e c e s s a r yc o n d i t i o nf o rt h et a n n e rg r a p h st oh a v eag i r t ho fa tl e a s t 1 0i sd e r i v e d ，w h i c hi sa l s oas u f f i c i e n tc o n d i t i o nf o rt h eg i r t ht ob e a tl e a s t6 f o rj = 2 ，t h ec o n d i t i o nf o r m sas u f f i c i e n ta n dn e c e s s a r y c o n d i t i o nf o rt h eg i r t ht ob e1 2 ac o d ec o n s t r u c t i o ns a t i s f y i n gt h ea b o v en e c e s s a r yc o n d i t i o ni s p r o - p o s e d t h ep a r i t y - c h e c km a t r i c e sh a v eav e r ys i m p l ed e s c r i p t i o n ，t h r o u g h t w om o d u l a rg o l o m br u l e r s f o rj = 2a n dl 一1b e i n gap o w e ro fap r i m e ，g i r t h 一1 2q c l d p c c o d e sw i t hm i n i m u mp o s s i b l el e n g t h sa r ec o n s t r u c t e db a s e do ns i n g e r p e r f e c t ( t i f f e r e n c es e t as p e c i a lm o d u l a rg o l o m br u l e r 2 1r e s e a r c hb a c k g r o u n d b a s e do nt h e i rc o n s t r u c t i o nm e t h o d s ，l d p cc o d e sc a nb er o u g h l yc l a s s i f i e d i n t ot w oc a t e g o r i e s ：r a n d o m - l i k ec o d e sa n ds t r u c t u r e dc o d e s e x p e r i m e n t a l s t u d i e ss h o wt h a tc a r e f u l l yd e s i g n e ds t r u c t u r e dl d p cc o d e sc a np e r f o r ma s w e l la so re v e nb e t t e rt h a nr a n d o m l yc o n s t r u c t e dl d p cc o d e sa ts h o r tt o m o d e r a t el e n g t h s1 6 ，7 ia n da p p r o a c hs h a n n o nl i m i tf o rh i g h r a t ec o d e sa t l o n gl e n g t h s1 8 i c o u p l e dw i t ht h e i ri m p l e m e n t a t i o na d v a n t a g e s ，s t r u c t u r e d l d p cc o d e sh a v ea t t r a c t e dal o to fa t t e n t i o ni nb o t ha c a d e m i ca n di n d u s t r i a l c i r c l e s t h ed e f i n i n gp a r i t y - c h e c km a t r i xf o ras t r u c t u r e dl d p cc o d ei sm a d eu p o faj la r r a yo fs u b m a t r i c e s ， h = a 0 ，0 a 1 ，0 a j 一1 ，0 a 0 ，1 a 1 ，1 a j 一1 ，1 a 0 ，l 一1 a 1 l 一1 a j 一1 ，l 一1 ( 2 1 ) w h e r eja n