臺灣博碩士論文加值系統

本論文的第一部份提出了利用數個技術設計一混合基底16/8/4/2的整數除法器，其中包含了利用運算元放大（Operand Scaling）、表格分割（Table Partitioning）及表格分享（Table Sharing）等技術，以期可增加執行效能，而不會增加複雜性。

第二部分提出了高抗雜訊的位址線轉換偵測電路，我們利用簡單的迴授電路來穩定的產生晶片選擇訊號（Chip Select ，簡稱為CS），以及兩個延遲元件來動態地調整晶片選擇訊號的長度。

The first topic of this thesis is a mixed radix-16/8/4/2 64b/32b integer divider which uses a variety of techniques, including operand scaling, table partitioning, and table sharing, to increase performance without paying the cost of increasing complexity.

The second topic is a noise immune address transition detector（ATD）circuit. We employ a simple feedback loop to stabilize the generated CS（chip select）signal and two delay cells to dynamically adjust the width of the CS strobe.

目錄
摘 要 i
Abstract ii
第一章 簡介 1
1.1 研究動機 1
1.2 相關研究 2
1.2.1 除法器演算法相關研究 2
1.2.2 ATD之相關研究 2
1.3 論文目的 3
1.4 論文大綱 4
第二章 數位遞迴除法演算法 5
2.1 除法運算定義 5
2.2 數位遞迴除法演算法 6
2.2.1 數位遞迴除法公式定義 6
2.2.2 商數位元之選擇集合 7
2.2.3 商數位元選擇函數與餘數後續處理 8

2.2.4 商數位元選擇區間上下界 9
2.2.5 數位遞迴除法執行流程 9
2.3 數位遞迴除法設計考量 11
2.3.1 運算元放大（Operand Scaling） 11
2.3.1.1 放大因子的計算（Scaling Factor Calculation） 12
2.3.1.2 使用四輸入之CSA樹放大預估殘數 13
2.3.2 表格分割（Table Partitioning） 15
2.3.2.1 商數位元分解（Quotient Digit Decomposition） 15
2.3.2.2 商數位元合成（Quotient Digit Assimilation） 17
2.3.3 殘數的計算 20
2.3.4 草上飛轉換器 21
第三章 整數除法器設計與實作 23
3.1 整數除法的定義 23
3.2 混合基底16/8/4/2整數除法器設計 24
3.3 程式碼撰寫與測試 28
3.3.1 組合電路部分設計 29
3.3.2 循序控制電路設計 32

3.3.3 設計架構驗證 34
3.4 晶片功能規格 35
3.5 晶片合成與佈局 39
3.6 實際晶片結果測試 42
第四章 高抗雜訊位址線轉變偵測器 46
4.1 緣由 46
4.2 設計原理及方法 46
4.2.1 ATD設計 47
4.2.2 雜訊排除 49
4.2.3 延遲元件之設計 49
4.3 電路架構 51
4.4 晶片模擬結果 52
4.5 晶片佈局 53
4.6 晶片測試結果 54
4.7 結論與討論 54
第五章 結論 56
參考文獻 58

附錄一 62
附錄二 78

