آموزش الگوریتم ضرب بوث — به زبان ساده همراه با مثال

در این مقاله از آموزش‌های مجله پی‌استور می‌خواهیم روش الگوریتم ضرب بوث برای ضرب اعداد را بررسی کنیم. الگوریتم ضرب بوث روشی کارآمد برای ضرب اعداد دودویی علامت‌دار است که محاسبات را بهینه و سرعت را افزایش می‌دهد. ایده اصلی این الگوریتم بررسی الگوهای خاص در ضارب (Multiplier) و اجرای جمع یا تفریق بر اساس این الگوها است.

مقدمه

در دنیای کامپیوتر ضرب دو عدد کمی متفاوت‌تر از ضرب دنیای واقعی است. به‌طور کلی، ما در ریاضیات ضرب را به‌عنوان نتیجه جمع‌های پشت‌سرهم می‌شناسیم. این درست است، اما باید بدانیم که پردازنده‌های اولیه زمان کافی داشتند تا به‌آرامی این کار را انجام دهند. با پیشرفت علم کامپیوتر و ظهور فناوری‌هایی مثل سیستم‌های تعبیه‌شده و یادگیری ماشین، نیاز به الگوریتم‌های ضرب سریع‌تر به وجود آمد.

یکی از اولین راه‌حل‌ها، الگوریتم کاراتسوبا بود. این الگوریتم با کمک برنامه‌ریزی پویا توانست کمی فرآیند ضرب را بهبود دهد، اما هنوز سرعت لازم در حد میکروثانیه را فراهم نمی‌کرد.

بنابراین الگوریتم بوث معرفی شد. این الگوریتم به‌دلیل کار با اعداد دودویی، توانست فرآیند ضرب را بدون نیاز به جمع‌های مکرر سرعت ببخشد. شاید بپرسید چگونه این کار بدون جمع انجام می‌شود؟ پاسخ این است که الگوریتم ضرب بوث عملیات جمع را انجام می‌دهد، اما تعداد این جمع‌ها را به‌شدت کاهش می‌دهد.

تعریف الگوریتم ضرب بوث

الگوریتم ضرب بوث (Booth’s Multiplication Algorithm) یک روش مؤثر برای ضرب دو عدد دودویی است که در سال ۱۹۵۱ توسط Andrew D. Booth معرفی شد. این الگوریتم به‌ویژه در پردازشگرهای دیجیتال و محاسبات عددی برای کاهش تعداد عملیات ضرب و بهبود کارایی به کار می‌رود. الگوریتم ضرب بوث به‌طور خاص برای ضرب اعداد دودویی با علامت (یعنی اعداد مثبت و منفی) طراحی شده است، ولی می‌تواند برای ضرب اعداد بدون علامت نیز مورد استفاده قرار گیرد.

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

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

الگوریتم‌های ضرب، از جمله الگوریتم ضرب بوث، در پردازش‌های دیجیتال اهمیت ویژه‌ای دارند، زیرا ضرب یکی از عملیات‌های اساسی در محاسبات است که مستقیماً بر سرعت و کارایی سیستم‌های پردازشی تأثیر می‌گذارد. در پردازنده‌های دیجیتال، حجم بالایی از عملیات شامل ضرب اعداد بزرگ یا اعداد علامت‌دار است. استفاده از روش‌های بهینه مانند الگوریتم بوث، تعداد مراحل محاسباتی را کاهش داده و از منابع سخت‌افزاری به شکل بهتری استفاده می‌کند.

پیش نیاز یادگیری الگوریتم ضرب بوث

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

آموزش تبدیل مبنا با روش سریع برای اعداد اعشاری و صحیح

کلیک کنید

مفهوم باینری و مکمل دو در ضرب اعداد

سیستم عددی دودویی یا باینری یکی از پایه‌های محاسبات دیجیتال است که تنها از دو رقم، یعنی ۰ و ۱ تشکیل شده است. در این سیستم، هر بیت نماینده یک توان از عدد ۲ است و با ترکیب این بیت‌ها، می‌توان مقادیر مختلف را نمایش داد. مانند:

