（微电子学与固体电子学专业论文）fpga配置数据校验和seu效应侦测的研究和设计.pdf

摘要 摘要 为了满足用户的高端应用需求，高性能f p g a 必须能够支持配置数据校验和 单事件翻转s e u ( s i n g l ee v e n tu p s e t ) 效应侦测的功能。针对该需求，本文对f p g a 配置数据校验和s e u 效应侦测进行了研究。并根据f p g a 配置数据和回读数据的 格式，设计了配置数据校验电路和s e u 效应侦测电路。其中数据的校验，采用的 是循环冗余校验c r c ( c y c l i cr e d u n d a n c yc h e c k ) 算法。 电路首先用m o d e l s i ms e 6 0 进行功能仿真；其次采用s m i c l 8t tc m o s 工艺库 和s y n o p s y s 公司的d e s i g nc o m p i l e r 进行综合，并做了综合后的仿真。实验结果表 明，在满足时序和占用合理面积的约束条件下，电路可以实现配置数据校验和s e u 效应侦测的功能，并且工作频率可达1 6 6 m h z ，满足设计要求。 关键词：f p g a 配置回读c r cs e u a b s t r a c t a b s t r a c t i no r d e rt om e e tt h en e e d so ft h eu s e r sh i g h - e n da p p l i c a t i o n s ，h i 曲- p e r f o r m a n c e f p g am u s tb ea b l et os u p p o r tt h ef u n c t i o no fc o n f i g u r a t i o nd a t ac h e c ka n ds e u ( s i n g l e e v e n tu p s e t ) e f f e c td c t e c t a g a i n s tt h ed e m a n d ，t h ep a p e rc o n d u c t e das t u d yo ff p g a c o n f i g u r a t i o nd a t ac h e c ka n ds e u e f f e c td e t e c t a c c o r d i n gt oc o n f i g u r a t i o nd a t aa n d r e a d - b a c kd a t af o r m a t ，d e s i g n e dt h ec i r c u i t so fc o n f i g u r a t i o nd a t ac h e c ka n ds e ue f f e c t d e t e c t u s i n gt h ec r c ( c y c l i cr e d u n d a n c yc h e c k ) a l g o r i t h mc h e c kt h ed a t a f i r s t , f u n c t i o ns i m u l a t i o nu s i n gm o d e l s i ms e 6 0 ，a n dt h e nu s i n gs m i c l8 一t tc m o s p r o c e s sa n ds y n o p s y sc o m p a n y sd e s i g nc o m p i l e rt o o ls y n t h e s i z e ，g e tt h ec i r c u i t sa n d d os i m u l a t i o na f t e rs y n t h e s i z i n g t h ee x p e r i m e n t a lr e s u l ti n d i c a t e st h a ti nm e e t i n gt h e c o n d i t i o n so ft i m i n ga n dr e a s o n a b l eo c c u p i e da r e a , t h ec i r c u i t sc a nr e a l i z et h ef u n c t i o n o fc o n f i g u r a t i o nd a t ec h e c ka n ds e ue f f e c td e t e c t , a n do p e r a t i n gf r e q u e n c yu pt o 16 6 m h z ，m e e t i n gt h ed e s i g nr e q u i r e m e n t s k e y w o r d s ：f p g ac o n f i g u r a t i o nr e a d - b a c kc r cs e u 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名： 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期型! ：2 。 日期坌丝! ：立墨 绪论 第一章绪论 1 1f p g a 背景知识 2 0 世纪7 0 年代，出现了基于与或阵列的可编程逻辑器件p l d ( p r o g r a m m a b l e l o g i cd e v i c e ) 。这种可编程逻辑器件的结构简单，由它实现的逻辑电路都具有高速 的性能，但是只能实现用少量的乘积项来表示小规模逻辑电路。如果乘积项增加， 它们的连线结构会变得十分庞大以至于无法实现。1 9 8 4 年，a l t e r a 公司采用c m o s 的e p r o m 工艺研制了首块可擦写的可编程逻辑器件e p l d ( e r a s a b l ep r o g r a m m a b l e l o g i cd e v i c e ) ，它可用紫外线擦除并重复编程。1 9 8 5 年l a t t i c e 公司用e e p r o m 工 艺研制出电可擦除的可编程逻辑器件通用逻辑阵列g a l ( g e n e r i ca r r a yl o g i c ) ， 它具有设计灵活、高速、低功耗、改写迅速方便的特点，成为当时的一种常用工 业标准器件之一。对于可编程器件的另一个分支，1 9 8 5 年x i l i n x 公司推出第一片 现场可编程逻辑器件f p g a ( f i e l dp r o g r a m m a b l eg a t e a r r a y ) 。它结合了p l d 的可 编程性和掩膜可编程门阵列m p g a ( m a s kp r o g r a m m a b l eg a t ea r r a y ) 的通用连线 结构，使得可编程器件具有较高的逻辑密度。 至今，f p g a 已经经历了二十几年的发展。在这二十几年的发展过程中，以 f p g a 为代表的数字系统现场集成技术取得了惊人的发展，现场可编程逻辑器件从 最初的1 2 0 0 个可利用门，发展到今天的嵌入类似于d s p ( d i 西t a ls i g n a lp r o c e s s o r ) ， m c u ( m i c r o c o n t r o l l e ru n i t ) ，存储器等专用模块的f p g a 芯片，f p g a 芯片已经 完全适应一般的电路系统设计，从而成为替代a s i c 及门阵列的一种通用器件【l 】。 纵观现场可编程逻辑器件的发展历史，其之所以具有巨大的市场吸引力，根 本在于：f p g a 不仅可以解决电子系统小型化，低功耗，高可靠性等问题，而且其 开发周期短、开发软件投入少、芯片价格不断降低，促使f p g a 越来越多地取代 了a s i c 的市场，特别是对小批量、多品种的产品需求，使f p g a 成为首选。目前， f p g a 产品采用的工艺有：r a m 工艺、f l a s h 工艺、反熔丝工艺。本文涉及的f p g a 芯片是基于r a m 工艺的。随着大规模现场可编程逻辑器件的发展，系统设计进入 “片上可编程系统s o p c ( s y s t e mo nap r o g r a m m a b l ec h i p ) 的新纪元，芯片朝 着高密度、低电压、低功耗方向挺进。国际各大公司都在积极扩充其p 库，以优 化的资源更好的满足用户的需求，扩大市场。特别是引人注目的f p g a 动态可重 配置技术的研究，将推动数字系统设计观念的巨大转变。 2 f p g a 配置数据校验和s e u 效应侦测的研究和设计 1 2 选题背景及意义 为了满足用户的高端应用需求，高性能f p g a 必须能够支持配置数据校验和 单事件翻转s e u ( s i n g l ee v e n tu p s e t ) 效应侦测的功能【2 】。 在f p g a 数据配置的过程中，由于现场状况等诸多可能出现的因素的影响， 通讯数据常常会发生无法预测的错误，为防止错误所带来的影响，一般在通讯时 采用数据校验的方法，而循环冗余校验c r c ( c y c l i cr e d u n d a n tc h e e k ) 是最常用、 极其有效的校验方法之一。基于通讯系统中数据校验的方法，将c r c 算法应用到 f p g a 数据配置过程的校验中来，可以以较高的准确度保证f p g a 数据配置的正确 传输，为f p g a 芯片的工作安全提供有利的保障。 s e u 是一种非破坏性事件，离子辐射穿过c m o s 器件晶体管时会出现这种效 应。在地面应用中，比较重要的两种离子辐射源是封装材料释放的a l p h a 粒子，以 及地球大气和宇宙射线相互作用产生的高能量中子。s e u 产生的电荷积累到一定 程度，对s r a m 单元存储节点发生作用，导致比特状态翻转，产生软误码，从而 可能导致f p g a 功能失常，因此必须侦测s e u 效应，判断是否需要重新配置f p g a 。 同样，利用c r c 数据校验方法，能够验证回读时的存储配置数据的正确性，从而 验证配置数据的有效性，保证正确配置后的f p g a 功能正确。 通过本次研究，首先可以熟悉并掌握高性能f p g a 的系统架构与配置控制电 路结构，其次可以对数据通讯中的数据校验算法有深刻的认识，同时通过本次研究 能够学到从理解算法到实现电路的整个流程，以及掌握电路功耗和时序等性能参 数的优化方法。 1 - 3 论文内容安排 第一章是绪论部分，主要介绍了f p g a 的优势及其发展方向，作者的主要工 作和论文的目的、意义。 第二章主要介绍了f p g a 的基本架构，并阐述了f p g a 中各单元模块的结构 和工作原理。 第三章主要介绍了c r c 算法基本原理，并分别描述了逐位运算法和查表法的 c r c 计算实现方法。 第四章是本文的重点，首先介绍了电路的系统框图和该系统的工作原理，其 次详细介绍了f p g a 配置数据控制电路、回读数据控制电路和c r c 校验电路的设 计方法及其设计实现，最后介绍了系统中其他模块的设计。 第五章根据第四章所介绍的系统设计，进行仿真和综合，给出了本次研究结 绪论 果，并对其进行分析。 第六章对本次设计进行总结和分析，提出了今后研究还需提高和改进的地方。 第二章f p g a 架构分析 第二章f p g a 架构分析 f p g a 器件从结构上讲，其核心部分是逻辑单元阵列l c a ( l o 西cc e l la r r a y ) ， l c a 是由内部逻辑块矩阵及周边的输入输出模块l o b ( i n p u t o u t p u tb l o e k ) 组成， 而其内部连线可编程互连资源p i ( p r o g r a m m a b l ei n t e r c o n n e c t i o n ) 则占据逻辑 块的行列之间，以及逻辑块与i 0 块之间的通道。l c a 的可编程逻辑块c l b ( c o n f i g u r a b l el o g i cb l o c k ) 和i o b 的功能及其互连，是由存储器( 如e e p r o m ) 中的配置程序来控制的。目前一些f p g a 器件，在传统的架构基础之上还增加了 延迟锁相环d l l ( d e l a y - l o c k e dl o o p ) 和块选随机存储器b r a m ( b l o c ks e l e c t r a m ) 等单元。图2 1 为含有d l l 和b r a m 的系统结构图，接下来将对该系统架 构做简要阐述与分析。 d l li o b sd l l v e r s a r i n g i o b sb r mc l bb r a mi o b s v e r s a r i n g ；。， d i 上 i o b s 工 图2 1f p g a 系统结构图 2 1 可编程逻辑单元( c l b ) f p g a 器件的主体部分是由相同的可配置逻辑单元c l b 构成的矩阵，每个 c l b 含有相同的组合逻辑和寄存器，一个c l b 里含有两个s l i c e ，每个s l i c e 里面 包含两个逻辑单元l c ( l o g i cc e l l ) ，一个l c 包括一个4 输入的函数发生器、一 个进位逻辑和一个存储单元，一个c l b 的结构如图2 2 所示， 6f p g a 配置数据校验和s e u 效应侦测的研究和设计 c o u t ，t 、 g 4 g 3 g 2 g 1 c b 唧& c o n t r o i c 毫t r y 矗 c o n g o l 3 p dq e c ， r c y b y g 4 g 3 y q g 1 岍hc a r r y & h 乏s p q c a r r y & 叫p q c o n t r o ll i e c 曼纠 3 i l e , e o y 8 y y o x b x x q c 删c 嫩 图2 2c l b 结构 除了4 个基本的l c 外，c l b 中还包括一些逻辑电路，与函数发生器一起实 现任意5 输入或6 输入的逻辑函数。查找表l i j t ( l o o ku pt a b l e ) 被用作函数发 生器。为实现这一功能，每个l u t 提供1 个1 6 1 位同步r a m 。同时，每个s l i c e 的两个u j t 可以组合成一个1 6 2 或3 2 1 的同步r a m ，或是1 6 1 的双端口同步 r a m 。l u t 还可以配置成一个1 6 位移位寄存器，用来捕获突发模式下的高速数 据。函数发生器的工作原理类似于r o m ，l u t 的输入等效于r o m 的地址码，通 过查找r o m 中的地址表可以得到相应的组合逻辑输出。 c l b 的专用进位逻辑为高速运算提供了快速的算术进位能力。每个c l b 支持 两个独立的进位链，进位链高度为2 b i t s ，每个s l i c e 有一个进位链。算术逻辑中包 含一个异或门，使每个l c 单元可以实现一个1 位全加器。专用的进位逻辑同时也 可用来级联函数发生器，以实现更加复杂的逻辑函数。此外，每个l c 中还有一个 用来有效实现专门乘法器的与门。 s l i c e 中的存储单元可配置成边沿触发的d 触发器或电平触发的锁存器。d 触 发器的输入可被s l i c e 内的函数发生器的输出信号驱动，也可以直接被s l i c e 的输 入驱动。除时钟和时钟使能信号外，每个s l i c e 的时钟和时钟使能信号可以同步置 位( s r ) 和复位( b y ) 。这些信号还可被配置成异步操作方式。 2 2 输入输出模块( i o b ) i o b 一般都支持很多种i o 信号标准，其结构如图2 3 所示。i o b 中存储单元 吖 艮融挖h 弧 燔x 船 吖 阿融眨h 畎 第二章f p g a 架构分析 的功能可以是边沿触发的d 触发器或电平敏感的锁存器。每个l o b 中三个触发器 共用一个时钟信号c l k ，但有独立的时钟使能信号。除了c l k 和c e 控制信号， 这三个触发器还共用一个置位复位( s r ) 信号，可实现同步置位、同步复位、异 步复位和异步清零。 可选上拉、下拉电阻和可选弱保持电路与每个p a d 相连。在配置之前，没有 配置的所有p i n s 都处于高阻态，上拉电阻的激活是由配置模式引脚所控制的。如 果上拉电阻没有激活，所有的引脚将悬空。所有的l o b s 都支持i e e e1 1 4 9 1 边界 扫描标准。 t r c e o o c e i l q s r c l l ( i c e 图2 3l o b 简化电路结构 当l o b 被定义为输入时，输入信号经p a d 进入输入缓冲器，并根据用户编程 要求，既可以直接输入，也可以通过d 触发器或电平触发的锁存器输入，而此时 亦可由配置选择到达触发器或锁存器的信号是否需要延时，以补偿时钟信号的延 迟。 当l o b 被定义为输出时，输出信号可以通过配置选择是直接传输到p a d ，或通 过d 触发器暂存后传输。可以选择用使能信号来输出缓冲器是否为高阻态，以实 现三态输出或双向i o 传输。 f p g a 配置数据校验和s e u 效应侦测的研究和设计 2 3 可编程路由资源( p i ) f p g a 是阵列式的结构，在模块之间存在着水平和竖直的布线通道。布线通道 中可被分割成任意长度的连线。大多数f p g a 采用层次式互连方式的可编程互连 线模型，该模型通常在布线通道中存在三种连线，即相邻高速互连层次短线、局 部连线层次的可分割长线和全局层次的长线。下面根据器件的结构介绍f p g a 内 部路由资源： 局部路由( l o c a lr o u t i n g ) v e r a s b l o c k 提供了局部路由资源，如图2 4 所示，它可以提供以下三种连接： 邻近的g r i d 邻近的g 雕 直接连接邻近的c l b 图2 4 局部路由 一、l u t 、触发器和通用路由矩阵g r m ( g e n e r a lr o u t i n gm a t r i x ) 间的连接。 二、内部c l b 反馈路径，这些路径可以在同一个c l b 中提供u j t 间的高速 互连，它们连在一起将达到最小的延时。 三、相邻c l b 之间的连接。 通用路由( g e n e r a lp u r p o s er o u t i n g ) 大多数信号是通过通用路由传送的，因此大多数互连资源都是与这个路由层 级相连接。通用路由资源位于c l b 行列间的路由通道内。通用路由包括： 一、每个c l b 的旁边有个通用路由矩阵g r m 。g r m 是水平、垂直路由资源 连接的开关矩阵，c l b 可通过它访问通用路由。 二、g r m 的每一边有2 4 根短线和相邻的g r m 相连。 三、g r m 的每一边有1 2 根可分割长线和离它6 个c l b 距离的g r m 相连， 三分之一是双向的可分割长线，其它是单向可分割长线。 第二章f p g a 架构分析 9 四、1 2 根双向长线，能有效地传送信号，水平和垂直的长线都贯穿整个器件。 i o 路由( f or o u t i n g ) 器件的周围有额外的路由资源，它们提供了c l b 阵列和i o b s 连接。使得引 脚交换和引脚锁定能更好的实现，该技术能够让逻辑重设计适应现有的p c b 板。 在进行逻辑设计的同时，p c b 和其它系统部件就可以制造，从而缩短了上市时间。 专用路由( d e d i c a t e dr o u t i n g ) 为了性能最优，一些信号需要专用的路由资源。有两种信号需要专用路由资 源： 一、水平路由资源由四条可分割总线组成，提供片上三态总线，如图2 5 所示。 二、垂直方向上相邻的c l b 间有两个专门的网络提供进位链。 上r 硼l ，lr p 吲i 上厂p 蚓1上 上 丫_ 一 上丫，l 丫 一 土 丁 丫上丫上、r上 丫上 上丫上 、r 上 、r 上丫 ，奔冷 、，奔冷，奔冷， t ，除斧 c l b c l bc l bc l b 图2 5 水平专用路由总线 全局路由( g 1 0 b a lr o u t i n g ) 时钟和其他高扇出信号由全局路由提供。器件包含两个层级的全局路由资源， 即主全局和次局部时钟路由资源。 一、主全局路由资源是四个专门的全局网络，用来提供高扇出时钟信号的路 由，以达到最小的时钟偏斜。每个时钟网络都可以驱动所有的c l b 、i o b 和b r a m 的时钟引脚。 二、次局部时钟路由资源包括2 4 根中枢线，器件的上下各1 2 根，次局部时 钟路由资源比主全局路由资源更灵活，它们不局限于时钟引脚的路由。 2 4 块选随机存储器( b r a m ) b r a m 是以列的形式组成的，分布在c l b 阵列的两边，共两列。不同型号的 器件，r a m 的数目也不一样。如图2 6 、2 7 所示，一块r a m 的容量是4 k b i t ，每 个端口可配置为指定的任意宽度，且有各自的控制信号，这样极大地简化了用户 的设计。 10f p g a 配置数据校验和s e u 效应侦测的研究和设计 i 4s # w e 。e n r s t c l kd o # ：0 a d d r # ：0 d i # ：o 图2 6 单端口b r a m 鼬蛐毋4s # s # 图2 7 双端口b r a m 一块r a m 可根据用户需求，配置成三种模式： 一、s i n g l e p o r t ：位宽可为1 、2 、4 、8 、1 6 ( 例如，r a m b 4s 8 表示位宽为8 的单端口r a m ) 。 二、d u a l p o r t ( 端口匹配) ：两个端口位宽相同，位宽可为l 、2 、4 、8 、1 6 ( 例如，r a m b 4 $ 1 6s 1 6 代表a 端口、b 端口位宽都为1 6 的双端口ra m ) 。 三、d u a l p o r t ( 端口不匹配) ：两个端口位宽不匹配的双端口r a m ( 例如， r a m b 4 一s 2 一s 4 代表a 端口位宽为2 ，b 端口位宽都为4 的双端口r a m ) 。 b r a m 的可配置位宽列表如表2 1 所示， 第二章f p g a 架构分析 表2 1b r a m 可配置位宽列表 宽度深度地址总线 数据总线 l4 0 9 6a d d r d 蛔巳 2 2 0 4 8 a d d r d a ：i a 41 0 2 4a d d r d a i a 8 5 1 2 a d d r d 娥 1 6 2 5 6a d d i k 7 ：o d a i ：f 气 2 5 延迟锁相环( d l l ) f p g a 有四个d l l 分别位于芯片内部的四个角上。这些d l l 可以用来完善和 简化系统级设计，比如提供零传播延迟、低时钟相位差和高级时钟区域控制等。 尤其对于时钟频率比较高、时序要求比较严格的应用，它可以有效的消除延时与 降低时钟偏斜。 每个d l l 可以驱动两个全局时钟，全局时钟分布网络可以根据不同的负载， 将时钟相位最小化。d l l 的主要特性如下： 一、d l l 在网络中补偿延迟，有效的消除了设备内从外部输入端口到时钟装 载的延迟，可根据用户的原时钟信号提供零延迟。 二、d l l 可提供时钟的二倍频或四倍频。 三、d l l 可对时钟进行1 5 、2 、2 5 、3 、4 、5 、8 、1 6 分频。 四、d l l 可提供固定相位差的时钟，如9 0 。、1 8 0 。、2 7 0 。 五、d l l 可降低多个设备间的时钟相位差。 下面通过一个d l l 电路框图来说明其工作原理。d l l 电路框图如图2 8 所示， 主要由鉴相器、可调延时线、控制器以及输出数据选择器组成。4 个次可调延时线 与一级鉴相器组成时钟移相器。 1 2f p g a 配置数据校验和s e u 效应侦测的研究和设计 图2 8d l l 简化模型 其基本原理是：时钟由c l ki n 输入进入d l l 的主可调延时线，产生源时钟 信号的延时版本c l kd 提供给时钟移相器。时钟移相器的鉴相器比较时钟移相器 的输入时钟与经过4 条次延时线输出时钟的相位，调整移相器的控制器来调节可 调延时线1 、2 、3 、4 的延时和，从而产生4 相移时钟信号c l k 一1 、c l k 一2 、c l k 一3 、 c l k4 ( 即时钟经过时钟移相器的延时为一个周期，并且每个可调延时线使时钟 相移9 0 。( 即1 4 周期) ) 。这些相移时钟信号和c l kd 输入到输出选择器的输入 端，由输出选择器根据需要产生所需的时钟信号输出到d l l 的输出端作为输出时 钟信号c l ko u t 。输出时钟信号进入时钟分布网络，由于时钟缓冲、重负载时钟 线的大电容、线路的传播时延等因素，使c l ko u t 延时偏移为延时时钟信号 c l ks ，作为逻辑电路的时钟信号，同时，由d l l 的反馈输入端，c l ks 作为反 馈时钟信号c l kf b 输入鉴相器，鉴相器比较c l ki n 与c l kf b ，判断c l kf b 相较于c l ki n 是滞后还是超前( 这里的滞后是指c l ki n 的上升边与相邻的下 一个c l kf b 的上升边之间的时间差小于c l kf b 的上升边与相邻的下一个 c l ki n 的上升边之间的时间差，超前是指前一个时间差大于后一个时间差) 。由 控制器决定增加或减少可调延迟线的传播时延d 和输出选择器的输出选择，以同 步时钟。 第二章f p g a 架构分析 2 6 本章小结 本章简单介绍了目前比较常见的f p g a 的架构，并对其中的各模块的功能和 工作原理进行了简单的分析，更进一步地了解f p g a ，为本次设计打基础。 第三章c r c 算法简介 第三章c r c 算法简介 在数据传输和存储的过程中由于噪声和干扰等原因，接收的数据可能与发送 的数据不一致。为了保证数据传输的正确率，通常在数据传输过程中采用一些编 码和检测方法。实现校验的方法很多，有奇偶校验、循环冗余校验( c r c ) 等。 c r c 校验以其高效率、高性能获得了广泛的应用。c r c 校验码是从循环码中派生 的缩短循环码，是一类很重要的检错码，它只能检测出错误，而不能纠正错误。 3 1c r c 校验基本原理 c r c 校验采用了多项式编码方法，被处理数据块可以看作是一个n 阶的二进 制多项式，a n l 工打- 1 + a n - 2 x ”2 + + 口l x + a o ( 比如一个8 位二进制数o x l o l l o l 0 1 可 以表示为：i x 7 + o x 6 + i x 5 + l x 4 + 0 x 3 + l x 2 + 0 x + 1 ) ，多项式乘除法运算过程与普通 代数多项式的乘除法相同即加减法运算以2 为模( 模2 运算) ，加减时不进、 借位，和逻辑异或运算一致【3 】【4 】【5 】【6 】阴。 目前，国际通用c r c 标准主要有： c r c 一4 ：r 4 + x + 1 c r c 一8 ：x + x s + x 4 + 1 c r c 一1 2 = x 1 2 + x 1 1 + x 3 + x 2 + x + 1 c r c a n s l = x 1 6 + x 1 5 + x 2 + l c r c c c i t t = x 岫+ x 1 2 + x 5 + 1 c r c 一3 2 = x 3 2 + + p + p + f 6 + 2 + f 1 + f o + f + f + + f + f + x + 1 采用c r c 校验时，发送方和接收方采用用同一个生成多项式g ( x ) 进行运算， 并且g ( x ) 的首位和最后一位的系数必须为1 ，其大致处理方法是：发送方以生成多 项式g ( x ) 去除待发送的二进制数据t ( x ) ，将得到的余数作为c r c 校验码，校验时， 以计算的校正结果是否为0 为依据进而判断数据帧是否改变。其实现步骤如下： 一、设待发送的数据块是m 位的二进制多项式t ( x ) ，生成多项式为r 阶的g ( x ) 。 在数据块的末尾添加价o ，数据块的长度增加到m + r , c t ，对应的二进制多项式为 x 7 t ( x ) 。 二、用生成多项式g ( x ) 去除x r t ( x ) ，求得余数为阶数为r - 1 的二进制多项式y ( x ) 。 1 6f p g a 配置数据校验和s e u 效应侦测的研究和设计 此二进制多项式y ( x ) 就是t ( x ) 经过生成多项式g ( x ) 编码的c r c 校验码。 三、用z 7 f ( 工) 以模2 的方式减去灭x ) ，得到二进制多项式x r t ( x ) 。x r t ( x ) 就是包含 了c r c 校验码的待发送字符串。 从c r c 的编码规则可以看出，c r c 编码实际上是将待发送的m 位二进制多项式 “x ) 转换成了可以被g ( x ) 除尽的m + r 位二进制多项式x r t ( x ) ，所以解码时可以用接 收到的数据去除g ( x ) ，如果余数为零，则表示传输过程中数据没有发生错误，如果 余数不为零，则在传输过程中肯定存在错误。 当然与一般的校验和纠错编码方式类似，c r c 算法也有一定的误码率，r 位生 成多项式产生的c r c 码可以检测出所有单个和两个错误、奇数位错误和突发长度 r 的突发错误，以及检测突发错误长度为r + 1 的概率为( 1 2 - ( r - l ) 和检测突发错误 长度 r + 1 的概率为( 1 2 ”) 。r = 1 6 时，能检测出所有突发长度1 6 的突发错误， 以及9 9 9 9 7 的突发长度为1 7 的突发错误和9 9 9 9 8 的突发长度 1 7 的突发错误。 在接收方解码后未发现除法余数时，传输过程也可能发生了错误，但误码率极其 低，所以c r c 算法在数据通讯等领域以较高可靠度和并不复杂的编码方式而备受 青睐。 由于c r c 的编码过程基本一致，只有位数和生成多项式不一样，为了叙述简 单，用一个c r c 4 编码的例子来说明c r c 的编码过程，以便更清楚地阐述c r c 校 验码的编码过程。 设待发送的数据t ( x ) 为1 2 位的二进制数据o x l 0 0 1 0 0 0 1 1 1 0 0 ，c r c 4 的生成多项 式为g ( x ) = 五+ x + l ，阶数r 为4 ，即1 0 0 1 1 。首先在t ( x ) 的末尾添= c 1 1 1 4 个o 构成x 4 t ( x ) ， 数据块就成了0 x 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 。然后用g ( x ) 去除x 4 t ( x ) ，不用管商是多少，只 需要得到余数y ( x ) 。 表3 1 给出了除法过程。可见，c r c 编码实际上是一个循环移位的模2 运算。 第三章c r c 算法简介 表3 1c r c - 4 除法过程 除数次数 被除数j g ( x ) 结果 余数 00 x l0 0 1 0 0 0 11 1 0 0 0 0 0 0o x l 0 0 1 11 0 0 0 0 0 0 0 x l0 0 11 0 x 00 0 0 1 0 0 111 0 0 0 0 0 0 10 x l0 0 1 1 l 0 0 0 0 0 00 x 1 0 0 0 0 0 0 0 x l0 0 1 1 0 x 00 0 0 01 0 0 0 0 0 0 20 x l0 0 0 0 0 0 0 x l l 0 0 0 x 10 0 11 0 x 0 0 0 1 1 0 0 3 2c r c 实现方法 根据实现应用的需要，c r c 算法可分为串行处理和并行处理两种类型，通常 有两种实现方法：逐位运算法和查表法，以下将对之做简要分析。 3 2 1 逐位运算法 该方法执行起来效率不高，但它确是真正体现c r c 算法的本质。为实现c r c 算法，先要实现c r c 除法。计算c r c 绝对不能简单地用除法指令，原因之一是， c r c 有专门的算法，原因之二是，被除数可能达几兆字节长，当今的处理器不可 能有这么大的寄存器。要想实现c r c 除法，需要通过除法寄存器逐步送入待处理 的信息。因此必须准确知道待处理的信息数据比特数，在下面的例子中，假设信 息为字节流且b i t 7 为最高位，字节流由第一字节高位开始即b i t 7b i t 6 b i t 0 ，然后 第二字节，比特次序同第一字节。 下面考虑生成多项式最高次数为4 ，生成多项式为1 0 11 1 ，执行除法需要4 个 寄存器，下面是执行除法的步骤： 一、初始化，将寄存器初始化为o 。 二、添尾比特，在信息比特流最后添加4 个o 。 三、左移，将寄存器左移1 比特，并从信息比特流读入下一比特写入第o 寄 存器。 四、移出比特是否为l 的判断，如果从寄存器移出的比特为1 ，则寄存器组= 18f p g a 配置数据校验和s e u 效应侦测的研究和设计 ( 寄存器组) 异或( 生成多项式) ；否则直接跳到第五步。 五、信息比特流是否结束的判断，信息比特流如果没有做完则返回到步骤三 继续执行，否则结束计算。 这种按比特计算的方法能够更好说明问题，更清楚地体现c r c 算法的本质。 必须清楚，上述除法算法适合任意c r c 宽度w ，具体的c 程序实现流程如图3 1 。 对c r c 4 ，假设有一个5 b i t 的寄存器，通过反复的移位和c r c 除法，那 么最终存储在该寄存器中的低4 一b i t 数据就是所要求的余数。可以将上述步骤用以 下算法执行流程加以简要描述： r e g 是一个5b i t s 的寄存器 把r e g 中的值置0 在原始的数据后添加r 个0 w h i l e ( 数据未处理完) b e g i n i f ( r e g 首位是1 ) 。 r e g = r e g x o r 0 x 0 0 1 1 把r e g 中的值左移一位，读入一个新的数据并置于r e g i s t e r 的0b i t 的位置 e n d 第三章c r c 算法简介 1 9 图3 1 逐位法实现c r c 的流程图 为了对优化后的算法有一种直观的了解，先将上面的算法换个角度理解一下。 在上面例子中，可以将编码看作如下过程： 由于最后只需要余数，所以只看低四位。构造一个四位的寄存器r e g ，初值为o ， 数据依次移入r e 9 0 ( r e g 的0 位) ，同时r e 9 3 的数据移r e g 。由上面的算法可以知道， 只有当移出的数据为1 时，r e g 才和g ( x ) 进行x o r 运算；移出的数据为0 时，r e g 不与 2 0 f p g a 配置数据校验和s e u 效应侦测的研究和设计 g ( x ) 进行x o r 运算，相当与和o x 0 0 0 0 进行x o r 运_ 算。就是说，r e g 和什么样的数据 进行x o r 由移出的数据决定。由于只有1 个b i t ，所以有2 种选择。 上述算法可以描述如下： r e g 是一个4b i t s 的寄存器 初始化t 【】= o x 0 0 0 0 ，0 x 0 0 11 把r e g 中所有的数据置为0 在原始的数据后添加r 个o w h i l e ( 数据未处理完) b e g i n 把r e g 中的值左移一位，读入一个新的数据并置于r e g i s t e r 的0 b i t 的位置 r e g = r e gx o rt 移出的位】 e n d 3 2 2 查表法 逐位运算法是以b i t 为单位进行串行处理的，这种算法每次只能处理一位数据， 效率低而且运算量大，为了快速实现c r c ，可以将上述算法扩展到一次处理4 位、 8 位、1 6 位、3 2 位。由于处理器的结构基本上都支持8 位数据的处理，所以一次 处理8 位比较合理，即以b y t e 为单位进行处理【8 1 。 现以c r c 3 2 为例进行说明，其实这是一种基于c r c 3 2 生成多项式来并行 处理8 b i t 数据的c r c 计算方法。构造一个四个b y t e 的寄存器r e g ，初始值为 0 x 0 0 0 0 0 0 0 0 ，数据依次移入r e 9 0 ( r e g 的o 字节，以下类似) ，同时r e 9 3 的数据 移出r e g 。用上面的算法类推可知，移出的数据字节决定r e g 和什么样的数据进行 x o r 。由于有8 个b i t ，所以有2 5 6 种选择，这2 5 6 种选择构成了一个和8 位数据 相对应的表，称为查找表。具体c 程序流程如图3 2 所示， 第三章c r c 算法简介 2 1 图3 2 查表法实现c r c 流程图 上述算法可以描述如下： r e g 是一个4b y t e 的寄存器 初始化t 口= 共有2 5 6 项。 把r e g 中的值置0 在原始的数据后添加r 8 个0 字节 w h i l e ( 数据未处理完) b e g i n 把r e g 中的值左移一个字节，读入一个新的字节并置于r e g 的第0 个b y t e 的位置 r e g = r e gx o rt 移出的字节】 e n d f p g a 配置数据校验和s e u 效应侦测的研究和设计 这种算法每次处理一个字节，通过查表法进行运算，大大提高了处理速度。 目前还有半字节查表法，其原理和字节查表一样，只是每次处理4 b i t 数据。 下面介绍按字节计算c r c 的查找表的计算方法： 首先假设寄存器组初始化为o ，其实寄存器组可以是任何值，这里只是为了下 面方便说明而己。 如果一次只对1 比特操作，则移出的数据只有两种可能o 、1 。如果移出0 ， 寄存器组的值保持不变；如果移出l ，寄存器组的值变为生成多项式p o l y ，即相当 于 移出o ：寄存器组= 寄存器组x o r0 移出1 ：寄存器组= 寄存器组x o r p o l y 由此可知，表格内只有两个值，即0 、p o l y 。 如果一次对2 比特操作，则移出的数据应有四种可能0 0 、0 1 ：1 0 、1 1 ，如果 移出o o ，寄存器组的值保持不变；如果移出0 1 ，寄存器组的值变为生成多项式p o l y ； 如果移出1 0 ，寄存器组的值为生成多项式左移一位( p o l y 1 ) ；如果移出1 1 ，寄 存器组的值变为生成多项式p o l y 加上生成多项式左移一位；相当于 移出0 0 ：寄存器组= 寄存器组x o r0 移出0 1 ：寄存器组= 寄存器组x o r ( p o l y ) 移出1 0 - 寄存器组= 寄存器组x o r ( p o l y 1 ) 移出1 1 ：寄存器组= 寄存器组x o r ( ( p o l y 1 ) + p o l y ) 由此可知，表内有四个值，即0 、p o l y 、p o l y 1 、( p o l y 1 ) + p o l y 。 同理，如果一次对3 比特操作，则移出的数据应有2 3 即八种可能0 0 0 、0 0 1 、 0 1 0 、0 1 1 、1 0 0 、1 0 1 、1 1 0 、1 1 1 ，推导和上面类似，即 移出0 0 0 ：寄存器组= 寄存器组x o r0 移出0 0 1 ：寄存器组= 寄存器组x o r ( p o l y ) 移出0 1 0 - 寄存器组= 寄存器组x o r ( p o l y 1 ) 移出0 1 1 ：寄存器组= 寄存器组x o r ( ( p o l y 1 ) + p o l y ) 移出1 0 0 ：寄存器组= 寄存器组x o r ( p o l y 2 ) 移出1 0 1 ：寄存器组= 寄存器组x o r ( ( p o l y 2 ) + p o l y ) 移出1 1 0 ：寄存器组= 寄存器组x o r ( ( p o l y “2 ) + ( p o l y 1 ) ) 移出1 1 1 ：寄存器组= 寄存器组x o r ( ( p o l y 2 ) + ( p o l y 1 ) + p o l y ) 可知，表内有八个值，即0 、p o l y 、p o l y 1 、( p o l y 1 ) + p o l y 、p o l y 2 、 ( p o l y 2 ) + p o l y 、( p o l y 2 ) + ( p o l y 1 ) 、( p o l y 2 ) + ( p o l y 1 ) + p o l y 。 同理