（通信与信息系统专业论文）低密度校验码ldpc的实现研究(1).pdf

哈尔滨工业大学t学硕士 学位论文 摘要 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 ) 码是一 类可以 用非 常稀疏的 校验矩阵 或二分图定义的线性分组纠错码，最初由 g a l l a g e r 发现，故亦称 g a l l a g e r 码. 它和著名t u r b o 码相似， 具有逼近香农限的性能， 几乎适用于所有信道， 因此成为近年来编码界研究的热点。 l d p c 码其奇偶校验矩阵呈现稀疏性，其译码复杂度与码长成线性关系， 克服了分组码在长码长时所面临的巨大译码计算复杂度问题，使长编码分组 的应用成为可能。而且由于校验矩阵的稀疏特性，在长的编码分组时，相距 很远的信息比特参与统一校验，这使得连续的突发差错对译码的影响不大， 编码本身就具有抗突发差错的特性。 首先，本文介绍了 l d p c码的基本原理，包括 l d p c码的基本概念、 编码算法、 译码算法。 在编码算法里详细讨论了l d p c码的稀疏校验矩阵和 生成矩阵的产生方法及其校验矩阵的环的分析。 在译码算法里介绍了mp 算 法集的基本原理和译码性能最好的和乘积译码算法。 其次， 本文采用的编码算法是一般线性码的生成方法， 即信息位和相应 的生成矩阵相乘， 译码采用的是和乘积算法， 信息概率在比特节点和校验节 点之间迭代的传输， 直到译码收敛或者达到最大的迭代次数。 根据编译码算 法， 构造了易于硬件实现的结构。 在编码部分构造了稀疏的无四线环的校验 矩阵， 生成了相应的生成矩阵。 提出的硬件结构使得编码得到简化。 译码部 分在实现复杂度和延迟时间上取了一个折中， 采用的是很通用的部分并行的 结构. 最后，在a wg n信道模型下完成了l d p c码的编译码器的f p g a基础 的硬件仿真。 关键词l d p c码:稀疏校验矩阵:和乘积算法 哈尔滨工业大学工学硕士学位论文 ab s t r a c t 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 ) c o d e i s a k i n d o f l i n e a r b l o c k c o d e t h a t d e f i n e d b y v e r y s p a r s e p a r i t y m a t r i x o r t a n n e r g r a p h , a n d it i s a l s o c a l l e d g a l l a g e r c o d e s i n c e g a l l a g e r i n i t i a l l y p r e s e n t e d i t . l d p c c o d e i s s i m i l a r w i t h t h e t u r b o c o d e , b o t h o f t h e i r p e r f o r m a n c e a p p r o a c h s h a n n o n l i m i t . l d p c c o d e h a s b e e n m o s t l y u s e d a l l o v e r t h e c h a n n e l s a n d b e c o m e s o h o t i n t h e r e s e a r c h f i e l d o f c h a n n e l c o d i n g i n r e c e n t y e a r s . l d p c c o d e s p a r i t y c h e c k m a t r i x h a s t h e c h a r a c t e r i s t i c s o f s p a r s e n e s s ; t h e d e c o d i n g c o m p l e x i t y i s j u s t t h e l i n e a r i n c r e a s e a c c o r d i n g t o t h e c o d e l e n g t h , a n d t h i s c h a r a c t e r m a k e t h e a p p l i c a t i o n o f l o n g b l o c k c o d e p o s s i b l e . mo r e o v e r , t h e s p a r s e m a t r i x m a k e s t h e m e s s a g e s f a r a w a y c h e c k e d a t a t i m e , a n d t h e l d p c c o d e c a n a v o i d t h e c o n t i n u o u s b u r s t i n g e r r o r s . f i r s t ly , t h e p a p e r i n t r o d u c e s t h e f u n d a m e n t a l p r i n c i p l e o f l d p c c o d e , i n c l u d i n g l d p c c o d e s b a s i c c o n c e p t i o n , e n c o d i n g a n d d e c o d i n g a l g o r i t h m . t h e n d i s c u s s e s h o w t o g e t t h e l d p c c o d e s f r e e o f l e n g t h o f f o u r c y c l e s s p a r s e p a r i t y m a t r i x a n d g e n e r a t o r m a t r i x i n e n c o d i n g a l g o r i t h m , a n d e x p a t i a t e s t h e p r i n c i p l e o f me s s a g e p a s s i n g a n d s p a w h i c h h a s t h e b e s t p e r f o r m a n c e i n d e c o d i n g a l g o r i t h m s e c o n d l y , e n c o d i n g a l g o r i t h m i s t h e s a m e w i t h t h e c o m m o n l y l i n e a r c o d e . a c o d e w o r d c a n b e a c q u i r e d t h r o u g h t h e p r o d u c t o f g e n e r a t o r m a t r i x a n d b i t n o d e s . t h e d e c o d i n g a l g o r i t h m i s t h e s p a , w h i c h h a s t h e b e s t p e r f o r m a n c e . m e s s a g e s p r o b a b i l i t y w i l l n o t t r a n s f e r b e t w e e n b i t n o d e s a n d c h e c k n o d e s u n t i l t h e d e c o d i n g c o n v e r g e n c e o r r e a c h i n g t h e m a x i m u m a l t e r n a t i o n n u m b e r . a c c o r d i n g t o e n c o d i n g a n d d e c o d i n g a l g o r i t h m , t h e p a p e r c o n s t ru c t s t h e a r c h i t e c t u r e s c a n b e e a s i l y i m p l e m e n t e d , a n d g e t s p a r i t y c h e c k m a t r i x f r e e o f l e n g t h o f f o u r c y c l e s a n d t h e c o r r e s p o n d g e n e r a t o r m a t r i x , w h i c h l e a d s t o e f f i c i e n t i m p l e m e n t a t i o n s f o r t h e e n c o d e r a n d d e c o d e r . t h e a r c h i t e c t u r e o f t h e d e c o d i n g i s p a rt l y p a r a l l e l , w h i c h p r o v i d e s a t r a d e o f f b e t w e e n t h e h a r d w a r e c o m p l e x i t y a n d t h e p r o p a g a t i o n d e l a y . f i n a l l y , t h e h a r d w a r e s i m u l a t i o n s b a s e d o n f p g a u n d e r t h e a wg n c h a n n e l i s i m p l e m e n t e d . 哈尔滨工业大学工学硕士学位论文 k e y w o r d s l d p c c o d e , s p a r s e p a r i t y c h e c k m a t r i x , s u m - p r o d u c t a l g o r i t h m 哈尔滨工业人学工学硕 七 学位论文 第1 章 绪论 1 . 1 课题背景 s h a n n o n创立信息论时就己经证明了对于任意信道都存在这样的分组 码系列，使得任意以低于信道容量的速率进行通信的误码率都能够任意的 小。 人们称这样的码系列为最佳码。 但是， s h a n n o n 的证明利用的是随机编 码理论，是非构造性的， 并不能以此得到实用的最佳编码。 于是，寻找这样 能够实际应用的最佳码就成了一项重要的从未间断的工作。 1 . 1 . 1 纠错码发展 1 9 4 8年，香农 ( s h a n n o n )在他的开创性论文 “ 通信的数学理论”中， 首次阐述了在有扰信道中实现可靠通信的方法， 提出了著名的有扰信道编码 定理， 奠定了纠错码的基石.以后， 纠错码受到了越来越多通信和数学工作 者， 特别是代数学家的重视， 使纠错码无论在理论上还是实际上都得到飞速 的发展。 迄今，纠错码已有 5 0多年的历史，其发展过程大致分为以下的几个阶 段。 2 0 世纪5 0 年代到2 0 世纪6 0 年代初，只是研究各种有效的编码译码方 法，奠定了线形分组码的理论基础:提出了著名的b c h码编码译码方法以 及卷积码的序列译码; 给出了纠错码的基本码限。 这是纠错码从无到有得到 迅猛发展的时代。 2 0 世纪6 0 年代至2 0 世纪7 0 年代初，这是纠错码发展过程中最为活跃 的时期。 不仅提出了许多有效的编码译码方法， 如门限译码、 迭代译码、 软 判决译码和卷积码的维特比译码等。 而且注意到了纠错码的实际化问题， 讨 论了与实用有关的各种问题， 如码的重量分布、 译码错误概率和不可检测错 误概率的计算、 信道的模型化等， 所有这些问题的研究都为纠错码的实用打 下了 坚实基础。 在此期间， 以 代数方法特别是以 有限域理论为基础的线形分 组码理论己经趋于成熟。 2 0 世纪7 0 年代初到2 0 世纪8 0 年代，这是纠错码发展历史上具有极其 重要意义的时期.在理论上以戈帕( g o p p a ) 为首的一批学者，构成了一类 哈尔滨t业大学工学硕上学位论文 g o p p a 码， 其中的一类子码能达到香农在信道编码定理中所提出的码一一香 农码， 所达到的性能， 这在纠错码历史上具有划时代的意义。 在这期间大规 模集成电路和微机的迅猛发展， 为纠错码的实用打下了坚实的物质基础， 因 而与实用相关的各种技术及其有关的问题得到了极大的关注， 并在实用中取 得了巨大成功。 如美国 在7 0 年代初发射的“ 旅行者” 号宇宙飞船中， 成功 地应用了纠错码技术， 使宇宙飞船在极其遥远的距离( 3 0 亿公里) ， 向地面传 回了天王星、 海王星等形体的天文图片， 发现了天王星的9 个卫星和光环以 及海王星的6 个卫星和光环等许多及其宝贵的资料。 若不应用纠错码， 这些 成就的取得是不可想象的。应当指出，在此期间的 f f t技术，从频谱观点 研究纠错码， 受到了特别重视， 使许多熟悉信号处理技术但不熟悉有限域理 论的工程师们， 能够较快的掌握纠错码理论， 并能熟练地应用到十几种， 从 而为纠错码在各类通信系统中的广泛使用，起到了极好的推动作用。 2 0 世纪8 0 年代初以来，戈帕等从几何观点讨论分析码，利用代数曲线 构造了一类代数几何码。 在这些码中， 某些码的性能达到了香农码所能达到 的性能。 由于代数几何码是一类范围非常广的码， 在理论上己经证明它具有 优越的性能， 因而在一开始就受到编码理论工作者， 特别是代数几何学者的 重视，使代数几何码的研究得到了非常迅速的进展，取得了许多成果。 1 9 9 3 年b e r r o u 发现了t u r b o 码， 仿真结果表明t u r b 。 码的性能距s h a n n o n 限仅差零点几个 d b ,结束了长期将信道截止速率作为实际容量限的历史， 同时也标志着纠错码理论进入了一个崭新的阶段。 目 前， 利用纠错码降低各种数字通信系统以及计算机存储和运算系统中 的误码率， 提高通信质量， 延长计算机无故障运行时间等， 在美国等西方国 家中已经作为一门标准技术而广泛采用。 而且纠错码技术还应用于超大规模 集成电路设计中 ，以提高集成电路芯片的成品率，降低芯片的成本。不仅 如此，自2 0 世纪7 0 年代末以来， 纠错码技术己经开始渗透到许多领域， 利 用纠错码中的许多编码、 译码原理和方法， 与通信系统中的其他技术相结合， 得到了令人惊喜的成果。 例如，纠错码和调制技术相结合所产生的t c m技 术， 已 经作为国际通信中标准技术而得到推广使用。 又如纠错码与密码相结 合，可以构造出一类既能加密、 签名，又能纠错、检错功能的密码系统。 纠 错码与信源编码相结合的成果， 使得通信系统更为有效可靠， 不仅如此， 纠 错码的许多译码思想和方法， 与神经网络中的能量函数有密切关系， 纠错码 中的许多译码技术， 可以用来解决神经元网络中的一些问题。 因而可以预料， 随着科学的进步和实际的需要， 纠错码理论必将进一步发展， 它的应用范围 哈尔滨工业人学工学硕士学位论文 必将进一步扩大。 1 . 1 .2 l d p c码的提出 1 9 6 2 年， r .g a l l a g e r 在 他的 博士 论 文 n 中 提出了 l d p c ( l o w d e n s i t y p a r it y c h e c k ) 码的概念，他的主要思想是选择低密度校验矩阵表示分组码，以便降 低分组码的编译复杂性，并且使用迭代译码算法使得码长的限制放宽，因此 可以使用长码来逼近s h a n n o n 信道容量。 但是由于当时的技术条件的限制， 再 加上人们普遍认为级联码更易于实用化，导致人们逐渐淡忘了l d p c 码。 近几年，由 于m a c k e y和 n e a l 的 工作， 情况发生了 变化， 人们重新认识 到l d p c码所具有的优越性能及其巨大的实用价值，并且从理论上证明了 l d p c 码就是最佳码( s h a n n o n 创立信息论时就己 经证明了对于任意信道都存 在这样的分组码系列，使得任意以低于信道容量的速率进行通信的误码率都 能够任意的小。 人们称这样的码系列为最佳码) ， 而且在现在的技术条件下也 是能够实际应用的。目前，l d p c 已经成为纠错码领域的一个新的研究热点。 1 .2 l d p c码的研究现状 l d p c码的优异性能引起了世界各国学术界和 i t界的高度重视，人们 在深入研究 l d p c码理论的同时，也积极探索 l d p c码在实际中的应用并 且取得了丰硕的成果。目前， 研究表明l d p c码具有良好的应用前景， 将在 移动和固定无线通信、磁/ 光/ 全息存储、深空通信、光纤通信、卫星数字视 频和声频广播、 电 缆调制/ 解调器、 压缩图 像传输、 正交频分多路复用( o f d m ) 系统和数字用户线( d s l ) 等中得到广泛应用。 1 .2 . 1 l d p c码编译码算法的研究现状 h .b e h a i r y 和s .c .c h a n g 提出了 一 种并 行级联g a l l a g e r 码 ( p c g c ) ， 它 是将l d p c码应用与t u r b o 码的编码结构， 使用两个l d p c码编码器作为子 码，不使用交织器，与信息码元直接并行输出，取得了很好的效果2 1 y u k o u s h u l i n 和f o s s o r i e r 第一次用一种代数方法有限分析几何 来构造l d p c码， 生成循环或者准循环的码字， 因此可以用简单的线性反馈 移位寄存器进行编码，简化了编码过程的复杂性， 其纠错性能也很接近 s h a n n o n 极限3 1 哈尔滨工业大学工学硕上 学位论文 彭立等人介绍了一种低密度校验码的位翻转迭代解码算法， 分别采用了 硬判决和软判决进行了分析， 虽然软判决的算法复杂度要比硬判决稍微高一 些，但是仍然低于置信传播的算法复杂度4 1 刘水平等人评论了一类低编码复杂度的非正则l d p c码的设计问题。 将 编码器分为几个子编码器， 将几个子编码器串行级联。 综合了低密度校验码 和级联码的特点， 不仅编码算法简单， 而且有了固定的结构， 取得了很好的 性能1 5 1 s o n g h u i s h i 等人提出了一种改进经典的置信传播的译码方法， 在译码 复杂度和性能上取得了 很好的协调6 1 叶芳等人研究了一种构造l d p c稀疏校验矩阵的扩展比特填充算法， 能 够 在 较 低复 杂 度的 情 况下 构 造高g i rt h ( 圈 长 ) 的 校验 矩阵 7 1 贺玉成等人提出了一种基于置信传播的快速 l d p c码迭代译码量化算 法， 该算法具有应用对称性， 显著降低了计算复杂度， 降低了所需存储容量， 使得l d p c码在实际通信系统中的应用成为可能8 1 彭立等人介绍了一种l d p c码的编码器设计方案。以一矩阵为子矩阵， 通过对子矩阵进行适当的组合排列， 构造了一种低密度校验矩阵。 再由校验 矩阵构造正则l d p c码19 1 m. g .l u b y 等指出，基于非正则图定义的码性能优于相应的基于正则图定 义的 码 0 1 , m .c .d a v e y 提出， 在非 二 元 有限 域中 定 义 码 和 采用 具 有非 均 匀 行、 列重量的非正则 校验矩阵 均可改善码的 性能11 q 。 在寻找好的 码结构方面， d .j .c . m a c k a y 提出对非正则码采用先选择轮廓再选择结构的两步选择方法， 验证了 s u p e r - p o i s s o n结构具有较好性能， 并指出: 能快速编码的 l d p c矩阵 通常具有下三角形结构0 z 1 t . j . r i c h a r d s o n通过优化非正则图的度数结构来寻找逼近容量的非正则 l d p c码 1 3 1 . t .j .r i c h a r d s o n和r . l . u r b a n k e 探讨了 要获得高效编码器如何 确定校验矩阵稀疏度的问题， 以及如何构造码才能使编码时间与码块长度实 际 上 符 合线 性 关 系 14 1 o m .g .l u b y 提出 了 一 类 基 于 级 联 双向 图 的l d p c码 用 于可擦除信道， 它不仅是线性时间编码， 而且也可实现线性时间译码11 5 1 在 将 l d p c码应用于衰落信道的 研究中， m .c h i a n i , j .h o u , b .m y h r e 和t . w a d a y a m a 等 进 行了 积 极 的 探 索 7 6 1 7 1 . m .c h ia n i 对l d p c 码 用于 有记 忆 块衰落( b l o c k f a d i n g ) 信道时的 性能 进行了 评估。 j .h o u 研究了 用于瑞利衰落 信道l d p c码的优化和性能分析， b . m y h r e 提出一种速率自 适应l d p c编码 调制的方案用于慢变化平坦衰落信道，t . w a d a y a m a 针对l d p c码应用于突 哈尔滨工业大学工学硕 七 学位论文 发信道( 包括衰落信道) 的情况， 提出了适合于隐马尔可夫噪声信道模型的由 和一 积算法和前一 后向似然估计构成的迭代译码算法。 1 . 2 .2 l d p c码硬件实现的研究现状 s u n g w o o k k i m等人构造了一种生成矩阵和校验矩阵都是稀疏矩阵的 l d p c码，由于其编、 解码结构的简单性，非常适合使用超大规模集成电路 来 实 现 181 a n d r e w j .b l a n k s b y和c h r i s j .h o w l a n d 实现了1 0 2 4比 特，码率为1 / 2 的软判决 l d p c码的译码器。 该译码器采用并行结构， 在迭代6 4次时可得 达到最大的吞吐量为 1 g b / s 。 该译码器的最大特点是功率为6 9 0 m w ，由1 . 5 v 电 源 提 供即 可 1 9 a n a n d s e l v a r a t h i n a m, e u n c h e o l k i m, g w a n c h o i 构造t一种在光纤信道 使用的吞吐 量高 达2 . 5 1 g b p s 的 l d p c 码的译码器， 频率为 2 5 4 m h z ，使用了 1 3 0 万 的 c m o s 门 2 0 1 j u n l e e等人将低密度校验码用于磁信道中，并构造出了其硬件实现的 结构，其结构还可以 用于其他的t u r b 。 码类的译码器2 l t .b h a t t 等尝试性地提出采用定点d s p ( 数字信号处理器) 实现l d p c 码的 方案，认为其实现成本低于浮点d s p 12 o t .z h a n g 和k .k .p a r h i 提出了 一 种码与 译码器 联合设 计、 适合执行部分 并 行译码的 面向v l s i 实 现的 方 法2 1 b . l e v i n e 等则给出了一种可以用目前商用f p g a实现的l d p c 码验证性 设 计 2 1 t o n g z h a n g 提出了 一种联合的列重量为3 的 一类约束的编码器和译码 器的结构， 既能达到部分并行的高速译码， 而且也降低了编码器的实现难度 2 2 , 2 3 在z h a n g t o n g 等人的另外一篇文章中 详细介绍了 最大容量为5 4 m p s 列重为3 ， 行重为6 ，码长为9 2 1 6比特的低密度校验码的译码器12 4 1 。该译 码器时用x i l i n x公司的f p g a实现的，采用部分的并行结构，在迭代次数 最高为1 8 时， 在加性高斯白噪声信道下， 信噪比为2 d b时， 误码率为1 0 -6 0 h .a .l o e l i g e r 等建议: l d p c码的和乘积算法译码模块可直接用模拟 v l s i 实 现， 以 避免数字实 现中 十 分复 杂的实 数 运算lz s l o x i a o y u h u等人也 提出了 一 种针对和乘 积算法而构 造的 硬件结构2 6 1 。 分析了 串 行结构和并 行 哈尔滨工业大学工学硕士学位论文 结构， 分别对应于栅格和树型拓扑结构， 采用对数似然概率在信息节点和比 特节点之间传递，降低了算法复杂度。 s u n g w o o k k i m提出了l d p c 编 码器、 译码器的 硬件实 现结构 2 7 1 。 译码 器的结构既有串行结构，又有并行结构。取得了很不错的性能。 mo h a m m a d mi n z e r ma n s o u r 根据迭代译码的原理， 构造了一种了l d p c 译码器的结构2 8 1 。 并实现了在 1 2 5 m h z容量为 1 . 6 g b p : 译码器， 耗电 仅为 7 6 0 mw o f l a r i o n 技术公司已开发了l d p c编/ 译码器产品， 称为v e c t o r l d p c 2 9 1 a 采用f p g a实现钟频 l 0 0 mh z ， 码率r = 0 .9 ， 编码器利用6 4 k 逻辑门和 1 3 k b 存储器时，用户数据速率可达1 .9 g b i t / s ;译码器使用3 2 0 k 逻辑门和3 8 k b 存储器时，用户数据速率为3 8 4 m b it / s .采用a s i c实现，钟频3 2 5 m h z , r = 0 . 9 ，译码器使用2 .6 m逻辑门和 1 9 0 0 存储器时，可工作在 l o g b i t / s . 此外， f l a r i o n 还开发了v l d p c集成至o f d m的芯片组， 其中fl a s h o f d m f p g a ( v i r t e x e ) 的v l d p c资源占2 5 0 0 0 l b s ( l o g i c b l o c k s ) , fl a s h o f d m a s i c ( 0 . i 8 p m) 中的v l d p c占4 5 k 逻辑门。 v o c a l公司推出了一种用于wl a n的l d p c / t u r b o 不对称解决方案， 即下行链路采用l d p c码，上行链路采用t u r b o 码，目的在于节能。据称， 采用该方案后用于i e e e 8 0 2 . 1 i a / b / g wl a n移动终端的电池寿命可延长至原 来 的 4 倍 30 1 e . e l e f t h e r i o u 建议把l d p c码用在d s l中， 模拟结果显示， l d p c码获 得的编码增益与t u r b 。 码相当， 但是运算量大大低于t u r b o 码并且没有t u r b o 码中出现的差错平底现象 3 1 。在0 . 5 - l o m s 延时条件限制下， l d p c码获得 的 编码增益远高 于g .9 2 2 . 1 建议中使用的t r e l l i s - c o d e d 调制所获得的 编码增 益。 h .s o n g 研究了 在磁记录 信道中 应用l d p c码的 情况3 2 e e .y e a 等提出 了用于磁记录的2 类l d p c码的译码方案和相应的串行结构， 它们具有高的 吞吐率和低的计算复杂度。 1 . 3 本文主要研究内容 l d p c码由于t u r b 。 的提出而被人们重新发现， 成为了继t u r b o 码之后 纠错编码领域的又一个研究热点。本文主要对 l d p c码进行实现研究和 f p g a基础的硬件仿真。 哈尔滨工业大学工学硕十学位论文 本文的主要内容安排如下: 第 i 章 绪论。指出了本课题的研究背景，对纠错码的发展历程进行了 简要的回顾，介绍了l d p c码的提出，并对 l d p c码的编译码算法和硬件 实现的研究现状进行了阐述。 第2章l d p c码的基本原理。首先介绍了低密度校验码 l d p c的基本 定义，在此基础上讨论了 l d p c码的稀疏校验矩阵和 l d p c码的双向图表 示， 详细介绍了l d p c码的稀疏校验矩阵的构造方法， 接下来介绍了生成矩 阵的产生， l d p c码环检测和短环的消除; 然后介绍了消息传播算法集的基 本思想，详细讨论了概率域和对数域s u m - p r o d u c t 算法。 第3 章l d p c码编码器和解码器的设计。 选定了一种固定的码型， 根据 c = m g设计了比较通用的编码器。在译码器部分，采用性能最为优越的 s p a 和乘积) 的译码算法， 采用了 一种部分并行的方式进行设计， 在实现难 度和延迟时间上取了一个折中。 第4 章l d p c码编码器和译码器的仿真和分析。 在加性高斯白噪声信道 ( a wg n ) 下， 在q u a r tu a s i i 4 . 0 软件下用v e r i l o g h d l 完成了以f p g a为基 础的编码器和译码器的仿真. 最后给出了本文的结论。 哈尔滨工业人学工学硕士学位论文 第2 章 l d p c码的基本原理 2 . 1 l d p c码简介 2 . 1 . 1 l d p c码定义 一个 l d p c码是由一个稀疏矩阵的零空间来定义的。稀疏矩阵a有如 下性质: ( 1 ) 每行有p 个元素 “ 1 , ( 2 ) 每列 有y 个元 素“ 1 , ( 3 ) 任何两行对应位置均为 “ 1 ”的个数，不超过 1 ; ( 4 ) p, y 与矩阵的列数n 和行数m相比，是较小的数 。 矩阵的密度:矩阵a中“ 1 元素的个数与矩阵a所有元素的个数之比 称作矩阵a的密度， 记为; ，r = p 1 n = y l m o 由 于p 和y 相比 于m 和n 非常小，因此a的 密度也是很小的。 根据上面的性质( 3 ) ，可得a的任何两行最多只能有一个位置上的元素 同为“ 1 。 上面定义的l d p c码叫做正则码， 如果不是所有的行( 列) 都有相 同个数的 “ 1 ，则 l d p c码叫做非正则码。 正是山于l d p c码是一个线性码， 因此它可以由 一个校验矩阵的零空间 来描 述. 设x 是一个码字. 当 且仅当a x t = 0 o 2 . 1 .2 相关术语及参数 ( 1 ) 行重: l d p c 码 校验矩阵中 一 行中 非零 元的 个数， 记 作w r 。 ( 2 ) 列 重: l d p c 码 校 验 矩阵中 一 列中 非 零 元的 个数 ， 记 作w c e 特别的， 若所有的行重相同且所有的列重相同， 则为正则码。 一个正则码 ( d , 心) 的 校 验 矩 阵 是 正 则 的 ， d ， 为 列 重 ， d f 为 行 重。 ( 3 ) 4线循环图:在一个校验矩阵的等价二部图中，存在环且最小的环 长为 4 . ( 4 ) 线 性 码: 域f 9 上 的 线 性 码c 是 线 性 空 间f q 的 一 个 子 空 间 ， 若 这 个 线 性子空间的维数是k ，则称c为一个【 n , k 码，n 是码长，k 是码的维数。 ( 5 ) 码字:设c是一个【 n , k 码，c中的每个元素称为一个码字。 哈尔滨工业大学工学硕士学位论文 ( 6 ) 最小距离与最小重量:设x 和y 是是两个码字， x 和y 之间的距离 记 为d ( x ,y ) ，定义为 d (x ,y ) = ( ill “ n , x ; ， ， 川 向量x 的重量，记为。( x ) = d ( x , 0 ) 0 码c的最小距离定义为 m in d (x ,y ) x e c ,y e c x x y c的最小重量为 m i n 。( x ) 】 x e c , x * o 。 2 .2 l d p c码的编码原理 2 . 2 . 1 稀疏校验矩阵结构及其双向图表示 一个长为n的( n , d v , d , ) 正则l d p c码可以由一个mx n的稀疏校验矩 阵a来定义， 校验矩阵a的行重量和列重量分别为d , 和d v ( d , d应该是相 对于n来说很小的整数) 。 分别按行和按列来求稀疏校验矩阵1 的数目，容 易 得到n d , = m d , ， 从而正 则l d p c 码的 码率r = ( n - m ) l n= 1 - d y l d , . 一个m二 从的 稀疏校验矩阵对应的信息码元为k= n一 m位， 设要发送 的 源 信息向 量为s = ( s k - 1 i s k - 2 i , s o ) ， 则它的 码 字可以由 生 成矩阵g 的 转置 和要发送的源信息相乘得到，即码字向量t = g t s o l d p c码可以用 t a n n e r 图来表示，它包括两种类型的节点 ( 即变量节 点和校验节点) ，因此通常称为双向图( b i p a r t i t e - g r a p h ) 。双向图中每一个变 量节点x ， 对应于校验矩阵a的一列， 也和生成码字t 中的一比特相对应: 每 个校 验节点z i 对应于 校验 矩阵a的 一行，同 样 也和一 个校 验方程相 对应。 只有当 一 个变量 节点x ， 和一个 校验节点z i 所对 应的 校 验矩阵a中的 值为1 时， 这两个节点 之间的 边e = ( x , 动才存在。 每个变量节点( 校 验节点) 所连 接的 边数叫 做这个变量节点( 校验节点) 的 度数。 如图2 - 1 所示为一个( 8 , 2 , 4 ) 的正则码和它所对应的双向图， 显然变量节点 x ; ( 1 _ i 5 8 ) 和校验节点 z j ( 1 5 j :5 4 ) 的度数分别为2 和4 0 哈尔滨t业大学工学硕_ : 学位论文 变量节点 图2 - 1 正则校验矩阵及其对应的双向图 对于非正则l d p c码来说， 变量节点 ( 相应的校验节点) 有着不同的度 数。一个非正则 l d p c 码通常由一个度数分布对份 ， 川来指定， 兄 = 怀 i a 2 1 . . . i a d, ) 为 变 量 节 点 度 数 分 布 向 量 ， 其 中 凡 ( 1 _ i _ d , ) 表 示 度 数 为， 的变量节点所连的边与变量节点连接的所有边的数目 之比， d , 为变量节点的 最 大 度 数 。 相 应 地 p = 伍 , p 2 , , p ) 为 校 验 节 点 度 数 分 布 向 量 ， 其 中 p i ( 1 _ i _ d . ) 表示度数为i 的校验节点所连的边与 校验节点 所连接所有边的 数目 之比， 祷为校验节点的最大度数。 同度数分布相对应的是生成函数， 一 个非正则码的生成函数可以 表示为式( 2 - 1 ) 和式( 2 - 2 ) a (x ) = y- id.2 a ;x -i (2 - 1 ) p ( x ) 一 2 d.2 只 x i-1y- i= 2 p ; x (2 - 2 ) 如图2 - 2 所示为 一个非 正则l d p c 码的 双向 图， 这里凡= 0 .4 , 凡= 0 .6 , p 3 = 0 .2 , p 4 = 0 .8 ，生 成函 数为a ( x ) = 0 .4 x + 0 .6 x 2 和p ( x ) 二 0 .2 x 2 + 0 .8 x o 校验节点 变量节点 图2 - 2 非正则码的双向图 2 .2 . 2 校验矩阵的生成 正则 l d p c码的稀疏校验矩阵可以采用随机生成方法、有限几何学方 法、代数方法等来设计，这些方法都有着各自的优点和局限性。 哈尔滨工业大学t学硕士学位论文 ( 1 ) g a l l a g e r 的构造方法 g a l l a g e r 提出了一种生成正则校验矩阵的方法， 是系统地构造参数为( 从d , d , ) 正则校验矩阵a 。 图2 - 3 所示的矩阵可以说明 这种构造方法的基本思想， 这种系统形式的校验矩阵可以分为d v 个子矩阵， 每个子矩阵的一列只有一个 i 。 这d v 个子矩阵的第一个子矩阵包含的1 是按 降序排列， 也就是第一个子矩阵第i 行只有从( i - i ) d , 列到i d , 列为1 。 其它子 矩阵仅仅是第一个子矩阵的随机列置换， 每种置换方式有着相同的概率。 这 种方法产生的校验矩阵很有可