(3.235.139.152) 您好!臺灣時間:2021/05/08 18:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:黃弘佑
研究生(外文):Hung yu Huang
論文名稱:一個在餘數系統底下的整數除法
論文名稱(外文):An Integer Division in Residue Number System
指導教授:林秀峰林秀峰引用關係
學位類別:碩士
校院名稱:逢甲大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:44
中文關鍵詞:餘數系統除法演算法
外文關鍵詞:RNSDivisionAlgoritm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:183
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
餘數系統中的除法運算為了方便計算,通常在被除數 X ,及除數 Y 中,選取中介值 M,i.e. X/Y=(X/M)(M/Y) 。傳統的做法此中介值 M 在餘數系統中是固定的。本論文提出一個不固定中介值 M,是以除數 Y 的大小來決定適當的 M 值,使得在不超過2次迴圈的次數就可以計算出 的商與餘數。
不同於以往的做法在於我們選擇適當的模 (modulus),使得最大的模小於或等於最小模的平方,如此整個除法演算法的迴圈數在低於模組個數的2倍減9次就能結束。分析及電腦模擬顯示此餘數系統的除法演算法不但在複雜度及實際電腦執行時間皆優於傳統的餘數系統除法。

An intermediate value M is used for division in residue number system (RNS), i.e. X/Y=(X/M)(M/Y), for dividend X and divisor Y, the result is computed by . The intermediate value M is a fixed value in the traditional RNS division. We propose a new scheme to choose a variable intermediate value M, which is based on divisor Y, such that the quotient and residue can be computed within at most 2 iterations.
In our proposed scheme, unlike the usual method, we choose appropriate modulus such that the largest modulus is less than or equal to the square of the least modulus. This leads to our subtle result: the number of iterations of our division algorithm is bounded above by 2 times the number of modulus subtracted by 9. Analytic and simulation results show that our proposed algorithm is superior to the traditional one in both time complexity and computation time.

目錄
1 前言 . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 餘數系統簡介
2.1 餘數系統基本定義 . . . . . . . . . . . . . . . . . . . . . 6
2.2 餘數系統的運算 . . . . . . . . . . . . . . . . . . . . . . 7
2.3 混合基底系 . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 餘數系統轉換到混合基底系統. . . . . . . . . . . . . . . . 8
2.5 中國餘數定理 . . . . . . . . . . . . . . . . . . . . . . . 9
3 餘數系統除法的相關研究
3.1 Mi Lu 的除法演算法. . . . . . . . . . . . . . . . . . . . 11
3.2 Markus 的除法演算法 . . . . . . . . . . . . . . . . . . . 12
3.3 Hiasat 的除法演算法 . . . . . . . . . . . . . . . . . . . 13
4 餘數除法研究架構
4.1 基底選擇 . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 主要想法 (Main Idea) . . . . . . . . . . . . . . . . . . 15
4.3 Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4 Algorithm 1 . . . . . . . . . . . . . . . . . . . . . . . 17
4.5 選擇適當中介值 Mi+2 並計算 Mi+2/Y 的商及餘數 . . . . . . 19
4.6 計算 X/Y 的商及餘數 . . . . . . . . . . . . . . . . . . . 20
4.7 Algorithm 2 . . . . . . . . . . . . . . . . . . . . . . . 22
5 模擬測試
5.1 測試環境及方法. . . . . . . . . . . . . . . . . . . . . . 24
5.2 模擬數據. . . . . . . . . . . . . . . . . . . . . . . . . 25
5.3 討論. . . . . . . . . . . . . . . . . . . . . . . . . . . 26
6 結論及未來方向. . . . . . . . . . . . . . . . . . . . . . . 31
7 附錄 . . . . . . . . . . . . . . . . . . . . . . . . . . 32

A. Hiasat,Hoda S,"Design and Implementation of An RNS Division Algorithm,' IEEE Trans. on Comp.,pp 240-249 1998.
A. Hiasat,Hoda S,"A High Speed Division Algorithm For Residue Number System," IEEE International Symposium on Circuits and Systems, 1995. ISCAS '95., vol. 3, pp 1996-1999 1996.
b. Bernardson, "Fast Memoryless over 64 bits, Residue to Decimal converter," IEEE Trans. on Circuits and Systems, CAS-32, pp 298-300, March 1985.
Markus A. Hitz and Erich Kaltofen,"Integer Division in Residue Number Systems," IEEE Trans. on Comp.,vol. 4, no. 8,pp 983-989 August1995.
Mi Lu and Jen-shium Chiang,"A Novel Division Algorithm for the residue Number System," IEEE Trans. on Comp.,vol. 41, pp 1026-1032, 1992.
M. Soderstrand, M. A., W. Jenkins, G. Jullien, F. Taylor, Eds., "Residue Number System Arithmetic:Modern Application in Digital Signal Proccessing,". IEEE PRESS, New York, 1986.
M. Soderstrand, C. Vernia, and J. Chang, "An improved residue system digital-to-analog converter,". IEEE Trans. on Comp.,C-34,pp903-907,Dec,1938.
N. Szabo, and R.Tanaka, "Residue Arithmetic and Its Applications to Computer Technology," McGraw Hill, New York, 1967.
T. Van Vu, "Efficient Implementations of Chinese Remainder Theorem for Sign Dectection and Residue Decoding," IEEE Trans. on Comp.,C-34,pp 646-651,July 1985.
Y.Wang and M. Abd-El-Barr, "A New Algorithm for RNS Decoding," IEEE Trans. Circuit and systems-I:
Fundamental Theory and Applications, Vol. 43, No. 12, pp. 998-1001,Dec 1996.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