（通信与信息系统专业论文）具有简单编码结构的ldpc码的研究.pdf

摘要 摘要 本论文主要研究了几种具有简单编码结构的低密度奇偶校验( 1 0 w d e n s i 霹 p a r i t y c h e c k ，l d p c ) 码，包括准循环l d p c ( q u a s i - c y c l i cl d p c ，q c - l d p c ) 码、级联 z 字( c o n c a t e n a t e dz i g z a g , c z ) 码以及级联简单奇偶校验f c o n c a t e n a t e dm n # e p a r i t y - c h e c k ，c s p c ) 码等。这些码无论扶编码到译码都利于硬件实现，具有很强的 实用价值。 第一章介绍了研究具有简单编码结构的l d p c 码的背景及意义，并回顾了 l d p c 码的基础知识，包括定义、构造、编码、译码以及性麓分析。 第二章提出了两种新的构造准循环或循环l d p c 码的方法。第一种方法通过 随机搜索部分平衡不完全区组设计的基本向量，然后通过循环移位产生其他的关 联商量。利用该方法构造准循环l d p c 鹦比传统的代数或几何方法更为灵活。第 二种方法利用对称平衡不完全区组设计构造准循环l d p c 码，该码具有如下两个 特点：生成矩阵和校验矩阵都是稀疏且循环的，易于编码和译码；可实时地构造 凡乎任何码率的码，是一种速率兼容码。最后提出了一种有效的基于环搜索的准 循环l d p c 码真实最小距离的计算方法。 第三章研究线性交织器在级联z 字码中的应用。利用修正的“总距离 概念 分析和优化缀联z 字码：推导了输入重量分别秀奇数和偶数的最小总距离之间的 关系；证明了最小总距离加上输入重量是最小距离一个紧的下界；接着提出了有 效的计算最小环长的方法，包括计算信息序列中产生的最小环长以及信息序列与 奇偶校验亭列之阉产生的最小环长；然霜提出了一种有效酶基于环搜索计算线性 交织器下级联z 字码最小距离的方法。最后基于以上结果，构造出了几个使用线 性交织器的具有较大的最小距离的级联z 字码。仿真表明，这些码具有非常优异 的性能。 第四章首先研究了级联简单奇偶校验码与q a m ( q u a d r a t u r ea m p l i t u d e m o d u l a t i o n ) 调制的联合优化。先通过分析加q a m 调制后的级联简单奇偶校验码 的近似联合雾，发现增大携带校验位的符号的欧式距离并相应减小携带信息位的 符号的欧式距离，能够提高整个编码调制方案误码率性能。再通过计算近似联合 界褥到了最优的校验位和信息位之间的功率分配。仿真表明，联合优化后的性能 要远好于未优化的性能。其次研究了通雳的格雷码映射的m - p a m ( m - a r yp u l s e 摘要 a m p l i t u d em o d u l a t i o n ) 、m - p s k ( m - a r yp h a s es h i f tk e y i n g ) 调制以及方m - q a m ( m - a r y q u a d r a t u r ea m p l i t u d em o d u l a t i o n ) 的软判决问题，提出了一种通用翡软判决方法。 与传统的方法相比，所提方法在不损失性能的前提下能大幅度地降低软判决的复 杂度。 第五章总结全文，并指出了下一步研究工作。 关键词：低密度奇偶校验码，准循环低密度奇偶校验码，级联z 字码，级联简单 奇偶校验码，编码调制 l l a b s t r a c t a b s t r a c t t h et h e s i sf o c u s e so nt h er e s e a r c ho fs o m es i m p l e - e n c o d i n gl d p c ( 1 0 w d e n s i t y p a r i t y c h e c k ) c o d e s ，i n c l u d i n gq u a s i - c y c l i cl d p cc o d e s ，c o n c a t e n a t e dz i g z a gc o d e s ， a n dc o n c a t e n a t e ds i n g l e p a r i t y - c h e c kc o d e s ， w h i c ha r e s i m p l e t o p r a t i c a l i m p l e m e n t a t i o n i nc h a p t e r1 ，b a c k g r o u n da n ds i g n i f i c a n c eo fr e s e a r c h i n go ns i m p l e - e n c o d i n g l d p cc o d e sa r ef i r s t l yi n t r o d u c e d t h e nt h ee l e m e n t a r yk n o w l e d g eo fl d p cc o d e s ， i n c l u d i n gd e f i n i t i o n , c o n s t r u c t i o n , e n c o d i n g , d e c o 豳ga n dp e r f o r m a n c ea n a l y s i s ，e t c a r ei n t r o d u c e d i nc h a p t e r2 ，t w on e wt e c h n o l o g i e st oc o n s t r u c tq u a s i ，c y c l i co rc y c l i cl d p c c o d e sa r ep r o p o s e d t h ef i r s ti st os e a r c hb a s ei n c i d e n c ev e c t o r so fp a r t i a l l yb a l a n c e d i n c o m p l e t eb l o c kd e s i g na tr a n d o m ，t h e nt h er e s ti n c i d e n c ev e c t o r sa r ea b t a i n e db y c y c l i c a l l ys h i f t i n gt h e s eb a s ei n c i d e n c ev e c t o r s i t i sm o r ef l e x i b l et oc o n s t r u c t q u a s i - c y c l i cl d p cc o d e st h a nt r a d i t i o n a lg e o m e t r i co ra l g e b r a i cm e t h o d s a n o t h e ri s b a s e do ns y m m e t r i cb a l a n c e di n c o m p l e t eb l o c kd e s i g n t h ec h a r a c t e r i s t i c so ft h e s e c o d e si n c l u d e ：b o t hg e n e r a t o rm a t r i c e sa n dp a r i t y - c h e c km a t r i c e sa r es p a r s ea n dc y c l i c ， w h i c ha r es i m p l et oe n c o d ea n dd e c o d e ；a l m o s ta r b i t r a r yr a t ec o d e sc a nb ee a s i l y c o n s t r u c t e do n - l i n e ，s ot h e ya r er a t e - c o m p a t i b l ec o d e s f i n a l l y , a ne f f i c i e n tc y c l e - b a s e d m e t h o di sp r o p o s e dt oc o m p u t et h er e a lm i n i m u md i s t a n c e so fq u a s i c y c l i cl d p c c o d e s i nc h a p t e r3 ，a l la p p l i c a t i o no fl i n e a ri n t e r l e a v e r si nc o n c a t e n a t e dz i g z a gc o d e si s i n v e s t i g a t e d am o d i f i e dc o n e e p ts oc a l l e d “s u m m a r yd i s t a n c e i se m p l o y e dt oa n a l y z e a n do p t i m i z et h el i n e a ri n t e r l e a v e r s f i r s t l y , t h er e l a t i o nb e t w e e nt h em i n i m u m s u m m a r yd i s t a n c eo fe v e ni n p u tw e i g h ta n do d di n p u tw e i g h ti sd e r i v e d i ti sp r o v e d t h a tt h em i n i m b n lm o d i f i e ds u m m a r yd i s t a n c ep l u si n p u tw e i g h ti sat i g h tl o w e rb o u n d o ft h em i n i m u mh a m m i n gd i s t a n c e t h e n , a l le f f i c i e n tm e t h o dt oc o m p u t et h eg i r t h a m o n gi n f o r m a t i o ns e q u e n c e sa n dt h e 舀劬b e t w e e ni n f o r m a t i o ns e q u e n c e sa n dp a r i t y s e q u e n c e s i so b t a i n e d i nt h ef o l l o w i n g , a ne f f i c i e n tc y c l e - b a s e dm e t h o di sp r o p o s e dt o c o m p u t e t h er e a lm i n i m u md i s t a n c e so fq u a s i c y c l i cl d p cc o d e s 。f i n a l l y , b a s e do nt h e i i i a b s t r a c t r e s u l t s ，s e v e r a lg o o dc o n c a t e n a t e dz i g z a gc o d e sw i t hl a r g em i n i m u md i s t a n c e sa r e g i v e n s i m u l a t i o nr e s u l t ss u p p o r tt h eg o o dp e r f o r m a n c eo ft h e s ec o n c a t e n a t e dz i g z a g c o d e s i nc h a p t e r4 ，j o i n td e s i g no fc o n c a t e n a t e ds i m p l ep a r i t y - c h e c kc o d ea n dq a m ( q u a d r a t u r ea m p l i t u d em o d u l a t i o n ) m o d u l a t i o ni sf i r s t l ys t u d i e d b ya n a l y z i n gt h e a p p r o x i m a t eu n i o nb o u n do nc o n c a t e n a t e ds i m p l ep a r i t y - c h e c kc o d ec o n s i d e r e dq p 州 m o d u l a t i o n , i ti sf o u n dt h a te n l a r g i n gt h ee u c l i d e a nd i s t a n c eb e t w e e nt h ep a r i t yb i t s a n dr e d u c i n gt h ed i s t a n c eb e t w e e nt h ei n f o r m a t i o nb i t sc a n i m p r o v et h eb e r ( b i t e r r o r r a t i o ) p e r f o r m a n c eo ft h ec o d e dm o d u l a t i o ns c h e m e a tl a s t , t h eo p t i m u mp o w e r d i s t r i b u t i o nb e t w e e nt h ep a r i t yb i t sa n dt h ei n f o r m a t i o nb i t si so b t a i n e db yc o m p u t i n g t h ea p p r o x i m a t eu n i o nb o u n d 。a n ds i m u l a t i o nr e s u l t sd e m o n s t r a t et h ep r o p o s e d s c h e m e p e r f o r m sr e m a r k a b l y b e t t e rt h a nt h et r a d i t i o n a l o n e s e c o n d l y , a l o w - c o m p l e x i t ys o f t - d e c i s i o nt e c h n i q u ei sp r o p o s e df o rp o p u l a r 研a ym a p p i n g m o d u l a t i o ns c h e m e s ，i n c l u d i n gm - p a m ( g - a r yp u l s ea m p l i t u d em o d u l a t i o n ) ，m - p s k ( m - a r yp h a s e s h i f tk e y i n g ) a n d s q u a r em - q a m a r yq u a d r a t u r ea m p l i t u d e m o d u l a t i o n ) c o m p a r e dw i t ht h et r a d i t i o n a lm e t h o d ，t h ep r o p o s e dt e c h n i q u ec a l l e f f e c t i v e l yr e d u c et h ec o m p u t a t i o n a lc o m p l e x i t yw i t h o u ta n yp e r f o r m a n c ed e g r a d a t i o n 。 c h a p t e r5c o n c l u d e st h et h e s i sa n di n d i c a t e st h ef u t u r ew o r k k e yw o r d s ：l o w - d e n s i t yp a r i t yc h e e k ( l d p c ) c o d e s ，q u a s i c y c l i cl d p c ( q c - l d p c ) c o d e s ， c o n c a t e n a t e d z i g z a gc o d e s ， c o n c a t e n a t e ds i n g l ep a r i t y - c h e c kc o d e s ，c o d e d m o d u l a t i o n i v 黼液露录 图i - 1 图l 。2 瑟l 。羹 图l 罅 图l 霆l 堪 图l 。7 图豁l 瑟2 - 2 图2 。3 图 委2 。s 圈2 - 6 图 霞囊蜷 图2 - 9 图2 。l 爨2 。董熏 图3 。l 图3 。2 惑娄堪 图3 罅 图3 岁 黧啦董 图舡2 熏描 圈零罐 图舢5 餮鲻 图表翼录 行列藏分别为4 和2 的l d p c 码奇偶校验矩阵。4 图1 1 套偶较验矩簿对应的t a n n e r 图4 基予g a l l a g e r 方法祷逮嚣鬻鹅棱验篷薄一5 z 字码编码器。6 级联z 字码编码器。6 缀袋s p c 黎羁器一一。7 具有避似下三角孵式的奇偶棱验矩阵。1 5 基本内量搜索过程2 8 基本憩塞篱蠡量一一簦 ( 9 3 6 0 ，8 1 9 0 ) l d p c 码的误码率性能。3 0 0 0 6 6 , 1 5 3 5 ) l d p c 码豹误码攀性能。3 2 霉系统l d p c 羁端译褥示意薰一。 几种方法构造l d p c 码的误粥率比较。3 9 几种方法构造l d p c 码韵误蜮窜比较3 9 奇霭校验矩薄魏夔舞2 獒l d p c 璃蘸饔长与褒享魏关系，霉董 环的形成。4 2 准循环p c 码麴环豹循环移位特性。4 3 难褥环l d p c 褥煞f e r 整蔻察遥鬟联舍莽稻 信息序列与校验序列之间产擞长为6 环时情况。5 6 二维缀联z 字码的搜索距离麴过程。5 8 三个鹈麓俦寞误霹奉注囊帮邋儆联含葬蕊麓一一酾 级联麓字码与采用p e g 方法构造的l d p c 码的误码率比较6 2 线 生交织器的级联z 字码与8 0 2 。1 6 e 中的黼种l d p c 码的误帧攀比较6 3 16 - q a m 重壅委一一一繇 不同儒噪比下的联合界与 乏间关系。6 9 缓联s p c 霹与1 6 。q a m 囊含勰链蓑老羧一，鞠 二避制反射方法构造格雷礴。程 格雷鹕映射8 - p a m 星座图。7 3 饔霉鹦映舞1 6 - p a m 薅鬻，美系一箨 、，i i i 图表目录 图4 7格雷码映射8 - p s k 调制中对和s l f 献g 7 5 图禾81 6 p s k 以及6 4 一q a m 调制时采用不同软判决方法的误码率比较7 8 图4 - 9超离阶调制时采用不同软判决方法的误码率性能比较7 9 表2 1两个准循环l d p c 码的最小距离、对应的码字数以及计算时间4 5 表3 。l 计算最小距离及所需时间6 0 表3 2三个码率为1 2 码的角度系数、最小距离以及最小环长6 l 表4 _ l几种方法计算一个m - p a m 符号需要的复杂度比较7 6 表4 - 2几种软判决方法计算一个m - p s k 符号所需的复杂度比较7 7 i x 缩略词表 缩略词表 瞅ap o s t e r i o rp r o b a b i l i t y 蜃验概率 a w g na d d i t i v ew h i t eg a u s s i a nn o i s e 加性向高斯噪声 b e c b i n a r ye r a s u r ec h a n n e l 二进制删除信道 b 瓢b i te r r o rr a t i o 误码率 8 笺8 db a l a n c e di n c o m p l e t eb l o c kd e s i g n 平衡不完全区缰设计 b i c mb i t - i n t e r l e a v e dc o d e dm o d u l a t i o n 比特交织编码调制 b p b e l i e f p r o p o g a t i o n 置信传播 b p s k b i n a r yp h a s es h i f tk e y i n g 二进裁摺位频移键控 b s c b i n a r ys y m m e t r i cc h a n n e l 二迸制对称信道 c y c l i cs y m m e t r i cp a r t i a l l yb a l a n c e di n c o m p l e t e循环对称部分不完全区组设 c s p b u d b l o c kd e s i g n计 c 瓣 c o n d i t i o n a lw e i g h te n u m e r a t i n gf u n c t i o n条箨重量救举函数 c s p cc o n c a t e n a t e ds i n g l ep a r i t y c h e c k 级联简荤奄偶校验码 c zc o n c a t e n a t e dz i g z a g 级联z 字 d e d e n s i t ye v o l u t i o n 密度进化 d ￥t pd i t h e r e dr e l a t i v ep e r m u t o r 搀动相关畿换器 d s l d i g i t a ls u b s c r i b e rl i n e 数据用户线 d v b d i g i t a lv i d e ob r o a d c a s t i n g 数字电视广播系统 e ge u c l i d e a ng e o m e t r i e s 欧式几何 溆f l a m ee r r o rr a t i o 误顿率 g ag a u s s i a na p p r o x i m a t i o n 高斯近似 g c d g r e a t e s tc o m m o nd i v i s o r 最大公倍数 g f g a l o i sf i e l d 有限域 i l i 灏匿f i n p u t - r e d u n d a n c yw e i g h te n u m e r a t i n gf u n c t i o n 输入冗余鬟蓬枚举函数 i 肋p c l o w - d e n s i t yp a d t y - e h c c k 低密度奇偶校验 l i j 良 l o g l i k e l i h o o dr a t i o 对数似然比 髓毛e m u l t i l e v e lc o d i n g多层编码 张、m p u ka m p l i t u d em o d u l a t i o n 脉冲幅度调制 p b m d p a r t i a l l yb a l a n c e di n c o m p l e t eb l o c kd e s i g n 部分平衡不完全区组设计 p e g p r o g r e s s i v ee d g eg r o w t h 逐步边缘增长 p g p r o j e c t i v eg e o m e t r i e s投影冗褥 p s k p h a s es h i f tk e y i n g 相位频移键控 q a m q u a d r a t u r ea m p l i t u d em o d u l a t i o n 正交幅度调制 q cq u a s i c y c l i c 准循环 ) ( 鳙硌运裘 q p p iq u a d r a t i cp e r m u t a t i o np o l y n o m i a li n t e r l e a v e r s ：7 欠黻换多项式黧燃器 爻焱鞭涔a e c u m u | a t e 重笺然驭玛 瑟r e e d - s o l o m o n至德撬罗羹 s b i b d s y m m e t r i cb a l a n c e di n c o m p l e t eb l o c kd e s i g n 对猕铲衡不完全隧撤设计 s ds u m m a r yd i s t a n c e 总飚离 s 妻 襄 s i g n a l 蘸s 惑r a t i o 蓥臻瓣 s 嚣氅 s u m - p r o d u c ta l g o r i t h m 释瓣瓣法 s p e s i m p l ep a r i t y c h e c kc o d e s 简蚺谢偶校验码 枝蚤dt r e l l i sc o d e dm o d u l a t i o n格粥调制 黎it e r r e s t r i a li n t e r a c t r em u l f i s e r v i c ei n f i a 壁a 3 1 c t u r e鏊囊交互袁多曼努褥褡系缝 u p u n i f o r m l ym o s tp o w e r f u l 一黢鬣优 x l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成栗。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书两健震过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说甓算表示谢意。 签名：生她霹期：研，舞瑚 f 关于论文使用授权的说明 本学位论文瘁者完全了解电子科技大学有关保留、使耀学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阕和借阕。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 醐：7 阴柚 第一章绪论 第一章绪论帚一早三：百t 匕 1 1l d p c 码研究的背景及意义 早在19 6 2 年，r gg a l l a g e r 就提出了低密度校验码( 1 0 w d e n s i t yp a r i t y - c h e c k c o d e ，l d p c ) 的概念，给出了规则l d p c 码的构造方法、编译码算法以及最小汉明 距离分析和译码算法的性能分析【1 】【2 1 。但由于当时的条件限制，长的l d p c 码的 编译码器硬件几乎不可能实现，导致l d p c 码默默无闻了几十年，一直到上世纪 九十年代中后期，这种情况才发生了改变。在深入研究t u r b o 码原理的过程中， 1 9 9 6 年m a c k a y 、n e a l 和s p i e l m a n 等重新研究了l d p c 码【3 4 1 ，几乎同时发现 g a l l a g e r 在1 9 6 2 年提出的l d p c 码也是一个好码，具有接近香农限的性质同时具 有更低的线性译码复杂度，从而掀起了l d p c 码的研究热潮。 近年来，l d p c 码很多研究成果表明l d p c 码是一类性能优异的好码【5 】【6 】。基 于l d p c 码的编码方案已经被下代卫星数字视频广播标准d v b s 2 采纳【。7 1 。在 我国地面数字电视传输标准建设备选方案中，广电总局广科院提出的 t i m i ( t e r r e s t r i a li n t e r a c t i v em u l t i s e r v i c ei n f r a s t r u c t u r e ) ，方案性能较好，该方案最大 的技术亮点就是采用了l d p c 码信道编码技术。虽然由于l d p c 码再发现比较晚， 因此与第三代移动通信标准失之交臂，但是基于l d p c 码的编码方案极有可能成 为下一代移动通信系统的应用方案【8 】。 我们知道，为了追求高的编码增益，必需加长码的长度，对于这样长的码， 采用随机构造法可以构造出很好的奇偶校验矩阵，但由于码的随机性，要存储这 么大的一个奇偶校验矩阵和生成矩阵将是件非常困难的事，特别是现代移动通信 带宽越来越宽，对编译码的计算速度和延迟要求非常苛刻，必需寻找能够线性编 码的码，才能使l d p c 码真正在实际中得到应用。因而本论文研究的课题非常有 实际的应用价值和意义。 对于易编码的l d p c 码的构造，t j r i c h a r d s o n 等提出一种叫做g r e e d y 的算 法【9 】，在很大程度上减轻了随机构造的l d p c 码在编码上的巨大运算量需求和存 储量需求。而除此之外，常见的传统的具有简单编码结构的l d p c 码的构造分为 两大类： 电子科技大学博士学位论文 一类是准循环l d p c ( q u a s i c y c l i cl d p c ，q c l d p c ) 码，这类码的基本的特点 是他们的奇偶校验阵由许多循环子矩阵构成的，在编码上能够采用循环移位寄存 器来完成，因而大大降低了编码的复杂度和存储空剐。o 】。准循环l d p c 码的构造 方法包括yk o u 等提出的基于有限域( f i n i t eg e o m e t r i e s ) 上的欧氏几何( e u c l i d e a n g e o m e t r i e s ，e g ) 和投影几何( p r o j e c t i v eg e o m e t r i e s ，p g ) 的方法【6 】【1 1 】【1 2 】，b a m m r r 等 提出的基于平衡不完全区组设计( b a l a n c e di n c o m p l e t eb l o c kd e s i g n ，b i b d ) i 拘方法 【1 3 】【1 4 】，b v a s i c 等提出的基于组合数学的方法 1 5 】，s l i l l 等提出的采用循环分解 ( c i r c u l a n td e c o m p o s i t i o n ) 技术的方法【1 6 1 ，以及m p c f o s s o r i e r 提出的利用循环置 换矩阵( c i r c u l a n tp e r m u t a t i o nm “c e s ) 的方法【1 7 j 【1 8 】。另外还有从光正交码( o p t i c a l o r t h o g o n a lc o d e s ) 等设计准循环l d p c 码【1 9 】【2 4 1 。准循环l d p c 码除了编码简单， 还由于这类码大都采用严格的代数方法构造，因而某些码的基本参数能够得到保 证，比如最小环长至少为6 等。 另外一个大类就是所谓半随机l d p c ( s e m i r a n d o ml d p c ) 石l - q 2 5 1 ，这类码特点 就是他们的奇偶校验矩阵可以分解成两个子矩阵，而其中有一个是双对角矩阵， 从而编码时可以采用类似卷积码的编码方式，从而大大地减少了编码的复杂度和 存储空间。而根据奇偶校验矩阵中另一个子矩阵设计的不同，半随机l d p c 码又 可分成几大类。一类叫做重复累积( r e p e a ta c c u m u l a t e ，r a ) 码t 2 6 】- 1 2 9 】，最早由d d i v s a l a r 提出。该码的编码过程如下：先是进行重复码的编码，然后再进行交织， 再进行只有两状态的卷积编码，最后得到就是所谓重复累积码。如果对重复累积 码的奇偶校验矩阵中非双对角矩阵进行非规则优化，则优化后就是非规则重复累 积( i r r e g u l a rr e p e a ta c c u m u l a t e ，瓜a ) 码【3 0 】【3 l 】。另一类叫做级联z 字( c o n c a t e n a t e d z i g z a g , c z ) 码【3 2 】，他是通过并行级联多个z 字码和交织器组成的，而每一个z 字 码又是由一个简单奇偶校验( s i n g l ep a r i t y - c h e c k ，s p c ) 硒j t 3 3 】和一个只有两个状态的 卷积码串行级联而成【3 4 1 ，因而他兼有t u r b o 和l d p c 码的特点，编码端可采用类 似卷积码的编码方式，译码端采用低复杂度的类似于置信传播( b e l i e fp r o p a g a t i o n ， b p ) 的译码算法【3 5 】。还有一类叫做7 1 旋转l d p c ( z r o t a t i o nl d p c ) 码t 3 6 h 3 9 1 。万旋 转l d p c 码的奇偶校验矩阵的非双对角矩阵的设计是先随机构造一个子方阵，然 后通过连续9 0 度旋转该方阵，并循环移位构造出非双对角阵。由于万旋转l d p c 码的编译码简单，易于硬件实现，该码已经被欧洲数字广播系统d v b ( d i g i t a lv i d e o b r o a d c a s t i n g ) 作为信道编码的可选标准。而级联s p c 码【3 3 】也可以看作是特殊类半 随机l d p c 码，与文献 2 5 】中描述的半随机l d p c 码所不同的是他的奇偶校验码 的两个子矩阵的一个为单位阵，而不是双对角阵。本论文就是围绕这两大类具有 2 第一章绪论 简单编码结构的l d p c 码展开研究。 l d p c 码被重发现至今，已有十年左右时间了，而研究其码的性能则引起越 来越多的研究者的关注。早期主要集中在对长码，即接近容量限的码的研究【删【4 1 1 ， 目前许多研究者也开始对中短码的研究产生兴趣【4 2 】【4 3 】。研究码的性能有两个方 向：一个是考虑最优译码，即最大似然译码时的码的性能，这类研究主要集中在 研究码的最小汉明距离和距离谱；另一个是考虑非最优译码，如迭代译码时的码 的性能，影响迭代译码性能主要有两个参数：一个是最小环长，另一个就是停止 集( s t o p p i n gs e t ) t 4 2 1 。本论文研究码的性能主要围绕着码的最小距离和最小环长两 个方面展开的。 1 2l d p c 码的定义 l d p c 码是一种奇偶校验矩阵为稀疏矩阵的线性分组码。参照s l m 的观点 1 6 1 ，狭义的规则l d p c 码的校验矩阵为稀疏矩阵，并具有如下几个特性： ( 1 ) 所有行重量都为一固定值p ； ( 2 ) 所有列重量都为一固定值y ； ( 3 ) 任意两行( 列) 中的“1 在共同位置最多只出现1 次； ( 4 ) 行重和列重相对于码长来说都非常小。 性质( 1 ) 和( 2 ) 保证该l d p c 码为规则码，否则就为非规则码。性质( 3 ) 确保该 码的t a n n e r 图中没有长为4 的环，如果没有这条限制，则该码就是广义的l d p c 码。性质( 4 ) 确保奇偶校验矩阵是一个稀疏矩阵。如图1 1 是一个列重为2 ，行重 为4 的奇偶校验矩阵，他的零空间是一个码长为8 ，码率为1 2 的规则l d p c 码。 l d p c 码的结构也可以从图论角度去理解。如图l 一2 所示，图中左边的节点 代表码字，被称为变量节点，用圆圈表示，图中右边的节点代表奇偶校验方程， 被称为校验节点，用方框表示，每一个校验节点都有一条或多条线与变量节点相 连，这种线被称为边，他代表每一个校验方程中具体参与的信息位，他与奇偶校 验矩阵中的“1 是一一对应关系。l d p c 码的这种表示方法最早由t a n n e r 提出m 】， 所以该图被称为t a n n e r 图。很显然，对于一个规则的l d p c 码，每一个校验节点 会有p 变量节点与之相连，对应于奇偶校验矩阵即每一行有p 个“1 一；而每一个 变量节点也会与y 个校验节点相连，对应地，奇偶校验矩阵中每- n 也有y 个“l ”。 环( c y c l e ) 是指由变量节点、校验节点和边首尾相连组成的闭合环路，环长( 西r t h ) 电子科技大学博士学位论文 定义为码的t a n n e r 图中最短的环的长度，如图1 1 和图1 2 中，黑线形成一个长 为4 的最小环。 h = 1o ol 1o 0l 10 1o 0l 01 一 巾 1 咖 平：手 卜：卜_ 图1 1行列重分别为4 和2 的l d p c 码奇偶校验矩阵 变量节点 校验节点 图1 - 2图1 - 1 奇偶校验矩阵对应的t a n n e r 图 1 3l d p c 码的构造 1 3 1 随机构造的l d p c 码 1 3 1 1g a l l a g e r 方法 g a l l a g e r 最早在文献 1 】中提出一个随机构造l d p c 码的方法，利用该方法构 造的l d p c 码具有如图l 一3 所示的结构，他具有明显的分层结构，每一层稀疏矩 4 第一章绪论 阵都是由随机交织器决定，其中第一层是由单位交织器决定。 1 1 1 1 1 1 1 1 1 1 1 11 11 由第一个矩阵的列 作随机交织得到 由第一个矩阵的列 作随机交织得到 第一个子矩阵 第二个子矩阵 第三个子矩阵 图1 3 基于g a l l a g e r 方法构造的奇偶校验矩阵 1 3 1 2m a c k a y 方法 在文献 3 】【4 仲，m a c k a y 等给出了几种构造随机l d p c 码的方法： 方法1 ：通过随机构造h ，要求构造的矩阵的列重固定，然后尽可能的保持 行重也是固定的，同时要求任意两列之间的“l ”的重叠数目最多为1 。 方法2 ：将m 2 的列，这里r n 指奇偶校验矩阵的行数，重量固定为2 ，并保 证任何两列之间没有重叠的“l ”，然后随机构造剩下的列，固定列重，并尽量保 持行重不变，与方法1 一样，要求任意两列之间的“l ”的重叠数目最多为l 。 方法3 ：删除掉基于方法l 或方法2 构造出来的h 矩阵中出现短环的列，并 补上重新随机构造的列使整个h 阵没有低于要求长度的环。 1 3 2 半随机构造l d p c 码 1 3 2 1 级联z 字码 z 字码的编码【3 2 1 过程如图1 - 4 所示，信息序列d 被分成1 个段( s e g m e l l t ) ，每 一段有，个比特，对第一个段的，个比特求奇偶校验，接着将该校验比特与下一 段的个比特再求奇偶校验，这样反复下去，直到，个段的校验比特都得到为止， 可以用下式表示每个z 字码的编码过程 ， p ( 1 ) = m j ) m o d 2 。：1( 1 - 1 )、， p ( i ) = e d ( i ，) + p ( f 一1 ) r o o d 2 ，i = 2 ，3 ，i 其中，d ( i ，) 为信息序列被重组成i d 的矩阵中的元素，p ( i ) 为校验比特。 电子科技大学博士学位论文 d 一 jd d 简单奇偶校验编码两状态卷积编码 图1 4z 字码编码器 d p o p l 气。 图1 5级联z 字码编码器 级联z 字码是通过并行级联k 个z 字码和k 个交织器构成的，如图1 5 所示。 而他们的奇偶校验矩阵可用如下矩阵表示 h = lh d h pi = lj h a oh po o h 矾oh p o ： h 4 川o oh p 这里i p 为，i 双对角矩阵，如下式所示 h p = 1o0 0 1l0 0 00o 1 ( 1 - 2 ) ( 1 3 ) o 为i x i 全零矩阵，而h 西，i = o ，l ，, k - i ，是一个由第i 维交织器决定的稀疏矩阵。 由此可见，级联z 字码是半