TW528986B - Method and apparatus for calculating a reciprocal - Google Patents

Description

528986 A7

發明蓺1 本發明乃關於信號處理 數或反數之方法與裝置。 曼明背景 質言之’本發明係關於計算倒 計算倒數乃屬除法運算中重要之一環，特別是於浮點小 數為然。利用倒數於兩數相除，其答案可由以除數之反數 乘被除數而獲得。此種相除方法可用以增進處理如電腦等 數位處理裝置中繁複計算以及如數位信號處理器等特殊用 途積體電路中之處理速度β 根據美國電機電子工程師協會之二進位浮點演算標準 〇754Ρ-1985，茲引介於此以供參考，浮點格式中之浮點標 準數字乃封入32位元内，以24有效位元長度為單一精準 度，或封入64位元内以53有效位元長度為加倍精準度。 有數種插入及疊代方法廣泛為開發者採用以計算倒數， 包括直接近似值，線性插入，平方插入，立方插入等。 在直接近似值方法以獲得數字之倒數中，倒數之一切可 能性尾數儲存於唯讀記憶器中。採用此法可迅速獲得答 案，但其需極大之記憶容量。例如，依據美國電機電子工 程師協會標準754單一精準度浮點格式以獲得一倒數，需要 223 Χ 23 = 184百萬位元之記憶器。 線性插入法係根據微積分中之均值原理，可適用於下列 之倒數計算··

(1) -4· 本紙張尺度適財@ g家標準(CNS) Α4規格(210X297讀—-—------ 裝 訂 線 528986

發明説明 其中 f £ [Χ〇，Χ]及X ^ X() 方插入或其它插入法以獲得所要 所有此等方法皆需另加乘法運 改正係數。插入法之主要缺點在 亦可採用平方插入，立 求精準度之倒數。不過， 算，並另需記憶器以儲存 於所要之精準度愈高，則所需儲存必要資料之記憶器量就 愈大。 牛頓拉弗生疊代法廣泛用於數位電腦中以計算倒數。此 法提供方程式之解法 (2) f(z) = 0 根據採用循環公式 2 /⑷7W) (3) 疊代i後所獲得之值Zi乃屬二次收斂至z，故疊代i及叠代 i + 1後之對應誤差ε以下式表達·： ε (zi + i) ^ ε 2(zj) (4) 利用牛頓拉弗生法計算倒數 x = + 產生以下表達式· xi + 1 = xi*(2-a*xi) (5) •5- 本紙張尺度適用中國國家標準(CNS) A4規格(210 X 297公釐) 528986 A7 ____Β7\ 五、發明説明（3 ) 自式（5 )中所見’此法之每一疊代步驟涉及依序所做之兩 次乘法運算及一次” 2之補數’，運算。故每一疊代步驟後之倒 數精準度皆獲倍增。牛頓拉弗生疊代法本身之缺點在於其 需多次疊代步驟以獲得所要氣精準度之倒數。 為克服上述缺點，業已發展出採用某種插入法獲得倒數 之初期近似值，然後根據此近似值採用疊代法。例如，經 建議使用反數表以獲得連續疊代之初期值。 發明概述 本發明提供一種方法和裝置，用以快速精準地除可遞送 一數之倒數的值。 依據此方法和裝置，採用線性插入法以獲得一數倒數之 近似值。然後此近似值用做牛頓拉弗生疊代之輸入值，以 計算高精準度之倒數。 本發明之方法與以前工技方法不同者在於提供一種計算 檢查表中最少數項目之公式，以獲所要求精準度之倒數的 近似值。本發明之方法並提供計算初期近似值及組成檢查 表中項目之改正係數的公式。實旅本發明方法之裝置包括 儲存此等值之檢查表記憶器，整數乘法器及減法器。 準此’本發明提供一種產生輸出信號之方法，該信號代 表具規格化尾數M(1 S M<2)輸入值D倒數之近似輸出值， 該尾數表示輸入信號，輸入信號包含一組最有效位元之 N0 ’且近似所要精準度ε=：2·Ν倒數之輸出信號，其中 N〇，包含步驟：&，就輸入信號之一組最有效位元p,產生 仏查表中項目之數η，其中11 = 21 ，包括次步驟：I，在第一 -6- 本紙張尺度適财@ @家標準(CNS) A4規格(2lGX297公幻 裝 訂 線 528986 A7 B7 五、發明説明（4 一檢查表中產生一組含有一群有效位元N之輸入項目yi， 其中i = 〇…n-1 ;及ii，在第二檢查表中產生一組含有一群有效位元（N-P)之輸入項目Ki，其中i = 〇…·η_ι ; b，查出 對應於輸入信號最有效位元p組之檢查表中之諸項目^及 Ki ’ c，以輸入信號有效位元p組後繼之含有效位元 群位元之#號乘Ki;d,自項目之有效位元N組減去最有 效位元群（N-p)〇 在本發明方法之另一方面，產生檢查表η項目之步驟包含 次步驟：iii，計算必要之檢查表項目之最小數獲得較 所要精準度更高之精準度，其中 2/ + 1 2/ + 2 及iv，就n = 2P查出檢查表項目之最小數，其中广“^及^ ，-於第一檢查表中產生一組輸入項目之步驟包含各次步 驟· A，計算 λ Ά+丄)十! _η 2)7 η 二 ι = ο …η-ι ’ x〇 = 1&Xi + l：=Xi + 1/n ’及Β，就i = 〇 w :出含組N有效位兀及^近似尾數之項目以及/或第二 檢查表中產生-組輸入項目之步驟包含次步驟：計算

