بخشی از مقاله
چکیده – امروزه نیاز به فیلترهاي دیجیتال سریعتر و با توان مصرفی پایین تر در بسیاري از زمینهها به ویژه الگوریتمهاي مخابراتی کاملاً مشهود است. ضرب کننده دیجیتال یکی از عناصر اصلی فیلتر دیجیتال میباشد. بنابراین براي بهینه سازي یک فیلتر دیجیتال، باید ضرب کننده آن بهینه باشد. الگوریتمهایی زیادي براي بهینه سازي ضرب کنندهها ارائه شده است که ضعف اصلی این الگوریتمها در عدم توانایی براي ضرب اعداد منفی میباشد. الگوریتم بوث از جمله الگوریتمهایی است که توانایی ضرب اعداد منفی را دارا میباشد، اما این الگوریتم از نظر توان مصرفی و سرعت انجام عمل ضرب الگوریتم مناسبی نیست.
در این مقاله روشی براي بهینه سازي این الگوریتم ارائه شده است. در این الگوریتم هدف کاهش تاخیر انتشار و کاهش تعداد گیتهاي مصرفی میباشد. الگوریتم ضرب کننده بوث و الگوریتم پیشنهادي بر روي FPGA سري Cyclone II و ACEX1K از سري هايAltera پیاده و با ضرب کننده IP core شرکت Altera مقایسه شده است. نتایج نشان دهنده آن است که الگوریتم پیشنهادي نسبت به الگوریتم بوث سریع تر بوده و بازدهی بیشتري دارد.
-1 مقدمه
فیلترهاي دیجیتال امروزه به طورگسترده در بسیاري از زمینهها علی الخصوص الگوریتمهاي مخابراتی کاربرد فراوان دارند. یکی از معمولترین راههاي پیاده سازي این فیلترها، پیاده سازي آن ها بر روي تراشههاي FPGA است. بر همین اساس بهینه سازي آن ها چه از نظر تاخیر انتشار، چه از نظر توان مصرفی و چه از نظر تعداد گیت هاي منطقی لازم براي پیادهسازي حائز اهمیت می باشد.
ضرب کننده دیجیتال یکی از عناصر اصلی فیلتر دیجیتال میباشد. بنابراین براي بهینه سازي یک فیلتر دیجیتال، باید ضرب کننده آن بهینه باشد. الگوریتم هاي زیادي براي بهینه سازي ضرب کنندهها ارائه شده است که از جمله مهمترین آنها، الگوریتم هاي CSE و BSE و BCSE می باشد.[1] در [2] یک روش جدید براي الگوریتم BCSE ارائه شده است که با کمک مالتی پلکسر تعداد جمع کننده ها را به میزان قابل توجهی کاهش داده است . اشکال اصلی این الگوریتم این است که قادر به ضرب اعداد منفی نیست. در [3] یک روش جدید بر پایه الگوریتم BCSE براي پیاده سازي بر روي یک گیرنده مخابراتی ارائه شده است.
یکی از الگوریتم هایی که می تواند ضرب اعداد منفی را انجام دهد الگوریتم ضرب کننده بوث - booth - می باشد . تلاش اصلی در این تحقیق ارائه الگوریتمی براي بهینه سازي الگوریتم ضرب کننده بوث میباشد. در ادامه ابتدا الگوریتم ضرب کننده بوث شرح داده میشود. دربخش بعدي الگوریتم پیشنهادي که بهینه سازي الگوریتم بوث می باشد را بیان کرده و پیاده سازي آن را برروي FPGA توضیح می دهیم . در مرحله بعد این الگوریتم را با الگوریتم ضرب کننده Altera مقایسه می کنیم. در نهایت ایده هایی براي بهینه تر کردن این الگوریتم مطرح می کنیم.
-2 الگوریتم ضرب کننده بوث [4]
قرار است عدد چهار بیتی x در عدد چهار بیتی y ضرب شود، با این فرض که پرارزشترین رقم، رقم علامت باشد. به عنوان مثال در صورتی که x=1101 - x=-3 - و y=0101 - y=5 - باشد، مراحل الگوریتم بدین صورت خواهد بود:
-1 تبدیل عدد x به یک عدد هشت بیتی، صفر یا یک بودن چهار بیت پرارزشی که به x اضافه می شوند را بیت چهارم x تعیین می کند، به طور مثال: x=11111101
-2 در نظر گرفتن متغیر s و A با مقدار اولیه صفر.
-3 اضافه کردن صفر به ابتداي .y حال y، 5 بیتی است به طور مثال: y=01010
-4 با توجه به دو بیت سمت راست y و جدول زیر، مقدار A تعیین میشود.
-5 مقدار A را با متغیر s جمع می کنیم و درون s قرار می دهیم .
-6 x<<1 x
-7 y>>1 y - نمادهاي << 1 و >>1 به ترتیب به معنی یک رقم شیفت به چپ و یک رقم شیفت به راست میباشند. -
-8 مراحل 4 تا 7 را تا رسیدن به دو رقم آخر y تکرار می شود.
-9 در نهایت مقدار s ، نتیجه حاصلضرب دو عدد x,y می باشد. مزیتی که الگوریتم بوث نسبت به خیلی از الگوریتم ها دارد این است که می تواند اعداد منفی را به راحتی در هم ضرب کند. اما در این الگوریتم تعداد زیادي مالتی پلکسر و جمع کننده استفاده شده است که خود باعث می شود زمان ضرب افزایش پیدا کند. در این پژوهش الگوریتمی پیشنهاد شده است که تعداد مالتی پلکسرها و جمع کننده ها را تا حدودي بهینه میکند.
-3 الگوریتم پیشنهادي
بلوك دیاگرام کلی این الگوریتم در شکل 2 نشان داده شده است. عدد x به همراه متمم شده آن به ورودي 4 عدد مالتی پلکسر داده می شوند . انتخاب x یا متمم آن با استفاده از ارقام y می باشد . مالتی پلکسر m0، یک مالتی پلکسر 2×1 و بقیه مالتی پلکسرهاي 4×1 می باشند. مقادیر خروجی مالتی پلکسرها بعد از خروج شیفت به چپ داده میشوند. در مالتی پلکسر m1 یک، در m2 دو عدد و در m3 سه عدد شیفت به چپ داریم ولی در m0 شیفت به چپ نداریم. لازم به ذکر است S0,S1,S2,S3 هشت بیتی هستند و مقادیر پرارزش آنها برابر با بیت پرارزش مقادیر خروجی مالتی پلکسرها میباشد.
در این الگوریتم براي کاهش زمان ضرب از متمم یک عدد x به جاي متمم دو آن استفاده شده است. سپس مقادیري که لازم است به عدد حاصل از جمع Sها اضافه شود تا متمم 2 بدست بیاید را با دو عدد مالتی پلکسر داخل یک الگوریتم به طوري که با بقیه مراحل به صورت همزمان انجام شود پخش شده است. این الگوریتم به صورت زیر بدست آمده است:
واضح است که براي به دست آوردن متمم دو یک عدد باید متمم یک آن عدد را با یک جمع نمود. در این الگوریتم ابتدا عملیات بر روي متمم یک عدد صورت میگیرد و سپس مقادیر یک و شیفت یافته آن با نتیجه جمع می شود. پس اعدادي که لازم است تا با نتیجه جمع شوند تا متمم 2 عدد بدست بیاید 1,10,100,1000 یا ترکیب این اعداد می باشد که به صورت دهدهی 1,2,4,8 می شود. با کمی دقت و با استفاده از روش سعی و خطا روشن میشود که لازم است فقط اعداد 1,2,4,5,8,9,10 با مجموع Sها جمع شوند تا حاصل ضرب نهایی بدست بیاید.
با این حساب با توجه به بلوك دیاگرام این الگوریتم مشاهده می کنیم که ابتدا با دو عدد مالتی پلکسر اعداد انتخاب می شوند. خروجی مالتی پلکسرها با استفاده از مدار ترکیبی طراحی شده براي آنها بین ورودي ها یکی را انتخاب می کند. خروجی مالتی پلکسر m4 صفر ، یک یا دو و خروجی مالتی پلکسر m5 صفر، چهار یا هشت می باشد .
چون خروجی m4 فقط دو بیت اول و خروجی m5 فقط دو بیت آخر آن تغییر می کند، میتوان با بهکارگیري عملگر الحاق و بدون استفاده از جمع کننده نتیجه درست را به دست آورد . بنابراین بدون استفاده از جمع کننده، اعداد لازم براي تبدیل اعداد به متمم دو را به دست آمده است. این نتیجه در نهایت با حاصل جمع Sها جمع می شود و حاصلضرب دو عدد به دست می آید.
-4 نتایج شبیه سازي
الگوریتم ضرب کننده بوث و الگوریتم پیشنهادي بر روي FPGA سري Cyclone II و ACEX1K از سريهايAltera پیاده و با ضرب کننده IP core شرکت Altera مقایسه شد و نتایج زیربدست آمد. نرمافزار مورد استفاده براي شبیه سازي، نرم افزار Quartus متعلق به شرکت Altera می باشد.
