شجرة والاس

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 30 صور
الموسوعة الحرة
اختزال والاس ذو الأربع طبقات لمصفوفة ضرب جزئي 8×8، باستخدام 15 جامع نصفي (نقطتان) و38 جامع كامل (ثلاث نقاط). النقاط في كل عمود هي بتات متساوية الوزن.

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

تم ابتكار مضاعفات والاس بواسطة عالم الكمبيوتر الأسترالي كريس والاس في عام 1964. [ 2 ]

تتكون شجرة والاس من ثلاث خطوات:

  1. اضرب كل بت من أحد الوسائط في كل بت من الوسائط الأخرى.
  2. قلل عدد المنتجات الجزئية إلى اثنين عن طريق طبقات من جامعات كاملة ونصفية .
  3. قم بتجميع الأسلاك في مجموعتين، واجمعهما باستخدام جامع تقليدي. [ 3 ]

بالمقارنة مع الجمع البسيط للمنتجات الجزئية باستخدام أدوات الجمع العادية، فإن ميزة شجرة والاس تكمن في سرعتها الأكبر.يا(سجل⁡ن){\displaystyle O(\log n)}طبقات الاختزال، ولكن كل طبقة تحتوي فقط على طبقات اختزاليا(1){\displaystyle O(1)}تأخير الانتشار. يتطلب الجمع البسيط للمنتجات الجزئيةيا(سجل2⁡ن){\displaystyle O(\log ^{2}n)}الوقت. لأن صنع المنتجات الجزئية هويا(1){\displaystyle O(1)}والإضافة الأخيرة هييا(سجل⁡ن){\displaystyle O(\log n)}، إجمالي عملية الضرب هويا(سجل⁡ن){\displaystyle O(\log n)}ليست أبطأ بكثير من الجمع. من منظور نظرية التعقيد ، يصنف خوارزمية شجرة والاس عملية الضرب ضمن فئة NC 1. أما عيب شجرة والاس، مقارنةً بالجمع البسيط للنواتج الجزئية، فهو عدد البوابات المنطقية الأعلى بكثير.

لا تأخذ هذه الحسابات في الاعتبار سوى تأخيرات البوابات ولا تتعامل مع تأخيرات الأسلاك، والتي يمكن أن تكون كبيرة جدًا أيضًا.

يمكن أيضًا تمثيل شجرة والاس بشجرة من 3/2 أو 4/2.

يتم دمجها أحيانًا مع ترميز بوث . [ 4 ] [ 5 ]

شرح مفصل

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

الخطوة الأولى، كما ذكرنا سابقًا، هي ضرب كل بت من أحد الرقمين بكل بت من الرقم الآخر، ويتم ذلك باستخدام بوابة AND بسيطة، مما ينتج عنهن2{\displaystyle n^{2}}البتات؛ الناتج الجزئي للبتاتأم{\displaystyle a_{m}}بواسطةبن{\displaystyle b_{n}}له وزن2(م+ن){\displaystyle 2^{(m+n)}}

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

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

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

مثال

