臺灣博碩士論文加值系統

在數位信號處理中，往往都是由乘法、加法等算術運算電路構成。而一般二進制運算因為運算位元寬度過長，導致運算時的進位傳遞延遲增加，因此在這些運算電路中常常都為了解決進位傳遞的問題，而發展出許多不一樣的架構。現在採用餘數系統的方式，可以透過餘數模組將原本要運算很大位元寬度的運算，變成較小位元寬度的運算。在數位濾波器的設計中，捲積運算是整個濾波器設計的核心部份，使用餘數系統時將會用到許多的乘法運算。為了降低乘法運算的個數，進而採用多項式餘數系統，利用此系統可以將原本需要N2的乘法運算減少至2N個乘法運算。由於N值的大小將影響運算時所選用的餘數模數，並造成運算上的延遲。
在本篇論文中提出共軛通道多項式餘數系統，使用此種架構可以降低N值，並且選用較小的餘數模數，加快PRNS的內部運算。針對正向與反向轉換的部份可以透過蝴蝶架構以及使用diminished-1的算術計算，讓整體的運算更有效率。
整個VLSI設計，是以兩個八點複數序列，在MOD 257的條件下進行運算，整個晶片的面積達14.1mm2，操作頻率可以到達33.3MHz。

Multiplication and addition are frequently used in DSP.　In general, large word length leads to decay the performance of the system. Because of the carry propagation is long. There have many kind of computing architecture to solve this problem. Nowadays, residue number system (RNS) is proposed. It can reduce word length of operand and reduce computing delay in internal arithmetic processing. Convolution is the heart of digital filter design. There will use too many multiplications in RNS. Convolution use Polynomial RNS will reduce number of multiplication.
In this thesis, we propose a new method based on PRNS, is CPCPRNS. It can choose smaller integer modulus. There will improve the speed of internal PRNS process, and not increase hardware cost. Whole chip area is 14.1mm2, and operation speed is 33.3MHz.

摘 要 I
ABSTRACT II
誌 謝 III
目 錄 IV
圖 目 錄 VI
表 目 錄 VIII
一、緒 論 1

1.1研究動機 1
1.2研究目標 1
1.3各章提要 1
二、背 景 3
2.1餘數系統 3
2.1.1二進制-餘數轉換 4
2.1.2餘數運算及特性 4
2.1.3餘數-二進制轉換 7
2.2二項式餘數系統 12
2.2.1 QRNS mapping 12
2.2.2 QRNS Parallel Multiplication 13
2.2.3 Inverse QRNS mapping 13
2.2.4利用QRNS進行複數乘法運算 13
2.3多項式餘數系統 15
2.3.1 PRNS mapping 15
2.3.2 Parallel multiplication 16
2.3.3 Inverse PRNS mapping 16
2.4 DIMINISHED-1數字系統 17
2.4.1 Diminished-1數值表示 17
2.4.2 B-D轉換 17
2.4.3 D-B轉換 18
2.4.4 Diminished-1的算術運算 18
三、線性捲積運算 22
3.1線性捲積運算 22
3.1.1數值代入運算 22
3.2 RNS線性捲積運算 23
3.2.1數值代入運算 24
3.3 PRNS線性捲積運算 25
3.3.1乘常數運算 26
3.3.2加法運算 27
3.3.3乘法運算 27
3.3.4數值代入計算 27
3.3.5蝴蝶架構計算 31
3.4 MPCPRNS線性捲積運算 38
3.5複數序列PRNS線性捲積運算 39
四、共軛通道多項式餘數系統 42
4.1 CPC-PRNS簡介 42
4.2 CPC-PRNS演算法推導 42
4.3 CPC-PRNS之複數線性捲積運算 44
4.4 CPC-PRNS運算複雜度的分析 45
4.4.1乘常數運算 45
4.4.2加法運算 45
4.4.3乘法運算 46
4.5 CPC-PRNS模擬 47
4.5.1乘法反元素 47
4.5.2傳統複數線性捲積運算 48
4.5.3 CPC-PRNS複數捲積運算 48
4.6 CPC-PRNS與其他方法計算量的比較 51
4.6.1傳統RNS之複數線性捲積計算量 51
4.6.2使用PRNS之複數線性捲積計算量 51
4.6.3 RNS、PRNS與CPC-PRNS計算量的比較 51
五、VLSI設計與晶片實現 52
5.1基本算術運算器 52
5.1.1單一位元加法器 52
5.1.2隱含固定值之加法器 54
5.1.3多位元加法器 55
5.1.4 進位保存加法器 57
5.2 DIMINISHED-1餘數運算器 58
5.2.1 B �� D 轉換電路 58
5.2.2 D �� B轉換電路 59
5.2.3 Diminished-1加法運算 59
5.2.4 Diminished-1乘2的冪次方計算 60
5.3 CPC-PRNS線性捲積之VLSI實現 65
5.3.1正向同型映對 65
5.3.2平行乘法運算 69
5.3.3反向同型映對 70
5.3.4整合運算 74
5.4 CPC-PRNS硬體模擬結果 74
5.5晶片實現 77
5.5.1晶片設計流程 77
5.5.2 Layout view及晶片資訊 77
六、結論與未來研究方向 79
參 考 文 獻 80

[1] N. S. Szabo and R. I. Tanaka, Residue arithmetic and its applications to computer technology, New York, McGraw-Hill, 1967.

[2]B.Parhami, “Optimal table-lookup schemes for binary-to-residue and residue-to-binary conversions,” Conference Record of The Twenty-Seventh Asilomar Conference on Signals, Systems and Computers, 1-3, vol. 1, pp. 812 – 816, Nov. 1993.

