المضاعف الثنائي

تعتمد الطريقة المُدرَّسة في المدارس لضرب الأعداد العشرية على حساب نواتج الضرب الجزئية، ثم نقلها إلى اليسار وجمعها. أصعب جزء هو الحصول على نواتج الضرب الجزئية، لأن ذلك يتطلب ضرب عدد طويل في رقم واحد (من 0 إلى 9).

 123 × 456 ===== 738 (هذا يساوي 123 × 6) 615 (هذا هو 123 × 5، تم تحريكه خانة واحدة إلى اليسار) + 492 (هذا يساوي 123 × 4، مع إزاحة خانتين إلى اليسار) ===== 56088

يقوم الحاسوب الثنائي بنفس عملية الضرب التي يقوم بها النظام العشري، ولكن باستخدام الأرقام الثنائية. في الترميز الثنائي، يُضرب كل عدد طويل في رقم واحد (إما 0 أو 1)، وهذا أسهل بكثير من النظام العشري، لأن ناتج الضرب في 0 أو 1 هو 0 أو نفس العدد. لذلك، فإن ضرب عددين ثنائيين يقتصر على حساب نواتج الضرب الجزئية (وهي 0 أو العدد الأول)، ثم إزاحتها إلى اليسار، ثم جمعها معًا (عملية جمع ثنائية، بالطبع).

 1011 (هذا هو التمثيل الثنائي للعدد العشري 11) × 1110 (هذا هو النظام الثنائي للعدد العشري 14) ====== 0000 (هذا يساوي 1011 × 0) 1011 (هذا هو 1011 × 1، مع إزاحة خانة واحدة إلى اليسار) 1011 (هذا هو 1011 × 1، مع إزاحة خانتين إلى اليسار) + 1011 (هذا هو 1011 × 1، مع إزاحة ثلاثة مواضع إلى اليسار) ========= 10011010 (هذا هو التمثيل الثنائي للعدد العشري 154)

هذا أبسط بكثير من النظام العشري، حيث لا يوجد جدول ضرب يجب تذكره: مجرد عمليات إزاحة وجمع.

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

لنفترض أننا نريد ضرب عددين صحيحين غير مُوَقَّعين من 8 بتات معًا: a [7:0] و b [7:0]. يمكننا إنتاج ثمانية نواتج جزئية عن طريق إجراء ثماني عمليات ضرب بت واحد، واحدة لكل بت في العدد المضروب a :

p0[7:0] = a[0] × b[7:0] = {8{a[0]}} & b[7:0] p1[7:0] = أ[1] × ب[7:0] = {8{أ[1]}} & ب[7:0] p2[7:0] = a[2] × b[7:0] = {8{a[2]}} & b[7:0] p3[7:0] = a[3] × b[7:0] = {8{a[3]}} & b[7:0] p4[7:0] = a[4] × b[7:0] = {8{a[4]}} & b[7:0] p5[7:0] = أ[5] × ب[7:0] = {8{أ[5]}} & ب[7:0] p6[7:0] = a[6] × b[7:0] = {8{a[6]}} & b[7:0] p7[7:0] = a[7] × b[7:0] = {8{a[7]}} & b[7:0]

حيث يتم استخدام تدوين Verilog التالي :

• {8{a[0]}} تعني تكرار a[0] (البت 0 من a) 8 مرات.
• يشير a [7:0] إلى اختيار a من البت السابع إلى البت صفر، بما في ذلك، ليصبح المجموع 8 بتات.
• &يرمز الرمز إلى عملية AND الثنائية.

للحصول على المنتج النهائي، نحتاج بعد ذلك إلى جمع جميع المنتجات الجزئية الثمانية، كما هو موضح هنا:

 p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0] + p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0 + p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0 0 + p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0 0 0 + p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0 0 0 0 + p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0 0 0 0 0 + p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0 0 0 0 0 0 + p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0 0 0 0 0 0 0 ----------------------------------------------------------------------------------------------- P[15] P[14] P[13] P[12] P[11] P[10] P[9] P[8] P[7] P[6] P[5] P[4] P[3] P[2] P[1] P[0]

بمعنى آخر، يتم إنتاج P [15:0] عن طريق جمع p0 ، p1 << 1، p2 << 2، وهكذا، لإنتاج منتجنا النهائي غير الموقع ذي 16 بت:

P [15:0] = p0[7:0] + (p1[7:0] << 1) + (p2[7:0] << 2) + (p3[7:0] << 3) + (p4[7:0] << 4) + (p5[7:0] << 5) + (p6[7:0] << 6) + (p7[7:0] << 7)

لنفترض أننا نريد الآن ضرب عددين صحيحين غير مُوَقَّعين من 16 بت: u [15:0] و v [15:0] باستخدام مُضاعِف 8×8 بت من قبل. باستخدام طريقة الضرب الجزئي (المُبرَّرة بخاصية التجميع في الضرب) والتنفيذ على أجزاء من 8 بت، نحصل على:

p0[15:0] = u[7:0] × v[7:0] p1[15:0] = u[15:8] × v[7:0] p2[15:0] = u[7:0] × v[15:8] p3[15:0] = u[15:8] × v[15:8]

سيكون المنتج النهائي كالتالي:

P[31:0] = p0 + p1 << 8 + p2 << 8 + p3 << 16

يلاحظ المرء أنه إذا كان المطلوب فقط هو P[15:0] (أقل 16 بت من النتيجة)، فلا حاجة لحساب p3.

