خوارزمية المقصورة هي خوارزمية الضرب التي تسمح لنا بضرب العددين الصحيحين الثنائيين الموقعين في مكمل 2، على التوالي. كما أنها تستخدم لتسريع أداء عملية الضرب. إنها فعالة جدًا أيضًا. إنه يعمل على بتات السلسلة 0 في المضاعف الذي لا يتطلب بتًا إضافيًا، فقط قم بإزاحة بتات السلسلة الموجودة في أقصى اليمين وسلسلة من 1 في وزن بت مضاعف 2كللوزن 2مالتي يمكن اعتبارها 2ك+1- 2م .
فيما يلي التمثيل التصويري لخوارزمية الجناح:
في المخطط الانسيابي أعلاه، في البداية، تكييف و سن + 1 تم تعيين البتات على 0، و SC هو عداد تسلسل يمثل إجمالي مجموعة البتات ن، وهو ما يساوي عدد البتات في المضاعف. هناك ر التي تمثل البتات المضاعفة، و QR يمثل البتات المضاعفة . بعد ذلك، واجهنا قطعتين من المضاعف كـ Qنو سن + 1، حيث يمثل Qn الجزء الأخير من QR، وQن + 1يمثل البتة المتزايدة لـ Qn بمقدار 1. لنفترض أن بتتين من المضاعف تساوي 10؛ فهذا يعني أنه يتعين علينا طرح المضاعف من المنتج الجزئي في المجمع المتناوب ومن ثم إجراء عملية التحويل الحسابي (عشر). إذا كان اثنان من المضاعفات يساوي 01، فهذا يعني أننا بحاجة إلى إجراء عملية إضافة المضاعف إلى المنتج الجزئي في المجمع AC ثم إجراء عملية الإزاحة الحسابية ( عشر )، مشتمل سن + 1 . يتم استخدام عملية التحول الحسابي في خوارزمية Booth لتحويل بتات AC وQR إلى اليمين بمقدار وحدة واحدة وتظل بتة الإشارة في AC دون تغيير. ويتناقص عداد التسلسل بشكل مستمر حتى تتكرر الحلقة الحسابية، بما يساوي عدد البتات (n).
العمل على خوارزمية بوث
- قم بتعيين البتات الثنائية المضاعف والمضاعف كـ M وQ، على التوالي.
- في البداية قمنا بضبط AC و Qن + 1يسجل القيمة إلى 0.
- يمثل SC عدد البتات المضاعفة (Q)، وهو عداد تسلسل يتناقص بشكل مستمر حتى يساوي عدد البتات (n) أو يصل إلى 0.
- يمثل Qn الجزء الأخير من Q، ويمثل Qن+1يُظهر البت المتزايد لـ Qn بمقدار 1.
- في كل دورة من خوارزمية المقصورة، Qنو سن + 1سيتم فحص البتات على المعلمات التالية على النحو التالي:
- عندما بتتين سنو سن + 1إذا كانت 00 أو 11، فإننا ببساطة نقوم بإجراء عملية التحول الحسابي الصحيح (ashr) إلى المنتج الجزئي AC. وبتات Qn و Qن + 1يتم زيادتها بمقدار 1 بت.
- إذا كانت أجزاء Qنو سن + 1يظهر إلى 01، ستتم إضافة البتات المضاعفة (M) إلى AC (سجل المجمع). بعد ذلك، نقوم بإجراء عملية التحول الصحيح إلى بتات AC و QR بمقدار 1.
- إذا كانت أجزاء Qنو سن + 1عندما يظهر إلى 10، سيتم طرح البتات المضاعفة (M) من AC (سجل المجمع). بعد ذلك، نقوم بإجراء عملية التحول الصحيح إلى بتات AC و QR بمقدار 1.
- العملية تعمل بشكل مستمر حتى وصلنا إلى n - 1 بت في خوارزمية المقصورة.
- سيتم تخزين نتائج البتات الثنائية للضرب في سجلات AC وQR.
هناك طريقتان مستخدمتان في خوارزمية Booth:
طبقة الشبكة في شبكات الكمبيوتر
1. RSC (تعميم التحول الأيمن)
يقوم بإزاحة البت الموجود في أقصى اليمين من الرقم الثنائي، ثم تتم إضافته إلى بداية البتات الثنائية.
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 (Sequence Count) يمثل عدد البتات، وهنا لدينا 4 بتات، لذا قم بتعيين SC = 4. كما أنه يوضح عدد دورات التكرار لخوارزميات الكشك ثم يتم تشغيل الدورات SC = SC - 1 مرة.
| سن | سن + 1 | م = (0111) م' + 1 = (1001) والتشغيل | تكييف | س | سن + 1 | SC |
|---|---|---|---|---|---|---|
| 1 | 0 | أولي | 0000 | 0011 | 0 | 4 |
| طرح او خصم (م + 1) | 1001 | |||||
| 1001 | ||||||
| تنفيذ عمليات التحول الحسابي لليمين (ashr) | 1100 | 1001 | 1 | 3 | ||
| 1 | 1 | تنفيذ عمليات التحول الحسابي لليمين (ashr) | 1110 | 0100 | 1 | 2 |
| 0 | 1 | إضافة (أ + م) | 0111 | |||
| 0101 | 0100 | |||||
| تنفيذ عملية التحول الحسابي لليمين | 0010 | 1010 | 0 | 1 | ||
| 0 | 0 | تنفيذ عملية التحول الحسابي لليمين | 0001 | 0101 | 0 | 0 |
المثال العددي لخوارزمية الضرب في Booth هو 7 × 3 = 21 والتمثيل الثنائي لـ 21 هو 10101. هنا نحصل على الناتج بالنظام الثنائي 00010101. الآن نقوم بتحويله إلى رقم عشري، مثل (000010101)10= 2*4 + 2*3 + 2*2 + 2*1 + 2*0 => 21.
قيمة سلسلة جافا
مثال: ضرب الرقمين 23 و -9 باستخدام خوارزمية الضرب الخاصة بـ Booth.
هنا، M = 23 = (010111) وQ = -9 = (110111)
| سنسن + 1 | م = 0 1 0 1 1 1 م' + 1 = 1 0 1 0 0 1 | تكييف | س | سن + 1SC |
|---|---|---|---|---|
| بدءًا | 000000 | 110111 | 0 6 | |
| 1 0 | اطرح م | 101001 | ||
| 101001 | ||||
| تنفيذ عملية التحول الحسابي لليمين | 110100 | 111011 | خمسة عشر | |
| أحد عشر | تنفيذ عملية التحول الحسابي لليمين | 111010 | 011101 | 1 4 |
| أحد عشر | تنفيذ عملية التحول الحسابي لليمين | 111101 | 001110 | 1 3 |
| 0 1 | إضافة (أ + م) | 010111 | ||
| 010100 | ||||
| تنفيذ عملية التحول الحسابي لليمين | 001010 | 000111 | 0 2 | |
| 1 0 | اطرح م | 101001 | ||
| 110011 | ||||
| تنفيذ عملية التحول الحسابي لليمين | 111001 | 100011 | أحد عشر | |
| أحد عشر | تنفيذ عملية التحول الحسابي لليمين | 111100 | 110001 | 1 0 |
سن + 1 = 1 فهذا يعني أن الناتج سلبي.
ومن ثم، 23 * -9 = مكمل 2 لـ 111100110001 => (00001100111)