$${(۱۰۱۱)_2} = 1*{۲^۳} + ۰*{۲^۲} + ۱*{۲^۱} + ۱*{۲^۰} = 11$$

برای نمایش اعداد منفی در سیستم دودویی، از مکمل دو استفاده می‌شود. مکمل دو این امکان را فراهم می‌کند که اعداد مثبت و منفی را با روشی یکپارچه در محاسبات استفاده کنیم. فرآیند به دست آوردن مکمل دو شامل معکوس کردن بیت‌های عدد و افزودن یک واحد به نتیجه است. این روش ساده و مؤثر، جمع و تفریق اعداد علامت‌دار را بهینه می‌کند و نقش کلیدی در الگوریتم بوث ایفا می‌کند.

معرفی دو روش اصلی الگوریتم ضرب بوث: RSC و RSA

الگوریتم بوث از دو روش اصلی شیفت دایره‌ای به سمت راست (RSC) و شیفت حسابی به سمت راست (RSA) برای مدیریت و اجرای عملیات استفاده می‌کند. روش RSC، یک شیفت دایره‌ای است که در آن بیت انتهایی رجیستر به بیت ابتدایی منتقل می‌شود و به این ترتیب، بیت‌ها به‌صورت چرخشی جابه‌جا می‌شوند. این روش ساختار کلی بیت‌ها را حفظ می‌کند و در مواردی استفاده می‌شود که علامت عدد در عملیات تأثیری نداشته باشد. در مقابل، روش RSA شیفتی است که در آن بیت علامت عدد (بیت پرارزش‌ترین) حفظ می‌شود و تنها سایر بیت‌ها به سمت راست منتقل می‌شوند. این روش برای محاسبات اعداد علامت‌دار ضروری است، زیرا تضمین می‌کند که علامت عدد پس از هر شیفت، بدون تغییر باقی می‌ماند.

روش شیفت دایره‌ای به سمت راست (RSC)

در روش شیفت دایره‌ای به سمت راست (Right Shift Circular)، بیت انتهایی یک رجیستر به ابتدای آن منتقل می‌شود و سایر بیت‌ها به ترتیب به سمت راست جابه‌جا می‌شوند. این روش هیچ تغییری در ساختار بیت‌ها ایجاد نمی‌کند و معمولاً برای جابه‌جایی داده‌ها بدون در نظر گرفتن علامت استفاده می‌شود. به‌عنوان مثال، اگر رجیستر ۱۰۱۰ باشد، پس از اعمال RSC، نتیجه ۰۱۰۱ خواهد بود. این روش ساده و سریع است و در بسیاری از کاربردهای دیجیتال مورد استفاده قرار می‌گیرد.

روش شیفت حسابی به سمت راست (RSA)

روش شیفت حسابی به سمت راست (Right Shift Arithmetic) بر حفظ علامت عدد در هنگام شیفت تأکید دارد. در این روش، بیت پرارزش‌ترین (که نشان‌دهنده علامت عدد است) ثابت باقی می‌ماند و سایر بیت‌ها به سمت راست جابه‌جا می‌شوند. این ویژگی باعث می‌شود که مقدار نهایی عدد پس از شیفت، به لحاظ منطقی درست باقی بماند. برای مثال، اگر رجیستر ۱۰۱۱ که معادل ۵- در مکمل دو است، شیفت حسابی شود، نتیجه ۱۱۰۱ خواهد بود که همچنان معادل ۵- است. این روش برای محاسباتی که نیاز به حفظ علامت اعداد دارند، حیاتی است.

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

اصطلاحات الگوریتم ضرب بوث

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

