臺灣博碩士論文加值系統

餘數數碼系統(Residue Number System)於算術運算處理時，資料的位元運算結果和相對應位元彼此之間是獨立(Independent)的關係，故餘數數碼系統本身具有無權重，無傳遞延遲(Carry-free)、模組化(Modality)、高平行度(High degree of parallelism) 以及可以減少資料運算長度(Strength)與位元變化(Bit activity)機率等特性。餘數數碼系統的表示是將一個大的整數切割成較小的整數組，然後讓系統內的算數運算能以較少的整數以及以並行的方式且無進位傳遞延遲的狀態下運行，如此一來便可以改善整個系統內的處理速度。除此之外，也因餘數數碼系統結合了無傳遞延遲與無進位等優點，可以降低電路的複雜度與功率的消耗。而餘數數碼系統的這一簡單特性使得他適合應用於一些需要加，減，乘運算諸如：數位訊號處理系統(DSP)，影像處理，容錯偵測(fault-tolerant detection)，密碼(cryptography)等系統。

餘數到二進位數碼的轉換在餘數數碼系統內是相當複雜的，通常此轉換器會影響到餘數數碼系統內的使用效能。而決定一個好的餘數數碼系統的應用取決於轉換模組的類型，而模組類型的選擇主要有三項的設計觀念:餘數數碼系統內部的處理速度、動態範圍(DR)的多寡以及轉換器轉換時的硬體設計的複雜度。另一方面，過去在做餘數到二進位轉換器的轉換演算法中，較常用的方法是中國餘數定理(CRT)、中國餘數定理1(CRT-I)、中國餘數定理2(CRT-II)與混合基底轉換(MRC)。

本研究裡，首先我們提出一組固定式三模組{2n, 2n+1-1, 2n-1}的餘數轉換器，此轉換器將餘數數碼轉換為二近位的數碼是利用了新中國餘數定理2來做轉換方法來達到降低轉換器的硬體成本。當所有模組應用在相同的動態範圍下，我們利用了台積電點18微米製程，分別求出本轉換器與其他具有動態範圍為4n位元寬與5n位元寬且同樣是三模組的轉換器在面積-速度-功率(ADP)乘積的數據做一比較，比較的結果，本模組平均分別比這些模組節省了51.12%與59.26%。

其次，本研究提出了一組具有動態範圍是6n位元同樣是固定式的四模{22n, 22n+1-1, 2n+1, 2n-1}的餘數組，此模組使用新中國餘數定理 2 (New CRT-II)做為模組的餘數轉成二進制的轉換數學來達到降低轉換器的面積，而利用台積電的90奈米製程，本轉換器在面積-速度-功率、面積-速度(AD)與面積-功率(AP)乘積方面分別與其他相關4模的餘數模組應用在相同的動態範圍位元寬度下來做比較，比較的結果。本模組平均可節省36.49%，20.66%與49.65%。除此之外，本研究也設計了具有(n+k)-模式的可調式模組，藉著調變k值由0到n來平衡模組的延遲路徑。而利用這k值的改變也可以適當的改變模組的動態範圍來達到電路硬體的最大利用。再者藉由調變k值，我們可以克服固定式餘數到二進制轉換器的過範圍設計問題。在已知應用的資料範圍，固定式模組的過範圍比值會隨著所應用的資料範圍的改變而在1.99至63.99的這個範圍內作週期性的改變、另一方面，我們研究的可調式模組即使在所應用的資料範圍改變了，可一直保持在1.99這個過範圍比值，所以於硬體的實驗結果，同時可達到降低轉換器的面積，增加轉換器的運算速度與降低轉換器的功率消耗問題。因此，第三點，我們設計出一組新的3模組，不具有(2n+1)，可調變式的{2n+k, 2n-1, 2n-1-1}模組，而此模組是由{2n, 2n-1, 2n-1-1}這個模組變化而來的。相較之下，本研究提出的這個(n+k)-模組就是為了降低其他固定式的3模組轉換硬體電路的複雜度。而本模組轉換電路的數學轉換是利用混合基底轉換方式來完成轉換。經由台積電點18微米技術的電路設計，本模組在與{22n, 2n-1, 2n-1-1}，{22n, 2n-1, 2n+1-1}和{22n-1-1,2n, 2n-1}做比較之下，在面積-延遲(AD)，面積-功率(AP)與面積-延遲-功率的乘積的比較，分別可達到最大的49.86%，42.18%與52.96%的節省值。

