اختزال الحدود

في عملية الضرب الثنائي، يكون كل صف من حدود الضرب إما صفرًا أو أحد العددين المراد ضربهما. انظر إلى المثال التالي:

 1001 x1010 ----- 0000 1001 0000 1001

الصفان الثاني والرابع من الحدود يكافئان الحد الأول. يتطلب إنتاج الحدود بوابة AND بسيطة لكل حد. مع توفر عدد كافٍ من بوابات AND، سيستغرق إنتاج الحدود دورة واحدة من وحدة الحساب والمنطق .

تُختزل الحدود باستخدام جامع كامل أحادي البت يقبل حدين أحاديي البت وبتة حمل. ينتج عن ذلك مجموع وحمل. تُرتّب الجامعات الكاملة بحيث يبقى المجموع في نفس عمود الحدود، بينما يُزاح الحمل إلى اليسار. في كل جولة اختزال، تُستخدم ثلاثة بتات في عمود واحد كحدين وحمل للجامع الكامل، مما ينتج عنه بتة مجموع واحدة للعمود. هذا يُقلل عدد البتات في العمود بمقدار 3. مع ذلك، سيُزاح العمود إلى اليمين بمقدار بتات الحمل، مما يزيد عدد البتات في العمود بمقدار ثلث عدد صفوف الحدود. في أسوأ الأحوال، سيكون الاختزال ثلثي عدد الصفوف لكل جولة اختزال.

يوضح الشكل التالي كيفية إجراء الجولة الأولى من عملية الاختزال. لاحظ أن جميع المواضع "الفارغة" في حدود المجموع تُعتبر أصفارًا (يُستخدم الرمز . هنا كمؤشر على "القيم الصفرية المفترضة"). في كل صف، تمثل البتات الثلاثة العليا المدخلات الثلاثة للجامع الكامل (حدان وقيمة الحمل). يُوضع المجموع في البت العلوي من العمود. تُوضع قيمة الحمل في الصف الثاني من العمود إلى اليسار. أما البت السفلي فهو مدخل واحد إلى جامع. يُوضع مجموع هذا الجامع في الصف الثالث من العمود. يتم تجاهل قيمة الحمل لأنها ستكون دائمًا صفرًا، ولكن بحسب التصميم، تُوضع في الصف الرابع من العمود إلى اليسار. من المهم ملاحظة أن الصفوف 1، 3، 5، ... (بدءًا من الأعلى) تُملأ بمجاميع من العمود نفسه. بينما تُملأ الصفوف 2، 4، 6، ... بقيم الحمل من العمود إلى اليمين.

 1011 x0110 ----- ...0000 1011. .1011.. 0000... ------- 0111010 000100. 00000..

تُجرى عملية الاختزال مرة أخرى بنفس الطريقة تمامًا. هذه المرة، لا يهم سوى الصفوف الثلاثة الأولى من الحدود لأن جميع الحدود الأخرى يجب أن تكون صفرًا.

0111010 000100. 00000.. ------- 0110010 001000.

عندما يتبقى صفان مهمان فقط من الحدود، تنتهي دورات الاختزال. يتطلب جامع كامل أساسي عادةً ثلاث دورات من وحدة الحساب والمنطق . لذلك، يبلغ طول كل دورة اختزال عادةً ثلاث دورات.

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