• Sequence Count یا SC: تعداد توالی ضرب است و نشان دهنده آن است که چند مرحله عملیات باید انجام شود. این تعداد بر اساس تعداد بیت‌های ضارب محاسبه می‌شود. این شمارنده هر بار که یک چرخه از الگوریتم به پایان می‌رسد، یک واحد کاهش می‌یابد و وقتی به صفر رسید، الگوریتم متوقف می‌شود.
• Multiplicand یا M: مضروب، عددی است که به‌عنوان ورودی برای ضرب استفاده می‌شود. این عدد در دودویی به صورت مکمل دو ذخیره می‌شود و در هر مرحله از الگوریتم می‌تواند با دیگر مقادیر ترکیب شود.
• Multiplier یا Q: ضارب، عددی است که با مضروب (M) ضرب می‌شود. این عدد نیز به‌صورت دودویی در الگوریتم ضرب بوث پردازش می‌شود و نقش کلیدی در تعیین چگونگی انجام عملیات ضرب دارد.
• AC: جمع‌کننده، یک رجیستر است که برای ذخیره نتایج میان‌برداری در حین اجرای الگوریتم ضرب بوث استفاده می‌شود. در ابتدا مقدار AC صفر است، و در هر مرحله از الگوریتم، ممکن است به آن مقدار اضافه یا از آن کسر شود.
• Multiplier Bit یا Qn: این بیت نمایانگر آخرین بیت از ضارب (Q) است که در ابتدا مقدار آن صفر در نظر گرفته می‌شود. در الگوریتم ضرب بوث، از این بیت برای تعیین عملیات‌هایی مانند جمع یا تفریق استفاده می‌شود.
• شیفت: شیفت دادن عدد به معنی جابجا کردن تمام بیت‌های یک عدد در دودویی (صفر و یک‌ها) به سمت راست یا چپ است. این عمل مثل این است که تمام ارقام دودویی را حرکت دهیم و جاهای خالی را با صفر یا یک پر کنیم، بسته به نوع شیفت و عدد.

قرارداد الگوریتم ضرب بوث

در این الگوریتم برای شروع عملیات جمع نیاز به یک قرارداد داریم تا بدانیم چه عملیاتی باید پیش بگیریم. الگوریتم ضرب بوث بر اساس مقادیر دو بیت انتهایی تصمیم می‌گیرد که چه عملی انجام شود. به طور کلی سه حالت در این الگوریتم وجود دارد:

• حالت ۱ (۰۰ یا ۱۱): اگر دو بیت آخر برابر با ۰۰ یا ۱۱ باشند، بدون اینکه عملیات جمع یا تفریقی انجام شود، به‌سادگی عملیات شیفت حسابی به سمت راست (ashr) را روی AC و Q انجام می‌دهیم.
• حالت ۲ (۰۱): اگر بیت‌های آخر برابر با ۰۱ باشند، باید بیت‌های Multiplicand را به AC (رجیستر جمع‌کننده) اضافه کنیم. سپس عملیات شیفت راست را به‌طور همزمان روی AC و Q انجام می‌دهیم.
• حالت ۳ (۱۰): اگر بیت‌های آخر برابر با ۱۰ باشند، باید بیت‌های Multiplicand را از AC (رجیستر جمع‌کننده) کم کنیم. سپس عملیات شیفت راست را روی AC و Q انجام می‌دهیم.

مثال الگوریتم ضرب بوث

بیایید یک مثال واقعی بزنیم تا بهتر با مفاهیم بالا و روش ضرب بوث آشنا شویم. فرض کنید میخواهیم عدد ۷ را در ۳ ضرب کنیم. در حالت عادی می‌دانیم که پاسخ ۲۱ است. اما بیایید این عملیات ضرب را با اعداد دودویی و به روش ضرب بوث انجام دهیم.

ابتدا کاری که باید انجام دهید این است که Multiplicand و Q را در معادل دودویی آن پیدا کنیم.

• معادل عدد ۷: 0111
• معادل عدد ۳: 0011
• مکمل عدد ۷: 1001

