（电路与系统专业论文）无线通信中reedsolomon编译码器的vlsi实现研究.pdf

摘要 摘要 r a 7 2 2 , s 9 fr e e d s o l o m o n ( r s ) 码由于其优秀的处理随机错误和突发错误的能力，在各种通信 系统，磁记录与存储等方面得到r 广泛的应用j 本论文设i t r 一种基于! 坚巳! 趱的r s 编 强亟熊理播黯r s d s p 。( 该处理器可以完成在3 8 4 k b p s 条件下r s ( 2 4 5 ，2 0 0 ) n1 4 4 k b p s 条 件下r s ( 2 2 5 ，1 8 0 ) 的变码率编译码功能该处理器可以和交织器、卷积编码v i t e r b i 译码器 组成级联r s v i t e r b i 信道编码系统广一一 论文在分析、比较各种r s 编译码算法的基础上，提出r 能够以高效率实现算法的专用 d s p 结构，并且制定r 有效的专用d s p 设计流程。设计采用c 语言对编译码算法进行r 模 拟，并针对d s p 实现进行了优化r s d s p 的电路设计使用r 硬件描述语言v h d l 进行 结构化和自顶向下的描述，以利于软硬件的协同没计和仿真同时开发r 基于指令的软件 ， 模拟器，用于汇编程序的开发( r s d s p 在f p g a 上的硬件实现不但可1 ：2 实时验证电路 的功能，而且为a s i c 设计提供f 快速的原型，设计代码可以无需修改地迁移到目标 二艺 库f p g a 硬件验证平台也提供了未来的芯片测试和系统测试功能d s p 的设计对不同模 块采用r 不同的测试策略，核心逻辑模块加入了全扫描和a t p g 测试，提高r 测试覆盖率 版图设计采用r 基于时序的设计流程，可以取得更优化的布局、布线和更准确的时延参数。 通过软件的模拟、硬件仿真和芯片测试，沦文所设计的r sd s p 能够满足设计的要 求，可以用于无线个人通讯系统，并取得r 较小的芯片面积和功耗 一) 无线通信中的r e e d s o l o m o n 编译码器的v l s i 实现研究 ， 摘要 a b s t r a c t r e e d s o l o m o n ( r s ) c o d eh a sb e e nw i d e l yu s e di nc o m m u n i c a t i o ns y s t e m ，m a g n e t i cs t o r a g e ， a n ds oo i l t h ep a p e rp r e s e n t sad s p b a s e dr e e d s o l o m o nc o d e cp r o c e s sw h i c hi sn a m e dr s d s pt h ep r o p o s e dp r o c e s s o rc a l la c c o m p l i s hr a t e a d a p t i v ee n c o d i n ga n dd e c o d i n go fr s ( 2 4 5 ， 2 0 0 ) w h e nd a t ar a t ei s3 8 4 k b p sa n dr s ( 2 2 5 ，18 0 ) w h e nd a t ar a t ei s1 4 4 k b p s t h ep r o c e s s o r ， t o g e t h e r w i t hi n t e r l e a v e ra n dc o n v o l u t i o u a le n c o d e r v i t e r b i d e c o d e r ，c a nm a k eu p o fa c o n c a t e n a t e dr s v i t e r b ic h a n n e lc o d i n gs y s t e ms u i t a b l ef o rw i r e l e s sc o m m u n i c a t i o n o nt h eb a s i so fc o m p a r i n gv a r i o u sr sc o d e ca l g o r i t h m s ，a n a p p l i c a t i o n - s p e c i f i c d s p s t r u c t u r ei sp r o p o s e dt oi m p l e m e n tr sc o d e cw i t ht h eh i g h e s te f f i c i e n c ya d e s i g nf l o wt od e s i g n r s d s pi sa l s op r o p o s e d t h ea l g o r i t h mi ss i m u l a t e du s i n gcl a n g u a g ea n do p t i m i z e df o rv l s i i m p l e m e n t a t i o n v h d li su s e dt od e s c r i p ts t r u c t u r e do fr s - d s pi nas t r u c t u r ea n d t o p d o w nw a y f o rt h es o f t w a r ea n dh a r d w a r ec o - d e s i g nas o f t w a r es i m u l a t o ri s d e v e l o p e dt op r o g r a mt h e a s s e m b l yc o d ec o n v i n e n t t y t h ef p g a h a r d w a r ev e r i f i c a t i o np l a t f o r mn o to n l yc a nr u nr e a l t i m e s i m u l a t o n ，b u ta l s oi saq u i c kp r o t o t y p ef o ra s i cd e s i g n ，t h ed e s i g nc a nb et r a n s f e r e dt oa s i c d e s i g nw i t h o u tm o d i f i c a t i o n t h ef p g ap l a t f o r mp r o v i d ec o n v i n e n c e f o rt h ef u t u r e c h i pa n d s y s t e mt e s t i n g w eh a v ea d o p t e dd i f f e r e n tt e s ts c h e m e sf o rd i f f e r e n tp a r t so fd s pa n dt h ec o r eo f d s pu s ef u l l - s c a na n da t p gt e s tw i t hh i g hf a u l tc o v e r a g et h el a y o u td e s i g nu s et i m i n g d r i v e n f l o ww i c hc a no b t a i no p t i m i z e d p l a c ea n d r o u t er e s u l ta n dm o r ea c c u r a t ed e l a yv a l u e t h er e s u l t so fs o f t w a r es i m u l a t i o n ，h a r d w a r ev e r f i c a t i o ns h o wt h a tt h ec h i pc a nm e e ta l lt h e f u n c t i o n s i tc a nb eu s e di nc h a n n e lc o d i n go fc o m n m n i c a t o ns y s t e ma n do b t a i ns m a l lc h i pa r e a a n di o wp o w e r 无线通信中的r e e d s o l o m o n 编译码器的v l s i 实现研究 第一章引言 第一章引言 ce s h a n n o n 的信道编码定理告诉我们，每一类信道都存在着一定的信道容量c ，它是 信道的最大极限传输能力，只要实际传输速率rcc 时，就可以实现在信道中无差错的传 输 s h a 4 8 但是，在实际信道上进行数字信号的传输时，由于信道传输特性不理想以及加 性噪声的影响，接收到的数字信号不可避免的会发生错误为r 在已知信噪比的情况f ， 达到一定的误比特率指标，除r 合理的设计基带信号，选择涧制、解调方式，采用频域均 衡和或时域均衡，使误比特率尽可能降低之外，采用信道编码，即差错控制编码，是降低 误比特率的有效方法随着差错控制编码理论的完善和超大规模集成电路( v l s i ) 的发 展，信道编码已经在各种通信系统，计算机，磁记录与存储等方面得到了，广泛的应用 1 1 纠错编码的发展 s h a n n o n 和af e i n s t e i n 给出在分组码情况下信道编码定理的证明时引用厂三个基本条 件： 1 ) 采用随机编、译码方式； 2 ) 编译长度l 斗o o ，即分组的码组长度无限： 3 ) 译码采用最佳的最大似然译码法 长期以来，构造好码基本上是按照s h a n n o n 所引用的三个基本条件的后两个，即条件 2 ) 和条件3 ) 为两条主线发展下来的由于译码的复杂度，人们将构造信道编码的重点放在 短码上，而码的构造空间也局限于低维数的短码。这些好码相对于未编码能提供一定的编 码增益，但是与信道编码定理要求的相差甚远 为f 获得可译的高维数的长码，人们以现有短码构造为基础提出r 串接式的级联码 1 9 6 6 年，f o m e y f o r 6 6 首先提出了，利用两个确定的短码来构造长码的串接式级联码串行 级联码是采用两个确定短码作为内、外码串接而成，其性能也是两个短码性能函数的串接， 即通过对外码的译码纠正内码尚未能纠正的差错 由于软判决比硬判决译码从理论上要好约2 d b ，因此，能进行v i t e r b i 软译码的卷积码 成为首选内码而外码则选用能同时纠正随机错误和突发错误的r e e d _ s o l o m o n ( r s ) 码， 同时，r s 编译码器也相对比较容易实现但由于信源干扰影响产生的随机错误码超过卷积 码的自由距离或者在有突发错误的信道中，v i l e r b i 译码会产生差错扩散，内码卷积码必须 采用交织技术使错误离散化卷积内码、r s 外码组成的级联码信道编码系统如图1 1 所 示这类串行级联码很快被应用于深空通讯中，并取得f 巨大的成功。它在采用最大似然 的软判决译码以后，其误码率几乎达到逼近理想s h a n n o n 限的优异性能 无线通信中的r e e d s o l o m o n 编译码器的v l s i 实现研究 第一章引言 c o n c a t e n a l e d _ c _ h a n n _ e _ ! 旦删蚋9 图表1 1 级联码信道编解码系统框图 1 9 9 3 年b e r r o u b e r 9 3 等人提出的t u r b o 码是一种并行级联卷积码，最初的报告成果表 明其译码性能可以接近s h a n n o n 理论值，如利用二个码率为1 2 的二元卷积码并联而成的 t u r b o 码，在信噪比为0 7 d b 时误码率可达1 0 5 因此t u r b o 码迅速受到国际上的广泛重视， 并试图应用于各种通讯系统t u r b o 由于实现中的困难，正处于研究之中。 1 2 纠错码的性能和应用 提高编码增益在通讯系统中，特别是对功率要求严格的情形有着重要的意义如深空 及卫星通信中能源极端受限，移动通信中的电池寿命是一个重要指标，军事通信中要求发 射信号功率尽可能低以降低被发现的概率比如美国的d s n ( d e e ps p a c en e t w o r k ) 使用 的3 4 米和6 4 米天线阵列耗资近1 亿美元，而l d b 或者2 6 的编码增益将节省近2 ，6 0 0 万 美元的开支 b d m 8 1 1 2 1 深空通信中的纠错码 在深空通信中，数据速率一般为几十至几百b p s ，而且对数据的实时性要求不高。当 外码用r s 码，内码用卷积编f i 马v i t e r b i 译码的级联码通信系统，在误码率为1 0 一5 时，级联 码的性能比仅仅用卷积编码v i t e r b 译码时的性能，要好25 分贝，同时级联码性能曲线很陡 峭，说明只要整个系统的功率增加很少，如0 5 分贝则误码率就能减低二至三个数量级 无线通信中的r e e d - s o l o m o n 编译码器的v l s i 实现研究 2 雾 鞫 蔓 r，；1l丑 一一l i 哥 蛋匡j睦 习 习一 阿 国 一 m 一 代 一 习 习 第一章引言 由卷积码作内码和r s 码作外码的级联码系统是n a s a 和欧洲空间局e s a 空问任务的 标准8 0 年代，美国将纠错编码用于一系列太空计划巾v o y a g e 是美国1 9 7 7 年发射的行 星际探测器，1 9 7 9 年到达木星附近， 1 9 8 1 年到达土星附近，1 9 8 6 年1 月到达天王星 v o y a g e 在1 9 8 0 年采用( 2 ，1 ，7 ) 卷积码和v i t e r b i 译码，在瓦n o = 4 7 8 d b 时，误码率 只1 0 1 9 8 6 年改为级联码，( 2 ，1 ，7 ) 卷积码为内码，( 2 5 5 ，2 3 3 ) r s 码为外码， 在e 6 n o = 25 3 d b 下，圪1 0 一，并以这一级联码作为基准系统其后的1 9 8 9 年美国 发射的用于木星轨道飞行探测的g a l i e o 空间飞行器选用r 由( 4 ，1 ，1 5 ) 卷积码和( 2 5 5 ， ! 三 墨 露 蓉 盘 2 矗 卜 蔫 - l 。0 一o 5o 口o 51 01 5 2 o 2 。s3 。03 ，5 o4 5 5 吣m o ，d b 图表1 2 深空通信中使用的级联码性能曲线 2 2 3 ) r s 码组成的级联码系统图1 2 给出r 在不同的编码方案下的该级联码的信噪比和 误比特率曲线 b d m b x 1 2 2 移动通信中的纠错码 信道编码( 即纠错编码) 也是移动通信中提高系统数据传输可靠性的有效方法在第 二代移动通信系统中采用卷积编码和交织，对保汪语音和低速数据的业务质量取得很好 的效果而第三代移动通信系统w c d m a 所提供的业务种类大大增加，可提供与固定网络 类似的多媒体业务、支持全球漫游并具有良好的服务质量i t u rm 1 2 2 5 文件对i m t 无线通信中的r e e d - s o l o m o n 编译码器的v l s i 实现研究 第一章引言 一2 0 0 0 系统提出r 关于业务的最低要求，即：支持分组数据和电路数据，所有传输环境下 都能支持对称和不对称业务，系统提供的数据速率最小应达到车载环境下1 4 4 k b p s ，步行 环境下3 8 4 k b p s ，室内办公环境下2 m b p s 与第二代移动通信系统相比，第三代移动通信 系统实现的复杂度大大增加r 目前，世界上许多机构和组织对i m t 一2 0 0 0 的标准化进行研究，主要的有i t u 、 3 g p p 、3 g p p 2 、e t s i 、a r i b 、t i p l 等国际上的主要电信设备制造公司，如n o k i a 、 m o t o r o l a 、e r r i c s s o n 、l u c e n t 、s i m e n s 等也都在对i m t 一2 0 0 0 的标准化进行研究已经 有上十种备选方案提交到i t u 的地面第三代移动通信无线传输技术( r t t ) w c d m a 传输信道提供两类纠错方式：前向纠错( f e c ) 和自动重发请求( a r q ) 。 f e c 是无线业务的最基本的纠错方式，a r q 作为一种补充方式w c d m a 有四种f e c 建 议：卷积码、r s 码与卷积码的串行级联码、t u r b o 和业务专用码 e t s l 0 0 下面简单介绍 一下前三种f e c 编解码方案 ( 1 ) 卷积编码和v i t e r b i 译码 卷积码适用于误比特率( b e r ) 为1 0 0 级别的业务，典型的有传统的话音业务，所用 的卷积码的参数和编译码方法与第二代移动通信系统基本相同卷积码约束长度为9 ，码 率可以是l 2 、1 3 、2 3 或1 4 等，我国的t d s c d m a 方案中还用到3 4 的卷积码译 码采用v i t e r b i 算法，其中1 2 和1 3 是最常用的码率 ( 2 ) r s 码与卷积码的串行级联码 r s 码与卷积码的串行级联编码用于b e r 为1 0 - 3 _ 1 0 曲的业务中，码率为4 5 左右，码 长根据业务速率和时延要求在一定范围内变化r s 码与卷积码之间加入交织器，交织的范 围在2 0 m s 1 5 0 m s 之间变化，属于帧交织具体的级联方式在图11 中给出r s 码利用多 进制码的优势纠突发错误，卷积码纠随机错误，它们的结合可以在译码复杂度增加不太多 的条件下实现高质量的业务传输r s 码可以采用典型的b e r l e c a m p m a s s e y 迭代译码算 法，卷积码仍采用软判决v i t e r b i 算法 ( 3 ) 并行级联卷积码一t u r b o 码 t u r b o 由于其接近s h a n n o n 限的性能，使得t u r b o 码候选用于高数据率( 3 2 k b p s 以上) 、 高质量的业务t u r b o 码可以被看作是一个采用随机编译码方式的最大似然译码算法的编 译码方式它是目前最接近s h a n n o n 提出的三个必要条件的编译码器目前t u r b o 用于第 三代移动通信系统的主要困难体现在一下几个方面：1 ) 由于交织长度的限制，无法用于 速率较低、延时要求较高的数据( 包括语音) 传输；2 ) 基于m a p 的软输出算法所需运算 量和存储量较大，而基于软输出v i t e r b i 算法( s o v a ) 所需迭代次数往往难以保证：3 ) t u r b o 码在衰落信道下的性能还有待进一步研究 以上仅仅讨论r 级联码系统在深空通信和移动通信中的成功应用，在其它方面也它有 无线通信中的r e e d - s o l o m o n 编译码器的v l s i 实现研究 4 第一章引言 着广泛地应用r s ( 2 0 4 ，1 8 8 ) 作外码、( 7 ，1 2 ) 卷积码作内码的级联码系统被欧洲电 信标准协会( e t s i ) 采纳作为卫星传送高清晰度电视( h d t v ) 的信道编码标准；军用陆 上和卫星微波线路有采用( 2 5 5 ，2 3 3 ) r s 码外加交织作为抗突发和人为干扰的有效手段， 特别适合于电子对抗( e c c ) 系统目前2 g b p s 的r s 译码器的计划正在实施，而v i t e r b i 译码器的数据速度已达2 5 0 m b p s 1 3 本文的主要工作 本论文主要研究r 适用于无线通信系统中的r e e d s o l o m o n 编译码器专用d s p 芯片 ( r s d s p 的设计与实现，以及r s d s p 在r s v i t e r b i 级联码系统中的应用。本文 的研究设计到v l s i 设计的诸多方面的问题：( 1 ) 复杂电路系统的划分，特别是专用d s p ( a s d s p ) 的软硬件协同设计和仿真在进行软硬件协同设计的时候广泛采用f 硬件描 述语言v h d l ，使得协同设计变得方便和快速( 2 ) 系统的快速原型设计和验证，使用 f p g a 对系统进行快速的建模，这样的硬件模拟不仅提高f 模拟的速度，而且缩短r 产品推 向市场的时间，可以提高产品的竞争力 随后的几章按照这样来组织：第二章首先介绍rr s 码的一些基本知识，然后讨论r r s d s p 的设计方法，作为r s d s p 的设计指导思想；第三章讨论rr s d s p 的算 法和优化，提出r 适用于v l s i 实现的r s 编译码算法；第四章讨论rr s d s p 的结构， 在对比各种可实现方法的基础上，提出r 专用d s p 的方法，并讨论rd s p 的体系结构、指 令集设计和流水线结构等：第五章讨论了r s d s p 的电路实现，如何采用r t l 对d s p 的每个模块进行描述，以及电路的可测性设计和低功耗设计；第六章讨沦rr s d s p 的 开发系统及软件模拟结果，给出了r s d s p 的软件开发环境和硬件仿真环境以及硬件验 证结果，最后给出了芯片的版图设计和芯片测试结果第七章讨论r 用于无线通信中的级 联码系统，r s d s p 在该系统中得到了应用，给出了级联码系统的软件模拟结果和硬件 实现方法；第八章是全文的总结 无线通信中的r e e d s o l o m o n 编译码器的v l s i 实现研究 一 第二章r s d s p 的系统设计方法 第二章r s d s p 的系统设计方法 r s d s p 的没计包括算法、结构、电路、f p g a 验证、版图设计、芯片测试和系统测 试等一系列的内容要在预期的时间内完成这些工作，必须有一个有效的设计方法本章 主要描述rr s d s p 的背景知识，并讨论r 我们是如何在既定的设计方法指导下完成r s d s p 的设计的 2 1 r s 码的背景知识 r e e d s o l o m o n 码是由i s r e e d 和gs o l o m o n 于1 9 5 8 年的1 2 月在m i t 林肯实验室的 一篇报告中提出的在发现r s 码的早期，由于没有好的译码算法，对于纠6 个以上的错误 都是比较困难的直到1 9 6 7 年，e b e r l e k a m p 提出rb c h 和r s 码译码的一种极有效的方 法，首次使得纠多个错误的r s 码的有效译码成为可能1 9 6 8 年，m a s s e y 提出r 一科，等效 于线性反馈移位寄存器( l f s r ) 综合方法的b c h 译码方法，该方法与b e r l e k a m p 的方法 是类似的该算法现在常称为b e r l e k a m p m a s s e y ( b m ) 算法，b m 算法使得译码复杂度 从o r h 印降到o ( n 勺1 9 7 5 年s u g i y a m a e ta 1 提出f 一种解关键方程的e u c l i d e a n 算法，该算 法的复杂度也是0 0 , e ) ，可以有效地译r s 码、b c h 码和g o p p a 码这些有效的译码算法 使得r s 码在实现高性能、低成本的应用中被广泛采用同时，人们发现采用级联码可以大 大的降低传输中的误码率卷积码作内码和r s 码作外码的级联码可以取得很高的编码增 益，该级联码系统在深空通汛( v o y a g e r 号天王星和海王星探索器) 、h u b b l e 空间望远镜 和高清晰度电视( h d t v ) 等中得到r 重要的应用 r s 码是一类非二进制b c h 码，在r h ，k ) r s 码中。输人的信息分成k m 比特一组 ( b l o c k ) ，每组包括k 个符号( s y m b 0 1 ) ，每个符号由m 比特组成m ，k ) r s 码的纠错 能力t l 字j 最小码距d = 2 t + 1 一些与r s 码相关的基本概念和术语请参见 【w a n 8 9 r s 码的每个符号都是有限域( 又称迦逻华域) g f ( 2 叫上的元素设口表示g f ( 2 m ) 的 本原元，n 么 1 ，口，口2 ，口2 。2 是g 即叫上的2 m 一，个不同的非零元素最小码距为d 的r s 码的生成多项式可以表示为： 6 + 2 t j2 r g ( x ) = 兀( x - - a ) = g 工7 无线通信中的r e e d - s o l o m o n 编译码器的v l s i 实现研究 6 第二章r s d s p 的系统设计方法 其中b 是一个非负整数，通常取1 但如果取6 = 2 一一t ，可以使得，可以使编码器的 乘法器个数从2 t 减少为t 个本论文c l t 设计的r s d s p 是用来实现g f ( 2 8 ) j 2 ( j jr s ( 2 4 5 ， 2 0 0 ) 码和r s ( 2 2 5 ，18 0 ) 码的编译码算法 2 2r s d s p 的设计方法 现有文献对r s 编译码器的v l s 实现的研究绝大多数是着重于如何取得更高的吞吐 率，在v l s i 实现上通常采用全并行硬件实现 l i u 8 4 【s t d 8 5 】 i y 9 4 】【u s p 7 4 】【u s p 8 8 而 针对如何减小面积的研究不多 k s 9 7 ，而在用于无线通信的产品中，芯片的面积和功耗往 往取着决定性的作用我们设计的r s d s p 为r 能够适用于无线通信系统，必须将重点 放在减小芯片面积和降低芯片的功耗，通过对r s 编译码算法的分析和比较，我们确定r 专 用d s p 的结构，我们设计的r s 编译码 专用d s p 称为r s d s p 专用d s p 的设计牵涉到软硬件的诸 多方面的问题，为r 缩短设计周期，达 到预期的效果，必须有一套好的设计方 法r s d s p 的设计流程如图2 1 所 不 我们在算法设计时分析、比较了r s 编译码的各种算法，选取r 适合于d s p 实现的代数译码算法，并针对v l s l 实现 “ 进行r 优化软件模拟采用c + + 和 m a t l a b 两种描述，c + + 模拟具有更快 的速度，而m a t l a b 因为其丰富的库函数 而作为早期的算法研究和对照 在电路设计时采用了广泛使用的硬 件描述语言v h d l 进行r t l 级的设计， 描述电路结构时采用结构化的、自顶向下的方法 f 不同的硬件实现 图表2 1 r 8 _ d s p 的设计流程 综合 试 试 v h d l 描述由于其工艺无关性，可以用 通常的v h d l 模拟器是基于时间或者事件驱动的，对于d s p 汇编代码的调试而言是基 于一条条的代码，因此v h d l 模拟器不适合于d s p 汇编代码的调试我们开发r 基于指令 的d s p 软件模拟器该模拟器可以方便地对汇编代码进行单步、断点等调试，可以方便地 观察、修改当前d s p 的内部寄存器和存储器的状态 无线通信中的r e e d s o l o m o n 编译码器的v l s i 实现研究 7 第二章r s d s p 的系统设计方法 f p g a 验证是设计的关键部分f p g a 由于其可编程特性，常常作为a s l c 的原型设 计a s i c 设计由于设计周期长、投人大，因而有较大的市场风险采用f p g a 设计可以快 速的对系统描绘出原型，方便的进行针对不同应用的修改我们采用a l t e r a 公司的f l e x i o e 系列的f p g a 器件，门数多，速度快，而且有内嵌的e a b 模块，可以方便的实现片内r a m 和r o m f p g a 的设计可以对a s i c 设计进行几乎实时的仿真，对专用d s p 而言，可以 大大提高软、硬件联合仿真的速度我们在f p g a 验证板的开发过程中也考虑到r 未来芯 片的测试，给；芷：片留r 位置在测试板上没插入芯片时，j e ：片的功能由f p g a 来完成；在 插人芯片之后，可以测试芯片的功能和系统的性能， f p g a 负责完成其它的功能 算法级 在完成r s d s p 的f p g a 版本之后，我们可以方便 的将其迁移到a s i c 设计因为v h d l 设计的工艺无关 性，而且我们在确定结构时将可综合的逻辑电路和不可综 合的部分( 如r a m 、r o m ) 分开，因此v h d l 代码无 需修改综合工具采用占有很大市场份额的s y n o p s y s ， 为r 提高测试的覆盖率，我们使用s y n o p s y s 的t e s t c o m p i l e r 工具对r s c o r e 部分插入r 全扫描电路，并产 生a t p g 测试向量，供a t e 测试仪使用在采用目标 库进行综合、优化之后，我们进行了门级仿真，此时的门 级仿真由于只含有单元的延时，而不含连线延时，因而是 不准确的但对o6 u m 的工艺而言连线延时很小，门级仿 真已经很接近实际性能r 行为级 r t l 级 门级 版图级 图表2 2d s p 不同级别的描述 版图设计我们采用了新的设计流程，采用时序驱动的方法借助于c a n d e n c e 的新一代 用于深亚微米的s i l i c o ne n s e m b l e 布局、布线工具，可以取得更准确的时延参数和更优化的 布局、布线结果加入时钟树以后的设计，减小r 时钟歪斜，大大提高了电路性能版图 设计的后仿真在v e r i l o g - x l 环境中进行 2 3 小结 专用d s p 的设计包括r 如图2 2 所示不同级别的描述每个级别都是对上一级别更精 精确的细化，更接近于实际的芯片功能，因而也更复杂在设计的过程中，我们采用相互 验证的方法，努力保持每个模型的一致性采用我们上述的设计流程，并借助一些成熟的 e d a 工具，我们可以在预期的时间内开发出r s d s p 无线通信中的r e e d - s o l o m o n 编译码器的v l s i 实现研究 第三章r s d s p 的算法设计和优化 第三章r s d s p 的算法设计和优化 前面介绍了，r sd s p 的系统设计设计方法，r s 码是级联码系统中的核心模块，具有 一定的复杂度从本章开始将介绍r s 编译码器r sd s p 从算法到芯片的设计流程。本章 将详细介绍r s 码编码和译码的算法，重点将介绍用于我们r s d s p 的代数译码算法和适 合于v l s i 实现的优化r s 码的编译码算法使用m a f l a b 和c ”进行r 软件模拟 3 i r s 码的编码算法 我们用m = ( 。，m 1 ，一，m 。) 表示g 即9 上的k 个信息符号序列，该信息矢量的多项 式形式可以表示为：m ( x ) = m o + m l x - t - 小x ”1 产生r s 码码字多项式c ( x ) 的方法主 要有两种： 直接编码将信息符号m 与生成多项式g 相乘，即c 俐3 m g 俐但这种方法产生 的码字不是系统码。因为信息符号不能在码字中直接找到而在解码过程中，必须从 编码后的码字c 中找出信息符号m 倒，所以这种发放会使得解码过程变得复杂 多项式除法编码要得到系统码形式的r s 编码多项式，将移位后的信息多项式与g ( x ) 相除，就可以得到： c ( x ) = x d - i m ( x ) + p ( x ) 其中和俐由信息多项式左移小，位得到，p 俐小，”o d g 倒是移位后的信息多 ”，g o 9 1 9 2 。 r 口r ，r z g a t e g ，g q + g + m d t e 。v ，。u 。s ： ；l： r b ， jr 4 f 艮 图表3 1 船编码器实现的结构框图 项式被g 除后的余式，它的次数低于= 小，p 俐被称为校验多项式显然，编码后的c 御 码字用矢量的形式表示为： 无线通信中的r e e d - s o l o m o n 编译码器的v l s i 实现研究 第三章r s d s p 的算法设计和优化 c2 【p o ，p 1 ，一，p d 一2 ，m o ，i ， 一1j 我们可以看到，信息位在编码后的码字中可以清晰地分开 采用多项式除法编码的实现结构框图如图3 1 所示图中，g o g l ，g t 2 。，是生成多项 式g 的口个系数，r o r t 2 1 是髓个移位寄存器开始工作时，t 2 个移位寄存器的初 始值全部为0 在前k 个时钟周期，两个开关都打到“o i l ”的位置，信息位直接连到输出， 校验位也同时生成，并存在r 0 r t 2 1 中；在接下来的n k 个时钟周期，从右至左依次将 r 0 r 2 t t 中的校验位移出至此，一次编码过程结束 3 2r s 码的译码算法 假设r ，i ，k ) r s 码编码后的码字多项式c 通过带有噪声的信道传输，噪声e 俐传输叠加 到c 例上送到接收端，接收端接收到的码字多项式，俐2 c ( x j 其中： c ( x ) = c o + c i 互+ - + c n - i x ”叫 e ( x ) = p o + g l x + + c n - i x ”_ r ( x ) = r o + 工+ + 0 一i x ”1 有的接收系统中可能还提供纠删( e r a s u r e ) 标志来指明那些可能发生错误的符号的位 置，纠删符号的个数5 和错误符号的个数v 满足2 v + s d 一1 对于纠删，只需找出错误 的值即可，因为错误位置在纠删标志中已经给出；对于错误，需要找出错误的位置和错误 值下面的讨论只针对仅有错误的r s 解码，对于含有纠删的r s 解码请参阅相关的书目。 找出错误的位置和错误值，即噪声矢量的系数值e ，( f = o ，1 ， 一1 ) 之后，从r 御中减去e 就得到译码后的正确码字c 2 r 一e r s 的译码与编码相比要复杂得多今天，已经有许多的算法和商用器件可以实现r s 的解码r s 的译码主要有两种算法：代数译码算法和变换域算法下面分别介绍两种算法 的过程、优化和比较 3 3r s 码的代数译码算法 r s 码的代数译码方法通常可以分为五个步骤，如图3 2 所示五个步骤分别为伴随式 计算、求解关键方程、c h i e n 搜索、错误值计算和纠错图中的f i f o 将错误值保存到错误 位置和错误值找到为止，因此译码核心部件的结构决定rr s 码译码的时延和f i f o 的大 小下面分别介绍每个解码的具体步骤 译码的开始是计算伴随式s i ( i = 1 2 2 t ) 的值，就是将甜( i = 1 , 2 ，2 f ) 代人接收多 项式，( 石) 之中求出多项式的值计算第i 个伴随式墨的值的公式为： 无线通信中的r e e d s o l o m o n 编译码器的v l s i 实现研究 第三章r sd s p 的算法设计和优化 i n p u t r d a t aj s y n d r o m e i ，b e r l l e k a ，【j m p c h i e ne r r o rv a l u e c o m p u t a t i o na l g o r i t h m s e a r c hg e n e r a t i o n - f i f o e r r o rv a l u e 图表3 2r s 码代数译码的框图 s 。= r ( a ) = r ，a “ 上面的方程可以写成： s ，= 一，口+ 一：b + _ ，k + + _ 扛。+ t o 这样我们可以通过下面的递推方程计算s s i 2 a t + r 其中s i 是第，步的部分和，并且s 一，= o ，s h = s ，计算第i 个伴随式s i 的结 构框图如图3 3 所示开始时 寄存器r 初始化为0 ，接收码 字l 依次输入到加法器a 中在第i 个时钟周期，寄存i n p 。f 器r 的值与常数口“进行迦 逻华域的乘法之后，m 的乘 积与接收码字进行迦逻华 域的加法，结果存回到寄存器 图表3 3 伴随式计算单元的结构框图 r 经过1 1 个时钟周期之后，r 中便存放着伴随式s 的值这样的2 t 个相同的单元便构成 了计算伴随式s i ( i2 0 ，l ，2 t - 1 ) 的值的结构 译码的第二步是求解关键方程，就是从已知的伴随式求出错误位置多项式的系数错 误位置多项式定义为 c r ( x ) = 丌( 1 一x ，x ) = 1 + 盯，x 。 = l 1 = 1 其中，= 口”是第”，个错误的错误位置，y 是实际的错误个数，盯f 是错误位置多项式的 无线通信中的r e e d s o l o m o n 编译码器的v l s i 实现研究 第三章r s d s p 的算法设计和优化 系数 求解关键方程有b e r l e k a m p m a s s e y 的线性反馈移位寄存器( l f s r ) 综合算法和 e u c l i d e a n 两种算法由于e u c l i d e a n 算法涉及到多项式的乘法和除法，不便于实现通常 采用b e r l e k a m p m a s s e y 的l f s r 算法b m 算法的软件流程图如图3 4 所示- i n i t i a l i z a t i o n o ( n = 1r = 0 l = 0占“) = 1 立习 0 ，= s ，+ a ，- a s ， 。，太 、岁，7 lr ( z ) = ( z ) 一，加( x ) l 1 a t x ) t ( x ) 卜 lb ( x l + _ ，1 ( j ) 1r l 倥型半 i ，套， 图表3 , 4b m 算法的流程图 在b m 算法的流程图3 4 中，a ( x ) 是错误位置多项式，t ( x ) 和b ( x ) 是临时变量多项 式，是错误的个数，r 代表循环的次数b m 算法是一个循环迭代的过程，r 从1 到2 t 循环每次循环的开始，利用伴随式s ( x ) 和a ( x ) 的系数计算一个差值a ，根据，的值 更新t ( x ) 、b ( x ) 、a ( x ) 和的l 值办次循环结束时，a ( x ) 内存放的便是位置多项式的 值 译码的第三步是从错误位置多项式找出错误位置据错误位置多项式的定义，错误位 置多项式的根的倒数便是错误位置在得到错误位置多项式之后，下面便是要找出它的根 如果实际的错误个数为v a c c ，d i 自增1 l dr 2 s i 暂时保存s i l ds i r o s i 指向s x s t a c c ， s i把a c c 内容存人s i 指向的存储器( s x ) s y ne n dl ds i r 2 s i 重新指向c x 4 4r s d s p 的流水线结构 一条指令的执行周期( 通常称为指令周期) 可以分为五个阶段来完成( 通常称为机器 周期) ：取指、译码、取操作数、执行和回写取指是从指令存储器中取出指令码；译码 操作对指令进行译码，给出a l u 、寄存器组等的控制信号，同时为存取数据存储器提供地 址，或者为a l u 提供操作数；取操作数是从数据存储器中读取数据，提供a l u 的操作数； 执行操作由a l u 根据指令泽码进行指定的操作，并置相应的标志位；回写操作是将a l u 执行的结果回写到寄存器或者存储器。 执行一条指令最简单的方法就是顺序执行上面的五个步骤，那么每条指令执行的时间 无线通信中的r e e d s o l o m o n 编译码器的v l s i 实现研究 第四章r s d s p 的结构设计 也是每个阶段时间的综合下面的给出r 使用a l t e r ae p f l 0 k 1 0 0 e 器件每个部分的执行时 间如果采用全串行的执行，那么一条指令的执行需要9 5n g 要达到2 0m i p s 的最低要求 执行操作执行时间 取指 2 0r l s 译码 1 5n s 取操作数 2 0 l l s 执行 2 0 l l s 回写 2 0 l l s 每条指令的执行时间不能超过5 0n s 因此，r s d s p 必须采用流水线操作，使两个或者 以上的操作并行的进行 流水线的级数越多，并行操作越多，处理器的处理能力越强，可以降低时钟频率，取 得较低的功耗但是随着流水线级数的增多，控制器的设计也越复杂而且流水线越多， 流水线的冲突也越多，要设计软件的优化编译器变得困难，可能反而会使效率降低通常 的d s p 采用图4 2 的流水线结构，每条指令一个周期完成但是采用该结构有如下的缺陷： ( 1 ) 由于取指的顺序可能不是顺序的，遇到跳转、循环等指令，需要先确定p c 的值会 使得取指的周期变得很长，甚至要延迟一拍取指( 2 ) 由于执行和取操作数并行执行， 如果当前指令的间址寄存器的地址来自上条指令的运算结果，