ارائه روشی کارآمد و سریع جهت تشخیص سرریز برای مجموعه پیمانه {2^n-1 ,2^n,2^n+1}

محورهای موضوعی : مجله فناوری اطلاعات در طراحی مهندسی

مرضیه سادات امیر شاکر می ¹ , مهدی حسین زاده ² , علی آستانه اصل ³

1 - گروه کامپیوتر دانشگاه آزاد اسلامی اراک
2 - گروه کامپیوتر دانشگاه آزاد اسلامی واحد علوم و تحقیقات
3 - دانشگاه آزاد اسلامی، واحد اراک، گروه ریاضی، اراک،ایران

تاریخ دریافت : 1395/12/23 تاریخ پذیرش : 1395/12/23 تاریخ انتشار : 1394/12/01

کلید واژه: 2^n, Residue Number System(RNS), Overflow Detection, moduli set {2n-1, 2n, 2n+1}, Common Multiple, سیستم اعداد مانده ای, شناسایی سرریز, مضرب مشترک, مجموعه پیمانه {2^n-1, 2^n+1},

چکیده مقاله :

امروزه با توجه به پیشرفت تکنولوژی و فناوری اطلاعات نیاز به محاسبات سریع داده امری ضروری می باشد. سیستم اعداد مانده ای، سیستمی نامتعارف و غیروزنی است که محاسبات به صورت موازی روی باقیمانده های تقسیم عدد بر چندین پیمانه، انجام می شود. انجام اینگونه محاسبات باعث بالا رفتن سرعت محاسبات و کاهش توان مصرفی می گردد. یکی از مشکلات این سیستم انتشار سرریز است که به دلیل انجام عملیات پیمانه‌ای و طبیعت بی وزن بودن اعداد است. برای رفع این مشکل در بسیاری از موارد استفاده از مبدل برعکس و تبدیل اعداد به سیستم وزن‌دار جهت مقایسه و شناسایی سرریز ضروری است. در این مقاله الگوریتم جدیدی به منظور بهبود شناسایی سرریز بر روی مجموعه پیمانه ارائه می دهیم که نیازی به انجام مقایسه کامل و فرآیند تبدیل معکوس ندارد. همچنین روش پیشنهادی در مقایسه با روش های قبلی، علاوه بر مولفه های سخت افزاری کمتر، تاخیر در آن بسیار پایین است.

چکیده انگلیسی:

Nowadays, due to advances in technology and information technology fast processing of data is a growing need. Residue Number System is an unconventional and non-Weighted System that parallel computing on remainders of dividing number on several modules is performed. The computations are performed cause to increase the speed of computing and reduce the power consumption. One of the problems in this system is published overflow that due to the modular operations and nature of non-weighting numbers. In order to solve this problem in many cases using to binary number system converter and convert the number to the weighted numbers to comparison and overflow detection is necessary. In this article, the novel methods to improve the detection of overflow in moduli set {2n-1, 2n, 2n+1} without doing a full comparison and need the reverse convert process. Also The proposed method is compared with previous approaches, in addition to fewer hardware components, the delay is very low.

منابع و مأخذ:

1) Garner H., “The Residue Number System”, IRE Trans. Electronic Computer, 1959,Vol. EC8, pp. 14 0-147.

2) Hosseinzadeh Mehdi, Sabbagh Amir and Navi Keivan, "An Improved  Reverse Converter  for the Moduli set {2ⁿ-1, 2ⁿ, 2ⁿ+1, 2ⁿ⁺¹-1}", IEICE Electronic Express, 2008, Vol. 5, No. 17, pp. 672-677.

3) Hosseinzadeh Mehdi," High-speed Low-Power VLSI Design for Capability of High Rate Processing Using the Multiple Valued Logic Residue Number Systems", ph.D Dissertation, Islamic Azad University, Science and Research   Branch,1387(In Persian).

4) Jaberipour Ghassem, "A One-step Modulo 2ⁿ+1 Adder Based on Double-lsb  Representation of Residues", Submitted, 2008.

5) Bajard Jean-Claude and Imbert Laurent, “Brief contributions: A Full RNS Implementation of RSA,” IEEE       Transactions on Computer, 2004, Vol. 53, No. 6, pp. 769-774.

6)  Askarzadeh Majid, Hosseinzadeh Mehdi, and Navi Keivan,“A New Approach to Overflow Detection in Moduli  Set {2ⁿ-3, 2ⁿ-1, 2ⁿ+1, 2ⁿ+3}”, Second  International Conference on Computer and Electrical  Engineering, 2009, pp. 439-442.

7)  Parhami Behrooz, “Computer arithmetic: algorithms and hardware designs.”Oxford University Press, New York, 2000.

8) Mi Lu ,“Arithmetic and Logic in Computer Systems”, John Wiley & Sons, Texas A&M University, 2004.

9) Siewobr H. and Gbolagade K.A.,"Overflow Detection in Residue Number Systems Addition before Forward Conversion", International Journal of Computational Intelligence and Information Security, 2011,Vol. 2, No. 9.

10)  Zimmerman Reto, "Efficient VLSI Implementation of Modulo (2n ±1) Addition and Multiplication", in Proc. 14th IEEE Symp. Computer Arithmetic, Adelaide, Australia, 1999, pp. 158-167.

11) Rouhifar Mehrin, Hosseinzadeh Mehdi  and Teshnehlab Mohammad, "A New Approach to Overflow Detection in moduli set {2ⁿ-1,2ⁿ,2ⁿ+1}", International Journal of Computational Intelligence and Information Securit, 2011,Vol. 2, No.3, pp. 35- 43.