最後，本文發表了新的一組同樣是可調式，4模組的{2n+k, 2n-1, 2n+1, 22n+1}轉換器模組，此模組的可調式動態範圍同樣是用來克服固定式轉換器過範圍設計的問題。而此模組不僅比已經存在的可調式3模組化的轉換器還具有較好的平行度與較大的動態範圍而且也比一般固定式且是4模組的轉換器具有較大的彈性化。藉由擴展k值能有效的得到較小的n值用以來增快本模組臨界通道的速度。除此之外，此模組是利用中國餘數定理(CRT)來做為轉換器的餘數到二進制的數學轉換方式，經實驗的結果，本可調式模組具有較少的面積與較快的轉換速度。最後藉由台積電點18微米技術之下製作本轉換器，本轉換器與其他兩組較優的模組在ADP上做一比較，比較之下，本轉換器分別平均可節省53.01%與25.13%。

Residue number system (RNS), which is a non-weighted number system that exhibit carry-free, modality, and high parallelism properties, reduces word strength and bit activity because no digital dependence exists between the result and each operand. RNS represents a large integer in slices of small integers. Arithmetic operations performed on large integers can now be performed on small integers in parallel without carry propagation, thus improving the processor speed. Additionally, because of the lack of complex hardware associated with carry generation and propagation, the RNS assists in reducing hardware complexity and the associated power consumption. This is because this simple feature of RNSs renders them highly suitable for the implementation of computationally intensive digital signal processing (DSP), image processing, fault-tolerant detection, and cryptography, where only addition, subtraction, and multiplication are required.

Reverse conversion of a residue to a binary number is considerably more complex and often offsets the performance improvements that are gained by using the RNS. One of the key factors for determining the performance of a successful RNS application is the form of the moduli set because it targets three critical design concepts: internal RNS processing speed, dynamic range (DR), and hardware design complexity of the reverse conversion. Furthermore, design of efficient reverse converters has attracted much interest in the past several decades, and has involved many algorithms, including Chinese remainder theorem (CRT), new Chinese remainder theorem-I (New CRT-I), new Chinese remainder theorem-II (New CRT-II), and mixed-radix conversion (MRC).

An efficient reverse converter design for the three-moduli set {2n, 2n+1-1, 2n-1} is presented in this dissertation. The reverse converter was achieved using an adder-based implementation of New CRT-II conversion to improve the related three-moduli set {2n, 2n-1-1, 2n-1} on the performance of the hardware cost. Furthermore, the proposed conversion technique was compared with earlier realizations described in the literature regarding the three-moduli set. Because DR can be equal to 4n-bit and 5n-bit requirements, the theoretical evaluation was supported by the experimental results, which were estimated using Standard Cell TSMC 0.18-μm CMOS technology. These experimental results indicated that the area-delay-power (ADP) for the same DR of the proposed New-CRT-II-based converter achieved an approximate average reduction of 51.12% and 59.26% for the 4n-bit and 5n-bit dynamic ranges, respectively.

