【doc】一种快速迭代的坐标旋转机结构

【doc】一种快速迭代的坐标旋转机结构 一种快速迭代的坐标旋转机结构 2002年第8期微电子学与计算机 一 种快速迭代的坐标旋转机结构 A13.FastIterativeCORDICArchitecture 西安微电子技术研究所梁政沈绪榜(西安710054) 摘要:最简单超越函数硬件实现方法是基于移位加的坐标旋转机算法CORDIC,这种方法的结构简单规则, 能以固定结构实现多种超越函数的计算.文章介绍了这种算法的工作方式和具体应用,引入冗余数计算以减少 单次迭代的延迟.同时讨论了冗余计算结构所需的尺度因子补偿,并提出了一种减小迭代次数的混合基结构. 关键词:计算机算术,初等函数,坐标旋转机 1引言 FPU中初等函数最常用的实现方法是多项式 迭代和移位加迭代.CORDIC算法迭代收敛时无需 乘法,占用面积小,并且逻辑实现时结构规则,仅使 用单一的结构,即可完成了多种核心函数的近似, 具有广泛的应用前景. 但CORDIC算法是线性按位收敛,关于这种算 法已有的应用仅限于计算器芯片以及INTEL80X87 系列协处理器.为了扩展CORDIC在高速系统中的 应用,本文在其迭代中引入了冗余数计算,通过减 小单次迭代的延迟来减小总延迟,同时对这种快速 算法的结构作了一定改进,可以明显减小总迭代次 数,提高初等函数计算速度. 2坐标旋转机CORDIC算法 CORDIC算法最早由VOLDERA提出,它属于 非还原Nonrestoring算法.Walther将CORDIC算法 拓展至双曲坐标,从而能够计算指数函数和对数函 数.通用CORDIC算法迭代公式为: l:mdny {Y+l=Y+dX2,'(1) 【Z+lZ一e() 式(1)中d,m,e的取值见 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 1,盯(n)的取值见 表2.在圆坐标中,常系数K=n.计算三n:0 角函数时,可取迭代初始值Xo=1/K,Yo=0,Zo=0. 双曲坐标的常系数为K,_n=,如果需 n:0 计算双曲函数sinh(0)与cosh(0),则迭代初始值为 Xl=1/K,Yl=0,Zl=0;从而函数e可由coshx与 sinhx获得.如要计算lnx,可作如下变换: In(x)=2tanh()(2) 在CORDIC中,还可以完成乘法,除法和平方根 的实现;但CORDIC收敛速度较慢;不如应用 BOOTH乘法和SRT算法. CORDIC算法不是最快速的计算初等函数的方 法,但其优点是以简单的结构和操作实现绝大多数 初等函数的迭代逼近,并且有利于硬件的实现. 表2CORDIC算法中(n)的取值 圆坐标(n)=n 直线坐标(n)=n (n)=n—k,双曲坐标 其中k为满足3"+2k一1?2n的最大髂数 3冗余迭代计算 CORDIC算法中基本操作为加法与移位,其中 表1CORDIC算法中的各种计算模式 坐标类型mekd=sign(z)旋转模式d=一sign(y)矢量模式 Xn--~K(xocoszo—yosinzo)x—+KY8 圆坐标larctan(2)y.----~K(yocoszo+xosinzo)v—0 z—0V0z—z0一arctan— X0 Xn—+X0 Xn—+X0 直线坐标02—yn—'y0+XOZOv—0 V0 z—0Zn—+Z0一一 X0 x_+K(XlCoShzl+ysinhz~)x—+KVx7Y} 双曲坐标一ltanh一2—y_+K(ylcoshzl+xsinhz~)yn_+0 z—0zn_+zl—tanh—l卫 XI 收稿日期:2002—02—26 12微电子学与计算机2002年第8期 加法器时延最大.为减小延迟,迭代中可采用冗余 数(进位存储数CarrySaveNumber,或带符号数位数 SignedDigitNumber)表示中间结果;这样,在迭代中 出现的加法操作可以由冗余加法器完成,没有进位 延迟. 但d的选择需确定冗余数符号,仍然无法回避 可能出现的全长度进位延迟.为了减小这种进位延 迟,还必须对方向因子引入冗余,使di=0,1外,还 允许d.=一1.限于篇幅,本文直接给出方向因子选 择函数. 3.1符号数位数实现方式 假设以基2符号数位表征Z,且z为2"z自小 数点后第一位的截断值.因lz一2"zls1/2,则: f一1,当z<0 d={0,当Zn=0(3) 【1,当z>0 3.2进位存储数实现方式 因此时Os2"Z一zs1,可选为: f一1,当z<1/2 d={0,当z=1/2(4) 【1,当Zn>1/2 冗余数方法诚然能带来快速计算的优势,但因 d为0的次数不是固定的,尺度因子K/K将不再 为常数.必须对K/K值作补偿处理,否则CORDIC 冗余算法无法直接应用于函数的计算中.最常用的方法是双旋转算法. 这种算法的思想由Delosme提出…,是两次执 行&arctan2角度旋转.假设是圆坐标中的旋转模 式,此时的分解基常数不再是e=arctan2一,而应是 e=2arctan2: ?当d=1时,两次执行arctan2…角度旋转; ?当cL=一1时,两次执行一arctan2-n-I;角度旋转; ?当d=0时,首先执行+arctan2…的旋转, 再执行一arctan2…的旋转. 则双旋转迭代公式为: Ix+l:x一d2—"y+(1—2d)2一"一x {x+:x一d2—"y+(1—2dJ2一"一x(5)【 z+:z一dw,:z一2darctan2一n一 此时新尺度因子: K…=n(1+2-2i-2)=1.355909673… 4混合基CORDIC 由式(5)中可以看到,x与Y的冗余数计算由 三个操作数构成,可由(6,2)CSA加法器实现;当 i>(n+1)/2后,n位迭代的尺度因子K…(n)的计 算值在工作精度范围内不受影响.所以当迭代序数 i>(n+1)/2后,双旋转迭代计算可化简为与非冗 余时的迭代算法相同.在结构设计时,前(i+1)/2 次迭代计算采用双旋转迭代公式,而后(i+1)/2次 迭代采用非冗余迭代. 至此所讨论快速移位加算法只能减小单次迭 代的延迟,迭代的总次数依然为工作精度的位数. 还可通过增加基值的方法,减少CORDIC所需迭代 次数,但相应地引入了两个新问题:一个是迭代中 方向因子选择函数的复杂度增加;另一个是尺度因 子K不再为常数,需要在每次CORDIC计算中现场 求取. 为回避上述问题,一方面我们选择迭代基值为 4,以简化选择函数;另一方面是尽力使K值保持为 常数. 双旋转CORDIC算法中,K值在(n+1)/2次 迭代后将在计算精度内保持常数.从而可以考虑采 用混合基的方法,在前(n+1)/2次迭代中采用基2 的双旋转算法,而在后续的迭代中可以采用基4的 算法;这种改进措施可以使迭代次数减少1/4. 基4的CORDIC迭代中需要选择方向因子d 值以及d选择函数.应用文献[2】中的方法,d的集 合为{0,?2,?4}.方向因子d由z一决定:首先将 移位后的余数4~z一的高8位(包含6位整数位和2 位小数位)转换为非冗余格式,取转换后的6位整 数值为T,则依据表3可根据T决定方向因子d. 例如:zz=[0.0011010111…】sD2,移位后的值 为4zz=[001101.O111…】,首先将4zz的高8位 转换为非冗余数43zz=[QQQ!:Q111…】soz,并获 Tz为[000100】z=4,相应的d,为4. 因为每次迭代对x,Y的放大尺度为 K;=,Jl+dri,如果希望在迭代中进行尺度因子 : 的补偿,即 X=(X一l—dr—Y一1)/K y:(y一dnr-nXn-1)/K(6) 对1/K作Taylor级数展开,上两式可重写为: 表3基4时方向因子的选择函数 2 — 2(下转第60页) 微电子学与计算机2002年第8期 还有一些方面可以进一步深入研究,比如,如何降 低晶闸管的的功耗,如何进一步提高电路翻转速度 等.用横向晶闸管构建ESD保护电路是提高集成电 路静电放电可靠性的一种有效方法. 15 —10 《 量 一5 0 ,, > 0 050100150(ns) 图6(a) 050 图6(b) 参考文献 【1]w格尔拉赫.晶闸管.北京:机械工业出版社,1984 【2] 【3] 【4] 陈星弼,唐茂成.晶体管原理.成都:国防工业出版社, 1981. MingDouKer.ElectrostaticDischargeProtectionCircuitsin CMOSIC'SUsingtheLateralSCRDevice:AnOverview. IEEE1998. RRenuka.JeyanthiRajesh.VKHaritharan&S.V.K. Shastry.SimulationoftheResponseofExternalESDPro— tectionCircuitsforICs.IEEE2000. LIMin,DAIQing—yuan(MicroelectronicTechnologyCenterof ShanghaiJiaoTongUniversity,Shanghai200030) Abstract:AnESDprotectionstructureformedwithlateralSCR isproposed.Equivalentcircuitandlayoutarealsogiven.The structureiSanalyzedandsimulatemodelofthisstructureiSbuilt inPSPICE.Afteral1thesehavebeendone.thestructureiSsim. ulatedwithEADsoftwaretovalidateitsfunctionalityandrelia— bility. Keywords:ESD.SCR.PSPICE (上接第12页) x=x一l—d.r一,r一l一1/2?dr一"x一l +1/2?d3.r一r,r一l+3/8?d4r一rI)【一l Y=Y一l—dnr一"x一l一1/2?dr一,r一l, +1/2?d3.r一rI)【一1+3/8?d4r一r,r一l 如果目标精度为扩展双精度,则基4迭代12次 后,上式左边第3项后的计算可忽略不计.混合基 的算法结构分为三段:首先以双旋转作前22位迭 代,接着以式(7)作23至29次迭代,此后尺度因子 不受方向因子影响,故30至40位的迭代公式为: x=(x一1一d4,Y一1) v==(y一.——d4一nx一.)(8) 混合基算法的基值较低,结构依然比较简单, 有利于逻辑设计. 5结论 本文研究讨论了FPU中初等函数独立单元模 块的设计方法,函数指令应用频率最低,过分追求 速度而牺牲资源面积的方法并不可取.因此文中深 入研究了采用冗余数计算来加速CORDIC迭代,并 针对CORDIC算法提出了一种混合基的算法结构, 可显着改善迭代的速度和次数.这种硬件实现方法 占用资源面积比较小,并且结构规则简单,适合于 VLSI设计实现,具有一定应用价值. 【2】 参考文献 SFHsiao,JMDelosme.HouseholderCORDICAlgorithms. IEEETransactionsonComputers,August1995,44(8): 990—1o00. TAoki,HNogi,eta1.High—radixCORDICAlgorithmsfor VLSISignalProcessing.Proc.1997IEEEWorkshopon SignalProcessingSystems,November,1997:183,192. LIANGZheng,SHENXu?bang (Xi'anMicroelectronicTechnologyInstitute,Xi'an710054) Abstract:Thesimplestalgorithmoftranscendentalfunctionis CORDICalgorithmbasedonshiftandaddoperation.Thisunified simpleandregulararchitecture dentalfunctionsapproximation. canimplementmanytranscen— CORDICworkingmodeandap— plicationdetailwerepresentedinthispaper,inwhichtheredun— dantnumbertopresentthepartialresultwasappliedtoaccelerate thesingleiteration.Furthermorethenecessarycompensationfor redundantcalculationwasdiscussedandamodifiedhybrid—base architectureforreducingiterationcycleswasproposed. Keywords:Computerarithmetic,Elementaryfunction,CORDIC 梁政博士.研究方向为VLSI.