臺灣博碩士論文加值系統

在本論文中主要的研究重點在於將外部輸入的數位訊號，利用我們新三餘數模組{2^(2n), 2^(n)+1, 2^(n)-1}構成的餘數系統進行運算。因為隨著電子產品數位化的趨勢，在數位訊號處理的硬體系統領域逐漸受注意，若使用二進制系統會增加效能的負擔，數位信號處理器的發展在相關的應用包含數位濾波器、頻譜分析、影像壓縮與錯誤容錯…等，均需大量與快速之平行計算，於是在眾多數碼系統中考慮了餘數系統；因它具有無傳遞延遲、模組化及高平行度等等特性，使它具有好的效能。而此模組的最大貢獻在餘數/二進制轉換器在做完合成分析後與其它[25-30]三餘數模組在相同動態範圍下相比，其對應到的轉換時間與功率消耗至少分別皆會省下50%、28%，若再進一步將三個與餘數/二進制轉換器相關的主要因素:功率、時間、面積的合成結果做乘積的分析，證實新模組與[25-30]在相同動態範圍32、64、128 位元下，效能至少也能省56%、59%、63%；最後將其餘數/二進制轉換器利用Verilog 硬體描述語言及TSMC 0.18μm 製程結合下的Cell-Based 設計流程完成 。在動態範圍32-bits 下，整個晶片的面積達1035.5*940 (μm^2)，操作頻率可以到達100 MHz。並且我們將應用在通訊系統架構中不可或缺的無限脈衝響應數位濾波器上。

In this paper the focus is using our new three moduli set - {22n, 2n +1, 2n-1}
to constitute the residue number system (RNS) to deal with external input digital signal. Because along with electronic products digitizing tendency, many systems include DSP algorithms for various applications, such as digital filter, spectrum analysis, image compression and processing, fault tolerant etc. These applications always require a large number of arithmetic computations in loop, and have to be implemented as VLSI chip for achieving real-time and low-power operations. However, the engineers are gradually recognizing that the binary system with long bit-width will degrade the whole hardware performance due to carry propagation. Many design engineers may consider the RNS for hardware architecture design because it possesses carry-free and parallel merits. By the synthesis, our residue-to-binary converter compare with [25-30], we can get the analysis that the corresponding conversion time and power consumption would save 50%, 28% at least. Besides, the mainly factors (power, delay, area) multiply of the synthesis results, it can be confirmed, our performance can save 56%, 59%, 63% when DR at 32-bits, 64-bits, 128-bits.After the HDL simulations and logic synthesis by TSMC 0.18μm process in DR 32-bits, the chip area is 1035.5*940 (μm2), and its operation speed can achieve 100 MHz .And we will application to 3-set RNS IIR architecture.

摘要 .................................................i
ABSTRACT ...................................................................ii
誌謝 ......................................................................iii
目錄 ...................................................................... iv
圖目錄 ............... .....................................................vi
表目錄 ....................................................................vii
第一章、餘數系統之緒論 ..................................................... 1
1-1、研究動機 .............................................................. 1
1-2、研究目標及論文摘要 .................................................... 1
1-3、前言 .................................................................. 2
1-3-1、餘數系統與二進制系統的差異 .......................................... 2
1-4、餘數系統之定義 ........................................................ 4
1-5、餘數系統之架構介紹 .................................................... 6
1-5-1、二進制/餘數轉換器(B-to-R converter, Binary-to-Residue) .............. 6
1-5-2、餘數基本運算定理與特性 ...............................................6
1-5-3、餘數/二進制轉換器(R-to-B converter, Residue-to-Binary)............... 9
第二章、高效能餘數/二進制轉換器之設計 ..................................... 13
2-1、前言 ................................................................. 13
2-2、新餘數模組的特色介紹 ................................................. 13
2-3、快速餘數/二進制轉換演算法推導 .........................................14
2-4、快速餘數/二進制轉換器之VLSI 實現 ..................................... 19
2-5、本章結論 ............................................................. 23
第三章、以3-moduli set 實現Infinite Impulse Response Filter 系統設計 ...... 24
3-1、濾波器導論與IIR 設計技巧 ............................................. 24
3-1-1、前言 ............................................................... 24
3-1-2、濾波器導論 ......................................................... 24
3-1-3、IIR 設計技巧 ....................................................... 27
3-2、RNS 與IIR 之結合與實現 ............................................... 29
3-2-1、基架構圖 ........................................................... 29
3-2-2、硬體評估 ........................................................... 30
3-3、效能評估 ............................................................. 36
第四章、結論與未來研究方向 ................................................ 36
參 考 文 獻 ............................................................... 37
附錄一、碩士班口試之Q&A 彙整. ............................................. 42

