بخشی از مقاله
خلاصه
سیستم اعداد مانده ای یک سیستم عددی غیر وزنی است که محاسبات موازی ، انتشار محدود رقم نقلی ، توان مصرفی کم و ارتباطات امن را پشتیبانی می کند و در کارهایی که از عمل های جمع ، تفریق و ضرب در یک محدوده از اعداد استفاده می کنند ، کاربرد دارد . مزایای استفاده از سیستم اعداد مانده ای سرعت بالا ، کاهش توان ، کاهش پیچیدگی ، تشخیص و تصحیح خطا می باشند . مبدل مانده ای به دودوئی یک عدد با نمایش مانده ای را به معادل وزنی دودوئی آن تبدیل می کند . از آنجا که این مبدل عکس مبدل دودوئی به مانده ای عمل می کند ، به مبدل معکوس مشهور است.
در این مقاله برای اولین بار طراحی بهبود یافته ای از مبدل مانده ای به دودئی ارائه شد که توانایی دریافت باقیمانده با فرمت افزونه را دارد. بدین صورت که در لایه اول مبدل، جمع کننده های ذخیره رقم نقلی افزوده شدند تا باقیمانده های باف رمت افزونه را پردازش کنند و سپس لایه دوم مبدل مانده ای به دودوئی، انها را با یکدیگر ادغام می کند . در نتیجه یک سیستم اعداد مانده ای با تاخیر کمتر حاصل میشود چون دیگر به واسط میانی در واحد حساب جهت تبدلیل باقیمانده های افزونه به عادی، قبل از ورود به مبدل مانده ای به دودوئی نیست.
.1 مقدمه
سیستمهای اعداد افزونهای اهمیت ویژهای در انجام محاسبات سریع دارند. ویژگی اصلی سیستمهای عددی افزونه، انجام عملیات جمع و تفریق بدون انتشار رقم نقلی میان- رقمی است. بدین صورت که رقم نقلی تولید شده در هر رقم افزونه، توسط رقم بعدی جذب شده و از انتشار آن به رقمهای بعدی جلوگیری میشود. بدین ترتیب نتیجه محاسبه نیز به صورت افزونه خواهد بود؛ بنابراین هر گاه تعداد زیادی عملیات جمع به طور متوالی مورد نظر باشد، استفاده از سیستم اعداد افزونهای نقش بسیار مؤثری در بهبود کارایی خواهد داشت.
ازآنجاکه زمان انجام سایر عملیات وابسته به زمان عمل جمع است، بهبود زمان جمع دارای اهمیت بسیاری میباشد. به دلیل انجام جمع به صورت موازی و با سرعت بالا در سیستم اعداد افزونهای، در کاربردهایی چون پردازش سیگنال دیجیتال، فیلترهای دیجیتال و الگوریتمهای رمزنگاری از آن استفاده میشود.[1] جهت افزایش نرخ انتقال داده میتوان سیستم اعداد ماندهای را به کار گرفت که سیستمی غیر وزنی است و از باقیماندههای تقسیم اعداد بر چندین پیمانه مشخص استفاده میکند.
در نتیجه محاسبات با سرعت بیشتر و توان مصرفی کمتر انجام میشود و میتوان این سیستم را در کاربردهایی که نیازمند پردازش بلادرنگ هستند مورد استفاده قرار داد. با اضافه کردن تعدادی پیمانه افزونه به سیستم اعداد ماندهای، سیستم اعداد ماندهای افزونه حاصل میشود که جهت تشخیص و تصحیح خطاها گزینه مناسبی به شمار میرود.
انتخاب مجموعه مناسب از مهمترین مسایلی است که تأثیر مستقیم بر محدوده نمایش، تعداد مکان مورد نیاز برای نمایش اعداد، حداکثر استفاده از حافظه، پیچیدگی الگوریتمهای ریاضی، سرعت محاسبات داخلی، سرعت مبدلها، سادگی مدارات و سختافزار دارد. مساله دیگری که سبب بهبود کارایی سیستم اعداد افزونه میگردد .[2]
با توجه به این نکته که الگوریتم کنترل خطای مورد استفاده در سیستم اعداد افزونه دارای هزینههای بالای زمانی، محاسباتی و سختافزاری است، در این مقاله الگوریتم کنترل خطای جدیدی پیشنهاد میشود که در مقایسه با الگوریتم پیشین بهبود قابلتوجهی را در موارد کاهش هزینههای نامبرده شده نشان میدهد . همچنین مجموعه پیمانه جدید{2n+1, 2n+1 -1, 2 n-1, 2 n+2 -1,n 2n+1 } در سیستم اعداد ماندهای افزونه ارائه میشود که پیمانههای اصلی آن شامل سه پیمانه { 2n+1, 2n+1-1, 2 n-1 و دو پیمانه 2n+2 --1 } {1,n2n+1 پیمانههای افزونه میباشند.
با استفاده از این مجموعه پیمانه جدید و الگوریتم پیشنهادی و با طراحی و پیادهسازی مبدل معکوسهای مورد نیاز بررسی میگردد که در سمت گیرنده چگونه رخداد خطا با تصحیح بیتهای دارای خطا، عدد اولیه بازیابی میشود .[3] سیستم اعداد افزونه از جمله تکنیکهای ارائه شده جهت کنترل و خطاست؛ که دارای ویژگیهای منحصربهفردی میباشد.
با توجه به اینکه کاهش هزینهها از جمله اهداف مهم سیستمهای تحملپذیر خطا است، در این پایاننامه با اصلاح الگوریتم کنترل خطای سیستم اعداد ماندهای افزونه، راهکار جدیدی ارائه میشود که طی آن ضمن کاهش چشمگیر هزینههای محاسباتی و سختافزاری، افزایش قابلملاحظه سرعت بازیابی عدد اولیه توسط الگوریتم کنترل خطا را شاهد هستیم.
بهگونهای که تعداد مبدل معکوسهای مورد نیاز جهت طراحی و پیادهسازی رویه کنترل خطا از ده به پنج عدد کاهش مییابد و به موجب آن، تعداد معکوس ضربیهای مورد نیاز برای طرتحی مبدل معکوس از 30 به 15 میرسد، در حالی که قابلیت کنترل خطا در مقایسه با الگوریتم پیشین تغییری نمیکند و همچنان تصحیح یک باقی مانده در یافتی دارای خطا و تشخیص دو باقیمانده دریافتی غیرصحیح امکانپذیر است.
همچنین مجموعه پیمانه جدید {2n+1, 2 n+1-1, 2n-1, 2n+2 -1,n2n+1 د سیستم اعداد ماندهای افزونه ارایه میشود که در آن سه پیمانه 2n+1, 2n+1-1, { 2n-1 پیمانههای اصلی و دو پیمانه{2n+2 -1,n2n+1-1 } پیمانههای افزونه میباشند. در طرح پیشنهادی بر اساس الگوریتم پیشنهادی و مجموعه پیمانه جدید در سیستم اعداد ماندهای افزونه و نیز با استفاده از الگوریتم تبدیل مبنای دهم، تمامی پنج مبدل معکوس مورد نیاز جهت کنترل خطا به صورت کامل طراحی و پیادهسازی میشود و در نهایت میزان کل هزینههای سختافزاری و تأخیر نیز محاسبه میگردد.
مقایسه نتایج به دست آمده در طرح پیشنهادی با مقادیر محاسبه شده برای الگوریتم پیشین کنترل خطا در سیستم اعداد ماندهای افزونه، بهبودهای حاصل شده در هزینه سختافزار و سرعت عملیات را تائید مینماید .[4] واحدهای حساب کامپیوتری مبتنی بر نظام عددی ماندهای با پیمانههای مطلوب {2n+1 , 2n, nn-1} به جمع کنندههای سریع نیاز دارند.
جمع کنندههای معمولی -n بیتی و انواع سریع آنها برای پیمانه 2n مناسباند؛ اما استفاده از آنها برای دو پیمانه دیگر مستلزم انجام یک عمل تصحیح افزایش یا کاهش است. تلاشهای متعددی برای کاهش زمان تصحیح به یک مقدار ثابت نا وابسته به n صورت گرفته است که در قالب جمع کننده پیمانهای یک مرحلهای نتیجه داده است .[5] در این پژوهش به طراحی بهبود یافته مبدلهای مربوط به سیستم اعداد افزونه با کارایی بالا و همچنین در مورد جمع کنندههای افزونه BSD,HRSDو ضرب کنندههای افزونهای BSDو مدارهای جمع و ضرب کننده و مدارهای مبدل SD-RNS و تحلیل آنها پرداخته شده است.
.2 اهداف
اهداف این تحقیق به شرح زیر میباشند:
-1 تحلیل و بررسی طراحی بهبود یافته مبدلهای مربوط به سیستم اعداد افزونه با کارایی بالا
-2 تحلیل و بررسی جمع کنندههای افزونه BSD
-3 تحلیل و بررسی جمع کنندههای افزونه HRSD
-4 تحلیل و بررسی ضرب کنندههای افزونهای BSD
-5 تحلیل و بررسی مدارهای جمع و ضرب کننده و مدارهای مبدل SD-RNS
-6 بهینهسازی تشخیص خطا از طریق بررسی سیستمهای عددی دیگر سیستم اعداد ماندهای دو سطحی، سیستم اعداد ماندهای وآنهات و سیستم اعداد افزونه
-7 شناسایی سیستم اعداد ماندهای چند سطحی دارای و بهینهسازی سادگی در انتخاب مجموعه پیمانه و محدوده نمایش بزرگ
.3 مفاهیم
.1-3 سیستم اعداد ماندهای
از آن جا که RNS به جای انجام محاسبات بر روی اعداد بزرگ - X - ، محاسبات را بر روی مجموعهای از اعداد کوچکتر انجام میدهد، این نمایش افزایش سرعت قابلتوجهی ایجاد میکند. چنانچه تعدادی عملیات حسابی به دنبال هم نیاز باشد، در این صورت تنها یک عمل تبدیل از اعداد دودویی استاندارد به اعداد ماندهای و یک عمل تبدیل از اعداد ماندهای به اعداد دودویی استاندارد لازم است. در نهایت کل عملیات سریعتر و سادهتر از اعداد دودویی استاندارد انجام خواهد شد. از مزایای سیستم اعداد ماندهای میتوان به دو مورد زیر اشاره کرد:
-1 مسأله انتشار رقم نقلی کاهش یافته و محدود به درون هر پیمانه میشود.
-2 این سیستم دارای قابلیت تحملپذیری خطا میباشد. از مهمترین معایب سیستم اعداد ماندهای، دو مورد زیر میباشد:
-1 عملیات حسابی تقسیم، تعیین علامت، مقایسه دامنه و تشخیص سرریز، پیچیده و مشکل میباشد.
-2 مدارهای تبدیل میان اعداد دودویی و ماندهای مورد نیاز است .[6]
