1、第28卷第3期 2008年3月電力自動化設備Electric Power Automation EquipmentMar.2008o基于牛頓迭代法的高精度快速開方算法張小嗚1,一,李永新1(1.南京理工大學機械工程學院,江蘇南京210094;2.江蘇工業學院計算機科學與x-4r-.Y_系,江蘇常州213164摘要:針對全波傅氏算法中的開平方運算較耗時影響微機保護瞬動性問題,提出一種選取接近定 點數開方真值的牛頓迭代初值的方法。該方法利用數字信號處理器(DSP的移位指令、256個單元 的查表技術和DSP的硬件乘法器,通過1次查表和1.2次乘法運算,就能快速確定迭代誤差小于 29的迭代初值。在TI

2、 DSP集成開發平臺上。運行牛頓迭代開平方匯編程序。運算結果表明:該算法 對范圍在00000004.0000H01FFFFFF.FFFFH的定點數抽樣開方運算,迭代次數均不大于3次,就 達到2娟以上迭代精度.且占用內存小。非常適合帶有硬件乘法器的嵌入式微處理器實現。關鍵詞:開平方;迭代;微機保護;DSP中圖分類號:TM 744文獻標識碼:A 文章編號:10066047(200803007503基于交流采樣的微機保護測量算法中最常用的 是并聯補償全波傅氏算法1】。該算法計算諧波幅值 時,要進行諧波實部平方和虛部平方的開平方運算。 因嵌入式微處理器無專門的開方指令。目前常見的開 平方算法主要有牛頓

3、迭代(Newton.Raphson算法21和逐位循環算法C3-6。在微處理器應用場合,通常用 牛頓迭代法實現開方運算。牛頓迭代法每次產生1個開方數.直到前后2次迭代的誤差小于希望的精 度為止。若取固定的迭代初值且被開方數較大時, 迭代非常慢。一般10次以上才能達到精度。若迭代 初值越接近開方結果,則迭代收斂的速度越快7.¨。 這里研究了定點數直接牛頓迭代開方初值的快 速選定算法,減少牛頓迭代次數,提高定點數牛頓迭 代開方結果的速度.使定點數開方牛頓迭代快速算 法能充分發揮定點CPU快速處理定點數的優勢。1被開方定點數數據格式定義微機保護系統測量的電流、功率等變化范圍較 大,為了達到較

4、高的牛頓迭代開方精度1.5X 10,設 置被開方定點數數據格式為8Byte,其中6Byte(即 3個字為整數部分,2Byte(即1個字為小數部分, 小數點默認位置如圖1所示。匡亟習望墮丑圈.區囹圖l被開方定點數數據格式Fig.1Data format of fixed-point number for evolution 因此,在牛頓迭代公式:X。l-(X。+A/X。/2中, A/X。用64位除以32位除法子程序運算,保證每次 產生的32位商中,小數始終保持16位,以便迭代結 收稿日期:20070306;修回日期:20070510 束條件滿足:占=lXn+l-X。I2。16(1 2牛頓迭代初值

5、選取新算法假設具有圖l數據格式的被開方數A最大為 1FF FFFF.FFFF H.用下列二進制通式表示:A=口。a,lalao.口一la一2口一m+l口一。 、(2 將式(2展開為以2為底的權展開和形式12】:A=口。×28+n一1x281+口lx21+口o×20+口一l×21+ a一2×22+nm+1×2一刖。1+口一m×2一肌 (3 其中,O乃24,1m16,口。=0或1,口。=0或l。將式(3中最高含1'的二進制位數n的權力作為 公因子提到公式最左邊.即在a。=1的情況下,有 A=2”×(1+口。1×

6、2-1+o】×24“+口o×2一“+口一1×21一“+口一2x2-2-n+口一,¨l×2-m+1-n+口一。×2“4 、/萬一=2n/2×(1+口。一lx21+口lx2-n+I+aox2咄+Q一1x2-I-n+口一2x2-2-n+口一。+l×2一”+1一”+口一。×2一”172(4 從公式(4可看出,、/丁的值由2個乘積項組 成,若牛頓迭代初值僅取第1項2n/2試驗表明,迭 代次數不大于5次.若考慮第l項2“/2與第2項的乘 積作為迭代初值,則迭代次數會進一步減少。但是, 第2項是一個開方運算。不能再用牛

7、頓迭代法計算, 可以用查表法解決開方問題。考慮最大的開方數 aM=1,則第2項的小數部分最大有23項,如果完 全把這些數E1.0,1.999的開方運算均采用查表求 解.則需要存放查表數據的內存字單元223=8M.不 僅占用內存資源太大,而且開方運算蛻變為完全查 表法,若用嵌入式系統實現,其性價比很差。考慮到 牛頓迭代初值選取較接近開方真值時,收斂速度較。 電力自動化設備 第28卷快.取小數部分的最高8位就能進一步加快收斂速 度.即第2項近似取值為V1+口。l×2-1+口。一s×28(7 其中,a。一。到a棚是最高含1的二進制位數乃 向右從高到低截取的8位。至此,提出牛頓迭代

8、初 值選定新算法的實現步驟。a.檢測被開方數A整數部分含l的最高位, 記錄該位的位長。記為n(從0開始計數。b.截取含1的最高位右邊的8位數,記為廠oc.將從a得到的含l的最高位的位長n除以 2所得商.該商數是該位以2為基底的權的開方數 的冪次方數,若該位長n(=2k是偶數,直接將該商 數作為2的冪次方數轉換成一個單字的二進制數, 即2;若該位長幾(=2k+1是奇數,則該商數作為2的冪次方數轉換成一個單字的二進制數后,再乘以 、/丁。即2kx、/丁的乘積取整為單字。正將從b得到的8位小數廠去查1.廠對應的開 方數表格,獲得1.廠的16位開方數,其中高8位整數, 低8位小數。e.將從d得到的開方

9、結果單字與從c得到的整 數單字相乘.得到32位乘積。該乘積就是牛頓迭代 開方較精確的迭代初值。注意:b截取含1的最高位右邊的8位時,若 位長不足8位,則應順序截取到被開方數的16位小 數部分。3牛頓迭代初值誤差分析牛頓迭代初值誤差6(截取誤差定義為6=(1+口plx21+ol×2一“+1+口ox24+口一l×214+ a一2×2-2-+4-+口一m+lx2一m+1咄+口一m×2一”卜81/2一 (1+口肛I×21+口肛8×28172X=l+21+28. Y=29+21“4則6=V霸了一、/可=(、/麗一、/iz1/2=、/i、/麗=(

10、1+Y/X1/2x= f1+y/(2x“2X=X+Y/2-Y2/(8X(9 其中,(I+Y/X1/2按泰勒級數展開,由于l,1, 故(I+Y/X忱一1+Y/(2X-YV(8X2代入式(9得到。 將式(9代人式(8,得到:4試驗結果(2x+y一2訂、/iaF1/2(8 開方的要求。 表l牛頓迭代初值選取新算法迭代次數試驗 Tab.1Iteration times and preeisions of 8cIuare root operation using initial value selection algorithm第3期 張小鳴,等:基于牛頓迭代法的高精度快速開方算法 啷 J5結語所介紹的

11、定點數開方新算法是一種結合256個 字單元查表和DSP硬件乘法器快速確定接近開方 真值的迭代初值的牛頓迭代開方算法。DSP芯片具 有專用的單周期查表指令TBLR、單周期16位乘法 指令MPYU等快速指令。使這種算法可充分利用 DSP的軟硬件資源,達到快速選取迭代初值的目的。 DSP仿真試驗表明:在所規定的開平方數值范圍內, 無論被開方數大小,迭代次數總是小于等于3次,就 能達到2一e以上的開方精度.比取固定初值的牛頓 迭代開方運算速度平均提高約3倍,且軟硬件開銷 很小.尤其適合帶有16位以上硬件乘法器的嵌入式 微處理器實現。可滿足微機保護中全波傅氏算法開 方運算的實時性要求。具有良好的工程應用

12、價值。參考文獻:1李晨,張杭,張愛民,等.一種能濾除衰減直流分量的新遞推離散 傅氏算法J.繼電器,2005,33(17:1720.LI Chen,ZHANG Hang,ZHANG Aimin,et a1.A recursive dis crete Fourier algorithm for filtering decaying DC componentJ. Relay.2005,33(17:1720.2孫志忠。袁慰平,聞震初.數值分析M.2版.南京:東南大學出 版社.2002.3孫志忠,裴亞強,胡仁杰.移位技術在交流采樣計算中的應用 研究J.電氣電子教學學報,2003,25(5:30一33.S

13、UN Zhizhong,PEI Yaqiang.HU Renjie.Study OD the appli cation of shift instruction in the computation of AC samplingJ. Journal ofEEE,2003,25(5:3033.4趙偉,王晶芝,白慧華.快速相對移位法開平方運算的研究與實 現J.吉林工學院學報,2000,21(3:40-42.ZHAO Wei,WANG Jingzhi,BAI Huihua.Research and appli cation of the high speed square root calculat

14、ion by the relative shifting methodJ.Journal of Jilin Institute of Technology, 2000,21(3:40.42. 5林志謀,盧貴主.一種適合FPGA實現的開平方算法J.廈門 大學學報,2006,45(2:199.201.ZHENG Hua,LIU Duren.Binary restoring shift/subtract Mlllare-rooter bit by bit based on ASICJ.Computer Technology and Development,2006.16(6:196197.7方壽海.

15、一種開平方的加速算法J.南京化工大學學報,1996, 18(4:98101.FANG Shouhai.QIlick arithrnatie of extraction of square root J.Journal of Nanjing University of Chemical Teehnoloy,199H6,18(4:98一t01.8涂時亮,姚志石.單片微機MCS一96/98實用子程序M.上海:復旦大學出版社.1991.9楊鵬,史旺旺.電力系統微機保護中開平方浮點算法的改進J. 電力自動化設備。2000.20(1:7.8.YANG Peng,SHI Wangwang.Study on

16、square root algorithm in microcomputer protectionJ.Electric Power Automation Equipment.2000,20(1:78.【10楊鵬,史旺旺.微機測量中數據表示與開平方算法的改進J. 揚州大學學報,2000,3(2:63.65.YANG Peng.SHI Wangwang.Study on￥quare root algorithm in microcomputer based testJ.Journal of YaIlgzllUniver sity,2000,3(2:6365.11曹海歐,袁宇波,鄭建勇.微機保護開平

17、方計算中牛頓迭代法的 改進J.江蘇電機工程,2006,25(5:4546.CAO Haion,YUAN Yubo,ZHENG Jianyong.The improvement of Newton iteration method in the square root calculation of microcomputer protectionJ.Jiangsu Electrical Engineering, 20016.25(5:4546.12周明德.微型計算機硬件軟件及其應用M.北京:清華大學出 版社.1982.(責任編輯:李玲作者簡介:張小鳴(1958一,男,安徽合肥人,教授,研究方向為

18、嵌入 式系統應用及電力監控系統(E-marl:xm0298163.corn。High-precision and fast square root algorithmbased on Newton iteration methodZHANG Xiaomin91,2,LI Yongxinl(1.School of Mechanical Engineering,Nanjing University of Science&Technology,Nanjing 21,0094,China;2.Department of Computer Science and Engineering,Jian

19、gsu Polytechnic University,Changzhou 213164,ChinaAbstract:As the square root calculation of full-wave Fourier algorithm takes longer time,the real -time performance of microcomputer-based protection is seriously influenced.A method based on Newton iteration iS proposed.To reduce the iteration times.

20、it can select the initial value very close to the real square root with error less than 2一by only executing displacement instruction,referring a 256一unit table once,and doing once or twice multiply operations with DSP hardware multiplier. The algorithm is programmed with assembly language and tested

21、 on TI DSP integrated development :platform.The results of sampling tests show that,the iteration time of the square root operation for the fixedpoint numbers ranging from 00000004.0000H to 01FF FFFF.FFFF H is not greater than 3 with the iteration precision better than 2一M.This method needs smaller

22、memory,very suitable for the embedded microcomputer with hardware multipliers.-Key words:square root;iteration;microcomputer-based protection;DSP 基于牛頓迭代法的高精度快速開方算法作者:張小鳴 , 李永新 , ZHANG Xiaoming, LI Yongxin作者單位:張小鳴,ZHANG Xiaoming(南京理工大學機械工程學院,江蘇,南京,210094;江蘇工業學院計算 機科學與工程系,江蘇,常州,213164 , 李永新,LI Yongxin

23、(南京理工大學機械工程學院,江 蘇,南京,210094刊名:電力自動化設備 英文刊名:ELECTRIC POWER AUTOMATION EQUIPMENT年,卷(期:2008,28(3被引用次數:0次參考文獻(12條1. 李晨 . 張杭 . 張愛民 一種能濾除衰減直流分量的新遞推離散傅氏算法 期刊論文-繼電器 2005(172. 孫志忠 . 袁慰平 . 聞震初 數值分析 20023. 孫志忠 . 裴亞強 . 胡仁杰 移位技術在交流采樣計算中的應用研究 期刊論文-電氣電子教學學報 2003(054. 趙偉 . 王晶芝 . 白慧華 快速相對移位法開平方運算的研究與實現 期刊論文-吉林工學院學報(

24、自然科學版 2000(035. 林志謀 . 盧貴主 一種適合FPGA實現的開平方算法 期刊論文-廈門大學學報(自然科學版 2006(026. 鄭華 . 劉篤仁 基于ASIC的重置逐比特移位相減開平方計算 期刊論文-計算機技術與發展 2006(067. 方壽海 一種開平方的加速算法 1996(048. 涂時亮 . 姚志石 單片微機MCS-96/98實用子程序 19919. 楊鵬 . 史旺旺 電力系統微機保護中開平方浮點算法的改進 期刊論文-電力自動化設備 2000(0110. 楊鵬 . 史旺旺 微機測量中數據表示與開平方算法的改進 期刊論文-揚州大學學報(自然科學版 2000(0211. 曹海歐

25、 . 袁宇波 . 鄭建勇 微機保護開平方計算中牛頓迭代法的改進 期刊論文-江蘇電機工程 2006(0512. 周明德 微型計算機硬件軟件及其應用 1982相似文獻(10條1.期刊論文 楊鵬 . 史旺旺 . YANG Peng. SHI Wang-wang 電力系統微機保護中開平方浮點算法的改進 -電力自動化設 備 2000,20(1在分析開平方迭代算法收斂速度的基礎上,提出了浮點數開平方的初值選取改進算法.該算法具有算法簡單、迭代次數少、精度高等特點,較好地解決 了開平方運算時間較長的問題.2.期刊論文 楊鵬 . 史旺旺 . YANG Peng. SHI Wang-wang 微機測量中數據表示

26、與開平方算法的改進 -揚州大學學報 (自然科學版 2000,3(2在分析開平方迭代算法收斂速度的基礎上,提出了開平方的初值選取改進算法.本算法具有算法簡單,迭代次數少,精度高等特點,較好地解決了開方運 算時間長的問題.3.期刊論文 趙偉 . 王晶芝 一種新的基于單片機的多字節浮點快速開平方算法 -微計算機應用 2003,24(1本文介紹一種可在單片微型計算機上由匯編語言完成的多字節浮點快速開平方運算的方法.它具有精度高、速度快和使用方便等特點.本文采用了"相 對移位"的新方法,將相對移位的試根區長度縮短了一倍,減少了移位時間,與普通的迭代算法平均迭代時間相比速度提高510倍

27、.4.會議論文 曹海歐 . 袁宇波 . 李澄 微機保護中一種新的快速開平方算法的討論 2005在分析了查表法以及迭代法的基礎上,提出了一種新的開平方運算方法-綜合法。該運算方法綜合了查表法以及迭代法,運算過程中只需要一次牛 頓迭代計算,并且據精度要求可以定量的確定表格的大小。既具有運算速度快的特點,又具有精度高、占用內存小的特點。解決了長期以來開平方算法 存在耗時長、精度低、存貯數據值范圍難以確定的問題。5.學位論文 龐勤 基于FPGA的傾角傳感器信號處理 2006本論文選用FPGA作為載體來實現傾角傳感器輸出信號的處理。研究內容涉及傾角傳感器的信號經A/D轉換后,通過串口傳入FPGA實驗板,

28、FPGA中的模 塊包括端口模塊,算術運算單元模塊等,通過建立數學模型,輸入傾角傳感器的測量值,輸出值為俯仰角和滾轉角,其優勢在于可以實時的處理傾 角傳感器的測量值。所涉及的方面包括FPGA設計流程、EDA工具、設計語言、硬件算法適用性比較。在本論文的內部設計中包括系統自項向下設計的模塊分解設計和總體模塊綜合,對于傳感器的信號處理的數學模型的建立,建立傳感器測量的坐標 軸體系,在算術模塊設計中,針對不同算術模塊采用了不同的硬件算法:乘法模塊采用了Booth算法,在三角函數和開平方函數的實現中采用了CORDIC算 法,并分析CORDIC算法實現不同函數時初始值設定,迭代次數對精度的影響,優化了該算法的迭代結構,并通過仿真結果與一般的數值方法比較,可以 直觀的看出算法的優勢,針對本論文的要求設計了通用異步串口接收模塊,包括串并轉化和并串轉換模塊。并作了整個模塊的信號處理的總體設計,分 析輸出值的精度。6.會議論文 曹海歐 . 袁宇波 . 李澄 電力系統微機保護中開平方運算的一種新的快速算法本文在分析了查表法以及迭代法的基礎上,提出了一種新的開平方運算方法-綜合法.該運算方法綜合了查表法以及迭代法,運算過程