مقاله سازوکار انواع دستگاه‌های اعداد مانده‌ای و کاربرد آن‌ها

بخشی از مقاله

خلاصه

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

.1 مقدمه

کارایی بسیاری از مدارهای VLSI2، همانند پردازش سیگنال دیجیتال - DSP - 3 و تراشههای رمزنگار RSA، بر اساس سرعت واحدهای حساب کامپیوتری، همانند جمع کنندهها و ضرب کنندهها تعیین میگردد. نمایش بهینه اعداد، کارایی عملیات حساب کامپیوتری را افزایش میدهد. در سیستم اعداد دودویی، سرعت محاسبات با افزایش تعداد بیتهای عملوند روبه کاهش میگذارد. بهعنوان مثال در جمع، این مسئله به دلیل احتمال انتشار رقم نقلی از کمارزشترین بیت به پرارزشترین بیت در روش جمع انتشار رقم نقلی و یا افزایش تعداد سطوح در جمع با محاسبه سریع رقم نقلی مانند روش CLA به وجود میآید. این محدودیت موجب گردیده است دستگاههای عددی متنوعی برای پیادهسازی کارآمد مدارهای حساب کامپیوتری ارائه شود.[1]

سیستم اعداد ماندهای - RNS - 1 یکی از مباحث مطرح در حساب کامپیوتری سریع است 2]و.[1 این سیستم مجموعهای متشکل از چند پیمانه است که برای نمایش اعداد، از باقیماندههای تقسیم آنها بر پیمانهها استفاده میکند. یکی از مهمترین خواص این سیستم انتقال محدود رقم نقلی، در محاسبات است. محاسبه بر روی تمام پیمانهها میتواند به صورت موازی و مستقل از هم انجام شود. این ویژگی بهطور فراوان ای سرعت محاسبات را افزایش میدهد.[2] درحالیکه تشخیص علامت، مقایسه اعداد و تقسیم در سیستم اعداد ماندهای پیچیده است. ازاینرواین سیستم در محاسبات با سرعت بالا و در بعضی از کاربردها که اساساً تعداد جمع و ضربهای بیشتری نسبت به سایر عملگرها دارند، به کار میرود.

بهعنوان مثال، این سیستم در پردازش سیگنال دیجیتال، فیلترهای دیجیتال، الگوریتمهای رمزنگاری، ارتباطات و در حالت کلی کاربردهایی که در یک محدوده مشخصی از اعداد، عملیات جمع، تفریق و ضرب تکرار میشود، بسیار مفید است. بهعلاوه RNS قابلیت فراهم آوردن ویژگی تشخیص و تصحیح خطا را دارد 3]،.[1 دستگاههای اعداد افزونهای نیز اهمیت ویژهای در انجام محاسبات سریع دارند. ویژگی اصلی دستگاههای عددی افزونه، انجام عملیات جمع/ تفریق بدون انتشار رقم نقلی میان رقمی است .

[4] بدینصورت که رقم نقلی تولیدشده در هر رقم افزونه، توسط رقم بعدی جذبشده و از انتشار آن به رقمهای بعدی جلوگیری میشود. بدین ترتیب نتیجه محاسبه نیز به صورت افزونه خواهد بود؛ بنابراین هرگاه تعداد زیادی عملیات جمع بهطور متوالی موردنظر باشد، استفاده از سیستم اعداد افزونهای نقش بسیار مؤثری در بهبود کارایی خواهد داشت. ازآنجاکه زمان انجام سایر عملیات وابسته به زمان عمل جمع است، بهبود زمان جمع دارای اهمیت بسیاری است. به دلیل انجام جمع به صورت موازی و با سرعت بالا در سیستم اعداد افزونهای، در کاربردهای زیادی از آن استفاده میشود. در سیستم اعداد ماندهای، انتشار رقم نقلی نسبت به سیستم اعداد دودویی استاندارد کاهش میباید؛ درحالیکه انتشار رقم نقلی داخل هر پیمانه هم چنان باقی است.

این مسئله میتواند یک عامل محدودکننده در کاربردهای بیدرنگ باشد. ازآنجاکه اعداد افزونه میتوانند در یکزمان ثابت و مستقل از طول عملوند باهم جمع شوند، ترکیب این ویژگی اعداد افزونه با حساب RNS به پیادهسازی بهتر مدارهای حساب کامپیوتری کمک میکند.[5] کاربردهای بسیاری وجود دارد که تنها شامل عملیات حسابی جمع و ضرب میباشند که از آن جمله میتوان به دستگاههای پردازش سیگنال دیجیتال و فیلترهای دیجیتال اشاره نمود.

در طول سالهای گذشتهفنّاوریهای شبکهی بسیار مختلفی درزمینه تشخیص و تصحیح خطا به کاربرده شدند که هرکدام از آنها انتقال یک نوع متفاوت از داده را بر عهده دارند. بسته به اهمیت دادههایی که منتقل میشوند،فنّاوریهایی شبکه با مکانیسمهای کدگذاری مناسب، مجهز میشوند . کدهای کنترل خطا بهطور عمده در دستگاههای ارتباطی، به منظور بهبود قابلیت اطمینان سیستم کاربرد دارند 2]و.[1 همانطور که میدانید تصحیح خطا در دستگاههای آنالوگ ممکن نیست و در عمل نمیتوان یک سیگنال واپیچیده آنالوگ را به حالت اصلی بازگردانید درحالیکه در دستگاههای دیجیتال به خاطر ماهیت دودویی، کافی است تا بیتهای اشتباه را شناسایی کرده - تشخیص - و آنها را معکوس نمود - تصحیح - ، یعنی بیت صفر را به یک و بیت یک را به صفر تبدیل کرد تا سیگنال دقیقاً به حالت درست بازگردد.

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

این نوع خطای کلی را خطای پیوسته مینامند . یکی از عوامل تعیین کارآمدی دستگاههای تشخیص و تصحیح خطا، بزرگی دسته خطاهای کلی است که توسط آن سیستم، قابل تصحیح است و هر چه خطای پیوستهی بزرگتری پوشش داده شود، سیستم کاراتر خواهد بود. لازم به ذکر است که برای تشخیص و تصحیح خطا نیاز به استفاده از دادههای اضافی است تا به کمک آنها بتوان عدم صحت دادههای دریافت شده و وضعیت صحیح اولیه را تعیین کرد.

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

.2 انواع دستگاههای اعداد ماندهای

.1-2 سیستم اعداد دوسطحی ماندهای

با توجه به خواص سیستم اعداد ماندهای در افزایش سرعت محاسبات، کاهش توان مصرفی، بالا بردن امنیت و تحملپذیری خطا میتوان عملیات حسابی روی هر پیمانه ر ا نیز با یک سیستم اعداد ماندهای جدید انجام داد و تکرار این عمل میتواند تا رسیدن به پیمانههای بسیار کوچک ادامه یابد، به بیانی دیگر این کار را میتوان تا چند سطح تکرار نمود .سیستم به دست آمده از فرآیند فوق، سیستم اعداد ماندهای چند سطحی نامیده میشود.[6] تنها محدودیتی که در سیستم اعداد ماندهای چند سطحی میبایست لحاظ شود، این است که محدوده نمایش سیستم اعداد ماندهای سطح i ام که برای هرکدام از پیمانههای سطح - ٌ - i  در نظر گرفته میشود، باید بزرگتر یا مساوی پیمانه موردنظر باشد .

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

[7] با داشتن تعداد کمی پیمانه با توان بزرگ در سطح اول،اولاً مشکل اول بودن پیمانهها نسبت به یکدیگر و نیز عدم توازن پیمانهها وجود نخواهد داشتثانیاً. به دلیل کم بودن تعداد پیمانهها، مدارات مبدل ساده بوده و تبدیلات به سرعت انجام میگیرد. همچنین در سطح دوم به دلیل اینکه پیمانهها کوچک میباشند و به دلیل انتشار محدودتر رقم نقلی محاسبات داخلی سیستم اعداد ماندهای با سرعت زیاد انجام میشود.[7]