A four-moduli set {22n, 22n+1-1, 2n+1, 2n-1} with a 6n-bit DR is also proposed, which is appropriate for RNS applications. Furthermore, an efficient algorithm for residue-to-binary (R-to-B) conversion was derived based on New CRT-II. Based on TSMC 90-nm CMOS technology, the converter hardware was designed to achieve averages of 36.49%, 20.66%, and 49.65% in ADP performance saving, area-delay (AD), and area-power (AP), respectively, compared with the latest converter using a four-moduli set under the same DR requirement. Additionally, an adaptable (n+k)-mode moduli set was designed by varying k from 0 to n, and it was possible to balance the delay path of the moduli set. Another advantage of using k was that the dynamic range could be tuned appropriately for maximum usage of the hardware. Moreover, by turning k, for the given application data range, the fixed modulie set has a periodic change of over-range ratio from 1.99 to 63.99 when application data range is modified. On the other hand, our adaptable module set can continuously keep the ratio 1.99. Then, the experimental results with hardware implementations are used to demonstrate that the converter designs with lower over-range ratio have better performances in terms of area, delay and power consumption. Therefore, a new (2n+1)-free, adaptable, three-moduli set of reverse converters for {2n+k, 2n-1, 2n-1-1} is proposed, which is an enhancement of the three-moduli set {2n, 2n-1, 2n-1-1}. The proposed (n+k)-mode moduli set assists in reducing the hardware complexity of the arithmetic circuits compared with other three-moduli sets. MRC was used to achieve adder-based arithmetic. Based on TSMC 0.18-μm CMOS technology, the proposed reverse converter is up to 49.86%, 42.18%, and 52.96% savings of AD, AP, and ADP than the designs of {22n, 2n-1, 2n-1-1}, {22n, 2n-1, 2n+1-1}, and {22n-1-1,2n, 2n-1}, respectively.

Finally, a novel, adaptable four-moduli set {2n+k, 2n+1, 2n-1, 22n+1} is presented. It offers diverse DRs that can resolve the over-range problem in RNS hardware design. The proposed adaptable set possesses the coarse parameter n and fine parameter k. It not only exhibits greater parallelism and larger DR than existing adaptive three-moduli sets, but is also more sizable and flexible than general four-moduli sets, which contain a single parameter. Moreover, the proposed set can effectively shrink the value of n to speed up the critical modulo channel by enlarging k. To achieve R-to-B conversion, a fast, reverse-converting algorithm was derived, based on CRT, and the efficient converter architecture is presented in this dissertation. The experimental results revealed that the proposed adaptable converter has a low hardware cost and high operation speed. Based on TSMC 0.18-μm CMOS technology, the proposed converter design can achieve ADP average savings of 53.01% and 25.13%, compared with the two most recent studies involving general four-moduli sets.

Abstract (Chinese) i

Abstract (English) iii

Acknowledgements vi

List of Contents vii

List of Tables ix

List of Figures x



Chapter 1 Introduction

1.1 Motivations 1

1.2 Main Contributions of This Work 2



Chapter 2 Residue Number System (RNS)

2.1 Instruction 3

2.2 Basic Definitions of Residue Number System 3

2.3 The Representation for Inverse Modulo in RNS 7

2.4 Operations in the Residue Number System- 7

2.4.1 Modular Addition 8

2.4.2 Modular Subtraction 9

2.4.3 Modular Multiplication 10

2.5 Theorem for Residue Number System 11

2.6 Multiplicative Inverse 13

2.6.1 Solving Linear Equation 13

2.6.2 The Cancellation Law of Multiplication 13

2.6.3 Existence of Multiplication Inverse 13

2.7 Conversion in Residue Number System 15

2.7.1 Binary to Residue Conversion (B/R converter) 15

2.7.2 Residue to Binary Conversion (R/B Converter) 16

2.8 Relative theorem 24



Chapter 3 Efficient Residue-to-Binary Conversion Modulo for the Fixed-Moduli Set

3.1 Design of Fixed-Modulo Reverse Converter for Three-moduli set {2n, 2n+1-1, 2n-1}------------------------------------------------------------------------------------26

3.1.1 Introduction 26

3.1.2 Residue-to-Binary Conversion Algorithm 27

3.1.3 Hardware Architecture Design 31

3.1.4 Performance Evaluation 32

