אלגוריתם הדוכן הוא אלגוריתם הכפל המאפשר לנו להכפיל את שני המספרים השלמים הבינאריים החתומים בהשלמה של 2, בהתאמה. הוא משמש גם כדי להאיץ את הביצועים של תהליך הכפל. זה גם מאוד יעיל. זה עובד על סיביות המיתר 0 במכפיל שלא דורש ביט נוסף רק הזז את סיביות המחרוזת הכי ימינה ומחרוזת של 1 במשקל סיביות מכפיל 2 ^ק למשקל 2 ^M זה יכול להיחשב כ 2 ^k+1 - 2 ^M .

להלן הייצוג הציורי של האלגוריתם של ביתן:

בתרשים הזרימה לעיל, תחילה, AC ו ש _{n + 1} סיביות מוגדרות ל-0, וה- SC הוא מונה רצף המייצג את סך הסיביות n, ששווה למספר הביטים במכפיל. יש BR המייצגים את סיביות מרובות, ו-QR מייצג את סיביות מכפיל . לאחר מכן, נתקלנו בשני סיביות מהמכפיל כ-Q _נ ו-Q _{n + 1} , כאשר Qn מייצג את החלק האחרון של QR, ו-Q _{n + 1} מייצג את הסיביות המוגדלות של Qn ב-1. נניח ששתי סיביות של המכפיל שווה ל-10; זה אומר שעלינו להחסיר את המכפיל מהמכפלה החלקית בצובר AC ולאחר מכן לבצע את פעולת ההסטה האריתמטית (אשר). אם שני המכפילים שווים ל-01, זה אומר שעלינו לבצע את חיבור המכפלה למכפלה החלקית במצטבר AC ולאחר מכן לבצע את פעולת ההזזה האריתמטית ( אשר ), כולל ש _{n + 1} . פעולת ההסטה האריתמטית משמשת באלגוריתם של Booth להזזת סיביות AC ו-QR ימינה באחת ונשארת סיבית הסימן ב-AC ללא שינוי. ומונה הרצף מופחת ברציפות עד שהלולאה החישובית חוזרת על עצמה, שווה למספר הסיביות (n).

עובדים על האלגוריתם של Booth

1. הגדר את הסיביות הבינאריות של Multiplicand ו-Multiplier כ-M ו-Q, בהתאמה.
2. בתחילה, הגדרנו את AC ו-Q _{n + 1} רושם ערך ל-0.
3. SC מייצג את מספר סיביות המכפיל (Q), וזהו מונה רצף המופחת ברציפות עד שווה למספר הסיביות (n) או מגיע ל-0.
4. Qn מייצג את הסיבית האחרונה של ה-Q, וה-Q _n+1 מציג את ה-bit המוגדל של Qn ב-1.
5. בכל מחזור של אלגוריתם הדוכן, ש _נ ו-Q _{n + 1} סיביות ייבדקו על הפרמטרים הבאים כדלקמן:
   1. כאשר שני ביטים Q _נ ו-Q _{n + 1} הם 00 או 11, אנו פשוט מבצעים את פעולת ההזזה האריתמטית ימינה (אשר) למוצר החלקי AC. והחלקים של Qn ו-Q _{n + 1} מוגדל ב-1 סיביות.
   2. אם החלקים של Q _נ ו-Q _{n + 1} הוא מראה ל-01, הסיביות המרובות (M) יתווספו ל-AC (אוגר מצבר). לאחר מכן, אנו מבצעים את פעולת ההסטה הנכונה לסיביות AC ו-QR ב-1.
   3. אם החלקים של Q _נ ו-Q _{n + 1} הוא מראה ל-10, הסיביות המרובות (M) יופחתו מה-AC (אוגר מצבר). לאחר מכן, אנו מבצעים את פעולת ההסטה הנכונה לסיביות AC ו-QR ב-1.
6. הפעולה פועלת ברציפות עד שהגענו ל-n - 1 ביט באלגוריתם הדוכן.
7. תוצאות הסיביות הבינאריות של הכפל יאוחסנו באוגרי AC ו-QR.

ישנן שתי שיטות בשימוש באלגוריתם של Booth:

1. RSC (Reight Shift Circular)

זה מעביר את הסיביות הכי ימינה של המספר הבינארי, ואז הוא מתווסף לתחילת הסיביות הבינאריות.

2. RSA (חשבון משמרת ימין)

הוא מוסיף את שני הביטים הבינאריים ואז מעביר את התוצאה ימינה במיקום של 1 סיביות.

דוגמא : 0100 + 0110 => 1010, לאחר הוספת המספר הבינארי העבירו כל סיביות ב-1 ימינה והכניסו את הסיביות הראשונה של התוצאה לתחילת הסיביות החדשה.

דוגמה: הכפל את שני המספרים 7 ו-3 באמצעות אלגוריתם הכפל של Booth.

שנים . כאן יש לנו שני מספרים, 7 ו-3. קודם כל, עלינו להמיר את 7 ו-3 למספרים בינאריים כמו 7 = (0111) ו-3 = (0011). כעת הגדר 7 (בבינארי 0111) כמכפיל (M) ו-3 (בבינארי 0011) כמכפיל (Q). ו-SC (ספירת רצף) מייצגת את מספר הביטים, וכאן יש לנו 4 ביטים, אז הגדר את ה-SC = 4. כמו כן, הוא מראה את מספר מחזורי האיטרציה של האלגוריתמים של התא ואז מחזורים רצים SC = SC - פעם אחת.

הדוגמה המספרית של אלגוריתם הכפל של Booth היא 7 x 3 = 21 והייצוג הבינארי של 21 הוא 10101. כאן, נקבל את התוצאה בבינארי 00010101. כעת נמיר אותו לעשרוני, כמו (000010101) ₁₀ = 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.

דוגמה: הכפל את שני המספרים 23 ו-9 באמצעות אלגוריתם הכפל של Booth.

כאן, M = 23 = (010111) ו-Q = -9 = (110111)

ש _{n + 1} = 1, זה אומר שהפלט שלילי.

לפיכך, 23 * -9 = המשלים של 2 של 111100110001 => (00001100111)