– نکته: باید مکمل مضروب نیز پیدا کنید، چرا که ما می‌توانیم به جای عمل تفریق، از عمل جمع با کمک مکمل Multiplicand استفاده کنیم که سرعت کار را افزایش می‌دهد. برای پیدا کردن مکمل یک عد دودویی، تنها کافیست اولین بیت سمت راست را بدون تغییر نگه داشته، و بقیه بیت‌ها را معکوس کنیم (اگر ۰ باشد ۱، و اگر ۱ باشد ۰ قرار می‌دهیم).

برای شروع یک جدول می‌کشیم و مقادیر را به صورت زیر جایگذاری می‌کنیم.

تعداد بیت‌های ضارب ۴ عدد است بنابراین مقدار SC را ۴ قرار می‌دهیم. این به این معنی است که در ۵ مرحله عملیات ضرب باید به اتمام برسد. همانطور که می‌بینید رقم آخر بیت ضارب در اینجا ۱ و بیت Qn در اینجا ۰ است (طبق قانون الگوریتم ضرب بوث)؛ بنابراین حالت ۳ از قرارداد (۱۰) یعنی عمل تفریق باید انجام گردد.

از آنجایی که می‌توانیم به جای انجام عمل تفریق، از عمل جمع استفاده کنیم، بنابراین مقدار اولیه AC را با مکمل Multiplicand جمع می‌کنیم؛

یعنی ۰۰۰۰ + ۱۰۰۱ = ۱۰۰۱

به جای Q نیز خود مقدار قبلی جایگزین می‌شود یعنی ۰۰۱۱ چرا که هنوز عملیاتی بر روی آن انجام نشده است. در ادامه باید عملیات شیفت را انجام دهیم. در انجام عملیات شیفت، همانطور که می‌دانید، بیت اول عدد از سمت چپ ثابت می‌ماند، سپس تمامی ارقام یک واحد به سمت راست شیفت می‌شوند. آخرین بیت Q نیز در عملیات شیفت به ستون QN منتقل می‌شود.

– نکته مهم: کاری که در ادامه انجام می‌دهیم این است که بیت آخر ضارب یعنی Q را در قسمت Qn وارد می‌کنیم. بنابراین خواهیم داشت:

در این بخش از مقاله الگوریتم ضرب بوث، همانطور که می‌بینید رقم آخر بیت ضارب ۱ و بیت Qn در اینجا ۱ است؛ بنابراین حالت ۱ از قرارداد (۱۱) انجام می‌شود. در ادامه بدون هیچ عملیاتی مقادیر را شیفت می‌دهیم. ابتدا مقادیر اولیه را می‌نویسیم سپس نتایج شیفت را در زیر آن می‌نویسیم. بنابراین خواهیم داشت:

در اینجا رقم آخر بیت ضارب ۰ و بیت Qn در اینجا ۱ است؛ بنابراین حالت ۲ از قرارداد (۰۱) یعنی عمل جمع باید انجام گردد. بنابراین Multiplicand را با AC جمع می‌کنیم؛

یعنی: ۰۱۱۱ + ۱۱۱۰ = ۰۱۰۱

مقدار Q نیز همان را می‌نویسیم و در ادامه عملیات شیفت را انجام می‌دهیم. خواهیم داشت:

در آخر نیز همانطور که می‌بینید بیت آخر Q و بیت Qn هر دو ۰ است و عملیاتی انجام نمیگیرد. تنها شیفت انجام می‌دهیم تا در نهایت ببینیم پاسخ درست به دست می‌آید یا نه. خواهیم داشت:

در نهایت، پاسخ نهایی ما بدون در نظر گرفتن صفرهای بی‌ارزش سمت چپ، برابر با ۱۰۱۰۱ خواهد بود. به صورت زیر داریم:

همانطور که در جدول نیز می‌بینید، مضروب (۰۱۱۱) و ضارب (۰۰۱۱) که به ترتیب معادل ۷ و ۳ در مبنای ۱۰ هستند، حاصل ضربشان معادل ۱۰۱۰۱ در مبنای ۲ (یا ۲۱ در مبنای ۱۰) است.

نتیجه گیری

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