(3.227.208.0) 您好!臺灣時間:2021/04/20 16:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:謝韶徽
研究生(外文):Shao-Hui Shieh
論文名稱:最少冗餘有號數字數系
論文名稱(外文):Minimally Redundant Signed-Digit Number Systems
指導教授:吳誠文
指導教授(外文):Cheng-Wen Wu
學位類別:博士
校院名稱:國立清華大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:英文
論文頁數:103
中文關鍵詞:有號數字數系冗餘數系無進位加法最少冗餘有號數
外文關鍵詞:signed-digit number systemredundant number systemcarry-free additionminimally redundant signed-digit
相關次數:
  • 被引用被引用:0
  • 點閱點閱:274
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
有號數字(signed-digit)數系是一種冗餘數系(redundant number system),因其具有無進位(carry-free)加法之潛在特性,長久以來即被應用於設計快速運算電路之場合。以往基於有號數字數系之無進位加法的研究認為:『當有號數字數系之基底(radix)越大時,要完成無進位加法所需之冗餘指標(redundancy index)也需要越大』。基於此種原因,以往之無進位加法器之設計,大多著重於依賴基底較小(例如:二進制,r=2)之有號數字數系表示法。因而我們提出最少冗餘有號數字(minimally redundant signed-digit;MRSD)數系,不論其在任何基底(r≧2)情況下均僅使用一個冗餘數字,此數系包括許多子數系,其中較重要之子數系為:非對稱高基底有號數字(asymmetric high-radix signed-digit)、最少冗餘正值數字(minimal redundant positive-digit)、對稱高基底有號數字(symmetric high-radix signed-digit)和二進制有號數字(binary signed-digit)等數系;我們指出最少冗餘有號數字數系具有無進位加法之潛在特性,並依運算元之種類將此數系之無進位加法分類成:完全封閉式(fully-closed)、準封閉式(quasi-closed)及次封閉式(sub-closed)三種。本論文提出用來建構兩級式及三級式基於最少冗餘有號數字數系之無進位加法的新演算法,並發現若規定數系之基底為r= ,其中m可為任何正整數,則二進制至最少冗餘有號數字數系表示法之轉換可在常數時間內完成;因而,最少冗餘有號數字數目至二進制之轉換電路的特性決定了基於最少冗餘有號數字數系表示法之算術運算系統的效能。
同時我們亦提出兩種將最少冗餘有號數字數系表示法轉換至二進制之方法:第一種使用新的專屬電路結構以獲取快速轉換之特性,第二種則使用簡單轉換及傳統加法以提供硬體之再使用性(hardware reusability);這些結果是非常重要的,因為最少冗餘有號數字數目至二進制之轉換被視為是基於最少冗餘有號數字數系表示法之算術運算系統的瓶頸。而將非對稱高基底有號數字數目表示法或最少冗餘正值數字數目表示法轉換至二進制之方法亦被證明可簡化等同於r補數加法,因此,針對下列三種應用:(1)r補數加法,(2)非對稱高基底有號數字數目表示法至二進制之轉換,及(3)最少冗餘正值數字數目表示法至二進制之轉換;所設計之優異硬體架構即可直接應用於其他二者。這個結果之貢獻在於:只要使用最少冗餘有號數字數目表示法之系統,不但可提升整體效能,更賦予硬體之再使用性及設計之彈性化(design flexibility)。
我們以一些應用設計如:循序加法器及陣列乘法器,來驗證本論文提出之演算法;並發現:基於最少冗餘有號數字數系之無進位加法特別適合用來設計『需要處理大量連續加法運算之高性能算術運算系統』。我們將基於有號數字數系之無進位加法存在的條件,依數系使用之基底及冗餘指標區分為:鬆散式限制、帕哈密式、緊密式限制及最高值限制等準則。最少冗餘有號數字數系因使用最少之冗餘數字,因而可用最少之信號儲存空間、較小之功率消耗、最緊密之電路結構及最小之晶片面積,來完成高性能無進位加法相關應用之算術運算系統設計,是以結論其為最佳有號數字數系中的一種數系。
We propose the minimally redundant signed-digit (MRSD) number system, including its subsets the asymmetric high-radix signed-digit (AHSD), the minimal redundant positive-digit (MRPD), the symmetric high-radix signed-digit (SHSD) and the binary signed-digit (BSD) number systems, for fast binary addition and multiplication, and show that the MRSD number system supports carry-free (CF) addition. The CF additions in MRSD, to be classified as fully-closed, quasi-closed and sub-closed additions, use only one redundant digit for any radix r≧2. The criterion for the existence of carry-free additions, in terms of redundancy-index and radix, is thus from tightly bounded down to loosely bounded.
Novel algorithms for constructing the two-stage and three-stage CF adders (CFA) based on the MRSD number system are also presented. Moreover, if the radix is specified as r= , where m is any positive integer, the binary-to-MRSD conversion can be done in constant time regardless of the word-length. Hence, the MRSD-to-binary conversion dominates the performance of an MRSD-based arithmetic system.
We also propose two efficient algorithms for converting MRSD numbers to binary ones. The first one uses a novel structure to achieve high speed, while the second one uses simple transformations and conventional additions to provide hardware reusability. These results are important since the conversion from MRSD numbers to binary ones has been considered the performance bottleneck of the MRSD-based arithmetic systems. Algorithms for converting from asymmetric high-radix signed-digit (AHSD) numbers and minimal redundant positive-digit (MRPD) numbers to binary numbers are proposed. Our approach is based on simple transformation among AHSD, MRPD, and conventional radix-r (CR) number systems. We also show that the conversion from AHSD or MRPD numbers to binary numbers can be reduced to r''s-complement addition. The result is important since the conversion from AHSD or MRPD to binary has been considered the performance bottleneck of the AHSD-based or MRPD-based arithmetic systems. We show that the
AHSD-to-binary conversion is similar to the MRPD-to-binary conversion. Therefore, a good hardware architecture for any of the following three applications can be used for the other two: 1) r''s-complement addition, 2) AHSD-to-binary conversion, and
3) MRPD-to-binary conversion. In addition to performance improvement, the main contribution of this work is hardware reusability and design flexibility, so far as the involved number systems are concerned. We also show that Blair''s work is just a special case (for r=2) as discussed in this dissertation.
Examples are given to demonstrate the proposed algorithms. The CF adder based on MRSD is especially suited to high-performance arithmetic with long sequences of addition-related computations performed on a massive amount of data. Practical implementations of the high-performance CF adder and array multiplier are presented.
We conclude that MRSD is one of the excellent number systems to have the possibility to achieve high-performance operations with the smaller integrated circuits in high circuitry density. The conditions for the existence of various carry-free additions, performed over different digit sets with sufficient redundancy, are also concluded as loosely-bounded, Parhami''s, tightly-bounded and uppermost-bounded criteria in terms of redundancy-index and radix.
摘 要 ----------------------------------------------- Ι
誌 謝 ----------------------------------------------- Ⅲ
目 錄 ----------------------------------------------- Ⅳ
第一章 概論 ------------------------------------------ Ⅴ
第二章 最少冗餘有號數字數系 -------------------------- Ⅵ
第三章 最少冗餘有號數字數系與二進制數系之轉換 -------- Ⅶ
第四章 應用與實現 ------------------------------------ Ⅷ
第五章 結論與未來之研究 ------------------------------ Ⅸ
英文附錄及參考文獻 ----------------------------------- Ⅹ
[1] Avizienis, ''Signed-digit number representations for fast parallel arithmetic,'''' IEEE Trans. Electronic Computers}, vol.EC-10, pp.389-400, Sept. 1961.
[2] Parhami, ''Generalized signed-digit number systems: A unifying framework for redundant number representations,'''' IEEE Trans. Computers, vol.39, pp.89-98, Jan. 1990.
[3] Parhami, ''Zero, sign, and overflow detection schemes for generalized signed-digit arithmetic,'''' in Proc. 22th Asilomar Conf. Singals, Syst., and Comput., (Pacific Grove, CA), pp.636-639, Oct. 1988.
[4] B. Parhami, ''Implementation alternatives for generalized signed-digit addition,'''' in Proc. IEEE 28th Asilomar Conf. Signals, Systems, and Computers}, (Pacific Grove), pp.157-161, 1994.
[5] B. Parhami, ''Comments on {"High-Speed Area-Efficient Multiplier Design Using Multiple-Valued Current-Mode Circuits"},'''' IEEE Trans. Computers, vol.45, pp.637-638, May 1996.
[6] V. Kantabutra, ''Designing optimum one-level carry-skip adders,''''IEEE Trans. Computers}, vol.42, pp.759-764, June 1993.
[7] K. Hwang, Computer Arithmetic: Principles, Architecture, and Design. New York: John Wiley & Sons, 1979.
[8] Koren, Computer Arithmetic Algorithms. Englewood Cliffs, New Jersey, 07632: Prentice-Hall Inc., 1993.
[9] F. J. Taylor, ''A VLSI residue arithmetic multiplier,'''' IEEE Trans. Computers, vol.31, pp.540-546, June 1982.
[10] B. Parhami, ''Carry-free addition of recoded binary signed-digit numbers,'''' IEEE Trans. Computers, vol.37, pp.1470-1476, Nov. 1988.
[11] B. Parhami, ''On the implementation of arithmetic support functions for generalized signed-digit number systems,'''' IEEE Trans. Computers, vol.42, pp.379--384, Mar. 1993.
[12] Peled, ''On the hardware implementation of digital signal processors,'''' IEEE Trans. Acoustics, Speech, and Signal Processing, vol.24, pp.76-86, Feb. 1976.
[13] S. Phatak, I. Koren, and H. Choi, ''Hybrid number representations with bounded carry propagation chains,'''' in Proc. Int. Conf.. Comput. Design (ICCD)}, (Cambridge, MA), pp.272-275, Oct. 1993.
[14] S. Phatak and I. Koren, ''Hybrid signed-digit number systems: A unified framework for redundant number representations with bounded carry propagation chains,'''' IEEE Trans. Computers, vol.43, pp.880-891, Aug. 1994.
[15] S. Kawahito, M. Ishida, M.~Kameyama, and T. Higuchi, ''High-speed area-efficient multiplier design using multiple-valued current-mode circuits,'''' IEEE Trans. Computers, vol.43, pp.34-42, Jan. 1994.
[16] S. Kawahito, M. Kameyama, T. Higuchi, and H. Yamada, ''A 32*32-bit multiplier using multiple-valued MOS current-mode circuits,'''' IEEE Journal of Solid-State Circuits}, vol.23, pp.124-132, Feb. 1988.
[17] M. Kameyama, S. Kawahito, and T. Higuchi, ''A multiplier chip with multiple-valued bidirectional current-mode logic circuits,'''' IEEE Computer , pp.43-56, Apr. 1988.
[18] Vandemeulebroecke, E. Vanzieleghem, T. Denayer, and P. G. A. Jespers, ''A new carry-free division algorithm and its application to a single-chip 1024-b RSA processor,'''' IEEE Journal of Solid-State Circuits, vol. 25, pp.748-756, June 1990.
[19] N. Takagi, H. Yasuura, and S. Yajima, ''High-speed VLSI multiplication algorithm with a redundant binary addition tree,'''' IEEE Trans. Computers, vol.34, pp.789-796, Sept. 1985.
[20] H. Makino, Y. Nakase, H. Morinaka, H. Shinohara, and K. Mashiko, ''An 8.8-ns 54*54-bit multiplier with high speed redundant binary architecture,'''' IEEE Journal of Solid-State Circuits, vol.31, pp.773-782, June 1996.
[21] R. Hartly, ''Subexpression sharing in filters using canonic signed digit multipliers,'''' Trans. Circuits and Systems II: Analog and Digital Signal Processing, vol.43, pp.677-688, Oct. 1996.
[22] R. Woods and J. McCanny, ''Design of a high-performance IIR digital filter chip,'''' IEE Proc. Pt. E, vol.139, pp.195-202, May 1992.
[23] H. R. Srinivas, K. K. Parhi, and L. A. Montalvo, ''Radix 2 division with over-redundant quotient selection,'''' IEEE Trans. Computers, vol.46, pp.85-92, Jan. 1997.
[24] S. Kuninobu, T. Nishiyama, H. Edamatsu, T. Taniguchi, and N. Takagi, ''Design of high speed {MOS} multiplier and divider using redundant binary representation,'''' in Proc. 8th IEEE Symp. Computer Arithmetic, pp.80-86, 1987.
[25] M. Makino, Y. Nakase, and H. Shinohara, ''A 8.8-ns 54*54-bit multiplier using new redundant binary architecture,'''' in Proc. Int. Conf. Comput. Design (ICCD), Cambridge, MA), pp.202-205, Oct. 1993.
[26] M. D. Ercegovac and T. Lang, ''Redundant and on-line CORDIC: Application to matrix triangularization and SVD,'''' IEEE Trans. Computers, vol.39, pp.725-740, June 1990.
[27] M. J. Irwin and R. M. Owens, ''Digit-pipelined arithmetic as illustrated by the paste-up system: A tutorial,'''' IEEE Computer, pp.61-73, Apr. 1987.
[28] M. Ercegovac and T. Lang, ''On-the-fly conversion of redundant into conventional representations,'''' IEEE Trans. Computers, vol.36, pp.895-897, July 1987.
[29] S. M. Yen, C. S. Laih, C. H. Chen, and J. Y. Lee, ''An efficient redundant-binary number to binary number converter,'''' IEEE Journal of Solid-State Circuits, vol. 27, pp.109-112, Jan. 1992.
[30] H. R. Srinivas and K. K. Parhi, ''A fast VLSI adder architecture,'''' IEEE Journal of Solid-State Circuits, vol.27, pp.761-767, May 1992.
[31] M. Blair, ''The equivalence of twos-complement addition and the conversion of redundant-binary to twos-complement numbers,'''' IEEE Trans. Circuits and Systems I: Fundamental Theory and Applications, vol.45, pp.669-671, June 1998.
[32] S.-H. Shieh and C.-W. Wu, ''On r''s-complement addition and conversion from asymmetric high-radix signed-digit numbers to binary numbers,'''' in Proc. 10th VLSI Design/CAD Symp., (Nantou), pp.161-164, Aug. 1999.
[33] S.-H. Shieh and C.-W. Wu, ''On r''s-complement addition and conversion from asymmetric high-radix signed-digit and minimal redundant positive-digit numbers to binary numbers,'''' submit to IEEE CAS II.
[34] J. E. Roberson, ''A new class of digital division methods,'''' IEEE Trans. Computers, vol.7, pp.218-222, Sept. 1958.
[35] L. MacSorley, ''High-speed arithmetic in binary computers,'''' Proc. IRE, vol.49, pp.67-91, Jan. 1961.
[36] A. Y. Chow and J. E. Robertson, ''Logical design of a redundant binary adder,'''' in Proc. Symp. Computer Arithmetic, (Santa Monica, CA), pp.109-115, Oct. 1978.
[37] S.-H. Shieh, B.-H. Lin, and C.-W. Wu, ''Carry-propagation-free adder based on an asymmetric high-radix signed-digit number system,'''' in Proc. Int. Computer Symp. (ICS), (Kaohsiung), pp.199-204, Dec. 1996.
[38] K.-J. Lin and C.-W. Wu, ''PMBC: a programmable BIST compiler for memory cores,'''' in IEEE Int. Workshop on Testing Embedded Core-Based System-Chips (TECS), (Dana Point), pp.P2.1-P2.6, Apr. 1999.
[39] B. Parhami, Computer Arithmetic Algorithms and Hardware Designs. New York, New York, 10016: Oxford University Press, Inc., 2000.
[40] W. E. Clark and J. J. Liang, ''On arithmetic weight for a general radix representation of integers,'''' IEEE Trans. Inform. Theory, vol.19, pp.823-826, Nov. 1973.
[41] S. Arno and F. S. Wheeler, ''Signed digit representations of minimal hamming weight,'''' IEEE Trans. Computers, vol.42, pp.1007-1010, Aug. 1993.
[42] S.-H. Shieh and C.-W. Wu, ''Carry-free adder design using asymmetric high-radix signed-digit number system,'''' in Proc. 11th VLSI Design/CAD Symp., (Pingtung), pp.183-186, Aug. 2000.
[43] S.-H. Shieh and C.-W. Wu, ''Asymmetric high-radix signed-digit number systems for carry-free addition,'''' J. Inform. Science and Engineering, accepted 2003.
[44] S.-H. Shieh and C.-W. Wu, ''Minimally redundant positive-digit number system: Theory and its applications,'''' in preparation.
[45] S.-H. Shieh and C.-W. Wu, ''Minimally redundant signed-digit number system: A unified framework for single redundant signed-digit representations,'''' in preparation.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