بخشی از مقاله
چکیده
محاسبات پیمانهای در کاربردهای متنوعی از جمله تصحیح و تشخیص خطا ،تبدیلات سریع عددی، تبدیل فوریه گسسته، فیلترهای دیجیتال و پردازش سیگنال دیجیتال مورد استفاده قرار میگیرند. ضرب پیمانه ای نقش مهمی را در علم رمزنگاری ایفا می کند. از جمله روش های رمز نگاری که به ضرب کننده پیمانه ای سریع نیاز دارد، روش رمزنگاری RSAمی باشد که در آن نیاز به توان رساندن اعداد بزرگ در پیمانه های بزرگ می باشد. معمولاً برای نمایش اعداد دراین حالت از سیستم عدد باقیمانده ای - RNS1 - استفاده می شود و ضرب به عنوان هسته توان رسانی دراین سیستم به کار می رود.
در این مقاله یک ضرب کننده باقیمانده ای مبتنی برادغام فاکتورهای تصحیح بدست آمده از مراحل تولید و کاهش حاصلضرب های جزئی ارائه شده است،که با یک جمع کننده سریع رقم کم ارزش دوتایی - DLSB2 - چرخشی پیاده سازی می شود. روی تولید و کاهش حاصلضرب های جزئی متمرکز می شویم و از اعداد به پیمانه2n 1 استفاده می کنیم.از آنجا که فاکتور های تصحیح حاصل از هر مرحله ادغام شده و تشکیل تنها یک فاکتور تصحیح را می دهند و با توجه به اینکه جمع کننده استفاده شده جز سریعترین جمع کننده های باقیمانده ای است،یک ساختار بهینه،هم ازنظر زمانی و هم از نظر ناحیه مصرفی ارائه می دهد.
-1 مقدمه
سیستم عددی باقیمانده ای یک سیستم عددی غیر وزن دار است.در این سیستم می توان بعضی از اعمال ریاضی تحت RNS را به صورت چند مجموعه زیر عمل ریاضی تقسیم کرد ولی به دلیل این که این اعمال فقط شامل جمع و ضرب و تفریق هستند از RNS در محاسبات »خاص منظوره« استفاده می شود. کاربردهایی از قبیل تبدیل فوریه RNS ،راه خود را درکاربردهایی مثل تبدیلات تئوری اعداد و تبدیل فوریه گسسته پیدا کرده است. همچنین مستقل بودن رقم های باقیمانده باعث می شود که رخ دادن خطا در یک رقم به رقم های بعدی منتقل شوند که این مسأله باعث ایجاد یک معماری fault tolerantمی شود
RNS. یک عدد صحیح را به صورت یک مجموعه باقیمانده بدست آمده با توجه به اعضایی که نسبت به هم اولند و پیمانه نامیده می شوند رمزنگاری می کند. با توجه به مفهوم رمزنگاری RNS یک عدد صحیح، در حقیقت به یک مجموعه از اعداد کوچکتر که می توانند به صورت موازی پردازش شوند تغییر شکل می دهد. اجازه دهید B,A
عدد صحیح باشند واجازه دهید m1 , m2 ,...mm پیمانه ها باشند. اعداد B,A که 0 A, B M m به صورت منحصر به فرد به شکل زیر نمایش داده می شوند.
در RNS عملیات های ریاضی به طور همزمان روی تعدادی از اعداد صحیح کوچک انجام می شود و مزیت بارز آن عدم انتشار رقم نقلی بین پیمانه هاست. یک عملیات ریاضی روی دوعدد y,x به صورت زیر انجام میشود که نشان دهنده یکی از سه عمل جمع یا ضرب یا تقریق است.
روش های ضرب پیمانه ای را می توان به دو دسته کلی تقسیم کرد. در دسته اول ابتدا عمل ضرب به صورت کامل انجام می شود و سپس کاهش به پیمانه روی نتیجه آخر اعمال می شود.این روش ها را Reduction after multiplication - RAM - گویند. در دسته دوم عمل کاهش به پیمانه در هر مرحله ضرب و یا هر حاصلضرب جزئی انجام می شود که به این روش ها Reduction during multiplication - RDM - می گویند.طرح های ارائه شده را می توان براساس روش پیاده سازی سخت افزاری به سه مجموعه تقسیم کرد.
مجموعه اول : از تعداد خاصی از پیمانه ها مثل 2 n یا 2n 1 استفاده می کنند. دراین مجموعه n می تواند مقادیر کوچک، متوسط وگاهی بزرگ داشته باشد.در پیاده سازی این طرح ها عمدتاً فقط از مدارات منطقی استفاده شده و از ROM استفاده نمی شود. این طرح ها پیمانه های خاصی محدود می باشندو به همین دلیل کاربردهای محدودی دارند.
مجموعه دوم : توانایی کار با هر پیمانه ای را دارند ولی پیاده سازی این گروه راه حل هایی براساس ROMدارند و معمولاً از مدارات منطقی دیگر استفاده چندانی نمی کند اندازه حافظه با افزایش n به سرعت رشد می کند که طرح را برای پیمانه ای بزرگ غیر عملی می سازد به طور مثال می توان طرح های[9] [10] و [8]را ذکر کرد.
مجموعه سوم : جهت پیمانه های متوسط و بزرگ اجرا می شوند معمولاً به صورت هیبرید هستند واز عناصر ریاضی پایه مثل ضرب و جمع کننده های باینری که به صورت موازی عمل می کنند به همراه چندین ROM با اندازه های کوچک و عناصری منطقی استفاده می کند.
در ساده ترین شکل ممکن هر ضرب کننده به پیمانه mi می تواند با استفاده از ROM ها پیاده سازی شود. طراحی با استفاده از ROM ها بر پایه یک جدول جستجو است . و برای ضرب کننده های پیمانه ای کوچک مناسب است گرچه درصورت بالا رفتن مقادیر اعداد فضای زیادی استفاده می کند. اندازه ROM برحسب تعداد بیت های هر عملوند به طور نمایی افزایش پیدا می کند.
روش دیگر در طراحی ضرب کننده باقیمانده ای استفاده از جمع کننده های باقیمانده ای است که منجر به پیدایش ضرب کننده های مبتنی بر جمع کننده یا full adder-based خواهد شد
Hiasat یک ضرب کننده ترکیبی مناسب برای پیمانه های سایز متفاوت به ویژه پیمانه های با سایز متوسط و بزرگ ارایه کرده استDiClaudio et al. [ 11] یک ضرب کننده شبه RNS را معرفی می کند Stouraitis et al .[13] یک ساختارتک پیمانه ای منفرد بر اساس جمع کننده های محاسبه رقم نقلی پیشرو برای ضرب کننده باقیمانده ای ارایه می دهد
ضرب کننده ارایه شده توسط Zimmerman استفاده ازجمع درختی Wallace-tree وکد گذاری booth روی حاصلضرب های جزئی را به منظور افزایش سرعت ضرب کننده ارائه می دهد. او همچنین از جمع کننده های پیشوندی موازی به منظور پیاده سازی جمع کننده سریع رقم نقلی چرخشی خود به پیمانه 2n 1 استفاده کرده است
ضرب کننده تفریق 1 به پیمانه 2n 1 که توسط Efstathiou et al. ارائه شده بودازیک آرایه n x n حاصلضرب جزئی به همراه درخت ذخیره رقم نقلی گردشی استفاده می کرد.نیاز به استفاده از n+3 حاصلضرب جزئی و اصلاح برای عملوند صفر از معایب این طرح به حساب می آمد
Vergos et al یک ضرب کننده باقیمانده ای پیمانه 2n 1 با نمایش وزن دار برای عملوندها معرفی کرده است.در این ساختار از n+1 حاصلضرب جزئی به همراه یک جمع کننده رقم نقلی نهایی چرخشی معکوسIECA در طبقه میانی و یک درخت جمع کننده ذخیره ساز رقم نقلی و یک جمع کننده موازی پیشوندی در طبقه آخر استفاده شده است.
در سال Vergos et al.2007 یک ضرب کننده دیگر را طراحی نموده[24] که نتایج بدست آمده حاکی از بهینه سازی راه حل های ارائه شده در مقالات[21] [22] [23] است. بعد از معرفی نمایش اعداد مکمل دو رقم کم ارزش دوتایی توسطParhami [25] در سال 2008 و معرفی مکمل گیری بیتی ،در سال 2010 جمع کننده نمایش دوتایی رقم کم ارزش خود را بر پایه منطق پیشوندی موازی ارائه کرد.
در این مقاله روی ضرب کننده های مجموعه اول و پیمانه 2n 1 متمرکز می شویم و از طرح دسته بندی ضرب کننده [23] استفاده می کنیم و یک جمع کننده رقم کم ارزش دوتایی سریع در [26] را در جهت بهبود زمان* ناحیه بکار می بندیم. بخش 2 روش دسته بندی در ضرب کننده Vergos et al را شامل می شود و بخش 3 جمع کننده رقم کم ارزش دوتایی سریع با منطق پیشوندی-موازی را معرفی می کند، بخش 4 ساختار پیشنهادی را ارایه کرده و در آخر نتیجه گیری می کنیم.
