Wallace ağacı - Wallace tree

14 yarım toplayıcı (iki nokta) ve 38 tam toplayıcı (üç nokta) kullanarak 8x8 kısmi ürün matrisinin 4 katmanlı Wallace indirgemesi . Her sütundaki noktalar eşit ağırlıktaki bitlerdir.

Bir çarpan Wallace a, donanım bir uygulama ikili çarpanı , çarpma iki tamsayı olduğu, bir dijital devre. Bu bir seçim kullanır tam ve yarım toplayıcılar ( Wallace ağaç veya Wallace azaltma iki sayı kalmayıncaya kadar kademeli olarak kısmi ürünlerini toplamak). Wallace çarpanları her katmanda mümkün olduğu kadar azalır, Dadda çarpanları ise indirgemeyi üst katmanlara erteleyerek gerekli kapı sayısını en aza indirmeye çalışır.

Wallace çarpanları, 1964 yılında Avustralyalı bilgisayar bilimcisi Chris Wallace tarafından tasarlandı .

Wallace ağacının üç adımı vardır:

1. Argümanlardan birinin her bitini diğerinin her bitiyle çarpın.
2. Kısmi ürünlerin sayısını, tam ve yarım toplayıcı katmanları ile ikiye azaltın .
3. Kabloları iki numarada gruplayın ve geleneksel bir toplayıcı ile ekleyin.

Normal toplayıcılarla saf bir şekilde kısmi ürünler eklemekle karşılaştırıldığında, Wallace ağacının avantajı daha hızlı olmasıdır. Bu sahip indirgeme katmanları, ancak her tabakanın sadece var yayılım gecikmesi. Kısmi ürünlerin saf bir şekilde eklenmesi zaman gerektirir . Kısmi çarpımları yapmak ve son toplama olduğu gibi, toplam çarpma toplamadan çok daha yavaş değildir. Bir itibaren karmaşıklığı teorik perspektiften, sınıfta Wallace ağaç algoritması koyar çarpma NC ¹ . Kısmi ürünlerin saf olarak eklenmesine kıyasla Wallace ağacının dezavantajı, çok daha yüksek kapı sayısıdır. ${\ Displaystyle O(\log n)}$${\görüntüleme stili O(1)}$${\ Displaystyle O(\log ^{2}n)}$${\görüntüleme stili O(1)}$${\ Displaystyle O(\log n)}$${\ Displaystyle O(\log n)}$

Bu hesaplamalar yalnızca geçit gecikmelerini dikkate alır ve çok önemli olabilen kablo gecikmeleriyle ilgilenmez.

Wallace ağacı ayrıca 3/2 veya 4/2 toplayıcılardan oluşan bir ağaçla temsil edilebilir.

Bazen Booth kodlaması ile birleştirilir .

Detaylı açıklama

Wallace ağacı, uzun çarpmanın bir çeşididir . İlk adım, bir faktörün her basamağını (her biti) diğerinin her basamağı ile çarpmaktır. Bu kısmi ürünlerin her biri, faktörlerinin ürününe eşit ağırlığa sahiptir. Nihai ürün, tüm bu kısmi ürünlerin ağırlıklı toplamı ile hesaplanır.

İlk adım, yukarıda belirtildiği gibi, bir sayının her bitini diğerinin her biti ile çarpmaktır, bu basit bir AND geçidi olarak gerçekleştirilir ve bitlerle sonuçlanır ; bit kısmi ürün ile ağırlığa sahiptir${\görüntüleme stili n^{2}}$${\ Displaystyle a_{m}}$${\ Displaystyle b_{n}}$${\ Displaystyle 2^{(m+n)}}$

İkinci adımda, elde edilen bitler iki sayıya indirgenir; bu şu şekilde gerçekleştirilir: Aynı ağırlığa sahip üç veya daha fazla tel olduğu sürece aşağıdaki katmanı ekleyin:-