裝 訂 線 528986 A7

Xi(xi + 以及就i = 〇…η -1查出含一 數部分之項目Ki。 組（N-P)有效位元及心之近似整 本發明並提供一種計算倒數i之裝置，倒數含具有規格化 尾數Μ之輸入值D精準度ε =2-n(其中包含一组有 效位元Ng其中N〇gN，此裝置至少含有一處理器及下述各 項··第一記憶器，構成檢查表稱為尾數M有效·位元？之函 數，並具含一組有效位元N之輸出1〇 ;第二記憶器，構成檢 查表稱為尾數乂有效位元p之函數，並具含一組有效位元 (N-P)之輸出K ·，（N-P)X(N-P)容量之乘法器，其具有尾 數Μ有效位元1>之後繼有效位元（N_p)組及輸出κ之兩輸 入’以及含有效位元（Ν-Ρ) X (Ν-Ρ)組之輸出MU ; —個加 法器/減法器’其具有輸出〗並具兩輸入分別連接以接受輸 入U和輸出MU之有效位元（Ν·Ρ)組。 在本發明裝置之另一方面，第一和第二兩記憶器併入一 储存裝置内，此裝置儲存1()和尺並稱為尾數Μ最有效位元Ρ 之函數；本發明裝置另含一種裝置，用以依據I而執行程式 计劃之牛頓拉弗生疊代法；第一記憶器含一唯讀記憶器； 第二記憶器亦含一唯讀記憶器；儲存裝置至少含一唯讀記 憶器；且或本發明裝置可含數位信號處理器中。 簡軍說明 -8- 本紙張尺度適用中國國家標準(CNS) A4規格(210x 297公釐) 裝 訂 線 528986

圖式中僅以範例方式顯示本發明之較佳具體實例。 圖1為一顯示本發明所採用緣性插入法之曲線圖； 圖2為一万塊圖，顯示本發明之線性插入法裝置，用以獲 件倒數尾數之N -位元精準度；以及 圖3為一方塊圖，顯示一牛頓拉弗生疊代法裝置，用以獲 得倒數尾數之2N -位元精準度。 發明說明 本發明適用於利用浮點格式中二進位數D之尾數m的計 算。輸入數之尾數Μ認定業經先期規格化，即等於或大於 一而小於二，亦即1$Μ<2。 圖1顯示線性插入法之較佳具體實例，本發明方法中用之 約計一數之倒數。關於直接近似值法，線性插入法大為減 少檢查表中所需儲存之項目數。在採用直接插入法以達成 倒數尾數Μ中Ν-位元精準度ε=2-Ν時，檢查表或需要广」 平均分隔之項目：緣於使用線性插入法以獲得倒數尾數之 相同Ν-位元精準度£=2·ν ,檢查表中具有2?項目即足，其 中PSN。每一項目與其前一項目之區別為2-Ρ，敌尾數％ 之最有效位元Ρ構成檢查表位址。 圖1中Xi及xi + 1之代表檢查表中有兩連續項目。^值代表 儲存於檢查表中1/Xi值之近似值。（x_Xi)乃由第一1最有效 位元後繼尾數位元代表。 所需倒數之近似值由下式表達： y = yi-ki(x.xi) -9- 本紙張尺度適用中國國家標準(CNS) Α4規格(210X297公釐) 528986 五、發明説明（ 其中ki為改正係數，ux<Xi+1 為獲得具有Ν·位元精準度之倒數尾㈣ 效位元Ρ之至少Ρ、籽-, 尾歡Μ《取有 之至/ (Ν-Ρ)份兀必須與圖丄中所示改正 之 至少(Ν-Ρ)有效位元相匹配。此等係數二。 xKi儲存於檢查表中。因此，声 數元式Κί_2 都涉及在(Ν-Ρ)χ(Ν-ρ)容量之整數乘法器中，以 mp)位元乘尾數Μ之（Ν·Ρ)位元，以2n.p除其結 果，再自yi減去其商等步驟^ yi之尾數μ的⑽元及整數Ka(n_p)位元皆儲存於檢查 表中。yi及Ki諸值乃依下式以N及（N p)精準度計算：