[3]S.J. Piestrak, “Design of residue generators and multioperand modular adders using carry-save adders,” IEEE Transactions on Computers, vol. 43, pp. 68 – 77, Jan. 1994.

[4]M. Bayoumi, G. Jullien, and W. Miller, “A VLSI implementation of residue adders,” IEEE Transactions on Circuits and Systems”, vol. 34, pp. 284 – 288, Mar 1987.

[5]Y. Wang, “Residue-to-binary converters based on new Chinese remainder theorems,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 47, pp. 197 – 205, Mar. 2000.

[6]H. Henkelmann, A. Drolshagen, H. Bagherinia, H. Ahrens and W. Anheier, “Automated implementation of RNS-to-binary converters,” IEEE International Symposium on Circuits and Systems, vol. 2, pp. 137 – 140, May 1998.

[7]B. Cao, C.H. Chang and T. Srikanthan, “An efficient reverse converter for the 4-moduli set {2/sup n/ - 1, 2/sup n/, 2/sup n/ + 1, 2/sup 2n/ + 1} based on the new Chinese remainder theorem,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol. 50, pp.1296 – 1303, Oct. 2003.

[8]A. Skavantzos and T. Stouraitis, “Polynomial residue complex signal processing”, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 40, pp. 342 – 344, May 1993.

[9]S. Sunder, F. El-Guibaly, and A. Antoniou, "Area-efficient diminished-1 multiplier for Fermat number-theoretic transform", IEE Proc., pt. G, vol. 140, no. 3, pp. 211-215, June 1993.

[10] L.M. Leibowitz, "A Simplified Binary Arithmetic for the Fermat Number Transform", IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. ASSP-24, pp 356-359, October 1976.

[11]M. Benaissa, A. Pajayakrit, S.S. Dlay, A.G.J. Holt, "VLSI design for diminished-1 multiplication of integers modulo a Fermat number", IEE proceedings, vol. 135, pp.161-164, May 1988.

[12]A. Skavantzos and F.J. Taylor, “On the polynomial residue number system [digital signal processing]”, vol. 39 , Feb. 1991.

[13]V. Paliouras, A. Skavantzos, and T. Stouraitis, “Low power convolvers using the Polynomial Residue Number System,” IEEE International Symposium on Circuits and Systems, vol. 2, pp. II-748 - II-751, May 2002.

[14]V. Paliouras and A. Skavantzos, "Novel forward and inverse PRNS converters of reduced computational complexity", The 36th Asilomar Conference on Signals, Systems and Computers, vol. 2, pp. 1603 – 1607, Nov. 2002.

[15]M. Abdallah and A. Skavantzov, ”The multipolynomial channel polynomial residue arithmetic system,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol.46, pp.165-171, Feb. 1999.

[16]A. Skavantzos, Z. Sarkari, and T. Stouraitis, "A complex DSP processor using polynomial encoding," IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 2, pp. 1310-1313, May 1989.

[17]Z. Sarkari, A. Skavantzos, and T. Stouraitis, "A reconfigurable systolic array for polynomial multiplication modulo Xn±1", Proceedings of the 21st Southeastern Symposium on System Theory (SSST-89), pp. 460-464, Mar. 1989.

[18]A. Skavantzos, J. Aravena and S. .Gupta, “PRNS approach to fast FIR filtering”, Southeastcon ''90. Proceedings., IEEE , 1-4, Pages:223 – 227, April 1990.

[19]Z.B. Sarkari and A. Skavantzos, “Linear arrays for residue mappers,” Application Specific Array Processors, 1990. Proceedings of the International Conference on , 5-7 , pp. 309 – 316, Sep. 1990.

[20]A. Wrzyszcz and D. Milford, "A new modulo 2a+1 multiplier," IEEE International Conference on Computer Design: VLSI in Computers and Processors, pp. 614-617, Oct. 1993.

[21]A. Skavantzos and N. Mitash, “Computing large polynomial products using modular arithmetic,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 39 , pp. 252 – 254, Apr.1992.

[22]M.G. Parker and M. Benaissa, “GF(pm) multiplication using polynomial residue number systems,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 42, pp. 718 – 721, Nov. 1995.

[23]D.J. Soudris, M.M. Dasigenis, and A. Thanailakis, 2000, "Designing RNS and QRNS Full Adder Based Converters", Proceedings of IEEE Int. Symposium on Circuits and Systems (ISCAS), Vol. 1, pp. 20-23, May 2000.

[24]R-S. Kao, “A multiplier-free fast transform with efficient VLSI implementation for polynomial RNS processors,” Acoustics, Speech, and Signal Processing, 1991. ICASSP-91., 1991 International Conference on , 14-17, pp.1601 – 1604, Apr. 1991.

[25]A. Skavantzos and N. Mitash, “Implementation issues of 2-dimensional polynomial multipliers for signal processing using residue arithmetic,” IEE Proceedings E Computers and Digital Techniques, vol. 140, pp. 45-53, Jan. 1993.

[26]A.B Premkumar, “A Formal Framework for Conversion from Binary to Residue Numbers,” IEEE Trans. Circuits and Systems II: Cites the 1994 VLSI Signal Processing VII paper, vol. 49, pp.135-144, Feb. 2002.

[27]M.G Parker and M. Benaissa, “Fault-tolerant linear convolution using residue number systems,” IEEE International Symposium on Circuits and Systems, vol. 2, pp. 441 – 444, June 1994.