（通信与信息系统专业论文）qcldpc码的研究与fpga实现.pdf

摘要 低密度校验码( l o w d e n s i t yp a r i t y - c h e c kc o d e s ，l d p c ) 已经被证明是一类纠 错性能逼近香农限的渐近好码。由于低密度校验码具有译码复杂度低、错误平层 低等诸多优点，它的良好应用前景已经引起学术界和r r 业界的高度重视，也使 其成为当今信道编码领域最受瞩目的研究热点之一。q c l d p c ( q u a s i c y c l i c l d p c ) 码是l d p c 码的一个子类，它在构造、编码和译码等方面，具备了其它类 型的l d p c 码不具有的很多优点。本文就q c l d p c 码的一些关键问题进行了研 究。主要完成的工作有以下几方面： 系统介绍了l d p c 码构造的基本方法，重点以一种基于有限域的代数方法对 q c l d p c 码的构造进行了研究。 系统地介绍了l d p c 码的编码方法和译码方法，重点研究了针对q c l d p c 码的编码实现方法和l d p c 码的最小和译码算法。 最后，在前面理论分析的基础上，结合硬件平台仿真，给出了准循环l d p c 码的编码器和译码器的f p g a 实现方法，主要包括了编译码器的总体结构设计， 各子模块设计、门级仿真结果等。其中编码是通过准循环结构的生成矩阵进行的， 译码则采用归一化最小和算法。 关键词：准循环l d p c 码有限域归一化最小和算法f p g a 编译码器 a b s t r a c t l o w d e n s i t yp a n t y - c h e c k ( l d p c ) c o d e sh a v eb e e ns h o w nt oh a v eg o o de r r o r c o r r e c t i n gp e r f o r m a n c et h a ta p p r o a c h e st h es h a n n o nl i m i t d u et ot h ea d v a n t a g e so f l d p cc o d e s ，s u c ha sl o w e rc o m p l e x i t yo fd e c o d i n ga n dl o w e re r r o rf l o o r , t h e i r a p p l i c a t i o n sh a v er e c e i v e dg r e a ti n t e r e s t sa n dh a v eb e c o m eo n eo fm o s ta t t r a c t i v ef i e l d i nc h a n n e lc o d i n gc o m m u n i t y q u a s i c y c l i cl d p cc o d e sf o r ma ni m p o r t a n ts u b c l a s so f l d p cc o d e s t h e s ec o d e sh a v ea d v a n t a g e si nm a n yr e s p e c t so v e ro t h e rt y p e so fl d p c c o d e s ，s u c ha sc o n s t r u c t i o no fc o d e s ，e n c o d i n ga n dd e c o d i n go fc o d e s a n d ，t h i st h e s i s i n v e s t i g a t e ss o m ek e yp r o b l e m so fq c l d p cc o d e s t h em a i nw o r k sa r es u m m a r i z e d a sf o l l o w s ： f i r s t s o m ec o n s t r u c t e da p p r o a c h e so fl d p cc o d e sa r es y s t e m a t i c a l l ys u m m a r i z e d ac o n s t r u c t e dm e t h o do fq c l d p cc o d e sb a s e do i lf i n i t ef i e l di sd e s c r i b e di nd e t a i l a n de n c o d i n ga n dd e c o d i n gm e t h o d so fl d p cc o d e sa r ea l s o s y s t e m a t i c a l l y s u m m a r i z e d e s p e c i a l l y , t h ee n c o d i n ga l g o r i t h mf o rq c - l d p cc o d e si se m p h a t i c a l l y i n t r o d u c e d a n d ，t h em i n - s u ma l g o r i t h m ( m s a ) i sa l s od e s c r i b e di nd e t a i l b a s e d0 1 1t h e o r e t i c a la n a l y s i sa b o v e ，c o m b i n e dw i t ht h eh a r d w a r es i m u l a t i o n , t h e f p g ai m p l e m e n t a t i o nm e t h o do fe n c o d i n ga n dd e c o d i n gf o rq c - l d p cc o d e sa r e p r o p o s e d ，a n da l lt h em o d u l e si nt h ef p g ad e s i g na n dt h eh a r d w a r es i m u l a t i o nr e s u l t s a r ea l s oi n t r o d u c e d 1 1 1 ee n c o d i n gs c h e m ei sb a s e do nt h eg e n e r a t o rm a t r i xo ft h e q u a s i c y c l i cs t r u c t u r e , n o r m a l i z e dm i n - s u ma l g o r i t h m ( m m s a ) a l g o r i t h mi su s e di n t h ed e c o d i n gs c h e m e k e y w o r d ：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 kc o d e s f i n i t ef i e l d n o r m a l i z e dm i n s u ma l g o r i t h mf p g ac o d e c 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：鎏亟堑日期型坦! ! ! 丝 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： 导师签名： e t 期三叫堡翌 日期一垫丝! ! ! 丝 第一章绪论 第一章绪论 本章首先简要介绍了数字通信系统的基本模型并概括了信道编码理论与技术， 接着简要概括了l d p c 码以及它的发展历史和研究现状，最后给出了本文的主要 工作和后续章节的行文安排 1 1 数字通信与信道编码理论 当今信息社会，通信技术飞速发展，各种现代化的通信设备进入人们的日常 生活，满足了人们丰富的信息需求。数字通信以其抗干扰、差错可控等众多优点 在现代通信领域应用尤为广泛。各种数字通信系统，包括移动电话、数字电视、 数字广播、有线或无线的因特网接入，还包括数字计算机的存贮系统和内部运算 以及数字计算机之间的数据传输等，尽管它们的实现细节大不相同，但它们都可 等效为图1 - 1 所示的典型数字通信系统模型。 图1 1 数字通信系统框图 图1 - l 中，信源可能是一个人或一台机器( 例如一台计算机或数据终端) ，信 源的输出可以是连续波形，也可以是离散的符号序列信源编码器将信源的输出 转换为二进制数字序列，这些序列称为信息序列。信源编码器被理想化的设计成： ( 1 ) 为表示信源输出所要求的比特率最低；( 2 ) 信源输出可以从信息序列确切地 重现。 信道编码器将信息序列变换成离散的编码序列，称之为码字。尽管在某些应 用中采用非二进制码，但在大多数情况下是二进制序列。 离散符号并不适合在物理信道上传输，也不适合记录到数字存储媒质上。数 字调制器或写入单元将信道编码器输出的每个符号转换为适合信道传输( 或记录) q c l d p c 码的研究与f p g a 实现 的波形。这些波形进入信道或存储媒质并受到噪声的干扰。典型的传输信道包括 电话线、移动蜂窝电话、高频无线电、微波和卫星链路、光缆等。典型的存储媒 质包括磁芯和半导体存储器、磁带、光盘、光存储单元等。这些例子中的每种都 受到不同类型的噪声干扰。解调器或读出单元处理信道或存储媒质输出的每一个 波形，然后产生离散( 量化) 或连续( 非量化) 的输出相对于编码序列，解调 器的输出序列称之为接收序列。 信道译码器将接收序列变换为二进制序列，称之为估计信息序列。译码策略 基于信道编码规则和信道( 或存储媒质) 的噪声特性而定。 信源译码器将估计信息序列变换为对信源输出的估计，并将该估计传送到信 宿。对于一个精心设计的系统，除非干扰太严重，否则这个估计将会是对信源输 出的准确重现。 在数字通信系统中，信息的传输( 或存储) 所遇到的最主要的问题是在传输 过程中出现的差错问题，也就是传输的可靠性问题。因此，数字通信系统设计的 主要问题就是如何控制差错以使得数据能够可靠的传输1 9 4 8 年，c e s h a n n o n 在他的开创性论文通信的数学理论( am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n ) t i j 中，应用概率论来研究和分析通信系统，首次阐明了在有噪信道中实现可靠通信 的方法，提出了著名的信道编码定理，从而奠定了信息论和编码理论的基石。 s h a n n o n 在文中【i j 指出：任何一个通信信道都有确定的信道容量c ，如果通信系 统所要求的传输速率r c ，则存在一种编码方法，当码长露充分大并应用最大似 然译码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 ) 时，信息的错误概率可以达到任意 小。这就是著名的有噪信道编码定理。要达到或接近该定理所提到的信道容量c ， 应该采用无限长的随机码，而译码应该采用最大似然译码。但是，采用随机编码， 使码长趋于无穷大并且采用最大似然译码将会使系统的复杂度和延时变得太大， 因而无法在实际中使用。 信道编码定理是一个存在性定理，它没有告诉我们如何构造实际中可实现并 且具有定理中所述性能的码的方法。这也正是信道编码要解决的问题，它推动了 信道编码理论以及数字通信系统的飞跃发展 迄今为止，信道编码已有了5 0 年的历史，无论是在理论还是在实际中都得到 了飞速发展，其发展过程大致分为以下几个阶段：5 0 年代至6 0 年代初，主要研 究各种有效的编、译码方法，奠定了线性分组码的理论基础；提出了著名的b c h 码、r s 码以及卷积码的序列译码；给出了纠错码的基本性能限；还出版了纠错码 的第一本专著。这是纠错码从无到有得到迅速发展的年代。 6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期不仅提出了许 多有效的编译码方法，如门限译码、迭代译码、软判决译码和卷积码的维特比 ( v i t e r b i ) 译码等而且注意到了纠错码的实用化问题，讨论了与实用有关的各 第一章绪论 种问题，如码的重量分布、译码错误概率和不可检错误概率的计算、信道的模型 化等，所有这些问题的研究为纠错码的使用打下了坚实基础。 7 0 年代初至8 0 年代，这是纠错码发展史中具有极其重要意义的时期。在理论 上以戈帕( g o p p a ) 为首的一批学者，构造了一类g o p p a 码，其中一类子码能达 到香农在信道编码定理中所提出的码香农码所能达到的性能，由于译码复杂 度过高而没有得到广泛应用，但这引起了一批学者对代数几何码的研究兴趣。在 这期间大规模集成电路和微机的迅速进展，为纠错码的实用打下了坚实的物质基 础，因而与实用相关的各种技术及有关问题得到了极大关注，并在实用中取得了 巨大成功。1 9 8 2 年，u n g e r b o e c k 将卷积码和调制技术结合成一个整体进行设计， 提出了网格编码调制技术( t r e l l i sc o d e dm o d u l a t i o n , t c m ) 瞄j ，这一成果对带宽受限 中的编码调制技术的发展具有划时代的意义，在现代通信系统中获得了广泛的应 用。 1 9 9 3 年，b e r r o u 等人提出的t u r b o 码【3 4 】被看作信道编码理论研究的重要里程 碑。b c r r o u 等人将卷积码和随机交织器相结合，同时采用软输出迭代译码来逼近 最大似然译码，取得了超乎寻常的优异性能和可以接受的编译码复杂度。在 a w g n 信道中，采用b p s k 调制的1 2 码率t u r b o 码，用大小为6 5 5 3 5 的随机交 织器进行交织和1 8 次迭代译码的情况下，在信噪比e w q q 0 = 0 7 d b 时，误码率可以 达到1 0 5 【3 , 4 1 。t u r b o 码的性能一举超越了截止速率，并且逼近了香农容量限，是 一种信道编码理论界一直梦寐以求的可实用非常好码，它的出现标志着信道编码 理论研究进入了一个崭新的阶段。随着对t u r b o 码研究的深入，人们重新发现 g a l l a g e r t 5 】早在1 9 6 2 年提出的l d p c ( l o w d e n s i t yp a r i t y - c h e c k ) 码亦是一种具有 渐进特性的好码，它采用和积译码算法，译码性能同样可以逼近香农限。由于 l d p c 码在长码上具有超过t u r b o 码的性能，并且具有译码复杂度低、可并行译 码以及译码错误的可检测性等特点，从而成为了信道编码理论新的研究热点。 1 2l d p c 码和图表示 低密度校验码( l o wd e n s i t yp a r i t yc h e c kc o d e s ) 是一类线性码，是因它的校 验矩阵是稀疏矩阵( 即校验矩阵中非零元素的个数占总元素个数的比例非常小) 而得名的。它能以可实现的接近香农限的译码算法进行译码。由于线性码c 可以 由生成矩阵g 或校验矩阵日唯一确定。如果码是由校验矩阵日确定的，则码c 就 是日的零空间。若一个码长为、信息位数为k 的线性码由一个生成矩阵g h 定 义，信息序列分组s “通过g 被映射到码字f = s g 。线性码也可以由一致校验矩 阵日吖，等效描述，所有码字均满足h c r = 0 。校验矩阵的每行表示一个校验约 4 q c - l d p c 码的研究与f p g a 实现 束z ，其中所有非零元素对应的码元变量c ，构成一个校验集，由一个校验方程表 示。校验矩阵的每一列表示一个码元符号参与的校验约束。根据校验矩阵的不同， l d p c 码分为两大类：规则l d p c 码和非规则l d p c 码。规则l d p c 码也称为 g a l l a g e r 码，它的校验矩阵的每行( 列) 中的非零元素个数相同，而非规则l d p c 码的校验矩阵每行( 列) 的非零元素个数未必相同。 g a l l a g e r 发明了l d p c 码之后，几乎被编码研究人员遗忘了2 0 年。直到1 9 8 1 年t a n n e r 发表论文【6 j 弓i a , 线性分组码的图形表示法( 即t a n n e r 图) ，表达了码字 比特与校验它们的校验和之间的关系。而且基于他自己提出的图形表示法，提出 了一种简单的l d p c 译码方法。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 图中，每个编码比特( 对应于校验 矩阵中的列) 对应一个顶点，称为变量节点( v a r i a b l en o d c ) 或者比特节点( b i t n o d e ) 。每个校验约束( 对应于校验矩阵中的行) 用一个顶点表示，称为校验节 点( c h e c k n o d e ) 。若某个比特参与了某个校验约束，即校验矩阵中对应位置的元 素不为零，于是在对应的变量节点和校验节点之间连一条边，把所有的边都连好 后，所得的图就是与该校验矩阵对应的t a n n e r 图。 下面是有关t a n n e r 图的几个定义： 度数( d e g r e e ) ：与一个顶点相连的边的数量。显然，变量节点的度数等于该 变量节点所对应的奇偶校验矩阵的列的列重，而校验节点的度数等于该校验节点 所对应的奇偶校验矩阵的行的行重。 环( c y c l e ) ：由变量节点、校验节点和边首尾相连组成的闭合环路。需要说 明的是，如果t a n n e r 图上包括短环，如长度为4 或6 的环，会影响译码性能。 围长( g i r t h ) ：码字t a n n e r 图中最短环的周长。 规则l d p c 码具有规则的t a n n e r 图结构，即每个变量节点与恒定数目的校验 节点相连，变量节点的度数不变；每个校验节点与恒定数目的变量节点相连，校 验节点的度数也不变。图1 2 ( a ) 是一个( 8 ，2 ，4 ) 短码的校验矩阵及校验方程组，图 1 2 ( b ) 是相应的t a n n e r 图表示，z l ，乞，毛，z 4 表示校验节点，玉，吒黾，毛，氏，而，黾 表示变量节点。 10101010i l 毛+ x 3 + x 5 + x 7 = 0 10 0 1010 1 ll 五+ + 魄+ 黾= 0 01 1 0 0 110i i 恐+ 毛+ 气+ 而= 0 010 1100 1 j【屯+ 一+ 毛+ 黾= 0 第一章绪论5 z i z 2z 3z 4 x lz 2工3 x 4 兀5 工6工7 x s ( b ) t a n n e r 图表示 图1 2 ( 8 ，2 ，4 ) l d p c 码的校验系统及t a n n e r 图表示 对于非规则l d p c 码，变量节点和校验节点的度数都不是确定的值，通常用 度分布对( d e g r e ed i s t r i b u t i o np a i r ) ( 名，力来描述，即 d。d。 无( x ) = 以x 卜1 ，p ( x ) = 乃x 产1 i = 2 j = 2 式中，兄( 石) 和p ( x ) 分别是变量节点和校验节点的度数分布多项式，五( b ) 表 示与度数为f ( ，) 的变量( 校验) 节点相连的边数在总边数中所占的比例，巩( 吐) 表 dd 示变量( 校验) 节点中的最大度数，且分别满足名，= l 和尸j = l 。 1 3l d p c 的发展与研究现状 l d p c 码的起源最早可以追溯到1 9 6 2 年g a l l a g e r 的博士论文“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 ”r 。g a l l a g e r 提出的二元l d p c 码是一类用稀疏奇偶校验矩阵定 义的线性分组码，这类码具有很好的汉明距离特性，在计算树上进行多次迭代后 验概率译码可以获得依码字长度呈指数降低的比特错误概率，后来人们把这种码 称为g a l l a g e r 码。由于当时计算机水平较低以及人们对这种码的认识不足，它的 出现并没有引起人们的重视，被认为是不实用的码，接下来几十年一直无人问津。 1 9 8 1 年t a n n e r 的一篇文章 6 1 为基于图模型的码奠定了基石，他引入了l d p c 的二 分( b i p a r t i t e ) 图，又称t a n n e r 图或双向图，还提出了和积( s u m p r o d u c t ) 算法 和最d , 和( m i n s u m ) 算法两种消息传递算法。直到1 9 9 3 年t u r b o 码【3 】出现以后，研 究者们才发现t u r b o 码迭代译码的方法和码集合的概念与l d p c 码有异曲同工之 妙。1 9 9 6 年，m a c k a y t s 】和s p i e l m a n l 9 】等人再度发现l d p c 码性能优异，2 0 0 1 年， c h u n g 等人【i o 】设计了1 2 码率的l d p c 码，其门限值离s h a n n o n 限在0 0 0 4 5 d b 之 内，这些可喜的成果唤起了人们对l d p c 码的研究热潮。 6 q c l d p c 码的研究与f p g a 实现 当前有关l d p c 码的研究热点主要包括快速编码、译码算法、码性能分析、 码构造、多进制l d p c 码以及基于d s p 或f p g a 的硬件实现及基于实际通信系统 的应用等。 在码构造方面，主要可以分为两大类，即代数构造方法和随机构造方法在 代数构造方法方面，s h ul i n 等学者提出了基于有限几何构造的l d p c 码【l ，这 类码在高码率时可以获得较好的性能，并且适宜采用循环移位寄存器实现线性时 间编码。此外，他们还提出了基于r s 码构造的l d p c 码，这类码也具有良好的 最小距离特性【1 2 l 。t a n n e r 和f o s s o r i e r 等人提出了基于循环移位矩阵构造的l d p c 码【l3 1 ，这类码容易消除小环，并且同样适宜用循环移位寄存器实现编码。此外， 还有一些基于其他数学工具的构造l d p c 码方法，包括差集、序列等。在随机构 造方法中，比较著名的有x i a o - y uh u 等学者采用逐步最优思想提出的一种称为 p e g ( p r o g r e s s i v ee d g eg r o w t h ) 算法【1 4 1 。该算法可以在给定度序列条件下构造较 大围长的l d p c 码。r y a n 等学者设计了可以快速编码的中等码长高码率的非规则 l d p c 码【1 5 】，这类码实质上是一种非规则r a 码此外还有l d p c 卷积码和广义 l d p c 码等码类。 在译码方面，f o s s o r i e r 等学者提出了一种简化的b p 算法，并采用归一化因子 来进一步改善译码性能【1 6 】一些学者采用密度进化结合仿真分析了s c a l i n g ( 对软 信息数乘) 、c l i p p i n g ( 限幅) 和q u a n t i z a t i o n ( 量化) 等对最小和算法的影响以及如何 优化。此外，也有学者研究了和积算法的量化实现。甚至，有学者研究采用线性 规划这样的优化算法来译l d p c 码。 q c l d p c ( 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 ) 码是根据系统化构造方法构造 的一类非常重要的l d p c 码，目前已经成为面向硬件实现l d p c 码研究的热点。 q c l d p c 码可以采用移位寄存器的方式进行编码，大大降低了编码复杂度。针对 该类型码字的准循环特性，可以专门设计适用于该类型码字的译码器。 q c l d p c 一般由代数几何的方法构造，其中最有成效的应该算是由yk o u 和 s l i n 引入的基于有限几何( f i n i t eg e o m e t r y ) f f j 低密度校验码，以及用组合构造的 方法设计的准循环l d p c 码，该类l d p c 码通过调整相应的参数快速的构造大量的 不同码率且性能较为合适的校验矩阵。 在硬件实现方面，美国a l b e r t a 大学研究人员成功地在现场可编程门阵列( f p g a ) 上实现 l d p c 编码排列，大幅度增强数据流和包交换系统的结构效率。z b h a r 等 人提出采用定氧d s p 实f 觅l d p c 码的编译码方案 1 y 1 h a l o e l i g e r t l 8 】等人运用模拟 v l s i 实现l d p c 码的和积算法译码模块，可以避免数字实现中十分复杂的实数运 算。t 动锄g 和k p a r h i 等人提出了一种编译码器联合设计、适合执行部分并行译码 的面向v l s i 实现的方法 1 9 1 。b l e v i n e 等人则给出了一种可以用于目前商用f p g a 实 现篚j l d p c 码验证性设计方案【2 0 】。 第一章绪论 f l a r i o n t e c h n o l o g i e s 公司实现了专有的l d p c 编码方法【2 1 1 ，已开发出名为 v e c t o r - l d p c 的l d p c 编译码器产品。w w i s e 联盟最近也向8 0 2 i l n w l a n 标准工 作组提出了一种l d p c 区块编码( b l o c kc o d i n g ) 方案，该编码方案可渗入到许多协议 内，以接近容量极限的噪音信道性能，使通信设计更接近s h a n n o n 极限。在芯片方 面，c o m t e c h t e l e c o m m u n i c a t i o n s 旗下的c o m t e c h a h a 公司( a h a ) 推出了一种l d p c 码前向纠错( f e c ) 编解码器内核。该l d p c 码内核比其它商用f e c 方式具有更高的 误比特率性能。由于整合了高反复性能，该l d p c 码的误比特率b e r 比现有其它纠 错技术更接近s h a n n o n 极限，其u ) p c 内核支持多种编码、调制格式及数据率，可 动态改变以适应变化的信道条件。 l d p c 码理论的深入发展推动了其实用化进程。 在无线城域网的i e e e 8 0 2 1 6 e 1 2 2 草案中，l d p c 码与t u r b o 码一起作为编码调 制的备选方案。草案中，采用矩阵分块技术( 码长从2 0 3 4 到5 7 6 ，码率为1 2 ，2 3 ， 3 4 ) ，将大规模的矩阵乘运算分解为小规模矩阵乘的并行结构，有效的解决了 l d p c 码编码复杂度高的问题。 舭的l d p c 码适用于远距离传输，能减少多种通信系统的传输功率，可应 用于无线、卫星通信、磁存储器及其它数据通信等方面。除了3 0 m b p s 的l d p c 内核外，a h a 还推出了一种单机l d p c 内核。 基于l d p c 码的编码方案己经被下一代卫星数字视频广播标准d v b s 2 采纳。 l d p c 码长度分别为6 4 8 0 0 和1 6 2 0 0 ，最低码率为1 4 ，最高码率为9 1 0 。休斯网络系 统将l d p c 码作为可合成核心，向半导体公司发放许可证。持有许可证的半导体公 司己于2 0 0 5 年下半年生产出业界首款基于l d p c 码的数字解调芯片，并将其应用于 遵循d v b s 2 的机顶盒中。在我国地面数字电视传输标准建设备选的方案中【2 3 l ，广 科院的t i m i 方案性能较好。该方案最大的技术亮点就是采用了l d p c 码信道编码技 术，最优地解决了保持l d p c 编译码性能最佳的状况下实现复杂度的难题。据此， i e e 8 0 2 1 l n 工作小组全体通过了在面向双绞线的1 0 g b i f f s 以太网标准1 0 g b a s e 草案 中采用l d p c 码。此外，低密度校验码在数据压缩、水印等方面的应用也取得了一 些成果。 总之，l d p c 码具有良好的性能，译码易于实现。当各变量节点与校验节点的 度数选择合适时，其性能非常接近香农限。目前，l d p c 码己成为第四代移动通信编 码技术中的首选和c c s d s 深空通信的备选码字。 1 4 行文内容和安排 本文主要对l d p c 码的一个子类q c l d p c 的若干问题进行了研究，包括码 8 q c l d p c 码的研究与f p g a 实现 的构造、编码和译码算法、f p g a 实现。由于多数非二元l d p c 码是由二元l d p c 码推广而来的，因此本文主要介绍二元l d p c 码的相关内容。全文共分为五章， 其它章节的具体内容安排如下： 第二章主要研究q c l d p c 码的构造方法。首先综述了l d p c 码的构造问题， 包括随机构造方法和结构化构造方法；接着简要介绍了q c l d p c 码的的基本概 念和特点；最后重点介绍了二元q c l d p c 的构造方法，主要针对基于有限域的 构造方法进行研究。 第三章主要研究q c l d p c 码的编码和译码问题。本章主要介绍q c l d p c 码 的编译码算法。首先介绍编码算法，先介绍了几种基于校验矩阵进行编码方法， 然后介绍了一种基于生成矩阵进行q c l d p c 有效编码的方法；接着对l d p c 码 的译码算法做了简要介绍，主要针对和积算法和最小和算法进行讨论。 第四章主要研究二元q c l d p c 的编译码器的f p g a 实现，并就其中的主要 问题进行分析，对实现过程中的主要模块进行介绍其中编码采用基于准循环结 构的生成矩阵的带反馈的移位寄存器的方法，译码采用修正最小和算法，具体的 编码和译码方法在第三章中会做详细讨论。 第五章对全文的工作进行总结。 第二二章q c l d p c 码的构造 9 第二章q c l d p c 码的构造 本章首先对l d p c 码构造的研究现状做简要概括，接着简要介绍了q c - l d p c 码 的基本概念，最后详细讨论了二元q c - l d p c 码的构造方法，其中主要介绍了一种 基于有限域构造q c - l d p c 码的方法，主要包括校验矩阵基矩阵的构造以及阵列扩 展的方法 2 il d p c 码的构造 l d p c 码的构造实际上就是根据不同的设计准则构造具有低密度特性的校验 矩阵日。一般说来，构造l d p c 码的奇偶校验矩阵日有两种方法。一种是随机 构造法，即先对校验矩阵日设置一些属性限制，如最小环长或节点度分布等，再 利用计算机搜索的方法随机或者类随机生成奇偶校验矩阵日，主要包括：g a l l a g e r 构造法、m a c k a y 构造法、超轻( u r l t r a - l i g h t ) 构造法、比特填充( b i t - f i l l i n g ) 构造法、 扩展的比特填充构造法、p e g ( p r o g r e s s i v ee d g e - g r o w t h ) 构造法以及基于外信息度 e m d ( e x t r i m i cm e s s a g ed e g r e c , e m d ) 的构造法。其中，前三种构造法主要针对规则 码( 日矩阵的行重列重固定) 的构造，后四种主要针对非规则码( h 的行列重不 为固定值) 的构造。上述的随机搜索方法由于没有太多的约束，所构造的l d p c 码性能一般较好，但由于随机性较强，不利于编码器的硬件实现。为此，学者们 提出了结构化的构造方法，以期使构造简单，且简化编码硬件实现。这些设计主 要是基于代数学方法和组合数学方法，常见的方法包括有限几何构造法、组合构 造法、由t a n n e r 和f o s s e r i e r 等改进的准循环l d p c 码构造法、分组移位构造法、 兀旋转构造法等。结构化方法构造的l d p c 码由于一致校验矩阵( 有时甚至包括 生成矩阵) 在结构上呈现出较强的规律性，使其编码容易实现，但目前对其t a n n e r 图中相应环结构的深入分析还很少，以至于很难有针对性地结合码性能进行结构 优化。下面就几种基本的构造方法做一简要的介绍。 2 i 1 随机构造法 ( 1 ) g a l l a g e r 方法 g a l l a g e r t 7 1 采用( 以，工七) 来表示一个规则低密度校验码，其中以表示码长，_ ，表 示校验矩阵中每列所含“l 的个数，而k 则表示校验矩阵中每行所含“1 的个 数。g a l l a g e r 采用随机置换的方法来构造校验矩阵，方法如下：( 1 ) 将校验矩阵日 1 0 q c l d p c 码的研究与f p g a 实现 分成，个子矩阵日，日2 ，日，每个子矩阵有伽一k ) ，行，并且每个子矩 阵的每列有且只有一个“1 ；( 2 ) 子矩阵日1 中的“l ”呈下降的阶梯状排列，即 第衍亍的k 个“l “从第“一1 ) k + 1 位排到第访位；( 3 ) 其余的子矩阵通过对日1 进 行随机列置换得到，所有置换是等概出现的。图2 1 所示为依此方法构造的一个 ( 2 0 ，3 ，4 ) l d p c 码。 从上面的构造方法不难知道，由g a l l a g e r 方法构造的校验矩阵并不是满秩的， 因为任意两个子矩阵的所有行向量是线性相关的。如果l d p c 码的监督矩阵是满 秩的，则其码率r = k n = 1 一胁万= 1 一y k ，因此g a l l a g e r 的方法构造的l d p c 码码率通常小于r 。由于g a l l a g e r 构造法中给出了一些约束条件，如对于行列重 量的限制等等，所以这类构造方法获得的性能还不是很理想，并且对于矩阵较大 时，构造的复杂度也很大。 lllloo oo oo0oo ooooo o o00 olllloo0ooo oooo0 o00o 0ooolllioo oo0 0 0 000 0o0ooo0o0lllloo0 0000000o00000 000l 11 lo00l0o01oool0oo000 0l0o dlo o olo0oo00l 00 o0loodlo0ooool0ool0 oo0lo o0o0ol000l000l 000000010 00100 0l0 0 0 l000ol00o 0 0lo0000l0 0loo 0 olo0ol0 o00looo 00 lo ooo iooool0oo 00l 000l00 00loo00l0 0lo 0 000ol0 000lo 000l00o0 图2 1 ( 2 0 ，3 ，4 ) l d p c 码 ( 2 ) m a c k a y 的随机方法 m a c k a y 构造的校验矩阵 2 4 1 ，使其对应的t a n n e r 图中循环的数目最少，同时 引入列重为2 的列( 这有利于译码，但会引入低重码字) 。m a c k a y 描述了四种关 系密切的矩阵构造方法，得到的矩阵去掉了长度为4 的短环四种构造方法依次 如下。 构造l ：膨矩阵日随机构造，列重t ( 如t = 3 ) 固定，行重f ，在每行中均 匀分布，而且两列间不存在周期为4 的环。这是基本的构造法，如图2 2 所 不 一 构造：矩阵日中，m 2 列的列重为2 ，这些列重为2 的列由两个 ( m 2 ) x ( m 2 ) 的单位矩阵上下叠放构成。如图2 3 所示。 o o o l o o o o l 第二章q c l d p c 码的构造 构造：删除i 和i i 方法所构造矩阵中的某些列， 有周长为某个长度( 如，= 6 ) 的短循环。 图2 2t = 3 ，= 6 ，码率1 2 使得矩阵的t a n n e r 图中没 图2 3 码率l 3 ( 3 ) 比特填充与扩展比特填充方法 比特填充法主要解决以下两个问题：一是给定比特节点数t 、比特节点度数a 和围长g ，使校验节点数t n 尽量小；二是给定校验节点数肌、比特节点数t 、比 特节点度数a 和校验节点度数b ，其中m b = 加，使围长g 尽可能大。比特填充法 的具体步骤如下： 假设已经得到了一个具有刀列的矩阵日，其列重为a 、行重没有超过b ，且围 长为g ：现在增加第疗+ 1 列到日上，把新列作为一个大小为a 、初始为空的集合 u ，它是以校验节点为元素的一个集合，是 1 ，2 ，m 的一个子集：进一步假设 已经增加了i 个校验节点到u ( o i 。t a n n e r 图由集合( 矿，e ) 表示。其中y 是节点的集合， v = k u r , 。e 是边的集合，当且仅当j | l f 。，0 ，鬼，h ，o f r - i ，0 _ ，n - i 时，边( c i ， ，f ) e 。假设变量节点的度序列为鼠= d o ，氐，d m 一，) ，其中巩，是变 量节点巧的度。校验节点的度序列为皿= 叱，如9 ooo ，如一。) ，其中如是校验节点白 的度。e = 民u eu u 民一，其中e ，包含了连接节点巧的所有边，连接节点y ， 的第k 条边表示为砖，0 s k s 或；一1 定义在以变量节点v ，为根节点扩展的深度 为，的树中所包含的校验节点集合为职，其补集为膨，则州，+ 影，= 匕。 基于上面的参数定义，具体的p e g 算澍2 5 j 如下： ( 1 ) 初始化：j = 0 ，k = 0 。 ( 2 )若k = 0 ，e = 边( c f ，1 ，) ，其中白是当前图民u 毛u u 毛中度最 小的校验节点。k = k + 1 若k 西，继续执行下一步骤，否则执行步骤( 4 ) 。 ( 3 )若k 0 且k 西，将当前图以y ，为根节点扩展成深度为，的树。若 影，f 2 j ，但影+ l = f 2 j 或者卅，随着，的增加不再增加但始终小于肼，磁聋边( c ，) ， 其中c 是影，中度最小的校验节点。k = k + l 。若k 巩，执行步骤( 3 ) ，否则执行 步骤( 4 ) 。 ( 4 )若k = 巩，j = j + l ，k z 0 若_ ， 刀，执行步骤( 2 ) ，否则终止整个过程。 p e g 构造的中、短码长的l d p c 码的性能要优于随机构造的l d p c 码的性能， 这是因为随机构造的t a n n e r 图无法保证环长和码最小距离的下限，而p e g 算法 构造的t a n n e r 图具有优秀的环长和码最小距离的特性。 p e g 算法构造的l d p c 码没有一定的码结构，编码复杂度高，并且其稀疏校 验矩阵不是系统形式的，也不是循环形式的，因此编码器非常复杂，不具有实用 性，但p e g 构造的l d p c 码在优化的度分布下具有优异的性能。p e g 构造算法 中，在连接变量节点，的第k 条边时，影，中度最小的校验节点可能不止一个，改 进的p e g 算法使用变量节点的外信息度来增加变量节点互连，减少小的停止集 2 6 1 。所谓停止集是指一个变量节点集合，这个集合中变量节点的所有邻接校验节 点连接到这个集合至少两次【2 刀。 2 1 2 结构化构造法 随机构造的矩阵没有确定的结构，编码复杂度大与随机构造的矩阵相比， 结构化矩阵具有确定的结构，循环长度较大，具有循环码或准循环码结构，编码 实现简单。结构化矩阵构造主要有以下几种方法：几何构造法将有限几何中的点 线与校验矩阵对应得到；b i b d 组合法将点块入射矩阵与校验矩阵对应得到结 第二章q c l d p c 码的构造 构化的校验矩阵的一大优点就是它的循环或准循环的结构，使得它的硬件实现非 常简单，从而推动了l d p c 码的实用化。关于结构化构造方法这里不再做详细讨 论，下面几节内容会针对一类q c - l d p c 基于有限域的构造方法做深入研究。 2 2q c l d p c 码的基本概念 q c l d p c ( q u a s i c y l i cl d p c ) ，即准循环l d p c 码。顾名思义，是一种准循环 结构的l d p c 码，其校验矩阵由循环矩阵组成，如下式所示： h 叮c = p 1 1p l ，2 p 2 ，1p 2 , 2 p c jp c 2 p 1 ， p 2 j