استخدمت بنى المضاعفات القديمة مُبدِّلًا ومُجمِّعًا لجمع كل ناتج جزئي، وغالبًا ناتج جزئي واحد لكل دورة، مما أدى إلى المفاضلة بين السرعة ومساحة الشريحة. ولتحقيق القدرة على إجراء عملية تجميع واحدة لكل دورة، يلزم وجود جامع سريع (أسرع من جامع التموج). ^{[ 8 ]}

تستخدم بنى المضاعفات الحديثة خوارزمية Baugh-Wooley (المعدلة) ، ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]} أشجار Wallace ، أو مضاعفات Dadda لجمع المنتجات الجزئية معًا في دورة واحدة.

في المضاعف السريع، تُساهم عملية اختزال الناتج الجزئي (أي حساب المجاميع الجزئية) عادةً في أكبر قدر من التأخير واستهلاك الطاقة ومساحة المضاعف. ^{[ 6 ]} ولتحقيق السرعة، تُنفذ مراحل "اختزال الناتج الجزئي" عادةً كجامع حفظ الحمل مُكوّن من ضواغط، بينما تُنفذ خطوة "حساب الناتج النهائي" كجامع سريع.

الضاغط هو أي جهاز يستقبل عددًا من البتات كمدخلات يفوق ما ينتجه كمخرجات. في سياق هندسة المضاعفات، يشير إلى جامع ذي مدخل ومخرج حمل. الضاغط الأساسي هو الجامع الكامل، أو "ضاغط 3:2": تستخدم العديد من المضاعفات السريعة هذا النوع من الضواغط المُنفذ بتقنية CMOS الثابتة .

لتحقيق أداء أفضل في نفس المنطقة أو نفس الأداء في منطقة أصغر، قد تستخدم تصميمات المضاعف ضواغط من رتبة أعلى مثل ضواغط 7:3؛ ^{[ 7 ] [ 6 ]} تنفيذ الضواغط في منطق أسرع (مثل منطق بوابة النقل، منطق ترانزستور المرور، منطق الدومينو )؛ ^{[ 8 ]} توصيل الضواغط بنمط مختلف؛ أو مزيج من ذلك.

يتم تحسين أداء تطبيق شجرة والاس أحيانًا عن طريق ترميز Booth المعدل لأحد المضروبين، مما يقلل من عدد المنتجات الجزئية التي يجب جمعها.

المضاعف "ذو الدورة الواحدة" (أو "المضاعف السريع") هو منطق توافقي بحت .

لو كان b عددًا صحيحًا مُوَقَّعًا بدلًا من عدد صحيح غير مُوَقَّع ، لكان من الضروري تمديد الإشارة للضرب الجزئي حتى عرض الضرب قبل جمعه. ولو كان a عددًا صحيحًا مُوَقَّعًا، لكان من الضروري طرح الضرب الجزئي p7 من المجموع النهائي بدلًا من إضافته إليه.

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

 1 ~p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0] + ~p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0 + ~p2[7] p2[6] p2[5] p2[4] p2[3] p2[2] p2[1] p2[0] 0 0 + ~p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0 0 0 + ~p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0 0 0 0 + ~p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0 0 0 0 0 + ~p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0 0 0 0 0 0 + 1 p7[7] ~p7[6] ~p7[5] ~p7[4] ~p7[3] ~p7[2] ~p7[1] ~p7[0] 0 0 0 0 0 0 0 --------------------------------------------------------------------------------------------------------------- P[15] P[14] P[13] P[12] P[11] P[10] P[9] P[8] P[7] P[6] P[5] P[4] P[3] P[2] P[1] P[0]

حيث يمثل ~p مكمل (القيمة المعاكسة) لـ p.

هناك العديد من التبسيطات في مصفوفة البتات أعلاه والتي لم يتم عرضها وليست واضحة.

• إن تسلسل البت المكمل الواحد متبوعًا ببتات غير مكملة يطبق خدعة المكمل الثنائي لتجنب تمديد الإشارة.
• إن تسلسل p7 (البت غير المكمل متبوعًا بجميع البتات المكملة) يرجع إلى أننا نطرح هذا الحد، لذلك تم نفيها جميعًا في البداية (وتمت إضافة 1 في أقل موضع أهمية).

في كلا نوعي التسلسلات، تُقلب البتة الأخيرة ويُضاف إليها ضمنيًا -1 أسفل البتة الأكثر أهمية (MSB) مباشرةً. عند جمع +1 الناتج عن نفي المتمم الثنائي للبتة p7 في الموضع 0 (LSB) مع جميع -1 في الأعمدة من 7 إلى 14 (حيث توجد كل بتة من البتات الأكثر أهمية)، يمكن تبسيطها إلى 1 واحد يظهر تلقائيًا على اليسار. لمزيد من الشرح والبرهان حول سبب توفير قلب البتة الأكثر أهمية لتمديد الإشارة، راجع كتابًا في الحساب الحاسوبي. ^{[ 13 ]}

يحتوي العدد الثنائي ذو الفاصلة العائمة على بت الإشارة، وبتات الأهمية (المعروفة بالمعامل)، وبتات الأس (لتبسيط الأمر، لا نأخذ في الاعتبار الأساس وحقل التركيب). تُجرى عملية XOR بين بتات الإشارة لكل معامل للحصول على إشارة الناتج. ثم يُجمع الأسّان للحصول على أسّ الناتج. وأخيرًا، تُضرب معاملات المعامل للحصول على معامل الناتج. مع ذلك، إذا كان ناتج الضرب الثنائي أكبر من إجمالي عدد البتات لدقة معينة (مثل 32، 64، 128)، يلزم التقريب، ويُعدّل الأس وفقًا لذلك.