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

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

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

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

تاريخ الإرسال : 14 الإثنين , جمادى الثانية, 1438 تاريخ التأكيد : 14 الإثنين , جمادى الثانية, 1438 تاريخ الإصدار : 11 السبت , جمادى الأولى, 1437

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

ملخص المقالة :

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

المصادر:

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.