3.1.5 Conclusion 33

3.2 Design of Fixed-Modulo Reverse converter for Four-moduli set {22n, 22n+1-1, 2n+1, 2n-1} 36

3.2.1 Introduction 36

3.2.2 Residue-to-Binary Conversion Algorithm 36

3.2.3 Hardware Architecture Design 39

3.2.4 Performance Evaluation 40

3.2.5 Conclusion 43



Chapter 4 Efficient Residue-to-Binary Conversion Modulo for an Adaptable-Moduli Set

4.1 Design for Adaptable Reverse converter for Three-Moduli Set {2n+k, 2n-1, 2n-1-1} 44

4.1.1 Introduction 44

4.1.2 Residue-to-Binary Conversion Algorithm 45

4.1.3 Hardware Architecture Design 48

4.1.4 Performance Evaluation 48

4.1.5 Conclusion 51

4.2 Design for Adaptable Reverse converter for Four -Moduli Set {2n+k, 2n+1, 2n-1, 22n+1} 51

4.2.1 Introduction 52

4.2.2 Residue-to-Binary Conversion Algorithm 53

4.2.3 Hardware Architecture Design 61

4.2.4 Performance Evaluation 62

4.2.5 Conclusion 65



Chapter 5 Conclusion and Future Studies

5.1 Conclusion 66

5.2 Future Studies 67

References 69

Biography 73

Publication List 74

[1]B. Parhami, Computer arithmetic: algorithms and hardware Design, 2nd Edition,

Oxford University Press, New York, 2010.

[2]K. Andra, C. Chakrabarti, T. Acharya, ” A VLSI Architecture for Lifting-Based Forward and Inverse Wavelet Transform,. ” IEEE Trans. Signal Processing, Vol. 50, pp. 966-977, April 2000.

[3]R. Zimmermann, “Efficient VLSI Implementation of modulo (2n狰1) addition and multiplication,” in Proc. 14th IEEE Symp. Computer Arithmetic, Adelaide, Australia, Apr. 1999.

[4]K.A. Gbolagade and S.D. Cotofana. Residue number system operands to decimal conversion for 3-moduli sets. Proceedings of 51st IEEE Midwest Symposium on Circuits and Systems,pp.791-794, Knoxville, USA, August, 2008.

[5]A.A. Hiasat and H.S. Abdel-AtyZohdy. Residue -to-binary arithmetic converter for the moduli set {2k, 2k −1, 2k−1−1}. IEEE Transactions on Circuits and Systems-II Analog and Digital Signal Processing, Vol.45, No. 2, pp. 204-209, Feb.,1998.

[6]A.S. Molahosseini and K. Navi. New arithmetic residue to binary converters. International Journal of Computer Sciences and Engineering Systems, Vol. 1, No.4, pp. 295-299, October, 2007.

[7]P.V.A. Mohan. Rns-to-binary converter for a new three-moduli set {2n+1-1, 2n, 2n-1}. IEEE Trans. on Circuits and Systems-II: Express briefs, Vol. 54, No.9, pp. 775-779, September, 2007.

[8]M. Sheu S. Lin and C. Wang. Efficient vlsi design of residue to binary converter for the moduli set {2n,2n+1−1,2n−1}. IEICE Trans. INF. and SYST., Vol. E91-D, No.7, pp. 2058-2060, July,2008.

[9]A.S. Molahosseini et al., “A new residue to binary converter based on MRC,” 3rd Int. Conf. on ICTTA, pp. 1-6, 2008.

[10]K.A. Gbolagade et al., “An improved RNS reverse converter for the {22n+1−1, 2n, 2n−1} moduli set,” Proceedings of IEEE Int. Symp. on ISCAS, pp. 2103- 2106, 2010.

[11]A. S. Molahosseini et al., “A new design of reverse converter for a three-moduli set,” Inte. Symp. on ISPACS, pp. 57-60, 2009.