• Aynı ağırlıktaki herhangi üç kabloyu alın ve bunları tam toplayıcıya girin . Sonuç, aynı ağırlıkta bir çıkış kablosu ve her üç giriş kablosu için daha yüksek ağırlığa sahip bir çıkış kablosu olacaktır.
• Aynı ağırlıkta iki kablo kaldıysa, bunları yarım toplayıcıya girin .
• Sadece bir tel kaldıysa, onu bir sonraki katmana bağlayın.

Üçüncü ve son adımda, elde edilen iki sayı bir toplayıcıya beslenir ve nihai ürün elde edilir.

Örnek

${\görüntüleme stili n=4}$, Çarpılması yoluyla : ${\displaystyle a_{3}a_{2}a_{1}a_{0}}$${\displaystyle b_{3}b_{2}b_{1}b_{0}}$

1. İlk önce her biti her bit ile çarpıyoruz:
   • ağırlık 1 – ${\displaystyle a_{0}b_{0}}$
   • ağırlık 2 – ,${\displaystyle a_{0}b_{1}}$${\displaystyle a_{1}b_{0}}$
   • ağırlık 4 – , ,${\displaystyle a_{0}b_{2}}$${\displaystyle a_{1}b_{1}}$${\displaystyle a_{2}b_{0}}$
   • ağırlık 8 – , , ,${\displaystyle a_{0}b_{3}}$${\displaystyle a_{1}b_{2}}$${\displaystyle a_{2}b_{1}}$${\displaystyle a_{3}b_{0}}$
   • ağırlık 16 – , ,${\displaystyle a_{1}b_{3}}$${\displaystyle a_{2}b_{2}}$${\displaystyle a_{3}b_{1}}$
   • ağırlık 32 – ,${\displaystyle a_{2}b_{3}}$${\displaystyle a_{3}b_{2}}$
   • ağırlık 64 – ${\displaystyle a_{3}b_{3}}$
2. Azaltma katmanı 1:
   • Yalnızca ağırlık-1 telini geçirin, çıkış: 1 ağırlık-1 tel
   • Ağırlık 2 için yarım toplayıcı ekleyin, çıkışlar: 1 ağırlık-2 tel, 1 ağırlık-4 tel
   • 4 ağırlık için tam bir toplayıcı ekleyin, çıkışlar: 1 ağırlık-4 tel, 1 ağırlık-8 tel
   • 8 ağırlık için tam bir toplayıcı ekleyin ve kalan kabloyu geçirin, çıkışlar: 2 ağırlık-8 tel, 1 ağırlık-16 tel
   • 16 ağırlık için tam bir toplayıcı ekleyin, çıkışlar: 1 ağırlık-16 tel, 1 ağırlık-32 tel
   • 32 ağırlık için yarım toplayıcı ekleyin, çıkışlar: 1 ağırlık-32 tel, 1 ağırlık-64 tel
   • Yalnızca ağırlık-64 teli geçirin, çıkış: 1 ağırlık-64 tel
3. İndirgeme katmanı 1 çıkışındaki teller:
   • ağırlık 1 – 1
   • ağırlık 2 – 1
   • ağırlık 4 – 2
   • ağırlık 8 – 3
   • ağırlık 16 – 2
   • ağırlık 32 – 2
   • ağırlık 64 – 2
4. Azaltma katmanı 2:
   • 8 ağırlık için tam toplayıcı ve 4, 16, 32, 64 ağırlıklar için yarım toplayıcı ekleyin
5. Çıktılar:
   • ağırlık 1 – 1
   • ağırlık 2 – 1
   • ağırlık 4 – 1
   • ağırlık 8 – 2
   • ağırlık 16 – 2
   • ağırlık 32 – 2
   • ağırlık 64 – 2
   • ağırlık 128 – 1
6. Telleri bir çift tamsayı ve bunları eklemek için bir toplayıcı olarak gruplandırın.

Ayrıca bakınız

• baba ağacı

Referanslar

daha fazla okuma

• Savard, John JG (2018) [2006]. "İleri Aritmetik Teknikleri" . dörtlü blok . 2018-07-03 tarihinde kaynağından arşivlendi . 2018-07-16 alındı .

Dış bağlantılar

• Wallace Ağaç Çarpanının Genel VHDL Uygulaması .