（电路与系统专业论文）一类低密度奇偶校验码的研究及FPGA实现[电路与系统专业优秀论文].pdf

重庆r 大学硕士论文 中文摘要 摘要 l 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 低密度奇偶校验码 是一种具有 极强纠错能力的差错控制编码技术 它是g a l l a g e r 于1 9 6 2 年提出的一种性能接 近香农 s h a n n o n 极限的好码 l d p c 码的优异性能及其在信息可靠传输中的良好 应用的景 例如光通信 卫星通信 深空通信 第4 代移动通信系统 高速与甚 高速率数字用户线 光和磁记录系统等 被认为将是下一代电信和磁存储系统 中广泛应用的纠错编码技术 已引起世界各国学术界和i t 业界的高度重视 成 为当今信道编码领域最瞩目的研究热点 l d p c 码在许多情况下将取代t u r b o 码 的趋势已很明显 研究l d p c 码的学术意义 商业价值和对i t 特别是通信 领域相关技术发展的推动作用是巨大的 l d p c 码可以通过b p b e l i e f p r o p a g a t i o n 置信传播 算法进行有效的译码 通常b p 译码算法中包含大量的乘法运算 可 以运用对数运算将b p 算法的乘法运算转变为l o g b p 算法中的加法运算 b p 算 法和l o g b p 算法实际上都是使用的相同译码规则 本文在深入广泛地阅读国内外大量的有关l d p c 码与b p 算法 又称为和积 算法 资料的基础上 从易于实现的角度出发 着重提出并研究了一类l d p c 系 统码以及该码在l o g b p 算法下的编码译码结构 并在此基础上深入研究了l d p c 码译码器和编码器的f p g a 实现问题 在本论文开始的时候 l d p c 码译码器和 编码器的f p g a 具体实现已经完成 本文第一章绪论里简要介绍了信道编码的发展动态 接着介绍了l d p c 码在 各类信道编码中的地位 以及简单介绍很多学者对其的研究 同时还对f p g a 设 计方法作了简要的介绍 第二章里 主要介绍了l d p c 码的一些基本的知识 由于l d p c 码是一类校验 矩阵非常稀疏的分组码 故也简单介绍了分组码的相关知识 同时还简要地描 述了l d p c 码的l o g b p 译码算法 l o g b p 译码算法决定了l d p c 译码器的结构 第三章主要介绍了该l d p c 码译码器的设计和f p g a 实现 也是本文的重点内 容 在该部分中 根据l d p c 的译码算法 提出了对应的部分并行译码结构 接 下来围绕着该l d p c 码 对结构中的各部分功能模块作详细的介绍 作者在该部 分重点探讨了以下几项内容 部分并行译码结构 软判决译码方法 初始化信息 外部进化信息的量化 译码器各部分功能模块的f p g a 实现 第四章主要介绍了该l d p c 码的仿真和测试 其中也简要介绍了编码器设计 重庆大学硕士论文中文摘要 方案 认为选用串行的编码器能够在速度上与译码器相匹配 关于l d p c 码的介绍很多都只是停留在理论上的 真正对其具体实现上的介 绍却是很少的 随着对l d p c 码的不断深入的讨论 特别是在其具体实现方面 l d p c 码取代t u r b o 码的趋势将日渐明显 关键词 低密度奇偶校验码 置信传播算法 迭代译码 部分并行译码 现场可 编程门阵列 l l 重庆大学硕士论文 英文摘要 a b s t r a c t l d p cc o d e l o w d e n s t i yp a r i t y c h e c kc o d e i sap o w e r f u le r r o rc o r r e c t i n g t e c h n i q u et h a ti sag o o dc o d en e a rs h a n n o nl i m i tp e r f o r m a n c e i n v e n t e db yg a l l a g e r n e a r l y4 0y e a r sa g o t h a n k st o i t se x c e l l e n tp e r f o r m a c ea n di t s b r i g h ta p p l i c a t i o n p r o s p e c t s u c ha s o p t i cc o m m u n i c a t i o n s s a t e l l i t ec o m m u n i c a t i o n s d e e ps p a c e c o m m u n i c a f i o n t h ef o u r t hg e n e r a t i o nm o b i l ec o m m u n i c a t i o ns y s t e m d i g i t a ls u b s c r i b e r l o o pw i t hh i g hs p e e do rh y p e r v e l o e i t y o p t i c a la n dm a g n e t i cr e c o r d i n gs y s t e m l d p c c o d ei s w i d e l y c o n s i d e r e da s n e x t g e n e r a t i o ne r r o r c o r r e c t i n g c o d ef o r t e l e c o m m u n i c a t i o na n dm a g n e t i c s t o r a g e w h i c h i s p u t a h i g hp r e m i u mo nb y a c a d e m i cc i r c l ea n di tc i r c l e a n dl d p cc o d eh a sb e e nt h em o s ts p e c t a c u l a rs p o ti n e r r o r c o r r e c t i n gc o d i n ga r e a i t sc l e a rt h a tl d p c c o d ew i l ld i s p l a c et u r b oc o d ei nt h e n e a rf u t u r e t h ea c a d e m i cs i g n i f i c a n c ea n dc o m m e r c i a lv a l u eo f s t u d yo nl d p c a l s o t h e i m p u l s eo na s s o c i a t e dt e c h n o l o g yi n i ta r e aa r e g r e a t l d p cc o d ec a nb e e f f e c t i v e l yd e c o d e du s i n g b p a l g o r i t h m s i n c et h ed i r e c t i m p l e m e n t a t i o no fb pa l g o r i t h mw i l lr e s u l t i n h i g hh a r d w a r e c o m p l e x i t y d u et oa l a r g e n u m b e ro fm u l t i p l i c a t i o n s w e m a yi n t r o d u c e s o m e l o g a r i t h m i cq u a n t i t i e st oc o n v e r tt h e s em u l t i p l i c a t i o n si n t oa d d i t i o n s w h i c hl e a d st o t h el o g b p a l g o r i t h m i nf a c t b o t hb pa n dl o g b pa l g o r i t h m a c to nt h es a m e d e c o d i n gr u l e t h i s p a p e r f o c u s e do nt h es t u d yo nl d p cc o d ea n di t sc o r r e s p o n d i n gd e c o d i n g a l g o r i t h m a f t e rt h a t f o re a s yi m p l e m e n t a t i o n t h i sp a p e rb r i n gf o r w a r dac l a s so f l d p c s y s t e m a t i cc o d e a n dt h e na d v a n c ei t se n c o d e ra n dd e c o d e ra r c h i t e c t u r eu p o n l o g b pa l g o r i t h m w ef u l f i l lt h ef p g ai m p l e m e n t a t i o no fl d p cc o d ee n c o d e ra n d d e c o d e rb e f o r et h i sp a p e r i n c h a p t e r1 c h a n n e le n c o d i n g sd e v e l o p m e n t t h ep l a c eo fl d p cc o d ei n c h a n n e le n c o d i n g a l s os o m es t u d yo nl d p cc o d ea r ei n t r o d u c e d a n dt h e n s o m e f p g a d e s i g nw a y s a r ed i s c u s s e d i nc h a p t e r2 s o m ef u n d a m e n t a lk n o w l e d g ea b o u tl d p cc o d e si n c l u d i n gt h e k o n w l e d g eo fb l o c kc o d e sa r ei n t r o d u c e d a l s ot h el o g b pa l g o r i t h mo fl d p c d e c o d e rw h i c hd e t e r m i n st h ea r c h i t e c t u r eo f l d p c d e c o d e ri sd i s c u s s e d i n c h a p t e r3 t h ed e s i g na n df p g ai m p l e m e n t a t i o no ft h el d p cc o d ea r e d i s c u s s e di nd e t a i l w h i c hi st h e t o p i c o ft h i s p a p e r a c c o r d i n gt o t h e l o g b p a l g o r i t h m t h ec o r r e s p o n d i n gp a r t l yp a r a l l e ld e c o d i n ga r c h i t e c t u r ei sb r o u g h to u t a n d i i i 重庆大学硕士论文英文摘要 t h e na l lf u n c t i o n a lm o d u l sa r ed i s c u s s e di n d e t a i l i h ea u t h o ri l l u m i n a t e st h e f o l l o w i n gi s s u e se m p h a t i c a l l y t h e p a r t l yp a r a l l e la r c h i t e c t u r eo f l d p cd e c o d e r s o f t d e c i s i o nd e c o d i n gr u l e t h eq u a n t i z a t i o ns c h e m eo f t h ei n t r i n s i ci n f o r m a t i o n o rc h a n n e li n f o r m a t i o r n a n dt h ee x t r i n s i ci n f o r m a t i o n t h ef p g a i m p l e m e n t a t i o n o fa l lt h ef u n c t i o n a lm o d u l so f t h el d p cd e c o d e r i n c h a p t e r4 t h ea u t h o rm a k e sa l l i n t r o d u c t i o no ft h es i m u l a t i o nr e s u l t b y q u a r t u s l i a n dh a r d w a r et e s t b yd o w n l o a d i n g t oc i m u i t b o a r d a n d t h ea u t h o r i n t r o d u c e st h ed e s i g ns c h e m eo f t h e c o r r e s p o n d i n ge n c o d e r b yc o m p a r i n g t h e p a r a l l e l e n c o d i n ga r c h i t e c t u r ea n dt h es e r i a le n c o d i n ga r e h i t e c t u l e t h ea u t h o rt h i n k st h a tt h e s e r i a lo n e c a nm a t c ht h e p a r t l yp a r a l l e ld e c o d i n ga r c h i t e c t u r e i nt h r o u g h p u t c a p a c i t y i nt h e p a s t t h et h e o r ya n dt h ep e r f o r m a n c eo fl d p c c o d e sh a v eb ei n t r o d u c e d m u c h b u t t h e i m p l e m e n t a t i o n o f i t i ss o l i t t l e a s m o l e a n d m o r e d i s c u s s i o n so f l d p c c o d e s e s p e c i a l l yo fi t sh a r d w a r ei m p l e m e n t a t i o n l d p cc o d e sw i l lr e p l a c et u r b o c o d e si nt h en l a rf u t u r e k e y w o r d s l o w d e n s i t yp a r i t y c h e c kc o d e l o g b pa l g o r i t h m i t e r a t i v e d e c o d i n g p a r t l yp a r a l l e l yd e c o d i n g f i e l dp r o g r a m m a b l e g a t e a r r a y s 重庆大学硕士论文1 绪论 1绪论 通信的目标是实现消息从信源到信宿的可靠传输 消息包括语音 图象 视 频 数据等多种类型 在数字通信系统中 所有不同类型的消息都被转换成比特 流的形式 信道可以是无线电链路 也可以是电话线 光纤 电缆等传输介质 在这些例子中 消息是从一个地方传输到另外一个地方 也就是我们通常意义上 的通信 除此之外 有时还需要将消息从一个时间转移到另外一个时间 即所谓 的存储问题 其典型的例子是磁记录系统 信宿通常在给定信道输出的情况下 简单而可靠地再现源端发送的消息 1 1 数字通信系统的数学模型 s h a n n o n 在其1 9 4 8 年的开创性论文 通信的数学理论 中i x 将点对点的 通信问题划分成两个独立的问题来看待 如图1 1 所示 首先 在给定所需的失 真率指标约束下 尽可能有效地表示原始消息 这一过程通常被称为信源编码 包括模拟信号的数字化以及压缩编码等在内都属于信源编码的范畴 其根本的目 标是实现信息的有效描述 提高通信的有效性 接下来是通过对信源编码的输出 添加适当的冗余来对抗信道可能产生的差错 即所谓的信道编码 引蛩唯卜癯卜阍 哥垌 图1 1 通用信息传输系统框图 f i g1 1 b l o c k d i a g r a mo f g e n e r a li n f o r m a t i o nt r a n s m i s s i o ns y s t e m s h a n n o n 的信道编码定理表明 每一个信道都具有确定的信道容量c 对于 任何小于c 的码率r 存在有速率为r 码长为n 的分组码及 n o k o m 卷积码 若采用最大似然译码 则随着码长的增加其译码错误概率p 可任意小 即有 p s a e x p n e r 和 p s a e x p m 1 h o e r a e x p n e a r 1 2 式中 山和a 为大于0 的系数 历倒和疋倒为正实数 称为误差函数 它与 r c 的关系如图1 2 所示 图中c l c 2 为信道容量 且c l c 2 由信息论的基本 知识可知 在高斯白噪声信道时 信道容量 重庆大学硕士论文 1 绪论 魄 射挑 式中 是信道所能提供的带宽 p s e j t 是信号功率 西是信号能量 r 是分 组码信号的持续时间即信号带宽 p j w 是单位频带的信号功率 d 是单位频带 的噪声功率 只舛w n o 是信噪比 e r 圈1 2e f 砷与r 的关系 f i g1 2 r a l a t i o n sb e t w e e ne r r a n dr 由式 1 3 和图1 2 可以看出 信道容量c 码长n 和概率p 之间的转换关 系 为满足一定的误码率p 的要求 可用两类方法来实现 一是增加信道容量c 从而使e 月 增加 由公式 1 3 可知 可以采用加大系统带宽或增加信噪比 的方法来提高c 例如 采用调频 调相等宽带调制方法 增加发射机的功率 应用高增益天线 采用分集接受及低噪声器件等方法 这些措施是从根本上改善 信道 增加信道容量 减少误码率的方法 是通信设计工作者经常采用的传统方 法 另外一种是在r 一定条件下 增加分组码长 也就是增加分组信号持续时 间t 可使p 随n 的增加而呈指数下降 但由于码长的增加 当r 保持一定时 可能发送的码字数目2 指数增加 从而增加了译码设备的复杂性 这种方法就 是信道编码定理所指出减少误码率的另一方向 它为通信工作者提供了一条新的 途径 2 1 2 信道编码的基本思想和分类 1 2 1 信道编码的基本思想 用图1 1 所示的模型来讨论二进制数字序列通过该系统时所发生的情况 设从信源送出字母a 它的二进制序列为1 1 0 0 0 以基带信号传送 经发射机调 制后 送往信道的已调信号如图1 3 所示 2 重庆火学硕士论文 1 绪论 s 1 m t 八 一 图1 31 1 0 0 0 发送的已调信号 f i g1 3 m o d u l a t e ds i g n a l 1 1 0 0 0 t r a n s m i t t e d 0 ls f f 扒一 一 7 图1 4 接收端收到的失真信号波形 f i g 1 4d i s t o r t i o ns i g n a lr e c e i v e d 由于信道的干扰 信道输出端的信号产生了失真 如图1 4 所示 这些失真 信号送入接收机进行判决时 第一 二 四 五码元的波形失真不大 容易正确 地判为l 1 和0 0 但对第三个码元来说 由于失真严重而难于判决 这时有 以下三种判决方法 一是勉强作出是0 还是1 的判决 即所谓硬判决 另一种是 对该码元暂且不作判决 而输出 个未知或待定的信号 x 称其为删除符号 第三种方法是输出一种有关该码元的信息 例如关于0 和1 的后验概率或似然函 数 这种作法称为软判决 当然软判决的性能较好 但实现起来较复杂 这里以重复编码来简单地阐述差错编码在相同的信噪比情况下为什么会获 得更好的系统性能 假设我们发送的信息0 1 等概率出现 采用2 p s k 方式 我们知道最佳接收的系统比特误码率为 只 纠罔 现假设只 1 0 即平均接收1 0 0 0 个中错一个 如果我们将信息0 编码 成o o 信息l 编码成1 1 仍然采用上述系统 则在接收端可以作以下判断 如 果发送的是o o 而收到的是0 1 或1 0 此时我们知道发生了差错 要求发送端重 新传输 直到传送正确为止 只有当收到1 l 时 我们才错误地认为当前发送的 是1 因此在这种情况下发生译码错误的概率是0 5p 同理 如果发送的是1 1 只有收到0 0 时才可能发生错误译码 因此在这种情况下发生译码错误的概率也 是o 5 乎 所以采用0 0 1 l 编码的系统比特误码率为雩 即l o 一 系统的性能 将明显提高 再如 在上例中 将0 1 采用0 0 0 0 0 1 1 1 1 1 编码 在接收端我们 用如下的译码方法 每收到5 个比特译码一次 采用大数判决 即5 个比特中0 的个数大于l 的个数则译码成0 反之译码成1 不采用a r q 方式 那么 我 们看到这种编码方式就变成了纠错编码 由于传输错误当接收端收到1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 中的任何 一种时 都可以自动纠正成0 0 0 0 0 重庆人学硕十论文 1 绪论 1 2 2 关于纠错码的一些分类 传输信道中常见的错误有以下三种 随机错误 错误的出现是随机的 一般而言错误出现的位置是随机分布的 即各个码元是否发生错误是互相独立的 通常不是成遍地出现错误 这种情况一 般是由信道的加性随机噪声引起的 因此 将具有此特性的信道称为随机信道 突发错误 错误的出现是一连串的 通常在一个突发错误持续时间内 开头 和末尾的码元总是错的 中间的某些码元可能错也可能对 但错误的码元相对较 多 这种情况如移动通信中信号在某一段时间内发生衰落 造成一串差错 汽车 发动时电火花干扰造成的错误 光盘上的一条划痕等等 这样的信道我们称之为 突发信道 混合错误 既有突发错误又有随机差错的情况 这种信道称之为混合信道 数字通信系统中 利用纠错码或检错码进行差错控制的方式有以下几类 检错重发 a r q 在接收端根据编码规则进行检查 如果发现规则被破坏 则通过反向信道要求发送端重新发送 直到接收端检查无误为止 a r q 系统具 有各种不同的重发机制 如可以停发等候重发 x 2 5 协议的滑动窗口选择重发 等 虽然a r q 系统需要反馈信道 效率较低 但是能达到很好的性能 前向纠错 f e c 发送端发送能纠正错误的编码 在接收端根据接收到的 码和编码规则 能自动纠正传输中的错误 其特点是不需要反馈信道 实时性好 但是随着纠错能力的提高 编译码设备相对复杂 混合方式 h e c 结合前向纠错和a r q 的系统 在纠错能力范围内 自动 纠正错误 超出纠错范围则要求发送端重新发送 它是一种折中的方案 根据差错控制编码的功能不同分为 检错码 纠错码 纠删码 兼检错 纠 错码 根据信息位和校验位的关系分为 线性码和非线性码 根据信息码元和 监督码元的约束关系分为 分组码和卷积码 1 3 信道编码技术的发展及其动态 自1 9 4 8 年s h a n n o n 提出有噪声信道的编码理论以来 人们就一直致力于高 效可靠的编译码理论及其实现方法的研究 也提出了许多高效实用的编译码方 案 其中c b e r r o u 等学者于1 9 9 3 年在总结卷积码的b c j r 算法 乘积码和级联 码等理论的基础上创造性地提出的t u r b o 码编译码新概念 称得上是编码理论的 一次重大突破口j t u r b o 码由于其接近s h a n n o n 限的纠错性能 从其一出现便成 为信道编码领域中的研究热点 并普遍认为t u r b o 码在深空通信 卫星通信以及 移动通信等数字通信系统中均具有诱人的前景 4 5 1 t u r b o 码之所以能够获得超强 4 重庆大学硕士论文 1 绪论 的纠错能力 一个极其重要的原因就在于其采用软输入软输出的译码算法 并通 过交织器以迭代的方式实现了各个子译码器间译码信息的共享 随着t u r b o 码的成功 人们也开始对t u r b o 码的诸多变种进行研究 如串行 级联卷积码 s c c c 混合级联卷积码等 已经证明 在相同译码复杂度的情况 下 s c c c 可以获得更好的译码性能 6 与此同时 也开始不断地将迭代的思想 应用于诸如解调 译码 信道译码 多用户检测 均衡 同步 信道估计等诸多方 面 并取得了大量的研究成果 另外 一些类似t u r b o 码的编译码方法也得到了 大量的研究 如g a l l a g e r 的低密度奇偶校验码 l d p c l o w d e n s i t yp a d t y c h e c k c o d e s 8 9 1 0 1 1 1 l u b y 等人提出的不规则低密度奇偶校验码 i r r e g u l a rl d p c c o d e s 1 2 d i v s a l a r 等的重复累加码 r e p e a t a c c u m u l a t ec o d e s 1 6 f r e y 等的 不规则t u r b o 码 i r r e g u l a rt u r b oc o d e s t c o s t e l l o 等的非对称t u r b o 码 a s y m m e t r i c t u r b oc o d e s h j 以及p i n g 等的级联树码 c o n c a t e n a t e dt r e ec o d e s 0 5 等等 各种不同的编译码方法都已有了较为深入的研究与仿真 人们发现 在编译码方案相匹配的情况下 不少方法都有超过传统t u r b o 码的性能 低密度奇偶校验 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 码 于1 9 6 2 年由m i t 的r o b e r tg a l l a g e r 在其博士论文中首先提出 9 1 在其论文中 g a l l a g e r 对l d p c 码进行了详尽的分析 并给出了高效的迭代译码算法一一和积算法 s u m p r o d u c ta l g o r i t h m 然而由于该算法极大的存储需求以及高的计算复杂 度 对于接近香农极限的码 从其提出一直到2 0 世纪9 0 年代中期都极少受到 编码界的重视 l 6 7 1 作为线性分组码的 大家族 l d p c 码因其校验矩阵中包含绝大多数的0 而 只有极少数的1 而得名 这 校验矩阵的稀疏特性使得其可以通过被称为和积算 法的消息传递 m e s s a g e p a s s i n g 过程来实现有效的译码 译码复杂度则大大低 于t u r b o 码的b c j r 算法和m a p 算法 目前对l d p c 码编译码方法及译码性能 的分析研究已有不少的成果出现 1 7 1 9 1 9 l d p c 码及其译码算法是于上世纪9 0 年代中期 c b e r r o u 等人提出t u 曲 码之后不久由m a c k a y 和n e a l 等人重新发现 并且已经证明了迭代译码算法对 于实际系统接近信道容量的重要性 1 7 1 9 2 0 现在人们已经知道l d p c 码至少具有 和t u r b o 码相同的纠错性能 尤其是不规则l d p c 码 与t u r b o 码相比 l d p c 码译码更为简单 便于并行的电路实现 且没有纠错 地板 f l o o r 效应 l d p c 码由于其优异的纠错能力 并且被广泛地认为将是下一代电信领域和磁存储领域 的纠错编码方案 最近在编码界引起人们大量的关注 l d p c 的重大发现是继 t u r b o 码后在纠错编码领域又一重大进展 现在l d p c 码已经被应用于诸如a d s l 等标准之中 17 1 8 1 9 2 0 2 1 1 重庆大学硕士论文1 绪论 1 4 l d p c 码的简述 l d p c 码的特点是 l d p c 码如能适当地设计 性能将会优于t u r b o 码 具 有较大的灵活性且没有纠错地板效应 e r r o rf l o o r s 描述简单 对严格的理论分 析具有可验证性 由于l d p c 码内在地采用了交织技术 因此 在l d p c 编码 器和信道之间不再需要交织器 译码复杂度低于t u r b 0 码 且可实现完全的并行 操作 硬件复杂度低 因而适合硬件实现 吞吐量大 极具高速译码潜力 研究结果显示 对于二元输入的b i a w g n 信道 码率为1 2 的i r r e g u l a r 非 规则 l d p c 码可具有距离容量不到o 0 6 d b 的门限 计算机仿真结果表明 最 好的非规则l d p c 码 长度为1 0 6 可获得在b e r 1 0 6 时仅偏离容量0 1 3 d b 的 性能 优于奕今所知道的最佳t u r b o 码t z 2 1 当码长为1 07 r 1 2 时 其性能距 s h a n n o n 限只差o 0 4 d b l 2 3 l d p c 码的优异性能及其在信息可靠传输中的良好应用前景 例如光通信 卫星通信 深空通信 第4 代移动通信系统 高速与甚高速率数字用户线 光和 磁记录系统等 己引起世界各国学术界和i t 业界的高度重视 成为当今信道编 码领域最瞩目的研究热点 l d p c 码在许多情况下将取代1 u b 0 码的趋势已很明 显 研究l d p c 码的学术意义 商业价值和对i t 特别是通信 领域相关技术 发展的推动作用是巨大的 近几年国际上对l d p c 码的理论研究已取得重要进 展 在应用基础乃至工程应用和v l s i 超大规模集成电路 实现方面的研究亦 正在全方位开展 l d p c 码结构可采用几何方法 图论方法 实验设计 置换 p e r m u t a t i o n 方法来设计 好的l d p c 码关键在于要有好的码性能和需要较少的编码时间 至 今找到的好码都是借助于大量的计算和筛选生成的 因为尚未提出构建l d p c 码 的系统 或代数 方法 在设计实验和统计分析相结合的实验设计方法中 b i b d 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 方法较为典型 2 5 1 m g l u b y 等 2 6 指出 基于非规则图定义的码性能优于相应的基于规则图 定义的码 m g d a v e y 2 7 1 提出 在二元有限域中定义码和采用具有非均匀行 列重量的非规则奇偶校验矩阵均可改善码的性能 在寻找好的码结构方面 d j c m a c k a y 等 2 卅提出对非规则码采用先选择轮廓再选择结构的两步选择方法 验 证了s u p e r p o i s s o n 结构具有较好性能 并指出 能快速编码的l d p c 矩阵通常具 有下三角形 1 0 w e r t r i a n g u l a r 结构 t j r i c h a r d s o n 等 2 2 通过优化非规则图的度数 d e g r e e 结构来寻找逼近容 量的非规则l d p c 码 t j r i c h a r d s o n 和r l u r b a n k e 2 9 1 探讨了要获得高效编码 器如何确定p a r i t y c h e c k 矩阵稀疏度的问题 以及如何构造码 使编码时间与码 块长度实际上符合线性关系 线性时间编码 而非通常认为的平方关系 m 6 重庆人学硕士论文 1 绪论 g l u b y 等 3 0 也提出了一类基于级联二分图 b i p a r t i t eg r a p h 的l d p c 码 用于 可抹 e r a s u r e 信道 成为e r a s u r ec o r r e c t i n g 码 它不仅是线性时间编码 而且 也可实现线性时间译码 d a s p i e l m a n 3 1 1 开发了一种试探法来寻找非规则l d p c 码参数的好的分 布 据此构建了在很低s n r 下b e r 低于t u r b o 码的码率为1 2 的l d p c 码 j c a m p e l l o 等 3 2 1 提出采用扩展的b i t f i l l i n g 算法来设计具有高码率 高g i r t h 和b e r 性能良好的l d p c 码 ym a o 和a h b a n i h a s h e m i l 3 3 1 则基于性能准则 提出根 据g i r t h 图中最小环长 的分布来设计好的l d p c 码的方法 s j j o h n s o n 和s r w e l l e r l 3 4 提出一种基于k i r k m a n t r i p l e 系统的组合设计方法 适合于构建短码 长 高码和在其t a n n e r 图中不出现环长为4 g i r t h 至少为6 的规则l d p c 码 y k o u s l i n 和m f o s s o r i e r l 3 5 探讨了基于有限几何学的l d p c 码结构 j r o s e n l a l 和ev o n t o b e l t 3 s l 研究了基于r a m a n u j a n 图和按照m a r g u l i s 的概念构建 的规则l d p c 码 其性能优于随机构建的 3 6 规则码 n v a n i c a 等 3 7 则对 2 2 中的优化方法作了修正 用于存在符号间干扰的部分响应信道中l d p c 码的优 化 1 5 f p g a 及其设计方法口8 1 删 1 5 1 f p g a c p l d 简介 当今社会是数字化的社会 是数字集成电路广泛应用的社会 数字集成电路 本身在不断地进行更新换代 它由早期的电子管 晶体管 小中规模集成电路 发展到超大规模集成电路以及许多具有特定功能的专用集成电路 但是 随着微 电予技术的发展 设计与制造集成电路的任务已不完全由半导体厂商来独立承 担 系统设计师们更愿意自己设计专用集成电路 a s i c 芯片 而且希望a s i c 的设计周期尽可能短 最好是在实验室里就能设计出合适的a s i c 芯片 并且立 即投入实际应用之中 而且出现了现场可编程逻辑器件 f p l d 其中应用最广 泛的当属现场可编程门阵列 f p g a 和复杂可编程逻辑器件 c p l d 早期的可编程逻辑器件只有可编程只读存储器 p r o m 紫外线可檫除只 读存储器 e p r o m 和电可檫除只读存储器 e e p r o m 三种 由于结构的限 制 它们只能完成简单的数字逻辑功能 其后 出现了一类结构上稍复杂的可编 程芯片 即可编程逻辑器件 p l d 它能够完成各种数字逻辑功能 这一阶段 的产品主要有p a l 可编程阵列逻辑 和g a l 通用阵列逻辑 这些早期的 p l d 器件的一个共同特点是可以实现速度特性较好的逻辑功能 但其过于简单 的结构也使他们只能实现规模较小的电路 重庆人学硕士论文l 绪论 为了弥补这一缺陷 2 0 世纪8 0 年代中期 a l t e r a 和x i l i n x 分别推出了类似 于p a l 结构的扩展型c p l d c o m p l e xp r o g r a m m a b l el o g i cd e v i c e 和与标准门 阵列类似的f p g a f i e l dp r o g r a m m a b l eg a t ea r r a y 它们都具有体系结构和逻 辑单元灵活 集成度高以及适用范围宽等特点 这两种器件兼容了p l d 和通用 门阵列的优点 可实现较大规模的电路 编程也很灵活 与门阵列等其它的a s i c 相比 它们又具有设计开发周期短 设计制造成本低 开发工具先进 标准产品 无需测试 质量稳定以及可实时在线检验等优点 因此被广泛应用于产品的原型 设计和产品生产 一般在1 0 0 0 0 件以下 之中 几乎所有应用门阵列 p l d 和中小规模通用数字集成电路的场合均可应用f p g a 和c p l d 器件 对用户 c p l d 与f p g a 的内部结构稍有不同 但用法一样 所以多数情况 下 不加以区分 c p l d 与f p g a 概况起来是由三大部分组成的 1 一个二 维的逻辑块阵列 构成了p l d 器件的逻辑组成核心 2 输入 输出块 连接 逻辑块的互连资源 3 连线资源 由各种长度连线线段组成 其中也有一些 可编程的连接开关 它们用于逻辑块之间 逻辑块与输入 输出块之间的连接 f p g a c p l d 芯片都是特殊的a s i c 芯片 它们除了具有a s i c 的特点之外 还具有以下几个优点 随着v l s i 超大规模集成电路 工艺的不断提高 单一芯片内部可以容纳 上百万个晶体管 f p g a c p l d 芯片的规模也越来越大 其单片逻辑门数已达到 上百万门 它所能实现的功能也越来越强 同时也可以实现系统集成 f p g a c p l d 芯片在出厂之前都做过百分之百的测试 不需要设计人员承担 投片风险和费用 设计人员只需在自己的实验室里就可以通过相关的软硬件环境 来完成芯片的最终功能设计 所以 f p g a c p l d 的资金投入小 节省了许多潜 在的花费 用户可以反复地编程 檫除 使用或者在外围电路不动的情况下用不同软件 就可实现不同的功能 所以 用f p g a c p l d 试制样片 能以最快的速度占领市 场e f p g a c p l d 软件包中有各种输入工具和仿真工具 及版图设计工具和编程 器等全线产品 电路设计人员在很短的时间内就可以完成电路的输入 编译 优 化 仿真 直至最后芯片的制作 当电路有少量改动时 更能显示出f p g a c p l d 的优势 电路设计人员使用f p g a c p l d 进行电路设计时 不需要具备专门的i c 集成电路 深层次的知识 f p g a c p l d 软件易学易用 可以使设计人员更能 集中精力进行电路设计 快速将产品推向市场 1 5 2 f p g a 设计方法 可编程逻辑器件的设计是指利用开发软件和编程工具对器件进行开发的过 重庆大学硕士论文l 绪论 程 高密度可编程逻辑器件的设计流程图如下所示 它包括五个过程 图l 5可编程逻辑器件设计流程图 f i g1 5d e s i g n f l o wd i a g r a m o f p r o g r a m m a b l el o g i cd e v i c e s 1 设计准备 在对可编程逻辑器件的芯片进行设计之前 首先要进行方案论证 系统设 计和器件选择等设计准备工作 设计者首先要根据任务要求 如系统所完成的功 能和复杂程度 对工作速度和器件本身的资源和成本连线的可布性等方面进行权 衡 选择合适的方案和合适的器件类型 2 设计输入 设计者将所设计的系统或电路以开发软件要求的某种形式表示出来并送入 计算机的过程称为设计输入 常用的有三种方式 即原理图 硬件描述语言 h d l 波形输入 本论文的l d p c 译码器的设计是采用v h d l 文本的方式和 系统的框图形式来作为输入的 3 设计处理 这是器件设计中的核心环节 在设计处理过程中 编译软件将对设计输入 的文件进行逻辑化简 综合优化 并且适当地用一片或多片器件自动地进行适配 最后产生编程用的编程文件 设计处理应当包括以下五个过程 语法检查和设计 规则检查 逻辑优化和综合 适配和分割 布局布线 生成编程数据文件 4 设计校验 设计校验包括功能仿真和时序仿真 这两项工作是在设计处理过程中同时 进行的 功能仿真是在设计输入完成之后 选择具体的器件进行编译之前进行的 逻辑功能验证 因此又称为前仿真 此时仿真无时延信息 对于系统初步的功能 检测非常方便 仿真前首先要利用波形编辑器或硬件描述语言建立测试向量 一 般的e d a 工具都可以方便地产生测试向量 仿真结果以报告的形式或波形的形 9 重庆大学硕士论文 1 绪论 式输出 从中可以看出各个节点的错误 如果有错误 则返回设计输入中修改逻 辑设计 系统前仿真的结果直接决定着后仿真的正确性 所以在前仿真时要格外 小心 时序仿真是在选择了具体器件并完成布局布线之后进行的时序关系仿真 因此也称为后仿真 由于不同的器件内部的时延不一样 不同的布局 布线方案 也给延时造成不同的影响 因此在设计处理以后 对系统和各模块进行时序仿真 分析其时序关系 估计设计的性能以及检查和消除竞争冒险是非常有必要的 实 际上这也是与实际器件工作情况基本相同的仿真 5 器件编程 编程是将编程数据放到可编程器件中去 器件编程要满足一定的条件 如 编程电压 编程时序和算法等 器件编程完毕之后 可以用编译时产生的文件进 行检验 加密等工作 对于具有边界扫描测试能力和在系统编程能力的器件来说 测试起