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

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

مقاله 6، دوره 8، پائیز و زمستان 1394، اسفند 1394، صفحه 76-87   

نوع مقاله: مقاله پژوهشی

نویسندگان

مرضیه سادات امیر شاکر می^{* 1}؛ مهدی حسین زاده²؛ علی آستانه اصل³

¹گروه کامپیوتر دانشگاه آزاد اسلامی اراک

²گروه کامپیوتر دانشگاه آزاد اسلامی واحد علوم و تحقیقات

³دانشگاه آزاد اسلامی، واحد اراک، گروه ریاضی، اراک،ایران

چکیده

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

کلیدواژه‌ها

سیستم اعداد مانده ای؛ شناسایی سرریز؛ مجموعه پیمانه {2^n-1؛ 2^n؛ 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.