（通信与信息系统专业论文）准循环ldpc码编译码的fpga实现.pdfVIP

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：奎尘! 童： e l 期：2 1 1 1 ：兰：兰2 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：生! 圭_ 导师签名：孓垄型) 日 期：2 1 ! ：墨：三艺 山东大学硕士学位论文 目录 c o n t e n t s i i i 摘要1 第一章绪论3 1 1 数字通信系统3 1 2 纠错码基础介绍4 1 3l d p c 码的发展与应用6 1 3 1l d p c 码的发展6 1 3 2l d p c 码的应用7 1 4f p g a 的基本知识7 1 4 1 可编程逻辑器件7 1 4 2f p g a 的设计基础。8 1 4 3 工具介绍9 1 5 本文的内容安排9 第二章l d p c 码概述1 1 2 1l d p c 码的定义1 l 2 2l d p c 码的t a n n e r 图表示1 1 2 3 q c l d p c 码12 2 4l d p c 码的分类1 3 2 4 1 规则l d p c 码和非规则l d p c 码1 3 2 4 2 二进制l d p c 码和多进制l d p c 码1 4 第三章l d p c 码的编码算法研究与实现1 6 3 1 由校验矩阵得到生成矩阵1 6 3 1 1 校验矩阵满秩的情况一1 6 3 1 2 校验矩阵不满秩的情况18 3 2 传统编码算法2 0 3 3 基于r u 算法的编码算法2 0 3 4 q c l d p c 码的编码算法研究与实现2 l 3 4 1串行编码算法2 l 3 4 2 并行编码算法2 5 3 4 3 两级编码算法2 9 3 - 4 4 一种改进的两级编码方式3 5 3 4 5 编码器性能分析一3 7 i 山东大学硕士学位论文 第四章q c l d p c 码的译码算法3 9 4 1l l rb p 算法3 9 4 2u m pb p b a s e d 算法( 最小和算法) 4 0 4 2 1 浮点仿真和性能分析4 2 4 2 2 定点仿真和性能分析。4 4 4 3 线性规划( l p ) 译码算法5l 第五章q c l d p c 译码器的f p g a 实现5 2 5 1l d p c 译码器的整体结构5 2 5 1 1 顶层控制模块5 6 5 1 2 输入数据预处理模块5 7 5 1 3 数据重排模块5 7 5 1 4 校验节点处理模块5 8 5 1 5 变量节点处理模块6 l 5 1 6 译码判决模块6 3 5 1 7 迭代结束判断模块6 4 5 2l d p c 译码器性能分析。6 4 结束语6 6 参考文献一6 7 致谢7 2 攻读学位期间的研究成果一7 3 i i 1 4i n t r o d u c t i o no f f p g a 8 1 4 1p r o g r a m m a b l el o g i cd e v i c e 8 1 4 2b a s i so f f p g ad e s i g n 8 1 4 3i n t r o d u c t i o no f s i m u l a t i o na n ds y n t h e s i st 0 0 1 9 1 5c o n t e n t so ft h et h e s i s 9 c h a p t e r 2f u n d a m e n t a l so f l d p cc o d e s 1 1 2 1d e f i n i t i o no fl d p cc o d e s 1 l 2 2t a n n e rg r a p hd e s c r i p t i o n 1 1 2 3q c l d p cc o d e s 1 2 2 4c a t e g o r i e so f l d p cc o d e s 1 3 2 4 1r e g u l a ra n di r r e g u l a rl d p cc o d e s 1 3 2 4 2b i n a r ya n dn o n b i n a r yl d p cc o d e s 1 4 c h a p t e r3r e s e a r c ha n di m p l e m e n t a t i o no fl d p ce n c o d i n ga l g o r i t h m 16 3 1f r o mp a r i t y - c h e c km a t r i c e st og e n e r a t o rm a t r i c e s 1 6 2 1 1c h e c km a t r i xw i t hf u l lr a n k 1 6 2 1 2c h e c km a t r i xw i t hn o nf u l lr a n k 1 8 3 2t r a d i t i o n a le n c o d i n ga l g o r i t h m 2 0 3 3e f f i c i e n te n c o d i n ga l g o r i t h mb a s e do na p p r o x i m a t i o nt r i a n g u l a rm a t r i x 2 0 3 4r e s e a r c ha n di m p l e m e n t a t i o nf o rq c l d p cc o d e s 2 1 3 4 1s e r i a le n c o d e r 2 l 3 4 2p a r a l l e le n c o d e r ：! ! ； 3 4 3t w o s t a g ee n c o d e r ：1 9 i i i 山东大学硕士学位论文 3 4 4an e wt w os t a g ee n c o d e r 3 4 3 4 5t h ea n a l y s i so f l d p ce n c o d e rp e r f o r m a n c e 3 7 c h a p t e r4d e c o d i n ga l g o r i t h m so f q c - l d p c c o d e s 。3 9 4 1l l rb pd e c o d i n ga l g o r i t h m 3 9 4 2m i n s u md e c o d i n ga l g o r i t h m 4 0 4 2 1f l o a t i n g - p o i n ts i m u l a t i o na n dp e r f o r m a n c ea n a l y s i s 4 2 4 2 2f i x e d - p o i n ts i m u l a t i o na n dp e r f o r m a n c ea n a l y s i s 4 4 4 3l i n e a rp r o g r a m m i n gd e c o d i n ga l g o r i t h m 一5 1 c h a p t e r5i m p l e m e n t a t i o no f l d p cd e c o d e ro nf p g a 5 2 5 1s t r u c t u r eo f l d p cd e c o d e r 5 2 5 1 1t o p l e v e lc o n t r o lm o d u l e 5 6 5 1 2i n p u td a t ap r e p r o c e s s i n gm o d u l e 5 7 5 1 3d a t ar e - a l i g n m e n tm o d u l e 5 7 5 1 4c h e c kn o d ep r o c e s s i n gm o d u l e 5 8 5 1 5v a r i a b l en o d ep r o c e s s i n gm o d u l e 6 1 5 1 6d e c o d i n gd e c i s i o nm o d u l e 6 3 5 1 7i t e r a t i o ns t o p p i n gc r i t e r i o nt e s tm o d u l e 6 4 5 2p e r f o r m a n c eo f l d p cd e c o d e r 一6 4 c o n c l u s i o n sa n df u t u r er e s e a r c h 6 6 b i l i o g r a p h y 6 7 a c k n o w l e d g e m e n t 7 ：! i v 山东大学硕士学位论文 摘要 低密度奇偶校验( l d p c ) 码是由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 ( 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 码的编、译码器的硬件设计。主要工 作包括： l 、针对q c l d p c 码的快速编码，实现了校验矩阵满秩时准循环校验矩阵转 换到准循环生成矩阵的算法，并对校验矩阵不满秩时的转换算法进行了研究。 2 、基于准循环生成矩阵，研究和实现了串行编码、并行编码、两级编码三种 编码算法。在两级编码的基础上，增加一级电路的复用，提出了一种新的编码器 结构，提高了编码效率和运行时间。 3 、在对l d p c 码编、译码器的计算机浮点仿真的基础上，对基于最小和算法 的译码初始化和译码过程进行了定点仿真。结果表明，定点仿真的结果比浮点仿 真的结果有0 3 0 5 d b 的性能损失，采用的定点处理算法是合理有效的。 4 、在i s e 8 2 和m o d e l s i m 6 2 软件平台上，运用v e r i l o gh d l 编程语言，基于 译码器的部分并行结构，设计实现了q c l d p c 码的最小和算法译码。 关键词：l d p c 码，准循环生成矩阵，快速编码器，最小和译码，定点仿真， 部分并行译码器，f p g a 实现 山东大学硕士学位论文 a b s t r a c t l o wd e n s i t yp a r i t y - c h e c k ( l d p c ) c o d ew a sp r o p o s e di n19 6 2b yg a l l a g e r , w h i c h i sak i n do fl i n e a rb l o c kc o d e sb a s e do n as p a r s ec h e c km a t r i x i t sd e c o d i n gp e r f o r m a n c e c a na c h i e v es h a n n o nl i m i t m a n yc o m m u n i c a t i o ns t a n d a r d sh a v ea l r e a d ya d o p t e d l d p cc o d e sa st h ee r r o r - c o r r e c t i n gc o d e s s o ，t h eh a r d w a r ei m p l e m e n t a t i o no fl d p c e n c o d e ra n dd e c o d e ra r eo n eo ft h er e s e a r c hi n t e r e s t sa tp r e s e n t t h em a i np r o b l e mo fl d p ce n c o d i n gi st of i n da ne f f i c i e n te n c o d i n ga l g o r i t h m w i t hl i n e a rc o m p l e x i t y , a n dt h em a i np r o b l e mo fl d p cd e c o d i n gi st om a k eat r a d e - o f f b e t w e e nh a r d w a r ec o m p l e x i t y , p e r f o r m a n c ea n d t h r o u g h p u t q c l d p cc o d ei sa ni m p o r t a n ts u b c l a s so fl d p cc o d e s b e c a u s eo ft h ec y c l i c s y m m e t r y , t h ee n c o d i n gc o m p l e x i t yo fq c l d p cc o d e sa r el i n e a r l yp r o p o r t i o n a lw i t h c o d el e n 蛋ha n dt h ed e c o d i n gs t o r a g es p a c ei sr e d u c e dg r e a t l y t h i st h e s i ss t u d i e sb o t h t h et h e o r ya n dh a r d w a r ei m p l e m e n t a t i o no fl d p cc o d e s ，a n di m p l e m e n t st h ee n c o d e r a n dd e c o d e ro fq c l d p cc o d e so nf p g a t h em a i nw o r k sa r ea sf o l l o w s ： 1 t h ea l g o r i t h mf r o mt h ep a r i t y - c h e c km a r xt ot h eg e n e r a t o rm a r xi sr e a l i z e d w h e nt h ec h e c km a r xi sf u l lr a n k ，a n dt h ec a s ew h e nt h ec h e c km a t r i xi sn o tf u l lr a n ki s a l s or e s e a r c h e d 2 t h r e ef a s te n c o d i n ga l g o r i t h m sf o rq c - l d p cc o d e sa r er e s e a r c h e da n dr e a l i z e d ， w h i c ha r es e r i a l e n c o d e r , p a r a l l e le n c o d e ra n dt w o s t a g ee n c o d e r b a s e d o nt h e t w o - s t a g ee n c o d e r , am o r ee f f e c t i v ee n c o d i n gs t r u c t u r eb yr e u s i n gt h ef i r s ts t a g ec i r c u i t s i s p r o p o s e d s i m u l a t i o n r e s u l t ss h o wt h a tt h e e n c o d i n ge f f i c i e n c y a n dw o r k i n g f r e q u e n c y a r ei m p r o v e d 3 f l o a t i n gs i m u l a t i o no ft h el d p ce n c o d i n ga n dd e c o d i n gs y s t e mi sp e r f o r m e d a n df i x e ds i m u l a t i o no ft h em i m s u md e c o d e ri sc o m p l e t e d t h er e s u l t ss h o wt h a tt h e r e a l ea b o u t0 3t o0 5p e r f o r m a n c e sl o s s e sa n dt h ef i x e d - p o i n tp r o c e s s i n gp r o g r a mi s r e a s o n a b l ea n de f f e c t i v e 4 h a r d w a r ed e s i g na n di m p l e m e n t a t i o no f p a r t i a l l y - p a r a l l e ld e c o d e r a r ec o m p l e t e d o nt h ei s e8 2a n dm o d e l s i m6 2s o f t w a r ep l a t f o r mu s i n gv e r i l o gh d l k e yw o r d s ：l d p c ，q u a s i c y c l i cg e n e r a t o rm a t r i x ，f a s te n c o d e r , m i n - s u m d e c o d i n g , f i x e ds i m u l a t i o n ，p a r t i a l l y - p a r a l l e ld e c o d e r , f p g ai m p l e m e n t a t i o n 2 山东大学硕士学位论文 第一章绪论 本章首先介绍了数字通信系统的组成和纠错码的基础，接下来重点介绍了 l d p c 码的发展和应用，最后是f p g a 设计的基本知识和本文的内容安排。 1 1 数字通信系统 通信的目的是把对方不知道的消息及时可靠的传送给对方f 1 1 ，因此要求一个 通信系统传输消息必须可靠有效，在数字通信系统中可靠性与有效性往往是一对 矛盾。若要求有效，则必须使得每个数据码元所占的时间缩短、波形变窄、能量 减少，从而在受到干扰后产生错误的可能性增加，传送消息的可靠性减低；若要 求可靠，则使得传送消息的速率变慢，有效性降低。信源编码的作用是除去信源 的冗余以减轻通信负担，通常也称为数据压缩，通过信源编码可以提高信息传输 的有效性；信道编码就是通常所说的纠错编码，它通过在有效信息中加入一些冗 余位用于检测和纠正传输中的错误，提高信息传输的可靠性。 1 9 4 8 年，s h a n n o n 在其论文通信的数学理论【2 d p 首次提出了在有扰信道中 实现可靠通信的方法，提出了著名的信道编码定理。s h a n n o n 指出在满足以下三个 条件的前提下，在有噪信道中可以实现无差错的传输：( 1 ) 编码采用随机编码方 式；( 2 ) 码长趋于无限长；( 3 ) 译码方式采用最大似然译码。该定理指明了有 效而可靠地传输信息的途径是编码，根据s h a n n o n 的理论，得到数字通信系统模型 【3 1 如图1 1 所示： 1 1 数字通信系统模型 一般的通信系统均可由上图来表示，主要包括九个模块：信源，信源编码， 3 山东大学硕士学位论文 信道编码，调制，信道加噪声，解调，信道译码，信源译码，信宿。 信源：产生消息的来源，消息可以是离散的也可以是连续的，通常信源的消 息是随机产生的，因而可以用随机变量和随机过程来描述。 信源编码：信源编码是将信源发出的信息( 语言、图像、文字等) 转换成二 进制或者是多进制序列。其目的是减少信息的冗余度，提高信息传输的有效性。 信道编码：通过人为的在有效信息中加入一些冗余信息，使得传输的序列具 有检错和纠错的功能，提高信息传输的可靠性。 调制：将纠错码信息序列变换成振幅、频率或相位受到调节控制的波形，使 其适合在信道中作较长距离的传输。 信道加噪声：信道是信号由发送端到接收端的媒介，典型的传输信道有明线、 电缆、高频无线通道、微波通道和光纤通道等。信道中存在两类干扰：一类是由 外界原因产生的随机干扰，称为加性干扰；另一类是信号受某些物理条件的变化 影响，引起信号参量的随机变化，又称乘性干扰。 解调：将从信道中传送过来的信号波形，还原为调制之前的数字序列。由于 信道中干扰的影响，还原的数字序列往往和原来输入调制器的数字序列有差别， 这就是误码现象。 信道译码：利用信道编码提供的冗余度，检查或纠正解调器还原的数字序列 中的错误，并把有用的信息序列送往信源译码器。 信源译码：把经过信道译码器核对后的信息序列转换为适合收信者接收的消 息形式。 信宿：信息要送往的目的地，如计算机、终端、存储器、遥控对象等。 系统框图中，把传输信道称为调制信道( 又称狭义信道) ，而把包括调制器、传 输信道和解调器在内的部分称为编码信道( 又称广义信道) ，它的输入是二( 多) 进制 的数字序列，输出一般也是二( 多) 进制的数字序列 4 】。 1 2 纠错码基础介绍 纠错码的基本思想是：在发送端被传输的信息码元后附加一些监督码元，这 些冗余的码元与信息码元之问存在某种确定的规则关联( 约束) 。在接收端按照 4 既定的规则检验信息码元 信息码元在信道传输中所 此，加入监督码元必然要 输速率为代价来换取传输 编码增益定义为在相同的 论的不断完善和数字电路 泛的应用 2 】。 在差错控制系统中使 分为检错码、纠错码和纠 分为线性码和非线性码； 分为系统码和非系统码； 和纠正突发错误的编码； 分组码和卷积码【l 】。图1 2 介绍了纠错码的各种类型。本论文所要研究的l d p c 码 是纠错编码领域中一类重要的线性分组码。 图1 2 纠错码分类 5 山东大学硕士学位论文 1 3l d p c 码的发展与应用 1 3 1l d p c 码的发展 低密度奇偶校验码( l o w d e n s i t yp a r i t y - c h e c kc o d e s ) 5 是一类用稀疏校验矩阵 h 或二部图( b i p a 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 码。受当时计算机处理水平的限制，在接下来的3 0 年中一直被 人们所忽视。1 9 9 3 年，d m a c k a y 、m n e a l 等人重新对它进行了研究，研究表明， l d p c 码也是一个好码，具有逼j 丘s h a n n o n 限的译码性能 6 】【7 】，同时具有更低的线 性译码复杂度。与t u r b o 码【8 】【9 】相比，基于非规则双向图的l d p c 长码的性能更优， 可以非常接近s h a n n o n 限。除此之外，l d p c 码还具有较小的译码错误概率和较低 的译码复杂度等优点，而且码长较长( 比如大于2 0 0 ) 时，不存在错误平层，其码率 也容易调整，实验结果中的错误也几乎均为可检测错误。所以，l d p c 码无论在理 论上还是在实际应用中都具有极其重要的价值，l d p c 码的重新发现是纠错码研究 领域的重大进展。1 9 9 7 年m i c h a e lgl u b y 等人首先提出了非规则的l d p c 码【l o 】， 并证明了非规则码比规则码具有更好的性能。t h o m a sj r i c h a r d s o n 和 r l u r b a n k e t 11 】等学者总结并发, 展：t r u b y 的分析方法，提出密度演化( d e n s i t y e v o l m i o n ) 方法，分析了消息传递译码下l d p c 码的容量，并设计出接近s h a n n o n 限 的非规贝j j l d p c 码，为l d p c 码的研究和应用作出了极大的贡献。 编码方面，直接编码运算量较大，复杂度与码长的平方成正比。编码的研究 方向是找到一种具有线性复杂度的编码算法。针对此问题，很多学者进行了研究。 t h o m a sj r i c h a r d s o n 和r l u r b a n k e t 论述了l d p c 码的快速编码方法，这种编 码方案仅仅对校验矩阵进行重新排列的预处理，使得编码的时间复杂度在多数情 况下都是可控的，甚至具有线性时间复杂度【1 l 】。l iz o n g w a n g 等学者提出了针对 准循环l d p c 码的编码实现方法【1 2 】，编码复杂度与校验比特的长度成正比。 译码方面，o a l l a g e r 曾提出了两种l d p c 码的迭代译码算法【6 】：硬判决和软判 决算法。后者虽然有较好的性能，但是复杂度太高。后来出现的置信传播( b r i e f p r o p a g a t i o n ，b p ) 算法，可以认为是二者的折中。而在b p 译码算法的基础上，发展 出了更适合硬件实现的b p - b a s e d 算法。在b p 算法和b p - b a s e ：c l 算法中，两类节点的消 息是通过t a n n e r l 蛩 1 3 传递的。t a n n e r - 相图在l d p c 编译码方面都具有广泛的应 6 山东大学硕士学位论文 用。后来又提出了最小和译码算法，这种算法是对b p 算法的进一步简化，虽然在 译码性能上有定的损失，但是却大大降低了译码的运算量，从而使得译码器的 硬件实现更加简单。 1 3 2l d p c 码的应用 l d p c 码作为一类特别的纠错码，由于具有较高的吞吐量和良好的译码性能， 受到了越来越多的关注。相对于t u r b o 码而言，l d p c 码的译码算法简单，支持并 行实现，因此便于利用v l s i 技术实现高速编译码器，l d p c 码的应用不仅仅局限 于数字通信，还可以应用在所有要求高数据率、良好的纠错性能的数字系统中， 比如光纤通信、卫星、存储设备、无线系统、有线系统等等，特别是在宽带无线 通信、多媒体通信和硬盘数据保护等方面有广阔的应用前景。 基于l d p c 码的编译码方案已经被下一代卫星数字视频广播标准d v b $ 2 1 4 】 采纳。在无线城域网的i e e e 8 0 2 1 6 e 1 5 】方案中，l d p c 码与t u r b o 码一起作为编码 调制的备选方案。方案中，采用矩阵分块技术( 码长从5 7 6 至1 j 2 0 3 4 ，码率为1 2 ，。2 3 ，3 4 ) ，将大规模的矩阵乘法运算分解为小规模矩阵乘的并行结构，有效地解 决了l d p c 码编码复杂度高的问题。在我国地面数字电视传输标准建设备选的方案 中 1 6 】，广科院提出了t i m i 方案，该方案最大的技术亮点就是采用了l d p c 码信道 编码技术，最优地解决了保持l d p c 编译码性能最佳的状况下实现复杂度的难题。 据此，i e e 8 0 2 1 1 n 工作小组全体通过了在面向双绞线的1 0 g b i t s 以太网标准 1 0 g b a s e 方案中采用l d p c 码。此外，低密度奇偶校验码在数据压缩、水印等方面 的应用也取得了一些成果。 总之，l d p c 码具有译码性能好、译码器易于实现和系统复杂度低的优点，已 经引起i t 业界的高度重视，成为当今信道编码领域最受瞩目的研究热点之一。目 前，l d p c 码己成为第四代移动通信编码技术中的首选和c c s d s 深空通信的备选纠 错码方案。 1 4f p g a 的基本知识 1 4 1 可编程逻辑器件 可编程逻辑器件【1 7 】是一种可以构造成各种逻辑用途的通用芯片，这种芯片在 7 山东大学硕士学位论文 数字电路设计中一直起着非常重要的作用。 现场可编程门阵歹w j f p g a 可实现用户现场可编程，也可实现较大规模的电路。 它是由许多较小的逻辑单元组成的内部阵列，单元间的信号连接通过其周围的布 线通道互连实现，逻辑单元及布线通道可由用户现场配置。 近几年来，由于微电子技术的迅猛发展，使得f p g a 的各项性能指标大大改进， 规模越来越大，功能越来越全，时钟性能越来越好，价格也越来越低，因而应用 越来越广泛，它不仅用在产品的设计阶段，而且可用在产品的生产阶段。 1 4 2f p g a 的设计基础 f p g a 的设计流程，主要包括以下几个步骤：设计输入( 代码或者原理图) 、 功能仿真、综合优化、布局布线、时序分析、门级仿真和实际验证。 ( 1 ) c o d i n g ( 代码编写) ：使用硬件描述语言( v e r i l o g ，v h d l ) 【1 8 1 1 9 1 1 2 0 或者 原理图对设计进行行为或功能描述 ( 2 ) f u n c t i o ns i m u l a t i o n ( 功能仿真) ：验证设计的逻辑功能是否符合要求。 ( 3 ) s y n t h e s i s ( 综合) ：把代码转化成对应目标器件的内部工艺结构。 ( 4 ) p l a c e r o u t e ( 布局布线) ：把设计映射到目标器件指定位置，进行布线。 ( 5 ) s t a ( 静态时延分析) ：验证设计编译配置后是否能在目标器件中实现。 ( 6 ) g a t es i m u l a t i o n ( 门级仿真) ：又称后仿真，主要为了验证系统的工作速率。 ( 7 ) e m u l a t i o n ( 验证) ：生成二进制码流文件，下载到器件中进行验证。 图1 3 为f p g a 的时序逼近流程，通过时序逼近使得系统性能达到预期的效 果。由于各方面原因，本文的设计只是做了简单的优化，在后续工作中会重点关 注该设计的优化工作。 8 山东大学硕士学位论文 1 4 3 工具介绍 1 、利用合适的代l 和5 技术 l1 1 1 、加警觌选 1 0 、在综合中加关 键路径约束 丁 i9 、重新评估代码 风格 t i8 、加x i l i n x 指定 l路径的约束 图1 3f p g a 设计时序逼近流程 本文使用的器件是x i l i n x 公司的v i r t e x 2 系列的x c 2 v 1 5 0 0f p g a ，设计工具使 用的是x i l i n x 公司的i s e 8 2 1 2 1 2 2 ，i s e 可以完成f p g a 开发的全部流程，包括设计 输入、仿真、综合、布局布线、生成b i t 文件、配置以及在线调试，其集成的时序 收敛流程整合了增强型物理综合优化，提供最佳的时钟布局、更好的封装和时序 收敛映射，从而获得更高的设计性能。仿真工具使用的是m o d e lt e c h 公司的 m o d e l s i m6 2 ，m o d e l s i m 是业界最优秀的h d l 语言仿真软件，它能提供友好的仿 真环境，是业界唯一的单内核支持v h d l 和v e r i l o gh d l 混合仿真的仿真器。它采 用直接优化的编译技术、t c l t k 技术、和单一内核仿真技术，编译仿真速度快，编 译的代码与平台无关，便于保护i p 核，个性化的图形界面和用户接口，是f p g a 设 计的首选仿真软件。 1 5 本文的内容安排 本文的主要内容安排如下： 第一章为绪论部分，首先介绍了数字通信系统的组成，纠错码的基础知识、 9 山东大学硕士学位论文 l d p c 码的发展历史、现状及其应用，然后介绍了f p g a 的一些基础知识，包括可 编程逻辑器件、f p g a 的设计流程和技巧以及所使用的软件工具。 第二章主要介绍l d p c 码的基本理论，包括l d p c 码的定义、l d p c 码的t a n n e r 图描述、l d p c 码的分类以及q c l d p c 码的基本概念。 第三章详细介绍了l d p c 编码算法及其f p g a 实现。首先介绍了l d p c 码由校验 矩阵得到生成矩阵的过程，其中包括两种情况：l 、校验矩阵满秩并且其中存在可 逆的满秩方阵；2 、校验矩阵不满秩或者满秩但是不存在可逆的方阵。然后介绍了 传统编码算法，基于近似下三角阵的编码算法，以及三种针对准循环l d p c 码的编 码方式( 串行编码、并行编码、两级编码) ，并提出了一种改进的编码方式：接下来 对这四种编码算法进行了f p g a 仿真，并对其性能进行分析。 第四章内容是q c l d p c 译码算法研究，主要包括l l rb p 译码算法、最小和算 法以及l p 译码算法。并对l l rb p 算法和最小和算法进行了浮点m a t l a b 仿真。因为 第五章中译码器的f p g a 实现采用的是最小和算法，因此在本章中还对基于最小和 算法的译码进行了定点仿真。 第五章详细介绍y q c l d p c 码译码器的f p g a 实现。首先给出了本文采用的译 码器的整体结构，然后详细介绍了译码器各个模块的实现原理，并给出了每个模 块的仿真波形及其r t l 级接口图，最后对译码器的性能进行了分析。 第六章是结论，对全文进行概括总结，指出文章的不足之处，并且提出了未 来研究的方向。 1 0 山东大学硕士学位论文 第二章l d p c 码概述 本章首先介绍了l d p c 码的基本定义及其t a n n e r 图表示，接下来介绍了准循 环l d p c 码，最后介绍了规则与非规则l d p c 码以及二进制与多进制l d p c 码。 2 1l d p c 码的定义 g f ( 2 ) 域上的l d p c 码是一种线性分组码( 力，后) ，码长为以，信息序列长度为k ， 可以由其校验矩阵h 唯一确定。h 的维数是m x 刀，每一行对应一个校验方程，每 一列对应码字中的一位。每一行中非零元素的个数称为行重，每- - n 中非零元素 的个数称为列重。一个二进制向量c = ( c 。，c ：，c , 0 ，当且仅当h c r = 0 时，才 是一个码字，其码率为r = k n 。 l d p c 码的名