[12]A. S. Molahosseini et al., “Efficient MRC-Based Residue to Binary Converers for the New Moduli Sets {22n, 2n-1, 2n+1-1} and {22n, 2n-1, 2n-1-1},” IEICE Trans. on Inf. &; Syst., vol. E92. D, no. 9, pp. 1628-1638, 2009.

[13]A. S. Molahosseini et al., “A Reduced- Area Reverse Converter for the Moduli Set {2n, 2n-1, 22n-1-1},” Int. J. of Advan. in Comput.Technology, vol. 2, no. 5, pp. 61-65, 2010.

[14]K.A. Gbolagade et al., “Residue-to- Binary Converters for the Moduli Set {22n+1−1, 22n, 2n−1},” 2nd Int. Conf. on ICAST, pp. 26-33, 2009.

[15]A. Afsheh, et. al., An improved reverse converter for moduli set (2n−1, 2n, 2n+1), Intl. Symp. on Communications and Information Technologies, pp. 928-933, Oct. 2010.

[16]W. Wang, et. al., A high-speed residue-to-binary converter for three-moduli (2k, 2k-1, 2k-1-1) RNS and a scheme of its VLSI implementation, IEEE Trans. Circuits. Syst.II, vol.47. no. 12, pp. 1576-1581, 2000.

[17]M. Hosseinzadeh, et al., An improved reverse converter for the moduli set {2n−1, 2n, 2n+1, 2n+1−1},”IEICE Electronics Express, vol 5. no. 17, pp.672-677, 2008.

[18]W. Zhang et. al., An efficient design of residue to binary converter for four moduli set {2n-1, 2n+1, 22n-2, 22n+1-3} based on new CRT II, Elsevier J. Inf. Sci., pp. 264–279, 2008.

[19]Leonel Sousa and Samuel Antao, MRC-Based RNS Reverse Converter for the Four-Moduli Sets {2n+1, 2n-1, 2n, 22n+1-1} and {2n+1, 2n-1, 22n, 22n+1-1}, IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 59, no. 4, pp. 244-248, Apr. 2012.

[20]C. Efstathiou, H. T. Vergos, and D. Nikolos, Fast parallel-prefix modulo 2n+1adder, IEEE Trans. Comput., vol. 53, no. 9, pp.1211-1216, 2004.

[21]Y. Wang, X. Song, M. Aboulhamid, and H. Shen. “Adders based residue to binary numbers converters for (2n-1, 2n, 2n+1),” IEEE Trans. Signal Process., vol. 50, no. 7, pp. 1772-1779, Jul. 2002.

[22]A. Hiasat and A. Sweidan , “Residue number system to binary converter for the modili set (2n-1, 2n-1, 2n+1),” Elsevier J.Syst. Architect. vol. 49, pp. 53-58, 2003.

[23]Su-Hon Lin, Ming-Hwa Sheu, Chao-Hsiang Wang and Yuan-Ching Kuo, “Area-time-power efficient VLSI design for residue-to-binary converter based on moduli set (2n, 2n+1−1, 2n−1)” IEEE Asia Pacific Conference on Circuits and Systems. no. 30, pp. 168-171, Dec. 2008.

[24]Wang W, Swamy M.N.S, Ahmad M.O and Wang Y. “A study of the residue-to-binary converters for the three-moduli sets,” IEEE Trans. Circuits Syst. I, vol. 50, no. 2, pp.235-243, Feb. 2003.

[25]Su-Hon Lin, Ming-Hwa Sheu, Jing-Shiun Lin and Wen-Tsai Sheu, “Efficient VLSI design for RNS reverse converter based on new moduli set (22n+1, 2n+1,2n-1), ” IEEE Asia Pacific Conference on Circuits and Systems. pp. 2020-2023, Dec. 2006.

[26]K. A. Gbolagade, R. Chaves, L. Sousa and S. D, “An improved RNS reverse converter for the {22n+1−1, 2n, 2n−1} moduli set,” Proceedings of IEEE Int. Symp. on ISCAS, pp. 2103- 2106, 2010.