[1] Bernocchi, G.L.; Cardarilli, G.C. et. al., “A Hybrid RNS Adaptive Filter for Channel Equalization,” Fortieth Asilomar Conf. on Signals, Systems and Computers, pp.1706–1710 , Oct. 29, 2006.
[2] Bernocchi, G.L. ; Cardarilli, G.C. ; Del Re, A. ; Nannarelli, A. ; Re, M.,
“Low-Power A-daptive Filter Based on RNS Components”. IEEE ISCAS, pp.
3211 – 3214, May, 2007
[3] Shahana, T.K. ; James, R.K. et. al., “Performance Analysis of FIR Digital Filter Design: RNS Versus Traditional,” Int. Symp. on Communications and Information Technologies, pp. 1–5, Oct. 2007.
[4] Smitha, K.G. ; Vinod, A.P., “A Reconfigurable High-speed RNS-FIR Channel Filter for Multi-Standard Software Radio Receivers,” IEEE Int. Conf. on Communication Systems, pp. 1354 – 1358, Nov. 2008.
[5] Are, R.B. ; Rajan, K., “An RNS Based Transform Architecture for H.264/AVC,” IEEE TENCON , pp. 1–6, Nov. 2008.
[6] Cardarilli, G.C. ; Del Re, A. ; Nannarelli, A. ; Re, M., “Impact of RNS Coding Overhead on FIR Filters Performance,” Asilomar Conf. on Signals, Systems and Computers, pp. 1426–1429, Nov. 2007.
[7] Pontarelli, S. ; Cardarilli, G.C. ; Re, M. ; Salsano, A., “Totally Fault Tolerant RNS Based FIR Filters,” 14th IEEE International On-Line Testing Symposium, pp. 192-194, 7-9 July 2008.
[8] Zhining Lim ; Phillips, B.J., “An RNS-Enhanced Microprocessor Implementation ofPublic Key Cryptography,” Asilomar Conference on Signals, Systems and Computers, pp. 1430–1434, 4-7 Nov. 2007.
[9] Bajard, J.-C. ; Imbert, L., “Brief Contributions: A Full RNS Implementation of RSA,” IEEE Transactions on Computers, Vol. 53, Issue: 6, June 2004.
[10] Wei Wang ; Swamy, M.N.S. ; Ahmad, M.O. “RNS Application for Digital Image
Processing,” IEEE International Workshop on System-on-Chip for Real-Time
Applications, pp. 77–80, July 2004.
[11] Pontarelli, S. ; et. al., “A Novel Error Detection and Correction Technique for RNS Based FIR Filters,” IEEE Int. Symp. on Defect and Fault Tolerance of VLSI Systems, pp. 436–444, Oct. 2008.
[12] Tomczak, T., “Fast Sign Detection for RNS {2n-1, 2n, 2n+1} ,” IEEE Transactions on Circuits and Systems I: Regular Papers, Volume : 55, Issue:6 , pp. 1502 – 1511, July 2008.
[13] Vinnakota, B., and Rao,V.B.B. “Fast conversion techniques for binary-residue number systems,” IEEE Transactions on Circuits and Systems, vol.41, pp. 927–929, Dec. 1994.
[14] Freking, W.L., Parhi, K.K. “Low-power FIR digital filters using residue arithmetic”Conference Record of the Thirty-First Asilomar Conference on Signals, Systems & Computers, 1997. vol.1 , pp. 739 - 743 ,2-5 Nov. 1997.
[15] Hiasat, A.A., “Arithmetic binary to residue encoders for moduli (2/sup n//spl plusmn/ 2/sup k/+1)” IEE Proceedings Computers and Digital Techniques, vol. 150 , pp. 369 – 374, 17 Nov. 2003.
[16] Piestrak, S.J. ” Design of residue generators and multioperand modular adders using carry-save adders” IEEE Transactions on Computers and Systems, vol. 43 ,pp.68 – 77, Jan. 1994.
[17] Premkumar, A.B.” A formal framework for conversion from binary to residue
numbers” IEEE Transactions on Circuits and Systems II: Analog and Digital
Signal Processing, vol.49, pp. 135 – 144, Feb. 2002.
[18] Piestrak, S.J. “A high-speed realization of a residue to binary number system converter”, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol.42, pp. 661 – 663,Oct. 1995.
[19] Premkumar, A.B. “An RNS to binary converter in a three moduli set with common factors”, IEEE Circuits and Systems II: Analog and Digital Signal Processing, vol.42, pp. 298 - 301, Apr. 1995.
[20] Pourbigharaz, F.A. “signed-digit architecture for residue to binary transformation”IEEE Transactions on Computers, vol.46, pp.1146 – 1150 Oct. 1997.
[21] Szabo, N., and Tanakar, R. “Residue Arithmetic and Its Applications to Computer Technology,” New York: McGraw-Hill, 1967.
[22] Y. Wang, X. Song, M. Aboulhamid, and H. Shen, “Adder 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.
[23] W. Wang, M. N. S. Swamy,M.O. Ahmad, and Y.Wang, “A high-speed residue-to -binary converter and a scheme of its VLSI implementation,” IEEE Trans. Circuits Syst. II, Analog. Digit. Signal Process., vol. 47, no. 12, pp. 1576–1581, Dec. 2000.
[24] 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.
[25] A.S. Molahosseini, K. Navi, and M.K. Rafsanjani. “A new residue to binary
converter based on mixed-radix conversion,” 3rd International Conference On
ICTTA, pp. 1-6, April 2008.
[26] Gbolagade K.A., Chaves R. ; Sousa L. ,Cotofana S.D. “An improved RNS reverse
converter for the {22n+1−1, 2n, 2n−1} moduli set,” , Proceedings of 2010 IEEE
International Symposium on ISCAS.
[27] A.S. Molahosseini, K. Navi and M.K. Rafsanjani, “A New Residue to Binary
Converter Based on Mixed-Radix Conversion,”Proc. of the 3rd International
Conference on ICTTA, 2008.
[28] A. Sabbagh Molahosseini, M. Kuchaki Rafsanjani, S.H. Ghafouri, M. Hashemipour,"A Reduced-Area Reverse Converter for the Moduli Set {2n, 2n-1, 22n-1-1}," International Journal of Advancements in Computing Technology, Vol. 2, No. 5, pp.61 ~ 65, 2010.
[29] A. Sabbagh Molahosseini, C. Dadkhah, K. Navi, “Efficient MRC-Based Residue to Binary Converters for the New Moduli Sets ” {22n, 2n-1, 2n+1-1} and {22n, 2n-1, 2n-1-1},” IEICE Transactions on Information and Systems, 2009.
[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, no.4, pp.660-668, 2008.
[31] A.S. Molahosseini, Chitra Dadkhah, and K. Navi, “A new five-moduli set for
efficient hardware implementation of the reverse converter,” IEICE Electronic Express, Vol. 6, No. 14, 1006-1012, 2009.
[32] M. R. Noorimehr, M. Hosseinzadeh, and R. Farshidi, “A new four-moduli set with high speed RNS arithmetic unit and efficient reverse converter,” IEICE Electronic Express, Vol. 7, No. 20, 1584-1591, 2010.
[33] Skavantzos, A. ; Abdallah, M. ; Stouraitis, T. ; Schinianakis, D., “Design of a Balanced 8-modulus RNS,” IEEE International Conference on Electronics, Circuits, and Systems, pp. 61-64, 13-16 Dec. 2009.