近年來，基數減1的模組(2n+1) 乘法器，有許多種做法。在此論文裡，我提出了一種新做法，專門針對基數減1的模組(2n+1) 乘法器，並且衍生出其它電路。
本論文提出2種一系列餘數乘法器，第一種應用在模數(2n+1)，比較於前人作法，在數據方面比較優良，並且不需要特別做偵測真實零的電路。
第二種是改良第一種，可以整合5種模數(2n+1)，2n，(2n-1)，(2n+1+1)，(2n+11)，利用加一些多工器，分工器，及少許電路，即可整合5種模數之餘數乘法器。
基本構想就是利用減法，這個理論不只可以用來表示基數減1的模數(2n+1) 乘法器，進而達到減少面積與功率上的消耗，更可以利用硬體共用之做法，來選擇模組(2n-1) 與2n與(2n+1-1)普通乘法器，更能產生過往作法不能產生的模數(2n+1+1)的基數減1乘法器，也就是可切換式多模數乘法器，還能夠節省偵測真實零的硬體電路消耗。

誌謝…………………………………………………………………. ii
中文摘要…………………………………………………………..... iii
List of Contents……………………………………………………... IV
List of Figures……………………………………………………… VI
List of Tables……………………………………………………….. VII
Chapter 1. 介紹………………………………………………….. 1
1.1 動機與RNS基礎流程介紹……………………….................. 1
1.2 動機與研究故事…………………..………………………….. 3
1.3 論文大綱……………………………………………................. 4
Chapter 2. 運算與架構……………………………….…………... 5
2.1 Wallice與Dadda 演算法的運算區別與討論………..……… 5
2.2 餘數乘法器中全加減器的實現………………….………….. 6
2.3 餘數乘法器的實現(即非基數減1)………………………….. 10
2.4 套用Wallice 演算法的基數減1之2n+1餘數乘法器………... 13
2.5 套用Dadda 的基數減1之2n+1餘數乘法器…………………. 17
Chapter 3. 改善公式，架構，與規則性之推導及應用…............ 20
3.1 加減法器之實現……………………………………………… 20
3.2 針對2n+1的基數減1之餘數乘法器…………………………. 21
3.3 多共用模數的基數減1之2n+1餘數乘法器………………….. 25
3.4 負數規則性與推導…………………………………………….. 29
3.5 可變換式的多模數乘法器(Multi-Modulo Multiplier)………… 40
3.6 Detection bit說明……………………………………………… 48
Chapter 4. 數據比較……………………………………………….. 53
4.1 Using strict delay constraints…………………………………… 53
Chapter 5. 結論…………………………………………………… 55
Reference ……………………………………………………… 60