ن=4{\displaystyle n=4}، الضربأ3أ2أ1أ0{\displaystyle a_{3}a_{2}a_{1}a_{0}}بواسطةب3ب2ب1ب0{\displaystyle b_{3}b_{2}b_{1}b_{0}}:

  1. أولاً، نقوم بضرب كل بت في كل بت:
    • الوزن 1 –أ0ب0{\displaystyle a_{0}b_{0}}
    • الوزن 2 –أ0ب1{\displaystyle a_{0}b_{1}}،أ1ب0{\displaystyle a_{1}b_{0}}
    • الوزن 4 –أ0ب2{\displaystyle a_{0}b_{2}}،أ1ب1{\displaystyle a_{1}b_{1}}،أ2ب0{\displaystyle a_{2}b_{0}}
    • الوزن 8 –أ0ب3{\displaystyle a_{0}b_{3}}،أ1ب2{\displaystyle a_{1}b_{2}}،أ2ب1{\displaystyle a_{2}b_{1}}،أ3ب0{\displaystyle a_{3}b_{0}}
    • الوزن 16 –أ1ب3{\displaystyle a_{1}b_{3}}،أ2ب2{\displaystyle a_{2}b_{2}}،أ3ب1{\displaystyle a_{3}b_{1}}
    • الوزن 32 –أ2ب3{\displaystyle a_{2}b_{3}}،أ3ب2{\displaystyle a_{3}b_{2}}
    • الوزن 64 –أ3ب3{\displaystyle a_{3}b_{3}}
  2. طبقة التخفيض 1:
    • مرر السلك ذو الوزن 1 فقط، الناتج: سلك واحد ذو وزن 1
    • أضف جامعًا نصفيًا للوزن 2، والمخرجات: وزن واحد - سلكان، وزن واحد - 4 أسلاك
    • أضف جامعًا كاملًا للوزن 4، والمخرجات: سلك وزن 4 واحد، وسلك وزن 8 واحد
    • أضف دائرة جمع كاملة للوزن 8، ومرر السلك المتبقي من خلالها، والمخرجات: سلكان للوزن 8، وسلك واحد للوزن 16
    • أضف جامعًا كاملًا للوزن 16، والمخرجات: سلك وزن 16 واحد، وسلك وزن 32 واحد
    • أضف جامعًا نصفيًا للوزن 32، والمخرجات: سلك وزن 32 واحد، وسلك وزن 64 واحد
    • مرر السلك الوحيد ذو الوزن 64، الناتج: سلك واحد ذو وزن 64
      طبقة التخفيض 1 لشجرة والاس 4×4
  3. الأسلاك عند مخرج طبقة التخفيض 1:
    • الوزن 1 – 1
    • الوزن 2 – 1
    • الوزن 4 – 2
    • الوزن 8 – 3
    • الوزن 16 – 2
    • الوزن 32 – 2
    • الوزن 64 – 2
  4. طبقة الاختزال 2:
    • أضف مُعدِّلًا كاملًا للوزن 8، ومُعدِّلات نصفية للأوزان 4 و16 و32 و64
      طبقة التخفيض 2 لشجرة والاس 4×4
  5. المخرجات:
    • الوزن 1 – 1
    • الوزن 2 – 1
    • الوزن 4 – 1
    • الوزن 8 – 2
    • الوزن 16 – 2
    • الوزن 32 – 2
    • الوزن 64 – 2
    • الوزن 128 – 1
      الطبقة النهائية لشجرة والاس 4 × 4
  6. قم بتجميع الأسلاك في أزواج من الأعداد الصحيحة وجهاز جمع لجمعها.

انظر أيضاً

مراجع

  1. ↑ تاونسند، ويتني جيه؛ شوارتزلاندر، إيرل إي؛ أبراهام، جاكوب أ. (2003). "مقارنة بين تأخيرات مضاعفات دادا ووالاس" . في: لوك، فرانكلين تي. (محرر). خوارزميات معالجة الإشارات المتقدمة، والهياكل، والتطبيقات XIII . وقائع SPIE. المجلد 5205.  الصفحات 552-560 . Bibcode : 2003SPIE.5205..552T . doi : 10.1117/12.507012 . ISSN 0277-786X . S2CID 121437680 .   
  2. ↑ والاس، كريستوفر ستيوارت (فبراير 1964). "اقتراح لمضاعف سريع". معاملات IEEE في الحواسيب الإلكترونية . EC-13 (1): 14-17 . doi : 10.1109/PGEC.1964.263830 . S2CID 34688264 . 
  3. ↑ بوهسالي، منير؛ دوان، مايكل (2010). "مضاعفات شجرة والاس ذات النمط المستطيل" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 15 فبراير 2010.
  4. ↑ "مقدمة" . مضاعف شجرة والاس المشفر بتقنية بوث 8x8 . جامعة تافتس. 2007. مؤرشف من الأصل بتاريخ 17-06-2010.
  5. ↑ ويمز الابن، تشارلز سي. (2001) [1995]. "مناقشة علوم الحاسوب 535 رقم 7: تمثيلات الأعداد" . أمهيرست: جامعة ماساتشوستس. مؤرشف من الأصل بتاريخ 2011-02-06.

للمزيد من القراءة

  • سافارد، جون جي جي (2018) [2006]. "تقنيات حسابية متقدمة" . كوادريبلوك . مؤرشف من الأصل بتاريخ 3 يوليو 2018. تم الاطلاع عليه بتاريخ 16 يوليو 2018 .
  • تطبيق عام لـ VHDL لمضاعف شجرة والاس .