الگوریتم بوث

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم ضرب بوث (Booth's multiplication algorithm) با استفاده از یک الگوریتم ساده، دو عدد علامت دار را در یکدیگر ضرب می کند. مراحل اجرای این الگوریتم را در عکس زیر مشاهده می نمایید.

الگوریتم بوث رویه ای را برای ضرب اعداد دودویی در نمایش متمم ۲ علامتدار ارائه می نماید. مبنای کار الگوریتم بر این اساس استوار است که رشته های 0 در مضروب فیه نیازی به جمع ندارند بلکه فقط جابجایی (شیفت) لازم دارند و رشته های 1 در مضروب فیه از بیت مرتبه 2k تا بیت 2m را می توان معادل 2k+1 - 2m تلقی کرد.

مثلاً عدد دودودیی 001110 (14+) دارای رشته های 1 از 21 تا 23 است. (k=3 و m=1). این عدد را می توان بصورت 2k+1 - 2m = 24 - 21 = 16 - 2 = 14 نوشت.

بنابراین ضرب Mx14 را که در آن M مضروب و 14 مضروب فیه است، می توان به صورت Mx24 - Mx21 انجام داد. لذا حاصلضرب با چهار بار شیفت مضروب به چپ و تفریق M که یکبار به چپ شیفت داده شده است بدست می آید.

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

  1. به محض برخورد با اولین 1 کم ارزش در رشته 1 ها در مضروب فیه، مضروب از حاصلضرب جزیی کم شود.
  2. به محض برخورد با اولین 0 (به شرطی که قبل از آن 1 باشد) در رشته ای از 0 ها در مضروب فیه، مضروب با حاصلضرب جزیی جمع شود.
  3. وقتی که بیت جاری مضروب فیه همانند بیت قبلی باشد، حاصلضرب جزیی تغییر نمی کند.

الگوریتم فوق، برای مضورب فیه های مثبت و یا منفی بفرم متمم 2 قابل استفاده است. این بدان علت است که مضروب فیه منفی به رشته ای از 1 ها خاتمه می یابد و آخرین عمل تفریق با وزن مناسب خواهد بود. مثلاً مضروب فیه 14- در نمایش متمم 2 عبارتست از 110010 و بصورت -24+22-21 = 14 با آن رفتار می شود.

Booths.jpg

یک نمونه اجرا از این برنامه برای اعداد 6 و 5 :

  1. Operation A Q Q' X

1 Initialize 0000 0101 0 0110

2 A <- A-M 1010 0101 0 0110

3 ShiftR 1101 0010 1 0110

4 A <- A+M 0011 0010 1 0110

5 ShiftR 0001 1001 0 0110

6 A <- A-M 1011 1001 0 0110

7 ShiftR 1101 1100 1 0110

8 A <- A+M 0011 1100 1 0110

9 ShiftR 0001 1110 0 0110