（信号与信息处理专业论文）基于代数方法构造的准循环ldpc码的研究.pdf

南京邮f b 人学钡小研究生学位论文 摘要 摘要 低密度奇偶校验( l d p c ：l o w d e n s i t yr a r i t y c h e c k ) 码是一类可以用非常稀疏的奇偶校 验( p a r i t yc h e c k ) 矩阵或二分图( b i p a r t i t eg r a p h ) 定义的线性分组纠错码，最初是由 g a l l a g e r 在1 9 6 2 年提出的，也称g a l l a g e r 码。m a c k a y 和n e a l 重新发现了它，并且证明 它在基于b p ( b e l i e f - p r o p a g a t i o n ) 的迭代译码的条件下具有逼近香农限的性能。 本文对l d p c 码的一种代数构造方法进行了分析，构建了系统仿真模型，其中，本人 的主要工作包括： 1 ) t a n n e r - l d p c 码参数选择方法的研究。t a n n e r 构造法是t a n n e r 提出的一种l d p c 码的代数构造方法，不过在t a n n e r 及已经知道的文献中，尚未找到该构造参数的 具体选择方法，本文提出一种具体的参数选择方法并证明是有效的。 2 ) 利用比特填充思想构造代数l d p c 码。比特填充算法是一种被广泛使用的随机构 造方法，将其基本思想应用于代数构造中，从而得到一种新的构造方法。 3 ) 其它几种代数构造函数的分析。t a n n e r 代数构造法采用指数函数做为生成函数， 文中思考了采用幂函数、三角函数时的性能，并对采用更复杂性函数可能的结果 做了简要的分析。 4 ) 仿真分析了各种类型代数构造方法的性能，验证了上面的分析结果。对上述的各 种思想、算法进行m a t l a b 仿真，验证思想、算法的正确性。 本文共分为六章。第一章是绪论，介绍了l d p c 码的背景和目前编码的一些情况； 第二章介绍了l d p c 码的一些基本概念，包括码的结构、g i r t h 的概念、编码算法、译码 算法；第三章着重研究了本文的基础一些已经发现的并具有比较好性能的代数构造 法；第四章是本文的重点，对代数构造法进行了一些有意义的扩展，然后给出代数构造法 的各种性能限；第五章给出了利用代数构造法生成的l d p c 码的仿真结果和性能分析； 第六章是本文的结论部分。 关键词：l d p c 码，正则码，代数方法，准循环l d p c ，t a n n e r - l d p c ， 线性解码 南京j | 1 ；1 也入学烦l 研究生学位论义a b s t r a c c t a b s t r a c t l d p cc o d ei sac l a s so fl i n e a rb l o c kc o d e sw h i c hc a r lb ed e f i n e db yt h es p a r s ec h e c k m a t r i xo r b i p a r t i t eg r a p h i tw a sf i r s td i s c o v e r e db yg a l l a g e ri n1 9 6 2 s oi ti sa l s oc a l l e d g a l l a g e rc o d e m a c k e ya n dn e a lr e d i s c o v e r e di ta n dp r o v e di t sa b i l i t yo fa p p r o a c h i n gs h a n n o n l i m i tb a s e do nb e l i e f - p r o p a g a t i o nd e c o d i n ga l g o r i t h m t h i sp a p e rr e s e a r c h e sam e t h o do fc o n s t r u c t i n gt h el d p cc o d ew i t ha l g e b r a ，s e t t i n gu pt h e s y s t e mt oi m i t a t et h et r u em o d e l ，t h em a i nr e s e a r c hc o n t e n t si n c l u d e ： 1 ) t h ec o n s t r u c t i o no ft h et a n n e r l d p cc o d e t a n n e r l d p cc o d ei sak i n do fa l g e b r a i c l d p cc o d e sp r o p o s e db yt a n n e r a l t h o u g ht h e r ea r em a n yp a p e r sc o n c e m i n gt h e c o n s t r u c t i o no ft a n n e r - l d p cc o d e s ，t h e r ea r en od e t a i l e dd e s c r i p t i o n sf o rt h ep a r a m e t e r s e l e c t i o n t h i sp a p e rp r o p o s e dap a r a m e t e rs e l e c t i o nm e t h o d s i m u l a t i o ns h o w nt h a tt h e p r o p o s e dm e t h o di se f f e c t i v ei np a r a m e t e rs e l e c t i o n 2 ) c o n s t r u c t i o no fl d p cc o d e sw i t hb i tf i l l i n g b i tf i l l i n gi sa ne x t e n s i v e l yu s e dr a n d o m l d c pc o n s t r u c t i o nm e t h o d an e wc o n s t r u c t i o nm e t h o dc a nb eo b t a i n e db ya p p l y i n gt h eb i t f i l l i n gm e t h o di na l g e b r al d p c c o n s t r u c t i o n 3 ) a n a l y s i so fs e v e r a lo t h e rc o n s t r u c t i o nm e t h o d so fa l g e b r al d p cc o d e s i nt a n n e r sm e t h o d ， e x p o n e n t i a lf u n c t i o ni su s e da st h eg e n e r a t i o nf u n c t i o n t h i sp a p e rc o n s i d e r ss e v e r a lo t h e r f o r m so fg e n e r a t i o nf u n c t i o n ，s u c ha st h ep o w e rf u n c t i o na n dt r i g o n o m e t r i cf u n c t i o n ，a n d a n a l y s i st h ep o s s i b l er e s u l t so f u s i n gm o r ec o m p l e xg e n e r a t i o nf u n c t i o n 4 ) a n a l y s i st h ep e r f o r m a n c eo ft h ea l g e b r al d p cc o d e sm e n t i o n e da b o v eu s i n gc o m p u t e r s i m u l a t i o n t h i st h e s i si sd i v i d e di n t os i xc h a p t e r s t h ef i r s tc h a p t e ri sa ni n t r o d u c t i o nt ot h e b a c k g r o u n do fl d p cc o d e s t h es e c o n dc h a p t e rd e a l sw i t ht h ef u n d a m e n t a l so fl d p cc o d e s i n c l u d i n gt h es t r u c t u r eo f l d p cc o d e s ，e n c o d i n ga n dd e c o d i n ga l g o r i t h m s ，c h a p t e r3 e m p h a s i z e dt os t u d yt h et e x t u a lp o i n t w i t ht h et a n n e r l d p cf o rr e p r e s e n t a t i v eo fa l g e b r a c o n s t r u c tt h em e t h o d ；ag e n e r a lp r o p e r t yo ft h ec o d ei si n t r o d u c e da tc h a p t e r4 i nc h a p t e r5w e g i v et h es i m u l a t i o nr e s u l t sa n ds o m ea n a l y s i so nt h ep e r f o r m a n c eo fl d p cc o d e sc o n s t r u c t e d b ya l g e b r am e t h o d f i n a l l y , w ed r a ws o m ec o n c l u s i o n si nc h a p t e r 6 k e y w o r d s ：l d p cc o d e s ， r e g u l a rc o d e s ， a l g e b r ac o n s t r u c t ，q c l d p c ， t ，m n e r l d p c i 南京邮电大学 硕士学位论文摘要 学科、专业：工学信号与信息处理 研究方向：现代通信中的信号与信息处理 作者：2 0 0 3 级研究生任红亮 题目：基于代数方法构造的准循环l d p c 码的研究 英文题目：as t u d yo np e r f o r m a n c e so fl d p cc o d e sc o n s t r u c t e d b ya l g e b r am e t h o d 主题词：l d p c 码正则码代数构造法q c l c p c t a n n e r l d p c k e y w o r d s ：l d p cc o d e s r e g u l a rc o d e s a l g e b r ac o n s t r u c t q c l d p c t a n n e r l d p c 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除r 文一f 特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书丽使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签躬：1 1 瑚 南京邮电大学学位论文使用授权声明 南京邮电火学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊髓) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：导师签名 日期 稍京懈l 毡人学i i i ii + 聊f 究生学纯论文锥一章缔论 第一章绪论 在透信系统中，为了抵消信道中各种噪声的干扰，以保证数据信息能够得到可靠、有 效的传输，往往翼利用纠错编码技术。近年来，随着无线数字通信的发展及各种赢速率、 突发性强的新业务的出现，研究并利用好纠错编码技术就显禧越来越重要。 1 9 4 8 年香农( s h a n n o n ) 在他的开创性论文“遥信的数学理论”中提出了著名的有扰 信道编码定理： 每个信道具有确定的信道容量c ，对于任何r i ) ，对每个c 中的值x 计算c 2 ，相加。 5 ) 如果需要计算各个g i r t h 对应的具体的点： 对c 中的每个值g ( i j ) = x 1 在h 矩阵中遍历第i 行和第j 行，找到对应1 的列( 参 见图2 4 ) 。其中任意两列的组合( c 2 ，种) 构成4 环。 将上述算法扩展至6 9 i r t h 判断。判断6 9 i r t h 的基础为不存在4 9 i r t h ( 存在4 9 i r t h 的时 候计算是否含有6 9 i r t h 没有意义，以下相同) 。 6 9 i r t h 判断的依据为g ( 半三角已经被清0 ) 是否含有3 角1 ( 或说1 三角) 。即如果 g ( i j ) = l ，g ( i ，k ) = 1 ，g 0 ，k ) = l ，我们说存在一个三角1 ，则对应一个6 9 i r t h 环( 参见图2 5 ) 。 具体算法不再描述。 8 9 i r t h 判断：g g = g g t ，同4 9 i r t h 的判断，( 注意其中g 不可以清三角) ，然后将 g g 等同于4 9 i r t h 中的g 即可。分析：如g g ( 1 ，2 ) = 2 ，表明g 中存在一个1 长方形( 等 同于g 中存在4 9 i r t h ) 。g 中的4 9 i r t h 对应h 中的8 9 i r t h 。 大于8 9 i r t h 的计算可以通过以上方法递推，这里不再具体介绍。 该方法是本人提出的，在仿真中可以确切找到各个具体的最小g i r t h 。 2 2 2 g i r t h 的基本性质 命题1l d p c 码的任意一个长度为l 的环，满足l 1 4 ，且l 是偶数。 证明：由于构成一个环需要至少经过3 个节点，所以l 3 ；( 如果经过两个节点可以形 成环，该两个节点之间存在多于一条边。h 矩阵的值为0 ，1 ) 下面证明l 是2 的倍数，根据t a n n e r 图的性质，信息节点 x i li _ 1 ，2 ，n 和校验节 点 z jj = 1 ，2 ，3 ，k ) 之间可能有边相连，但是信息节点和校验节点内部没有相连的边。假 如从x 出发经过奇数步回到本身，那么必然在集合 x ii = 1 ，2 ，n 或者集合 z j ij = 1 ，2 ，3 ，k ) 内部存在一条边，这与t a n n e r 图的性质是不相符合的，因此l 必定为偶数。 南京岫l 乜人学坝士研究生学位论文 第二章l d p c 码基础 2 2 3 g i r t h 的理论限 在文献【2 8 】中，给出了g i r t h 的树结构上限，下面在具体说明的基础上给出具体的应用 实例。使用树型结构分析得到的结论为l d p c 码的理论g i r t h 上限，跟使用什么构造方法无 关。 基本思路：利用上面提及的环的定义，现在分析一个节点( 假设为校验节点) 出发形 成的g i r t h 情况。对一个校验节点( 行) 而言，对规则l d p c 码( k ，j ) ，一定对应j 个比 特节点，而个比特节点一定对应( k 一1 ) 个校验节点( 不包括由校验节点进入的边) 。 如此不断延伸，如果矩阵一定不包含g m i 。，则经过g 嘶次递推以后，该树中不包含重复的 点，而不包含重复点的必要条件为树中对应节点的个数不大于h 矩阵中对应节点的总个数 ( 比特节点数不大于列数，校验节点数不大于行数，否则肯定存在重复，肯定存在环) 。 下图表示了一个节点开始形成的树结构： c o a 8 t z a i a tl e v e ll b i tl 自v 岳l1 c o n s t r a l a tl 自帕l2 b i tl w e l2 辫0 辫 妇碎c 坤i 踮b e v e lj 图2 6 g i r t h 树型图 如图2 - 6 所示，一个校验节点出发，对应k 个比特节点，经比特节点到校验节点，有 k ( j 一1 ) ( 不包含入边) 个，然后再到比特节点，有k ( j 一1 ) ( k - - 1 ) 个，如此递推。得 到经过i 次比特节点以后，经过的比特节点总个数为： p i = k + k ( j 1 ) ( k 0 + k ( j 一1 ) 2 ( k 1 ) 2 + + k ( ；1 ) 1 ( k 1 ) ( 2 一1 ) 如果p i 超过比特节点的个数n ( 码长) ，则至少一个比特节点在树中出现两次，即形成 一个环，因此： 设c = m a x f i ：p i 三n ) ( 2 - - 2 ) 表示图中比特节点的层数，则图中比特节点中的边数为：4 ( c 一1 ) 当p 。 0 ，则可以判定o = 1 ，否则c 。= o 。应用贝叶斯准则，上面表达式的 分子： prc。=1l，j，l。)】。：二!：!：11_121。：；!掣(z-s) ，l j 只一 ) 上面的推导从第二个式子到第三个式子是假设了c 。，0 独立于 ，。) 。这样，2 - 9 式可以简化推导为以下形式： 旯一：l o g ! 匕三! 坐曼三! 监! ! !“ 厂( k c 。= o ) p r ( c , ，= 0 i ，。 ) 一0 2 2r + l o g 糍， 弘聊 需要指出的是，在2 - 8 式中第一项反映了最终第1 1 位的检测信息来自于第n 个比特的 信道观察值的贡献，通常它被称为固有信息，或者先验信息。第二项反映了第n 位的检测 信息来自于其它观察值，通常它被称为边信息。不难发现，两个贡献的结合只通过简单的 加反映出来。此外，边信息正比于第n 个信道的观察值。 下面解释奇偶校验满足的t a n h 准则。定义矿( c ) e o , 1 为具有n 个比特的向量 c = c ，c 。 ，如果在向量c 中有偶数个1 ，则( c ) = 0 ；如果有奇数个1 ，则( c ) = 1 。如果 向量c 中比特是独立的，则对于奇偶校验的先验对数似然比服从t a n h 准则。 t a n h 准则的定义如下：令c = q c 。】 o ，1 ) ”是一个n 比特向量，并且这n 个比特是相 互独立但不等概的；让 = l o g ( p r 【c 。= l 】) ，b g ( p r c , = o 】) 表示第i 个比特的对数似然比。贝0 有 做为判定奇偶校验结果的先验对数似然比以2 l o g ( p r ( c ) 2 l 】) l o g ( p r 庐( c ) 2 - - 0 1 ) 满足下式： t a n h ( 二竽) ；nt a n h ( 二当) ( 2 1 8 ) 下面给出证明：一个向量f c 。c 。 的奇偶校验庐( c ) 可以由下式表达： 矿( c ) 5 ( 1 - n ( 1 2 c ) ) 2 ， ( 2 1 9 ) 又有p r 【妒( c ) 2 1 _ e 矿( c ) ( 1 一e ( 兀0 2 c ，) ) ) 2 2 ( 1 n ( 1 2 e ( c ，) ) ) 2 ( 考虑独立条件) _ - lj = l 2 南京| | | | j 电人学硕士研究生学位论文 第一二章l d p c 码基础 又因为e h 】= p r 【q = 1 】= 啬，代入上式可得 p r _ 1 附冉等) 2 - ( 1 。冉蛐( 刮2 ) ) 2 ( 2 - 2 0 ) 因为p r ( c ) = o _ l p r 庐( c ) = 1 】，所以 丑。，= l 。g ( p r 【( c ) = 1 ) l 。g ( p r 庐( c ) = 。 ) = l 。g i l ：- _ j l ? - i i ：i i t a 矗n 五h i ( ：- ：j a f i - 厂2 西) ( 2 - 2 1 ) 根据t a n h ( 一a 2 ) = ( 1 一p 1 ) ( 1 + p 2 ) ，并令t = 兀，t a n h ( 一 1 2 ) ， i 一旦 触( 半) - 拦十i - i , t a n h ( - 枇) ，彻 下面将奇偶校验满足的t a n h 准则用到2 - 2 1 式中，将检测信息和奇偶校验信息联系起 柬。 因为码字c 的j 个奇偶校验保证了对于所有的净1 j ，都有c 。= 庐( c 。) ，代入( 2 1 0 ) 式得： 铲盯2 r + l o g 器警 陪z z ， 九2 盯- 面瓦麓面j 厕 “纠 如果二分图是没有圈，向量。( 1 】，。( ：) ，。( 力在n ，。) 已知的情况下是线性独立的；此外， 在 ，。) 已知情况下，。“) 自身的分量之间也是相互条件独立的。所以( 2 1 5 ) 式可以变为 铲孝川。s p “( c ) = 1 i 。) ) p r ( ( c m ) = 0i r t , n ) 弓。+ 缸鬻湍弓+ 圭i = 1 ， p 2 ， 这里由于比特是条件独立的，每个h n 】满足t s n h 准则，此时，我们定义 五，：l o g 坠! ：! 盟旦堕( 2 - 2 4 ) 一叫0 8 丽嘉可瓦万 将2 - 2 2 式代入2 - 2 7 式，可得 九弓一喜时1 ( 愈t 酬孚) p ：s ， 结合二分图，我们可以很好的解释( 2 - - 2 7 ) 式，它反映了节点到节点的信息传递 ，旦，兀 南京b 火学坝卜研究生学位论文 第二章l d p c 码基础 过程。我们可以设想涉及到c 。的变量节点传递信息 ，第i 个奇偶校验节点。相反，从第i 个奇偶校验节点的角度来看，它将从它所涉及到变量节点( 包括c 。) 收集k - 1 个输入信息， 为它们的奇偶校验计算后验对数似然比_ ( 。1 ) ，然后传递这个信息给第n 个变量节点，最 后第n 个变量节点通过将输入的信息和寺相加来计算以。而对于兄叫，我们可以通过使 用2 - 2 8 式递归迭代获得，条件是二分图是无圈的。根据以上分析，我们将可以给出具体的 算法。 信息传递算法是一种在二分图中信息在节点间被传递的解码技术，节点可以做为独立 的处理器来工作，可以收集输入信息和产生输出信息。关于时间和信息的内容没有全局的 控制存在；相反，比特和校验节点服从一个普遍的本地准则( 1 0 c a lr u l e ) ，即一旦所有的输 入信息都得到接收就可以产生一个输出。当图是无圈的，信息传递算法在经过有限次信息 传递后可以收敛到2 2 2 式定义的后验对数似然比。但是，大部分好码在它们的二分图中都 存在圈。当存在圈的码得到使用，信息传递算法不再是准确，而只是近似。幸运的是，即 使当图有圈的存在，信息传递算法也是工作的非常好，并且它的复杂度非常低。 下面将给出一个对数域上规则码或者不规则码的信息传递算法。定义下标集合 m 。= 卅：h 。= 1 ) 和n 。= ”：h 。= 1 ) 。定义“嚣在第1 次迭代中从校验节点m 传递到变 量节点n 的信息。并且让硝，指经过1 次迭代过后第n 个比特的对数似然比预测值。 算法如下： 初始化 对于所有的m l ，m 和n sn n ，令“恐= o 对于所有的n 1 ，n ，令群= ( 2 盯2 ) 迭代 f o r 迭代次数l = 1 ，2 ，。， 校验节点升级 f o r m 1 m 并且n n 。， 妒z t a n h 一、fnt a n _ h ( 掣) 1 l ，e 。一” 变量节点升级 f o r n 1 n ) ， 群= ( 2 仃2 ) + “锶 m e m 一 这个算法可以进一步为二分图中信息传递过程来解释。在第0 次迭代的时候，从每个 南京邮电大学硕：卜研究生学位论文 第二章l d p c 码攮础 变量节点到它所涉及到的校验节点的信息是( 2 t y2 ) 0 ；第1 1 1 个校验节点收集它的输入信息， 产生反映它奇偶校验结果的奇偶校验对数似然比，并把这个对数似然比做为输出信息进行 传递，上述过程中要排除某个变量节点传递信息到某个校验节点，而该校验节点将信息又 传递回来的情况。每个变量节点接收j ( j 由该变量节点的度决定) 个信息。并且第1 1 个变 量节点通过将( 2 t r2 ) t ，和所有的输入信息相加产生一个新的预测值。这个过程可以重复， 即变量节点传递它们新的预测值给校验节点，而校验节点再将信息传递给变量节点，同样 要排除信息正反馈给自身的情况。 根据算法的特点，我们很容易意识到该算法基于二分图的并行实现是可行的，m 个校 验节点可以是m 个独立的处理机，对于n 个变量节点，每个节点是一个求和节点。并行 实现使得在极高速率的条件下使用l d p c 码和迭代解码成为可能。当然，对于该算法软件 实现一般来说都是串行的。b p 算法在对数域上进行，和概率域上进行相比可减少乘法运算 次数。 b p 算法每次迭代大约需要m ，( d ，+ d 。) 次浮点乘运算，每译出l b i t 大约需 埘。( d 。+ d 。) r ( t 为平均迭代次数) 次浮点乘运算，与码长无关，总的乘法次数约为 t n d 。( d 。+ d ，) 。可以看到b p 算法的复杂度为码长的线性函数。b p 算法的迭代过程中，如 果试验译码得到成功，译码过程立即结束而不是进行固定次数的迭代，有效地减少了算法 的迭代次数。如果算法运行完预先限定次数的迭代后仍未找到有效的译码结果，译码器将 报错，这时的译码错误为可检测的，若算法找到一个与x 不相等的叠满足方程 礅= 0 m o d2 时将产生不可检测的错误。不可检测错误的出现概率基本可忽略不计，b p 算法译码后的误码率可随信噪比的增加任意减小，不存在误码率下降减速的e r r o rf l o o r 现 象。 2 4 3b p b a s e d 算法 xw e i 、a n a k a n s u 2 5 在研究中注意到，s p a 算法或b p 算法因为都是定义在对数似 然比( l l r ) 域上，等效于l o g m a p 译码。将t u r b o 码中简化l o g m a p 算法得到 m a x l o g m a p 算法的思想，即用取最大值操作( m a xo p e r a t o r ) 替代“对数一指数( l o g e x p ) ” 运算；l n ( e 1 + e ) = m a x ( x ，y ) + l n ( 1 + e l 。一”) m a x ( x ，y ) ， 引入到l d p c 码的译码中来，即可得到适用于l d p c 码的m a x l o g m a p 算法。 m a r c e c f o s s o r i e r 等人 1 6 】，以b p 算法为基础，独立地研究出b p b a s e d 译码算法。 性能虽然较b p 算法稍有下降，但译码复杂度大大下降，且译码算法独立于信道特征，无 2 4 南京i l l l l i u 人学删h 口f 究生学位论文第二章l d p c 码基础 须进行信道估计，因而在计算复杂度和译码性能之间取得了良好的折中( t r a d e o f f ) 。 b p - b a s e d 算法与m a x l o g m a p 算法的基本思想一致。b p b a s e d 算法和b p 算法的不 同主要体现在译码器的初始译码消息和校验节点的消息处理上。在正则码上的实验结果表 明，前者较后者的性能差距只有约0 6 d b 。 堕皇! ! ! 查兰塑兰坐型生堂堡丝苎 苎兰翌! ! 塑塑鲨塑垫生里! 里塑 第三章代数方法构造l d p c 码 l d p c 码的h 矩阵生成方法主要有两种：( 1 ) 随机伪随机生成法 3 1 1 6 ，其基本的思 路或典型的算法为b i t 填充算法【8 】，不管是理论还是仿真都证明 8 1 5 1 随机构造法：特别是 在码长比较大的情况具有非常好的性能。l d p c 码做为一种线性编码，影响其性能最重要 的因素为最小距离。如果我们可以穷尽所有可能的h 矩阵而选择其中最优的h ，当然是最 好的，但在实际中这根本是不可能的。所以我们的构造无法达到最优，而仅仅是次最优。 我们通过某一种特定的方法，来生成h 矩阵，而且生成的h 矩阵具有比较好的性质，则这 种方法是我们需要的。 在随机构造中，我们的问题是给h 矩阵的自由度太大，有太多的随机性。而构造方 法给我们的这些自由度我们是无法充分利用的。面对这种情况，我们有两种改进的方法： ( 1 ) 研究好的h 矩阵所具有的性质，进而构造满足这些性质的码。例如：密度演进使我 们可以选定好码具有的次数分布对特征，然后我们按着这种次数分布对来生成h 矩阵。( 2 ) 选定某种具体的构造方法，判断按这种方法生成的h 矩阵是否具有好的性质。两种方法互 相依存，共同实现一个从随机到确定的过程。 对不规则l d p c 码而言，密度演进是一种强大的工具。但对规则l d p c 码的构造， 本人在随机构造中没有发现一种系统的、有效的方法。利用随机构造法构造规则l d p c 码， 没有充分利用规则l d p c 码的优点。我们知道在图论中，规则码对应的是正则图，在有限 几何中，规则码也可以简化设计。在我们下面提到的基于基矩阵的设计方法，只可以设计 规则码。对规则码而言，其特点为规则、整齐、对称、和谐等。利用随机方法构造h 矩阵， 规则码和非规则码对我们都是一样的约束。从这个角度而言，利用代数方法构造规则码是 有优势的。 l d p c 码的特征在于h 矩阵的稀疏性，这也是l d p c 码的定义。稀疏性保证了h 矩阵 对应的乘法运算的简单性，更重要的是：l d p c 码的稀疏性保证了h 矩阵不含有小环，这 是b p 系列解码算法可以使用的必要条件。因此，g i r t h 的分布是l d p c 中及其重要的特征。 所以在下面的分析中，所有h 矩阵的优劣判断都是通过h 矩阵的g i r t h 分布来比较的。 本文讨论的主要为代数构造法中的类：利用基矩阵的方法构造h 矩阵。并没有对有 限几何法进行探讨。不过，下面通称为代数构造法。即下面的代数构造法只包含基于基矩 阵的l d p c 构造法。 南京邮l 乜人学坝i 】f 究生学位论文 第二章代数方法构造l d p c 码 解决问题的一个最基本的方法是：将一个大的问题、比较复杂的问题转化为若干小的、 比较简单的问题。在构造l d p c 码的时候，我们需要生成一个大的、比较复杂的h 矩阵， 一个自然的思考为先生成若干比较小的矩阵h ，我们称之为子矩阵，然后将若干个h 组 合生成h 。事实上，在 1 中，g a l l a g e r 在给出的示例中，在生成一个( 3 ，6 ) 的l d p c 码 中，即是由3 个( 1 ，6 ) 生成，就可以看作是一种代数构造法。更进一步，我们将各个子 矩阵产生固定的关联，利用某种变换，我们可以由一个子矩阵产生另一个子矩阵。一般化， 我们定义一个矩阵为基矩阵，所有的子矩阵通过某种基矩阵的变换生成，而h 矩阵通过各 个子矩阵的一定排列、堆砌而成，这就是基于基矩阵的代数构造法。 代数构造法的基本思路：通过基矩阵的变化生成子矩阵，通过子矩阵的排列生成h 矩 阵。 在上述分析中可以看出，我们利用代数构造法需要解决三个问题： 1 ：基矩阵的选择 2 ：基矩阵的变换规则 3 ：子矩阵的排列 三个部分的任何一个部分的不同，均可以产生不同的代数构造法，下面分别简要分析 如下： 1 1 基矩阵的选择 代数矩阵主要应用于规则l d p c 码的生成，因为代数构造法的基本思路为“分块”， 而不规则l d p c 码：我们利用密度演进 1 6 1 得到分布次数对，然后构造h 矩阵，次数对是 针对h 矩阵的行、列的，我们使用“块”去对应是不合适的。在规则l d p c 码中，表示其 性能的重要参数为行重、列重。做为基矩阵，其应该为h 矩阵的基本要素，因此选择单位 矩阵是合适的。因为单位矩阵为( 1 ，1 ) 的方阵，用单位阵( 或其某种变形) 做为基阵， 可以构造任意行重、列重的规则阵。在这里也可以发现，h 矩阵由基矩阵构成，则h 的行 长，列长和基矩阵均有对应的关系，所以代数构造法不能构造任意码长、码率的h 矩阵( 规 则码本身就含有该约束) 。 使用单位阵做为基矩阵，形成规则( k ，p ) l d p c 码时，k 、p 就表示行列堆积子矩 阵的个数。 2 ) 变化规则 对一个矩阵的变化，可能有如下方式： 列交换 行交换 2 7 南京帅i b 人学顶j 。研多t 生学位论文 第三章代数方法构造l d p c 码 循环平移 矩阵旋转 列交换和行交换，对应的基矩阵只有部分发生变换，而且行交换和列交换是矩阵变 换的基本方式。任何线性变化都可以分解为这两种变化，概念太大。循环平移是一种很好 的方法，优点表现在循环平移生成的矩阵为循环矩阵，各个循环子矩阵构成准循环的h 矩 阵。定义循环平移只需要一个参数：循环平移量。矩阵旋转在下面的刀旋转矩阵构造法 中有使用，其优点为在实际使用中各个旋转矩阵使用同一个硬件电路，其缺点是只有4 种 旋转结果，性能上有损失。 3 1 = 列规则 一般均为直接排列，或者给出固定的结构。当定义特定的结构时，一般都是强制为 上( 下) 三角以实现线性解码。 下面使用以上的思路分析说明几种已经被提出且广泛使用的代数构造法。 3 1丌旋转矩阵构造法 在文献 2 3 - 2 4 中，给出一种旋转矩阵代数构造法。其定义基矩阵为万，每列只有一 个l ，每行只有一个1 。可以看出疗