' (尤，) + —* _2n

Xl (Xi ^--) ⑺ 装 訂 2N-r Xi(Xl +-) n ⑻ 線 其中η為檢查表中項目數。 =出1與2兩者間規格化尾數Μ之倒數方面，線性插入法 之最大誤差ε乃由η決定，並以下式表示： 一 2” + 1 ΠΓ •10-

528986 A7 B7 五、發明説明（8 ) 必需之檢查表中項目之數n可由公式（9)決定，由之獲知 所要求之最大誤差ε。 例如，就η = 64而言，獲得倒數之線性插入法最大誤差ε 么2.98*10-5>2·16，而η = 128時，依據線性插入法，最大誤 差 ε 々 7·54*1(Γ6<2·16 〇 圖2顯示本發明計算倒數之裝置（1〇)，其實施上述之方 法。輸入數D尾數Μ之最有效位元ρ構成含2Ρ項目之唯讀記 憶器（1 2 )之位址線。此唯讀記憶器（i 2 )最好儲存ν位元以 供尾數最有效位元P之反數yi(儲存— 位元固已足，因 反數之首位元永遠為” 0 ”故也）及修正係數Ki之（N _ ρ)位 元，以進行線性插入法。 改正係數K之（N-P)位元供至具有（N-P)x(N-P)容量之整 數乘法器（14)之一輸入。供至乘法器（14)另一輸入者為輸 入尾數Μ之最有效位元P後繼之（N-P)位元值。（Ν-Ρ)χ(Ν-Ρ)位孓相乘之乘積（Ν-Ρ)最有效位元MU供至具Ν容量之整 數減法器（1 6 )之輸入。輸入M U之最有效位元ρ均為” 〇 ”而 乘積之最低有效位元（Ν·Ρ)予以拋棄。供至減法器（16)另 一輸入者為自唯讀記憶器（12)之倒數近似值yi<N位元（如 圖2中所示之I)。相減後之答案構成裝置（1〇)之N位元輸 出。 請注意，若輸入尾數Μ之最有效位元P等於（即最有效 位元為"1 ”而其它（Ρ -1 )位元為” 〇 ”），則輸出I可表示為M u 之（N-Ρ)位元之”1”的補數，從而簡化了計算。 圖3顯示一裝置（20)，用以實施線性插入法結果之牛頓拉 -11- 本紙張尺度適用中國國家標準(CNS) Α4規格(210X 297公釐) 528986 A7 _____ B7 五、發明説明（9 ) ^ ^ " 弗生疊代法，以提升N -位元至2N -位元結果之精準度。自 插入法裝置（10)之輸出I之N位元供至NX2N容量之整數乘 法器（22)。供至乘法咨（22)之另一輸入為多工器（24)之輪 出2N位元。多工器（24)交互選定輸入尾數Μ<2Ν最有效 位元及2之補充裝置（26)輸出之2Ν位元。 乘法器（22)產生一 3Ν位元長之答案。此乘積之最低有效 組Ν捨棄。乘積之最有效位元Muli2N供至補充裝置 (26)。此2之補充裝置（26)之輸出2N位元長供至乘法器 (24)。在第二次通過乘法器（22)，乘積之最有效位元^1^形 成裝置（20)之2N位元輸出（如圖3中所示之^)。 固然已以範例方式說明本發明之較佳具體實例，惟對嫻 於技藝者而言，可做變化與修改而不離本發明所附申請專 利範圍者。 線 -12· 本紙張尺度適用中國國家標準(CNS) A4規格(210X 297公-----

Claims (1)

1. 528986 六、申請專利範圉 A8 B8 C8

   1· 一種產生輸出信號之方法，，輪出信號代表近似輸入值1^ 倒數之輸出值，輸入值含有由輸入信號所表示之規格化 尾數Μ(其中，I入信號包含一組最有效位元 N〇且輸出信號以所要精準度ε=2·Ν(其中ν$ν〇)而近似 於該倒數，此方法包含之步驟為： a,就輸入信號之一組最有效位元P，於多個檢查表中 產生η數項目，其中n==2P，本步驟含各分步驟： 裝 1 , 在第一檢查表中產生含有效位元組N之一組 輸入項目L，其中i = 0…n-1 ;及 ii， 在第二檢查表中產生含有效位元組（N_p)之 .一組輸入項目Ki，其中i = 〇…nq ; b，查出檢查表中對應於輸入信號最有效位元組p之項 目yi及Ki ; c，以輸入信號最有效位元組P後繼之含有效位元組 (N-P)之信號與Ki相乘；及 d ,自項目yi有效位元組N減去最有效位元組（N_p)。 線 2·如申請專利範圍第1項之方法，其中於檢查表中產生n項 目之步驟包含分步驟： iii，為獲得所要精準度更高精準，計算其必要之檢查表 項目之最小數1，其中 2/27+2 及 2/-1—ΊΓ 以及 -13-

   528986

   中請專利範圍 2P> 3· ^申請專利範圍第1項之方法，其中在第一檢查表中產生 —組輸入項目之步騾含有分步驟： A，計算 · 凡=. '(尤丨十一)十..... η 2η 其中 ι = 0，…，η-1，χ0=1 及 Xi + 1 = Xi+1/n ;及 B，查出含有效位元組N之項目^丨及就丨=〇…n _ i求y i尾數 之近似值β 4·如申請專利範圍第i項之方法，其中在第二檢查表中產生 一組輸入項目之步驟含有分步驟： A，計算 2w-p 裝 訂 其中 η X 〇 = 1 Xi + i= Xj + l/ n，及 線 ^，查出含有效位元組（N-P)之項目Ki及就i = 0…η-!* ^整數部分之近似值。 5· —種計算反數I之裝置，其具規格化尾數之 輸入值D之精準度^ = 2^，尾數含一組最有效位元n〇， 其中Ν〇^Ν，此裝置包含： 至少一個處理器； 第一記憶器構成檢查表，稱為尾數]VI最有效位元Ρ之函 -14 - 本紙張尺度適用中國國家標準(CNS) Α4規格(210X297公釐) 528986

   數，並具有含一組有效位元N之輸出“，· (請先聞讀背面之注意事項再填寫本頁) 第一元憶器構成檢查表，稱為尾數Μ最有效位元P之函 數，並具有含一組有效位元（Ν-Ρ)之輸出Κ ,· (ν·ρ)χ(Ν-Ρ)容量之乘法器，其具有兩個輸入，其一 輸入為尾數Μ最有效位元組ρ後繼之有效位元組（Ν_ρ)及 另一輸入為輸出Κ，並具有含（心以父^ —㈠有效位元組 之輸出M U ;以及 加法器/減法器，其具以輸出I並具有兩個輸入，分別 連接以接受輸出1〇及輸ώΜυ之最有效位元組（Ν_ρ)。 6.如申請專利範圍第5項之裝置，其中第一及第二兩記憶器 併入一儲存裝置，其儲存“及尺並稱為尾數Μ最有效位元 Ρ之函數® 7·如申請專利範圍第5項之裝置，其另含根據！以執行牛頓 拉弗生疊代法程式規劃之裝置。 8·如申請專利範圍第5項之裝置，其中第一記憶器含有一唯 讀記-憶器（ROM)。 9·如申請專利範圍第5項之裝置/其中第二記憶器含有一唯 讀記憶器。 10.如申請專利範圍第6項之裝置，其中儲存裝置至少含一個 唯讀記憶器。 經濟部中央標準局員工消費合作社印策 11· 一種含有申請專利範圍第5項裝置之數位化信號處理裝 置。 -15- 本紙張尺度適用中國國家揉準（CNS ) A4規格（210X297公釐）