[27]A. Riyaz and B. Said, “Fast parallel-prefix architectures for modulo 2n-1 addition with a single representation of zero,” IEEE Trans on.Comput., vol. 56, no.11, pp.1484-1492, Nov. 2007.

[28]S. H. Lin, M. H. Sheu, C. H. Wang, and Y. C. Kuo, “Area-time-power efficient VLSI design for residue-to-binary converter based on moduli set (2n, 2n+1-1, 2n-1),” IEEE Asia Pacific Conf. Circuits and Systems, pp. 169-171, 2008.

[29]K.A. Gbolagade et al., “An improved RNS reverse converter for the {22n+1−1, 2n, 2n−1} moduli set,” IEEE Int. Symp. on ISCAS, pp. 2103- 2106, 2010.

[30]A .Hariri, K. Navi, and R. Rastegar. “A new high dynamic range moduli set with efficient reverse converter,” Elsevier Journal of Computers and Mathematics with Applications, vol. 55, issue 4, pp. 660-668, 2008.

[31]B. Cao, T. Srikanthan, and C. H. Chang, “Efficient reverse converter for the four-moduli sets {2n-1; 2n, 2n+1; 2n+1+1} and {2n-1, 2n, 2n+1, 2n-1-1},” Proc. IEE Comput. Digit. Tech., vol. 152, no. 5, pp. 687-696, Sep. 2005.

[32]P. V. A. Mohan, A. B. Premkumar, “RNS-to-Binary converters for two four-moduli sets {2n-1, 2n, 2n+1, 2n+1–1} and {2n-1, 2n, 2n+1, 2n+1+1},” IEEE Trans. Circuits Syst. I. vol. 54, no. 6, pp. 1245-1254, 2007.

[33]A.S. Molahosseini, F. Teymouri, and K. Navi, “A new four-modulus RNS to binary converter,” Proc. of IEEE Int. Symp. on ISCAS, pp. 4161- 4164, 2010.

[34]B. Cao, C. H. Chang, and T. Srikanthan, “An efficient reverse converter for the 4-moduli Set (2n-1, 2n, 2n+1, 22n+1) based on the new Chinese remainder theorem,” IEEE Trans. Circuits Syst. I, vol. 50, no. 10, pp. 1296–1303, Oct. 2003.

[35]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 Syst. I, vol. 57, no. 4, pp. 823-835, Apr. 2010.

[36]L. Sousa and S. Antao, “MRC-based RNS reverse converter for the four-moduli sets {2n+1, 2n-1, 2n, 22n+1-1} and {2n+1, 2n-1, 22n, 22n+1-1},” IEEE Trans. Very Large Scale Integer(VLSI) Syst., vol. 59, no. 4, pp. 244-247, Apr. 2012.

[37]W. Zhang and P. Siy, “An efficient design of residue to binary converter for four moduli set {2n-1, 2n+1, 22n-2, 22n-3} based on new CRT II,” Elsevier J. Inf. Sci., vol. 178, no. 1, pp. 264–279, Jan. 2008.

[38]R. Chaves, and L. Sousa. “{2n + 1, 2n+k, 2n - 1}: a new RNS moduli set extension,” Proc. of the Euromicro Symposium on Digital System Design, pp. 210-217, Sep. 2004.

[39]G. Chalivendra, V. Hanumaiah, and S. Vrudhula,, “A new balanced 4-moduli set {2k, 2n - 1, 2n + 1, 2n+1-1} and its reverse converter design for efficient FIR filter implementation,” Proc. of the Great Lakes Symposium on VLSI, pp. 139-144, 2011.

[40]C. H. Chang and J. Low, “Simple, fast, and exact rns scaler for the three moduliset,” IEEE Trans. Circuits Syst I., vol. 58, no. 11, pp. 2686 –2697, November. 2011.