參考文獻
[1]M. D. Ercegovac and T. Lang, “Division and Square Root - Digit-Recurrence Algorithms and Implementations,” Reading: Kluwer Academic Publisher, 1994.
[2]K. Hwang, “Computer Arithmetic: principles, architecture, and design,” Reading: John Wiley & Son, 1979.
[3]S. F. Oberman and M. J. Flynn, “Design Issues in Division and Other Floating-Point Operations,” IEEE Trans. Computers, vol. 46, no. 2, pp. 154-161, Feb. 1997.
[4]P. Soderquist and M. Lesser, “Division and Square Root - Choosing the Right Implementation,” IEEE Micro, pp. 56-66, July/August 1997.
[5]S. F. Oberman and M. J. Flynn, “Division Algorithms and Implementations,” IEEE Trans. Computers, vol. 46, no. 8, pp. 833-854, Aug. 1997.
[6]J. F. Cavanagh, “Digital Computer Arithmetic: design and implementation,” Reading: McGraw-Hill, 1984.
[7]“IEEE Standard for Binary Floating Point Arithmetic,” ANSI/IEEE Standard 754-1985, New York: IEEE, 1985.
[8]L. Gwennap, “Intel’s P6 Uses Decoupled Superscalar Design – Next Generation of x86 Integrates L2 Cache in Package with CPU,” Microprocessor Report, vol. 9, no. 2, Feb. 1995.
[9]M. D. Ercegovac and T. Lang, “On-the-Fly Conversion of Redundant into Conventional Representations,” IEEE Trans. Computers, vol. 36, no. 7, pp. 895-897, July 1987.
[10]“Pentium Pro Family Developer’s Manual,” Intel, 1996.
[11]“Pentium II Processor Developer’s Manual,’ Intel, Oct. 1997.
[12]“Intel Architecture Software Developer’s Manual,” Intel, Oct. 1997.
[13]“Cyrix M II Data Book,” Cyrix, Apr. 1998.
[14]“Statistical Analysis of Floating Point Flaw in the Pentium（TM） Processor （1994）,” Intel Corporation, Nov. 1994.
[15]H.R. Srinivas and K.K. Parhi, “A Fast Radix-4 Division Algorithm and its Architecture,” IEEE Trans. Computers, vol. 44, no. 6, pp. 826-831, June 1995.
[16]J. Cortadella, and T. Lang, “High-Radix Division and Square-Root with Speculation,” IEEE Trans. Computers, vol. 43, no. 6, pp. 919-931, Aug. 1994.
[17]M. D. Ercegovac, T. Lang, and P. Montuschi, “Very-High Radix Division with Prescaling and Selection by Rounding,” IEEE Trans. Computers, vol. 43, no. 8, pp. 909-917, Aug. 1994.
[18]D.E. Thomas and P.R. Moorby, “The Verilog Hardware Description Language Third Edition,” Reading: Kluwer Academic Publisher, 1997.
[19]P. Kurup and T. Abbasi, “Logic Synthesis Using Synopsys Second Edition,” Reading: Kluwer Academic Publisher, 1997.
[20]M. D. Ercegovac, and T. Lang, “Simple radix-4 division with operands scaling,” IEEE Trans. Computers, vol. 39, no. 9, pp. 1204-1208, Sep. 1990.
[21]P. Montuschi, and L. Ciminiera, “Design of a radix 4 division unit with simple selection table,” IEEE Trans. Computers, vol. 41, no. 12, pp. 1606-1611, Dec. 1992.
[22]J. Fandrianto, “Algorithm for high-speed shared radix 4 division and radix 4 square root,” Proc. 8th IEEE Symp. on Computer Arithmetic, pp. 73-79, Como, Italy, May 1987.
[23]M. Kuriyama, S. Atrumi, K. Imamiya, Y. Iyama, N. Matzukawa, H. Araki, K. Narita, K. Masuda, and S. Tanaka, “A 16-ns 1-Mb CMOS EPROM,” IEEE. J. of Solid-State Circuits, vol. 25, no. 5, pp. 1141-1146, Oct. 1990.
[24]N. Tomita, N. Obuaki, J. Miyamoto, K. Imamiya, Y. Iyama, S. Mori, Y. Ohshima, N. Arai, Y. Kaneho, E. Sakagami, K. Yoshikawa, and S. Tanaka, “A 62-ns 16-Mb CMOS EPROM with voltage stress relaxation technique,” IEEE. J. of Solid-State Circuits, vol. 26, no. 11, pp. 1593-1599, Nov. 1991.
[25]H. Nakai, K. Kanazawa, M. Asano, I. Sato, H. Iwahashi, K. Sakai, M. Yahata, S. Tanaka, N. Tozawa, M. Yatabe, and S. Saito, “A 36ns 1Mbit CMOS EPROM with new data sensing technique,” 1990 Symp. On VLSI Circuits, vol. 10-1, pp. 95-96, 1990.
[26]A. Sekiyama, T. Seki, S. Nagai, A. Iwase, N. Suzuki, and M. Hayasaka, “A 1-V operating 256-kb full-CMOS SRAM,” IEEE J. of Solid-state Circuits, vol. 27, no. 5, pp. 776-782, May 1992.
[27]C.-C. Wang, C.-J. Huang, and I.-Y. Chang, “Design and analysis of Radix-8/4/2 64b/32b integer divider using COMPASS Cell library,” VLSI Design, vol. 11, no. 4, pp. 331-338, Dec. 2000.
[28]C.-C. Wang, C.-J. Huang, and G.-C. Lin, “Cell-based implementation of Radix-4/2 64b/32b signed integer divider using COMPASS Cell library,” IEE Proceedings – Computers and Digital Techniques, vol. 147, no. 2, pp. 109-115, March 2000.
[29]林國卿，“64位元前瞻性微處理器之混合多基底整數除法器設計與實作”，中山大學電機工程學系碩士論文，民國八十七年六月。
[30]張一言，“混合基底 8/4/2/之64位元除以32位元整數除法器之設計與實作”，中山大學電機工程學系碩士論文，民國八十八年六月。
[31]黃振榮，“應用於訊號處理之高速基本算術元件硬體實作”，中山大學電機工程學系博士論文，民國八十九年五月。
[32]C.-C. Wang, Y.-H. Hsueh, C.-W. Chen, J.-J. Wang and R. Hu, “A Cost-Effective 8051-based Chinese Voice Dialer for DECT Handsets,” 5th WSES/IEEE Word Multiconference on Circuits, Systems, Communications and Computers 2001, (accepted, no. 572).
[33]C.-C. Wang, P.-M. Lee, J.-J. Wang and C.-J. Hunng, “Design of a Cycle-Efficient 64B/32B Integer Divider Using a Table-Sharing Method,” 8th IEEE International Conference on Electronics, Circuits and Systems 2001 (ICECS 2001), (accepted, no. 80).