خوارزمية بوث

بووث

إذا كنا محددين بالنظر فقط الخانتين ثنائيتين فقط فإننا عندها نستطيع محاولة المطابقة مع الحالة السابقة بالنظر لحالة هاتين الخانتين الثنائيتين :

الضارب

خوارزمية بووث الموضحة في المخطط التالي مع ملاحظة أن الحالة الأولى تملك أربع احتمالات : بالاعتماد على حالة الخانتين الثنائيتين، وعدنا نفترض أن الخانتين الزوجيتين المفحوصتين تتألفان من الخانة الحالية والخانة التي على يمينها والتي كانت الخانة الحالية في الخطوة السابقة وبالتالي خطوات الخوارزمية كالتالي : 1- بالاعتماد على الخانة الآنية والسابقة قم بأحد التالي :

منتصف العملية هو أصفار، لا داعي لعملية حسابية	00
نهاية سلسلة من الواحدات لذا نضيف الضارب إلى النصف الأيسر من الناتج	01
بداية سلسلة من الواحدات لذا قم بطرح الضارب من النصف الأيسر من الناتج	10
سلسلة من الواحدات، لا داعي لعملية حسابية	11

الآن وبعد أن شوهدت آلية عمل خوارزمية (بالإنجليزية: BOOTH) أصبح بالإمكان لمعرفة سبب نجاحها في الأعداد الصحيحة الثنائية لتجعل (a) الضارب و(b) المضروب به وسوف تستخدم (ai) للإشارة إلى البت رقم (i) من (a) وباسقاط الخوارزمية السابقة على الفرضيات في مسألتنا هذه فإننا نجد :

• عنوان Booth

طالما علم أن إزاحة الضارب يساراً على أنه ضرب لقوى العدد (2) فإن خوارزمية بووث يمكن أن تكتب كالتالي :

(a-1-a0)*6*2^0 (+) 
(a0-a1)*6*2^1 (+) 
(a1-a2)*6*2^2 (+)
(a29-a30)*6*2^30 (+)
                                              (a30-a31)*6*2^31

في الواقع إن خوارزمية بووث تشكل جداء عبر المتمم الثنائي ب ِA&B كما هو موضح في الشكل :

إن استبدال العمليات الحسابية بعملية الإزاحة يمكن أن يحصل أيضاً في عملية الجداء بعدد ثابت، حيث أن بعض المترجمات تستبدل عملية الجداء بعدد ثابت من خلال سلسلة من الإزاحات، الجمع، الطرح ولأن إزاحة عدد خانة واحدة نحو اليسار يمثل ضعفي العدد، فإن إزاحة الخانات نحو اليسار له نفس التأثير كما لو أنه الضرب بقوى العدد (2) لذلك فإن كل مترجم سوف يستبدل كل إزاحة يسارية كجداء لقوى العدد 2

لقد مرت خوارزمية بووث أثناء تحديثها بثلاث مراحل :

• الإصدار الأول من خوارزمية القسمة وبنيتها الهاردويرية :

حيث يكون مسجل القاسم والمقسوم فرضاً وكذلك مسجل الALU ومسجل الباقي عبارة عن مسجلات بعرض (64 bit) أما مسجل الناتج فهو عبارة عن (32 bit) إن المخطط يظهر لنا البنية الهاردويرية والتي سوف نعتمدها.

• سوف نستخدم الخوارزمية في حساب قسمة (00000111)2 على (0010)2

الجدول يظهر كيفية خلق الناتج في أسفل المسجل للباقي وكيفية كون كلاهما سيزاح نحو اليسار في خطوة عملية واحدة.

• الإصدار الثاني لخوارزمية القسمة وبنيتها الهاردويرية :

مرة أخرى قام العلماء بتعديل هام على الإصدار الأول عند ملاحظة أنه دائماً يتم الاستغناء عن نصف المقسوم فماذا لو كانت لدينا معلومات هامة نريد وضعها في ذلك النصف وبالتالي دائماً لدينا المسجل للمقسوم وكذلك لل ALU مقسومات للنصف. إن إزاحة الباقي نحو اليسار بدلاً من الإزاحة للمقسوم نحو اليمين يولد نفس المجاراة ويحقق الأهداف في تبسيط البنية الهاردويرية الضرورية لل ALU والمقسوم والمخطط)يوضح البنية الهاردويرية المبسطة للإصدار الثاني من الخوارزمية.

• الإصدار الثالث والنهائي لخوارزمية القسمة :

يوضح الشكل البنية الهاردويرية لهذه الخوارزمية.

• سوف نستخدم الخوارزمية في حساب قسمة (00000111)2 على (0010)2

الجدول يظهر كيفية خلق الناتج في أسفل المسجل للباقي وكيفية كون كلاهما سيزاح نحو اليسار في خطوة عملية واحدة.

القسمة

من الممكن ملاحظة أن البنية الهاردويرية ممكن أن تستخدم من أجل كلا الضرب والقسمة. المطلب الوحيد هو مسجل خانة (64) الذي يكون بإزاحة نحو اليمين أو اليسار، وكذلك ALU ب (32) خانة الذي يقوم الجمع والطرح فعلى سبيل المثال :MIPS تستخدم (32) خانة عليا و(32) خانة سفلية من أجل كل من الضرب والقسمة. كما يمكن أن نتوقع من الخوارزمية السابقة فإن الخانات العليا تحتوي الباقي والخانات السفلية تحتوي الناتج بعد اكتمال تعليمات القسمة للتعامل مع كل من الأعداد الصحيحة المؤشرة والأعداد غير المؤشرة فإن (MIPS) تحتوي على تعليمتين : divide(div) وكذلك divide unsigned أي (divu) أي مفسر الMIPS يسمح لتعليمات القسمة أن تحدد ثلاث مسجلات تولد التعليمات في مسجل أغراض عامة

MIPS

Mflo أو Mfhi لتوضيع النتائج

المراجع

cs:Boothův algoritmus de:Booth-Algorithmus Booth's multiplication algorithm]] es:Algoritmo de Booth fa:الگوریتم بوث it:Algoritmo di Booth ja:ブースの乗算アルゴリズム lv:Buta algoritms pt:Algoritmo de multiplicação de Booth ru:Алгоритм Бута