（物理电子学专业论文）针对正弦余弦计算的cordic算法优化及其fpga实现.pdf

硕士学位论文摘要 摘要 随着超大规模集成电路( v e r yl a r g es c a l ei n t e g r a t e dc i r c u i t e s ， v l s i ) 技术的飞速发展，经常需要用硬件快速和精确地进行三角函数 值的计算，而坐标旋转算法( c o o r d i n a t er o t a t i o n a ld i g i t a lc o m p u t e r ， c o r d i c 、) 能够将多种难以用硬件电路直接实现的复杂的三角函数运 算分解为统一的加减、移位操作，极大地降低了硬件设计的复杂性。 本文在基于传统的c o r d i c 算法的理论分析和实验的基础上，提出了 一系列的优化措施。理论分析和实验测试表明，优化后的算法在精度 保持不变的情况下，可以提高运算速度和降低系统所占用的硬件资源。 本文的主要研究成果为：1 ) 通过对每次旋转的角度分析，减少了反正 切函数表的容量和流水线的级数，降低了系统的资源消耗；2 ) 减少了 系统迭代时对反正切函数表的访问次数，提高了系统的运算速度；3 ) 简化了校正因子的运算；4 ) 利用三角函数的对称性，将输入角度的范 围扩大到一个完整的周期；5 ) 提出了以现场可编程门阵列( f i e l d p r o g r a m m a b l eg a t e a r r a y ，f p g a ) 为平台的硬件设计实现方案，采用 超高速集成电路硬件描述语言( v h s i ch a r d w a r ed e s c r i p t i o n l a n g u a g e ，v h d l ) 完成了整个系统的设计，通过了仿真与适配；详 细地论述了系统总体框架及内部模块设计，重点介绍了优化c o r d i c 算法实现单元的设计，并在系统设计中加入了异步串行接口，完善了 整个系统的模块化。成功地实现了正弦函数、余弦函数的运算，仿真 结果表明所设计的算法提高了运算速度、降低了系统所占用的硬件资 源。 关键词：超大规模集成电路，坐标旋转算法，超高速集成电路硬件描 述语言，现场可编程门阵列 硕士学位论文 a b s t r a c t a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fv e 巧l a r g es c a l ei n t e g r a t e dc i r c u i t e s ， h a r d w a r ei so f t e nu s e di nt h eq u i c ka n da c c u r a t et r i g o n o m e t r i cf u n c t i o n c a l c u l a t i o nc o o r d i n a t e r o t a t i o nd i g i t a lc o m p u t e r ( c o r d i c ) c a n d i s a s s e m b l ec o m p l e xo p e r a t i o n sw h i c ha r eh a r d l ya c h i e v e db yt h e h a r d w a r ec i r c u i td i r e c t l yi n t ou n i t i v ep l u s m i n u sa n ds h i f to p e r a t i o n ， d e c r e a s i n gt h ec o m p l e x i t y o ft h eh a r d w a r ed e s i g n o nt h eb a s eo f t h e o r e t i c a la n de x p e r i m e n t a la n a l y s i so ft r a d i t i o n a lc o r d i c ，t h i st h e s i s p r o p o s e s s e r i e s o p t i m i z e dm e a s u r e s t h e t h e o r e t i c a l a n a l y s i s a n d e x p e r i m e n t a lt e s t si n d i c a t et h a tw i t h t h es a m ep r e c i s i o n ，t h eo p t i m i z e d a r i t h m e t i cc a ni n c r e a s et h eo p e r a t i o ns p e e da n dd e c r e a s et h es y s t e m o c c u p y i n gh a r d w a r er e s o u r c e t h em a i ns t u d yp r o d u c t i o ni s ：1 ) t h r o u g h t h e a n a l y s i s o fr e v o l v i n g a n g l e e a c ht i m e ，t h e s y s t e m r e s o u r c e c o n s u m m a t i o ni sr e d u c e dw i t ht h ed e c r e a s eo ft h ev o l u m eo ft h et a b l eo f c o u n t e r - t a n g e n tf u n c t i o n a n dt h ep r o d u c t i o nl i n e sp r o g r e s s i o n 2 ) t h e s y s t e mo p e r a t i o ns p e e di s i n c r e a s e dw i t ht h ed e c r e a s eo ft h et a b l eo f c o u n t e r - t a n g e n tf u n c t i o n sa c c e s s i n gt i m e sw h e ni t e r a t e d 3 、) t h eo p e r a t i o n o fe m e n d a t i o nf a c t o r si ss i m p l i z e d 4 ) u s i n gt h es y m m e t r yo ft r i g o n o m e t r i c f u n c t i o n ，t h es c o p eo f t h ei n p u ta n g l ei se x t e n d e dt oa i n t a c tc i r c l e 5 ) t h e t h e s i sp r o p o s e st h eh a r d w a r ed e s i g ni m p l e m e n tp r o j e c to nt h ep l a t f o r mo f f i e l dp r o g r a m m a b l eg a t ea r r a y ( f p g a ) ，w h i c hc o m p l e t e st h ew h o l e s y s t e md e s i g nw i t hv h s i c h a r d w a r ed e s c r i p t i o nl a n g u a g e ( v h d l ) a n d p a s s e ss i m u l a t i o na n da d a p t i o n t h i sp a p e rd e t a i l e d l yd i s c u s s e st h ew h o l e s y s t e mf l a m ew o r ka n di n t e r i o rm o d u l ed e s i g na n dm a i n l yi n t r o d u c e st h e i m p l e m e n t u n i t d e s i g n t o i m p r o v e c o r d i c a l g o r i t h m ，a d d i n g a s y n c h r o n i s ms e r ia l i n t e r f a c ei nt h es y s t e md e s i g n ，p e r f e c t st h ew h o l e s y s t e mm o d u l a r i z a t i o n r e a l i z e ss i n e 、c o s i n ea l g o r i t h m t h es i m u l a t i o n r e s u l t si n d i c a t et h a tt h ea l g o r i t h m si m p r o v e sc o m p u t i n gs p e e da n d r e d u c e st h es y s t e mh a r d w a r er e s o u r c e s o c c u p i e d k e yw o r d s ：v l s i ，c o r d i c ，v h d l ，f p g a i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：弛j 丝红 日期：芝堕年上月孚日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：地i 慈型导师签名 吼堕年! 月挈日 硕上学位论文第一章绪论 1 1 研究意义 第一章绪论 求三角函数值是科学计算和工程设计中的一种重要的运算，如在三角学、二 次方程求解、二维建模、误差计算、数值分析、概率统计、图象处理等科学技术 领域中频繁使用，计算过程复杂，运算速度明显低于其他运算，特别是硬件不易 实现，为此，人们一直在寻找一种易于硬件实现的算法来提高三角函数的运算速 度，c o r d i c 算法i l 】就是目前公认的这样的一种较为理想的算法。 一种算法的硬件实现，目前主要依赖于复杂可编程逻辑器件和现场可编程门 阵列( c p l d f p g a ，c o m p l e xp r o g r a m m a b 1el o g i cd e v i c e f i e l dp r o g r a m m a b1e l o g i cd e v i c e ) ，其中，运算速度和占用的芯片面积是衡量一种算法优劣的主要 技术指标。c o i m i c 算法虽然已经能够用硬件较满意地计算三角函数，但由于该 算法的复杂性，使得它还可能存在一定的可改进的空间以期进一步提高三角函数 的运算速度、降低占用的芯片面积。因此，本文的研究工作具有一定的理论意义 和实际应用价值。 1 2 数学函数的硬件实现方法 -。，_ 数学函数的硬件实现方法可归纳如下： l 、查找表法 通过查找表求函数值是一种直接方法，适用于任何函数计算。对于函数 y = ( x ) ，若x 和y 长度都是nb i t s ，则需要一个2 n 的r o m 。这种方法适用于 较小，如对于双精度数，= 6 4 ，实质上无法采用这种方法实现。 2 、多项式拟合 对于y = e 。，则可以采用t a y l o r 多项式，如果x 是一个非常小的数，则这个多 项式收敛速度很快，但是，对于一个接近于1 的参数，则这个多项式需要很长的 步骤才能收敛。并且，其硬件实现也比较复杂，因为对于不同的超越函数，需要 不同的硬件来分别实现。 3 、基于查找表的多项式拟合法 这是一种把查找表和多项式拟合结合到一起的算法，即基于查找表的多项式 拟合法，但是这种算法实现的芯片面积代价比较大。 4 、d i g i t - b y - d i g i t 算法 硕士学位论文第一章绪论 d i g i t b y d i g i t 算法主要是基于迭代，通过移位和加法运算来实现超越函数的 计算，这种算法的主要缺点是较慢的线性收敛速度。 5 、c o r d i c 算法 c o r d i c 算法是一种基于坐标旋转的数字计算机算法，作为一种高效的硬件 算法，在理论上已经被证明可以用于实现三角函数运算【2 】。随着半导体技术的飞 速发展，f p g a 芯片的规模越来越大，运算速度越来越快，使得该算法在电路硬 件实现中呈现出越来越高的应用价值。 1 3c o r dlc 算法研究现状 1 3 1c o r d i c 算法的起源、应用 c o r d i c 算法是j v o i d e r 1 】等人于1 9 5 9 年在美国航空控制系统的设计中提出 来的，它是一种用于计算一些常用的基本运算函数和算术操作的循环迭代算法， 其基本思想是用一系列只与运算基数相关的角度的不断偏摆从而逼近所需旋转 的角度。从广义上讲这是一个数值性计算逼近的方法，由于这些固定的角度只与 计算的基数有关，只需要进行移位和加法运算。为了扩展可解决的基本函数个数， 1 9 7 1 年j w a l t h e r 提出了统- - c o r d i c 算法( t h eu n i f i e dc o r d i ca l g o r i t h m s ) 睇j ，把 圆周旋转、双曲旋转和直线旋转统一到同一个c o r d i c 迭代方程里，这就为设计 一个通用的c o r d i c 芯片通过选择不同的m 值实现多种不同的计算功能提供了坚 实的理论基础。 c o r d i c 算法可计算的函数包括乘、除、平方根、正弦、余弦、反正切、向 量旋转( 即复数乘法) 、坐标转换、指数运算以及f f t 、d h t 、d f t 、d c t 、d s t 等技术函数【3 罐】。以往完成这些变换通过两类方法：第一类是专用硬件电路或专 用数字信号处理器，通常采用比较或查表的方法，这类方法一般来说运算结构精 度低、芯片面积大，更为关键的是设计的灵活性差；第二类则采用软件编程的方 法，由于这些变换均是非线性变换，完成一次运算需要运行较多的程序，运算速 度较低。上述两种方法在精度、速度、简单性和效率方面都不能兼顾，难以满足 现代高速实时信号处理的要求。 相比之下，c o r d i c 算法则很好地兼顾了这几方面，这种算法实现简单，只 有移位与加法运算，非常适合于v l s i 的实现【9 。1 。因此，c o r d i c 算法越来越受 到研究与应用人员的重视，更加展示出广泛的应用发展前景。在传统的硬件算法 设计中，乘、除等基本数学函数运算是一种既耗时又占用面积大的运算，甚至有 时是难以实现的，c o r d i c 算法正是为解决这种问题而产生的。它从算法本身入 手，将其分解成为一些简单的且在硬件中容易实现的基本算法，如加法、移位等， 2 硕士学位论文第一章绪论 因此使得这些算法在硬件上可以得到很好的实现。又由于该算法是一种规则化的 算法，它满足了硬件对算法的模块化、规则化的要求，因此c o r d i c 算法可以充 分发挥硬件的优势，利用硬件的资源，从而实现硬件与算法相结合的一种优化方 案。 1 3 2c o r d i c 算法的国内外发展状况 c o r d i c 算法的原始思想一经提出，就受到了人们的普遍关注，4 0 多年来人 们不断地对其进行探索研究，并提出了各种改进算法和优化方案以适应各种不同 的需求【1 2 d5 。 1 9 7 1 年j w a l t h e r 提出了统一c o r d i c 算法，1 9 8 0 年g e n el h a v i l a n d 和 a l a t u s z y n s k i 研制成功的算术处理器c a p 【6 】执行一组三角运算需要约4 0 p s ，1 9 8 7 年m c o n s n a r d 和j m u l l e r 等研制了基于c o r d i c 的算术处理器f e l i n 。 1 9 9 3 年法 c h r i s t o p h em a z e n c 等人提出计算反正弦和反余弦的c o r d i c 结构 1 7 1 o 2 0 0 4 年t s o b i n gj u a n g 等又提出了一种改进的并行的c o r d i c 算法【l0 1 ，大大 提高了c o r d i c 算法的迭代速度，并且达到了很高的精度。 国内对c o r d i c 算法的研究是近年来才形成一定规模，中国科学院声学所的 胡国荣( 1 9 9 1 年) ，成都电子科技大学龚耀寰【1 4 】( 1 9 9 7 年) 、北京理工大学李 滔、石晶林和韩月秋1 5 , 1 6 1 ( 1 9 9 9 年) 、南京大学谈宜育和卞文兵【1 7 】( 2 0 0 1 年) 、 电子科技大学的甘露【1 8 l ( 2 0 0 4 年) 、阎啸和秦开掣1 9 】( 2 0 0 6 年) 及西北工业大 学的丘伟和刘诗斌1 2 0 】( 2 0 0 6 年) 等相继对c o r d i c 算法的应用和实现提出了许多 运算算法和结构，都在不同程度上提高了原始c o r d i c 算法的速度和效率，并拓 展了c o r d i c 算法的应用范围。 可以看出，c o r d i c 算法的发展趋势是高进制、高精度、高吞吐率。 1 4 硬件实现方式f p g a 随着微电子技术的发展，设计与制造集成电路的任务已不完全由半导体厂商 来独立承担。系统设计师们更愿意自己设计专用集成电路( a s i c ) 芯片，而且希望 a s i c 的设计周期尽可能短，最好在实验室里就设计出合适的a s i c 芯片，并且立 即投入实际应用，因而出现了现场可编程逻辑器件( f p l d ) ，其中应用最广泛的 当属现场可编程门阵歹i j ( f p g a ) 和复杂可编程逻辑器件( c p l d ) 。 大规模可编程逻辑器件c p l d 和f p g a 是当今应用最广泛的两类可编程专用 集成电路，f p g a 兼有串、并行工作方式和高集成度、高速、高可靠性等特点， 时钟延时可达到纳秒级，在基于芯片的设计中可以减少芯片数量，缩小系统体积， 3 硕士学位论文第一章绪论 降低能源消耗，提高系统的性能指标和可靠性。正是由于这些优点，f p g a 在数 字信号处理领域有广阔的应用前景。电子设计工程师利用它可以在办公室或实验 室里设计出所需的专用集成电路。此外，可编程逻辑器件还具有静态可重复编程 和动态在系统重构的特性，使得硬件的功能可以像软件一样通过编程来修改，极 大地提高了电子系统设计的灵活性和通用性。由于具备上述两方面的特点，c p l d 和f p g a 受到了世界范围内广大电子设计工程师们的普遍欢迎，f p g a 在数字信 号处理领域中的应用日益广泛。 1 5c o r dic 算法的问题与优化 1 5 1c o r d i c 算法存在的主要问题 l 、实现c o r d i c 算法可以使用一个算法单元，将输出反馈到输入反复迭代 计算。这种结构节省硬件资源，可以实现算法精度可调，但是速度很慢。由n 个算法单元组成的n 级流水线结构，可以大大提高系统速度，每增加一次迭代精 度提高一位，理论上可以通过增加迭代次数无限制提高精度，但是精度受流水线 级数的限制，要提高精度必须增加流水线级数。随着流水线级数的增加，速度又 会降下来，而且还会增加系统的面积，很难解决速度、面积、精度之间的关系。 2 、c o r d i c 算法在每一级迭代中都需要在r o m 表中取出事先预存好的 a r c t a n ( 2 一) 值。但是随着运算字长的扩大，r o m 表的容量成指数增长，系统所 占资源急剧加大，每次访问r o m 表也会降低系统速度f 2 m 3 1 。 3 、传统c o r d i c 算法的旋转角度覆盖的角度只有一9 9 8 8 。+ 9 9 8 8 。，为了 确保c o r d i c 算法收敛，其所有旋转角度之和必须大于实际需要旋转的角度， 因此，无法覆盖整个周期0 。o s3 6 0 。 1 5 2c o r d i c 算法的优化 由于c o r d i c 算法本身的局限性，曾提出过多种改进和优化措施【2 4 。3 3 1 ，主要 技术总结如下： 1 、增加多次i = 0 的迭代，使得c o r d i c 算法旋转覆盖的角度范围达到一个 完整的周期【0 ，2 n 】； 2 、跳过不必要的旋转。跳过输入相位值中为0 的位对应的旋转，减少了迭代 次数，并且只有正向旋转。对于特殊角度，例如n - 4 ，通过很少次数的旋转就已 经达到该角度，即可不再进行后面的旋转； 3 、对旋转角度进行编码来减少旋转次数： 4 硕士学位论文第一章绪论 4 、用几位最高有效数字来决定旋转的方向。 以上4 种技术主要针对c o r d i c 算法角度覆盖范围和运算速度方面的局限 性对其进行改进，有效地优化了传统的c o r d i c 算法。但是，每种改进方法也 同时引入了一些新的问题，例如：方法l 中校正因子为变量，很难确定其值。方 法2 不能显著的减少迭代次数；方法3 、4 能有效的减少迭代次数，但是会引起 比例因子的变化。 鉴于以上分析，本文提出了进一步的优化措施。 1 6 论文结构安排 本文共分六章，简要介绍各章的主要内容： 第一章，绪论。介绍了三角函数在现代工程计算中的重要性及硬件实现三 角函数运算的c o i i c 算法，概述了c o r d i c 算法的起源、发展、应用及优缺 点。 第二章，c o r d i c 算法的基本原理。主要介绍c o r d i c 算法的圆周系统是 如何实现正弦和余弦两个函数，c o r d i c 算法通过参数m 将三种系统统一起来， 如何选择不同的初始值来实现不同的函数。 第三章c o r d i c 算法的优化。本章是本文的重点部分，详细地介绍了传统 c o r d i c 算法的优化措施，解决了传统方法的几个局限性。 第四章，改进的c o i m i c 算法的f p g a 整体设计。概述面向f p g a 的开发 流程及e d a 工具，介绍本文采用的设计方法及硬件开发平台，详细地阐述了改 进c o r d i c 算法的f p g a 整体设计结构及模块划分，简要介绍各子模块的主要 功能。 第五章，c o r d i c 算法优化后的f p g a 模块设计与仿真。本章也是本文的 重点部分，详尽地介绍了改进c o r d i c 算法各个模块的实现方法，并给出部分 仿真结果。 第六章，总结与展望。对本文的研究工作进行了总结，提出了还需要改进的 地方，展望本课题研究的前景。 5 硕上学位论文第二章传统c o r d i c 算法基本原理 第二章传统c o r d i c 算法基本原理 传统c o r d i c 算法根据不同的旋转轨迹分成圆周系统、线性系统、双曲系 统；每一系统又有旋转模式和向量模式两种。本章以圆周系统为对象，介绍 c o r d i c 算法的基本原理，是下一章提出优化措施的理论铺垫。 2 1c o r dic 算法 设一向量( x ；，y ：) ，旋转秒角后得新向量( x ；，“) ，如图2 - 1 所示，根据坐标变 换规则，两者有如下关系： - c 。s i s , 秒, o j - l l 少x ；j = c 傩臼 二口 0 一t a , , o - i x ； ，儿刊 图2 1c o r d i c 算法原理图 ( 2 - 1 ) 一l 将旋转角秒分解为n 个递减的小旋转角只之和，即0 = 万，秒j ，其中幺o ， 幺顺时针旋转时点= 一1 ，逆时针旋转时4 = 1 。对于每次4 、的旋转有 再令 ： = c 。s p 谚。二谚一喀t a n 谚 ，i = 0 , 1 , 2 , - - - , n - 1 , c 2 - 2 ， 6 硕士学位论文第二章传统c o r d i c 算法基本原理 只2 a r c t a n ( 2 “，卢o l ，2 ，一1 ( 2 3 ) 即t 粕幺= 2 ，这时 c 。s 够2 志2 了亍告，f = 。j ，2 ，一 ( 2 4 ) ( 2 - 2 ) 式可改写为 盼c o s 协，一州嘲i = 0 , 1 , 2 , - - , n - 1 , p 5 ， 于是，向量( x ：，y ：) 经过n 步旋转之后到达向量( x ；，以) ，可表示为 要 = ( 垂c 。s 谚 4 ：一，一气2 一 委 = k ( 磬 巧三一，一t 2 一 要 ， c 2 - 6 ， 其中k 为模校正因子，且有 k = 专= 尊c o s 谚= 尊志 p 7 ， 当n 一0 0 时，有k - - o 6 0 7 2 5 3 ，故k 可以看做一个常量。 这样，向量旋转式( 2 1 ) 的计算问题转换为式( 2 7 ) 的计算以及如下迭代 运算 。一h l 爿，- 4 y , 乏一i ，础，l ，2 ，_ 1 ，( 2 - 8 ) y l “= y lj r4 x t 2 1 其中，( x o ，y 。) = ( x ；，“) ，而( h ，y ) = 尸( x ：，少：) 。由于式( 2 7 ) 是一个常数，可 以预先计算，故实际上只需计算式( 2 8 ) 。 式( 2 8 ) 中仅含移位、加减法算法，特别适合硬件实现，为硬件快速计算三 角函数提供了一种新的算法，这就是提出c o r d i c 算法的初衷。迭代计算时，为 了跟踪已经旋转的角度，还需引入一个新变量，定义为 z = z 。一点a r c t a n ( 2 一) ，i = 0 , 1 ，2 ，n 一1 ，( 2 9 ) 表示第f 次旋转后剩余未旋转角度。上式中a r c t a n ( 2 一) 可以预先求出，保存在寄存 器中。式( 2 8 ) 与式( 2 9 ) 构成了c o r d i c 算法的基本迭代关系。 根据谚取值的判读方式，c o r d i c 算法又分为旋转模式和向量模式。 硕十学位论文第二章传统c o r d i c 算法基本原理 2 1 1 旋转模式 设初始旋转的角度为铂= 秒，经过次旋转后，使得z = o ，这时 谚= ：糍囊i = 0 , 1 , 2 , - - , n - 1 , 这样的模式称为旋转模式。由式( 2 8 ) 与式( 2 9 ) 得 x = p 【石oc o s z o y os i n z o 】 y = p 【y oc o s z o + 工o s i nz o 】 z n2 0 如果取x o = 1 e ，j ，o = o ，z o = 0 ，则有 ( 2 一l o ) ( 2 - 1 1 ) - - - p ( x oc o s z 0 - y os i nz o ) 、= c o s 0 ( 2 1 2 ) y p ( y oc o s z o + x os i nz 0 ) = s i n0 、 由此可见，c o r d i c 算法的旋转模式可以用来计算一个输入角的正弦和余弦。 2 1 2 向量模式 设初始旋转的角度为z 。= 口，经过次旋转后，使得峨= o ，这时 耻 ：渤三三，i = 0 , 1 , 2 , - - - , n - 1 , 陋 这样的模式称为向量模式。由式( 2 - 8 ) 与式( 2 9 ) 得 x n ：p 蹶 y = 0 ( 2 - 1 4 ) z n = 8 + a r c t a n ( y o x o 、) 如果取0 = 0 ，则有 x = 尸厢忑 ( 2 一1 5 ) z j = a r c t a n ( y ox o ) 由此可见，c o r d i c 算法的向量模式可以用来计算向量( x 。，y 。) 的长度和反 正切，很显然，也可以将直角坐标转换为极坐标，还能进行开方运算。 2 2c o r dlc 算法统一结构 为了能计算更多的基本函数，1 9 7 1 年，j s w a l t h e r 提出了统一的c o r d i c 8 硕士学位论文 第二章传统c o r d i c 算法基奉原理 算法，引入参数历表示工作模式：聊= 1 为圆周系统、m = 0 为线性系统、m - - 一l 为双曲系统) ，将三种系统统一到同一个c o r d i c 迭代方程中【2 5 。0 1 ，表示为 x l “= x i - m 4 y , 2 一l y “l = 少j + 点一2 一，= 0 , 1 ，2 ，n 一1 ， z l n2z i 一6 i e i ( 2 - 1 6 ) i a r c t a n 2 ，m = l 其中，谚= 2 ，m = o 。选择不同参数可得到不同的计算结果，如表2 一l 所 l a r t a n h 2 ，m = 一1 表2 1c o r d i c 算法的参数选择及结果 其中心= 县n - i 丽i ，吒= 尝赤。 2 3c o r d i c 算法实现的结构 2 3 1 反馈结构 c o r d i c 迭代算法的一种直接实现方式是反馈结构【3 4 。4 0 1 ，此结构只设计一级 c o r d i c 运算迭代单元，然后在系统时钟的驱动下，将本级的输出作为本级的输 入，通过同一级迭代完成运算。这种方法硬件开销很小，但控制比较复杂，而且 完成一次c o r d i c 运算需要多个时钟周期，运算速度较慢不利于数据的高速实时 9 硕上学位论文第二章传统c o r d i c 算法基本原理 处理，结构图如2 1 所示。 2 3 2 流水线结构 c o r d i c 迭代算法的另一种实现方式是流水线结构p 卜) u j ，每一级c o r d i c 迭代运算都使用单独的一套运算单元，它的处理速度非常快，流水线填满之后每 个时钟周期就会计算出一组结果，为数据实现高速实时处理提供了前提。每一级 实现的功能是根据式( 2 8 ) 和式( 2 9 ) 进行一次迭代，移位的位数等于当前的迭代级 数，加减法选择由该级中z 的最高位( 符号位) 决定，得到下一级的x 、y 和z 的 值。经过级流水线运算后，z 的值变为0 ，x 和y 的值则为初始值的余弦和 正弦值。每一级电路结构主要包括2 个移位器和3 个加( 减) 法器，级与级之间直 接相连，不需要额外的寄存器。p 的值为a r c t a n ( 2 一) ，可将该小数转换为二进制数 后，存储于存储单元中，为每一级流水线提供查找表，结构图如2 2 所示。 x xz i 图2 - 1c o r d i c 算法反馈结构图 虽然这种结构大大提高系统运算速度，但是精度受流水线级数的限制，要提 高精度必须增加流水线级数，此时硬件资源消耗又提高了。 因此，在采用适当的流水线级数的同时还要兼顾速度和精度的要求。通过对 两种结构的对比，由于本课题对处理速度要求较高，流水线结构的实现方式更适 合本设计。 1 0 硕士学位论文第二章传统c o r d i c 算法基本原理 y 0 两 图2 2c o r d i c 算法流水线结构图 硕士学位论文第三章c o r d i c 算法的优化措施 第三章c o r dic 算法的优化措施 本章以旋转角9 为研究对象，深入分析c o r d i c 算法中存在的问题，针对 这些问题从理论上提出了相应的优化措施。 3 1 迭代次数与数据精度的关系 由于旋转角度z ( 0sz 2 j r ) 在迭代过程中可能出现负值，为了方便，可用b 位二进制补码表示，角度最小值为2 一。要使得最后一次旋转有意义，最后一次旋 转角度必须小于这个最小值。由于这些旋转角度值都存储在r o m 表中，所以要 求表中存储的最小角度小于2 。设r o m 表中也用a 位二进制补码数存储表示角 度，则最小角度为2 ，要求a b 。 已知r o m 表中存储的角度序列是a r c t a n ( 2 叫+ 1 ) ，i = 0 , 1 ，2 ，n 一1 ，n 为c o r d i c 算法的运算字长。当i 较大时，a r c t a n ( 2 1 “) 2 一”，故 a r c t a n ( 2 一“) 2 一“2 4( 3 一1 ) 即 nal(3-2) 因此，对于运算字长为1 6 位的c o r d i c 算法，至少需要1 5 级流水线才能够 达到所需要的精度。 3 2c o r d i c 算法的局限性 3 2 1 存储容量 对于刀级流水线，o o 到眈一。为i 从0 到n 一1 的旋转角度p = a r c t a n ( 2 1 ) ， f = 0 ，l ，2 ，n 一1 。通常将p 值提前算出，作为每一级流水线单元的输入，预先存储 在r o m 表中。表3 一l 和表3 - 2 分别给出了1 6 位和3 2 位表示的9 值，由于谚参加 有符号运算，故均采用补码表示。最高l 位为符号位，低1 5 位和低3 l 位分别表 硕上学位论文第三章c o r d i c 算法的优化措施 示小数部分。从这两个表给出的数据可知，随着流水线级数的增加，r o m 表的容 量成指数增长，增加了系统的面积。 表3 1r o m 表中的数据 3 2 2 运算速度 从图2 2 可以看出，c o r d i c 算法完成一次运算必须使用多次迭代，而每 次迭代的方向都必须根据上一次迭代的结果确定。迭代次数越多，方向判断的次 1 3 硕上学位论文第三章c o r d i c 算法的优化措施 数也越多，影响了运算速度。 表3 - 2r o m 表中的数据 反正切弧度值对应二进制数 吼。 幺， 氏 a r c t a n ( 2 0 ) 0 7 8 5 3 9 8 1 6 3 4 0 1 1 0 0 1 0 0 l 0 0 0 0 1 111 11 0 1 1 0 1 0 1 0 l o 0 0 1 a r c t a n ( 2 。1 ) 0 4 6 3 6 4 7 6 0 9 0 0 0 1i1 0 11 0 1 0 11 0 0 0 1 1 0 0 111 0 0 0 0 0 1 0 1 0 a r c t a n ( 2 2 ) 0 2 4 4 9 7 8 6 6 3 1 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 b 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 a r c t a n ( 2 3 ) o 1 2 4 3 5 4 9 9 4 50 0 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 a r c t a n ( 2 一) 0 0 6 2 4 18 810 0 a r c t a n ( 2 5 ) 0 0 3 1 2 3 9 8 3 3 4 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 a r c t a n ( 2 “) 0 0 1 5 6 2 3 7 2 8 6 0 0 0 0 0 0 0 1111 111 1111 11 0 1 0 1 0 1 0 1 0 1 0 1 a r c t a n ( 2 。7 ) 0 0 0 7 8 12 3 4 11 a r c t a n ( 2 。8 ) 0 0 0 3 9 0 6 2 3 0 1 a r c t a n ( 2 巧) 0 0 0 19 5 312 2 5 a r c t a n ( 2 。1 0 ) 0 0 0 0 9 7 6 5 6 2 2 a r c t a n ( 2 1 ) 0 0 0 0 4 8 8 2 8 1 2 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 a r c t a n ( 2 2 8 ) 0 0 0 0 0 0 0 0 0 3 7 a r c t a n ( 2 2 9 ) 0 0 0 0 0 0 0 0 0 1 9 a r c t a n ( 2 3 0 ) 0 0 0 0 0 0 0 0 0 9 3 2 3 角度范围 假设迭代次数为n ，按照j w a t l h e r l 2 1 提出的迭代序列刀= 0 , 1 ，2 ，3 ，n 一1 ，则旋 1 4 锦 夙 易 级 织 良 铱 易 钛 编 印 郎 硕士学位论文 第三章c o r d i c 算法的优化措旌 转角度范围为： - 1n - 1 - z a r c t a n ( 2 1 ) 秒a r c t a n ( 2 1 ) n = 0n = 0 根据上式可以算出给定n 值所对应的旋转角度变化范围，如表3 3 所示。 表3 3 给定n 值所对应的旋转角度变化范围 ( 3 3 ) 从上表可以看出，旋转角度的范围最大为一9 9 8 8 。0 9 9 8 8 。，无法达到 一个完整的周期0 。0 3 6 0 。为了确保c o r d i c 算法的收敛，旋转角度之和必 须大于实际需要旋转的角度，必须对输入的角度进行预处理。 针对以上提到的几个问题将通过改进c o r d i c 算法解决。 3 3c o r dic 算法的优化 3 3 1 优化反正切函数表 c o r d i c 算法的式( 2 9 ) 需用到反正切函数，通常的方法是预先计算出相 应数据列成表2 1 或表2 2 存入r o m 中，占用资源也影响速度。如果能在保证 精度前提下减少整个迭代过程的次数，则能有效提高运算速度。通过对旋转角度 值谚的研究，发现这种可能性是存在的。 利用a r c t a n ( x ) 函数的泰勒级数 a r c t a n c x ，= j 一手+ 等一号+ 萼一鲁，h - ， 可将谚= a r c t a n ( 2 。) ，i = 1 ，2 ，n 一1 展开成级数 ( 3 4 ) 硕士学位论文第三章c o r d i c 算法的优化措施 a r c t 卸( 2 - j ) _ 2 - 。一三矿+ 三2 - 5 _ 专矿+ 万1 2 - 9 ；1 1 i ，( 3 - 5 ) 显然，a r c t a n ( 2 一) 与2 一之差随着迭代次数i 增加而迅速减小。若从第m 级迭代 开始用2 1 代替a r c t a n ( 2 1 ) 所产生的误差对最终计算结果准确性没有影响，则此时 迭代计算中的查r o m 表的过程可以用移位运算取代，即可加快计算速度，也能 减少占用r o m 资源。理论的关键是用2 1 代替a r c t a n ( 2 1 ) 时产生的误差可以忽略 不计，即，对于位精度的c o r d i c 算法，m 应该满足 2 一”一a r c t a n ( 2 一”) l 2 一 即要求 b 2 勘一! 2 - 5 m + ! 2 _ 锄12 - 9 m + 土2 川m j 2 一 1 3 579l l l 成立。因 三2 一，m 一! 2 一s m + ! 2 一，m 一! 2 一，m + 土2 一t 伽 ! 2 一，m 35791 13 故对任意的m ，0 m n ，若 一1 2 - 3 ” 2 - n 3 则式( 3 6 ) 成立，这时 所阻n - l o g ；) 。| - 式中p l m m m 掌的最大整数。该关系式的正确性可验证如下： ( 3 6 ) ( 3 - 7 ) ( 3 8 ) ( 3 - 9 ) ( 3 一i o ) 1 5 若n = 1 5 ，可以求出聊= 5 ，另一方面，由表3 - 1 可知，a r c t a n ( 2 。5 ) - - z 2 ， t = 6 故有i2 一a r c t a n ( 2 - 5 ) i - 2 q 6 2 - 1 5 ；若n = 3 1 ，可以求出m = 1 0 ，由表3 - 2 知， 3 l a r c t a n ( 2 。) = 2 一，故有1 2 - l 。- a r c t a n ( 2 - 1 0 ) | - 2 - 3 2 2 - 3 1 。 ，- l l 可见，对于c o r d i c 算法，当迭代到第m 级流水线时，即当i m 时，若用2 一 代替a r c t a n ( 2 1 ) ，不再需要从r o m 表中查找a r c t a n ( 2 一) 值，节省了访问r o m 的时 间，提高了计算速度，还能减少2 3 的存储表2 1 或表2 2 数据的r o m 资源。 1 6 硕士学位论文 第三章c o r d i c 算法的优化措旌 3 3 2 简化校正因子 将式( 2 4 ) 展成泰勒级数 删= 去= 1 2 。2 卜1 + 3 2 埘。3 + ，i = 0 , 1 ，, - - - , n l ， ( 3 1 1 ) 、1 + 2 叫 、 i c o s 秒t 一i i = | _ 2 2 卜1 + 3 2 前。+ 2 卜。，