[1] F. Taylor, “A Single Modulus ALU for Signal Processing,” IEEE Trans. Acoustics, Speech, and Signal Processing, vol. 33, pp. 1302-1315, 1985.
[2] E.D. DiClaudio, F. Piazza, G. Orlandi, “Fast Combinatorial RNS Processors for DSP Applications,” IEEE Trans. Computers, vol. 44, pp. 624-633, 1995.
[3] J. Ramirez, A. Garcia, S. Lopez-Buedo, A. Lloris, “RNS-Enabled Digital Signal Processor Design,” IEEE Electronics Letters, vol. 38, no. 6, pp. 266-268, 2002.
[4] R. Chaves and L. Sousa, “RDSP: A RISC DSP Based on Residue Number System,” in Proc. Euromicro Symp. Digital Systems Design, Sept. 2003, pp. 128-135.
[5] A. S. Ashur, M. K. Ibrahim, A. Aggon, “Novel RNS structures for the moduli set(2n-1, 2n, 2n+1) and their application to digital filter implementation”, Signal Processing, vol.46, pp.331-343, 1995.
[6] M. Soderstrand, K. Jenkins, G. Jullien, F. Taylor, Residue Number System Arithmetic: Modern Applications in Digital Signal Processing, IEEE Press, New York, 1986.
[7] F. Taylor, “A VLSI residue arithmetic multipliers”, IEEE Trans, Comput., vol. c-31, no. 6, pp. 540-546, 1982.
[8] L.M. Leibowitz, “A Simplified Binary Arithmetic for the Fermat Number Transform,” IEEE Trans Acoustics, Speech, and Signal Processing, vol. 24, pp. 356-359, 1976.
[9] T.K. Truong, J.J. Chang, I.S. Hsu, D.Y. Pei, I.S. ReeD, “Techniques for Computing the Discrete Fourier Transform Using the Quadratic Residue Fermat Number Systems,” IEEE Trans. Computers, vol. 35, pp. 1008-1012, 1986.
[10] M. Benaissa, A. Bouridane, S.S. Dlay, A.G.J. Holt, “Diminished-1 Multiplier for a Fast Convolver and Correlator Using the Fermat Number Transform,” IEE Proc. G, vol. 135, pp. 187-193, 1988.
[11] S. Sunder, F. El-Guibaly, A. Antoniou, “Area-Efficient Diminished-1 Multiplier for Fermat Number-Theoretic Transform,” IEE Proc. G, vol. 140, pp. 211-215, 1993.
[12] R. Zimmermann, A. Curiger, H. Bonnenberg, H. Kaeslin, N. Felber, W. Fichtner, “A 177 Mb/s VLSI Implementation of the International Data Encryption Algorithm,” IEEE J. Solid-State Circuits, vol. 29, no. 3, pp. 303-307, 1994.
[13] B. Cao, C.H. Chang, T. Srikanthan,”An Efficient Reverse Converter for the 4-Moduli Set{2 n -1, 2 n, 2n + 1, 22n + 1}Based on the New Chinese Remainder Theorem,” IEEE T Trans. Circuits and Systems—I: FUNDAMENTAL THEORY AND APPLICATIONS, vol. 50, no. 10, 2003.
[14] B. Cao, C.H. Chang, T. Srikanthan,”New Efficient Residue-to-Binary Converters for 4-Moduli Set (2n - 1,2n, 2n + 1,2n+1 - l },” IEEE International Symposium on Circuits and Systems, 2003, vol 4, pp. IV-536 - IV-539.
[15] B. Cao, T. Srikanthan, C.H. Chang, “Efficient reverse converters for four-moduli sets {2n-1, 2n, 2n+1, 2n+1 - 1} and {2n-1, 2n, 2n+1, 2n-1 - 1},” IEE Proc.-Comput. Digit. Tech., Vol. 152, No. 5, 2005.
[16] A. S. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei, and S. Timarchi, “Efficient Reverse Converter Designs for the New 4-Moduli Sets {2n-1, 2n, 2n+1, 22n+1 - 1}and {2n-1, 2n+1, 22n, 22n + 1} Based on New CRTs,” IEEE Trans. Circuits and Systems—I: REGULAR PAPERS, vol. 57, no. 4, pp.823-835, 2010.
[17] C. Efstathiou, H. T. Vergos, G. Dimitrakopoulos, & D. Nikolos,” Efficient modulo 2n+1 tree multipliers for diminished-1 operands,” ICECS, vol.1, pp.200-203, 2003.
[18] C. Efstathiou, H. T. Vergos, G. Dimitrakopoulos, & D. Nikolos “Efficient Diminished-1 Modulo 2n+1 Multipliers,” IEEE Trans. Computers, vol. 54, no. 4, 2005
[19] L. Dadda, “Some Schemes for Parallel Multipliers,” Alta Frequenza, vol. 34, pp. 349-356, 1965.
[20] R. A. Hall, S. Ragunathan, E. Earl, “A Comparison of Timing Delays for 32-bit Wallace and Dadda Multipliers in 0.18 Micron Technology,” ACISC ,May 15, 2007.
[21] T. Y. Chang, J. R. Huang, H. Y. Lo, P. S. Wang, and K. Yang,”The On-the-fly Circuits That Can Be Applied to Array Multiplier and Fast Gray Code Adder” Proc. 43rd IEEE Midwest Symp. on Circuits and Systems, Lansing MI, vol.1, Aug, 2000, pp342-345.
[22] K. Hwang, Computer Arithmetic Principles, Architecture, and Design, in section 6.3, John Wiley & Sons, NY, 1979.
[23] Z. Wang, G. A. Jullien , W. C. Miller, "An Efficient Tree Architecture for Modulo 2n+1 multiplication", J. of VLSI Signal Processing, vol.14, pp. 241-248, 1996.
[24] M. Bhardwaj, T. Srikanthan, and C. T. Clarke, “A reverse converter for the 4-moduli superset {2n-1, 2n, 2n+1, 2n+1 + 1},” in Proc. 14th IEEE Symp. Computer Arithmetic, Adelaide, Australia, Apr. 1999, pp. 168–175.
[25] A. P. Vinod and A. B. Premkumar, “A memoryless reverse converter for the 4-moduli superset {2n-1, 2n, 2n+1, 2n+1 - 1},” J. Circuits, Syst., Comput., vol. 10, no. 1&2, pp. 85–99, 2000.
[26] B. Cao, C. H. Chang, and T. Srikanthan, “A residue-to-binary converter for a new five-moduli set,” IEEE Trans. Circuits Syst. I, Reg. Papers, vol. 54, no. 5, pp. 1041–1049, 2007.
[27] H. T. Vergos, C. Efstathiou, and D. Nikolos, “Diminished-one modulo 2n + 1 adder design,” IEEE Trans. Computers, vol. 51, no. 12, pp. 1389–1399, 2002.
[28] C. Efstathiou, H. T. Vergos, and D. Nikolos, “Modulo 2n ± 1 adder design using select-prefix blocks,” IEEE Trans. Computers, vol. 52, no. 11, pp. 1399–1406, 2003.
[29] S.-H. Lin and M.-H. Sheu, “VLSI design of diminished-one modulo 2n +1 adder using circular Carry selection,” IEEE Trans. Circuits Syst. II, Exp.Briefs, vol. 55, no. 9, pp. 897–901, 2008.
[30] T.-B. Juang, M.-Y. Tsai, and C.-C. Chiu, “Corrections on ‘VLSI design of diminished-one modulo 2n + 1 adder using circular Carry selection,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 56, no. 3, pp. 260–261, 2009.
[31] Y. Ma, “A Simplified Architecture for Modulo (2n +1) Multiplication,” IEEE Trans. Computers, vol. 47, no. 3, pp. 333-337, Mar. 1998.