درخت والاس

**ضرب‌کننده والاس** (Wallace multiplier) یک پیاده‌سازی سخت‌افزاری از یک ضرب‌کننده دودویی است؛ مداری دیجیتال که دو عدد صحیح را در هم ضرب می‌کند. این مدار از مجموعه‌ای از تمام‌جمع‌کننده‌ها و نیم‌جمع‌کننده‌ها (**درخت والاس** یا **کاهش والاس**) استفاده می‌کند تا حاصل‌ضرب‌های جزئی (Partial products) را طی مراحلی جمع کند تا زمانی که تنها دو عدد باقی بمانند. ضرب‌کننده‌های والاس در هر لایه تا حد امکان عمل کاهش را انجام می‌دهند، در حالی که ضرب‌کننده‌های دادا (Dadda multipliers) سعی می‌کنند با به تعویق انداختن کاهش به لایه‌های بالاتر، تعداد گیت‌های مورد نیاز را به حداقل برسانند.

ضرب‌کننده‌های والاس توسط دانشمند رایانه استرالیایی، کریس والاس، در سال ۱۹۶۴ ابداع شدند.

درخت والاس دارای سه مرحله است:

# ضرب هر بیت از یکی از آرگومان‌ها (اعداد ورودی) در هر بیت از آرگومان دیگر.
# کاهش تعداد حاصل‌ضرب‌های جزئی به دو عدد توسط لایه‌هایی از تمام‌جمع‌کننده‌ها و نیم‌جمع‌کننده‌ها.
# گروه‌بندی سیم‌ها در قالب دو عدد و جمع کردن آن‌ها با یک جمع‌کننده معمولی.

در مقایسه با روش ساده (Naive) جمع کردن حاصل‌ضرب‌های جزئی با جمع‌کننده‌های معمولی، مزیت درخت والاس سرعت بالاتر آن است. این روش دارای O(\log n). لایه کاهش است، اما هر لایه تنها  O(n)  تأخیر انتشار دارد. یک جمع ساده‌ی حاصل‌ضرب‌های جزئی به زمان O((\log n)^2)
 نیاز دارد. از آنجا که تولید حاصل‌ضرب‌های جزئی  O(n)  و جمع نهایی O(\log n). زمان می‌برد، کل عملیات ضرب O(\log n).خواهد بود که خیلی کندتر از جمع نیست. از دیدگاه نظریه پیچیدگی، الگوریتم درخت والاس عمل ضرب را در کلاس NC قرار می‌دهد. نقطه ضعف درخت والاس در مقایسه با جمع ساده حاصل‌ضرب‌های جزئی، تعداد گیت‌های بسیار بیشتر آن است.

این محاسبات تنها تأخیر گیت‌ها (Gate delays) را در نظر می‌گیرند و به تأخیر سیم‌ها نمی‌پردازند، که می‌تواند بسیار قابل توجه باشد.

درخت والاس را می‌توان به صورت درختی از جمع‌کننده‌های ۳/۲ یا ۴/۲ نیز نمایش داد.

این روش گاهی با کدگذاری بوث (Booth encoding) ترکیب می‌شود.

## نحوه عملکرد
درخت والاس عملیات ضرب را در سه مرحله اصلی انجام می‌دهد:

# **تولید حاصل‌ضرب‌های جزئی (Partial Products):** ابتدا هر بیت از عدد اول (ضریب) در هر بیت از عدد دوم (مضروب‌فیه) ضرب می‌شود (معادل عملیات AND منطقی). اگر هر دو عدد n بیتی باشند، n^2 بیت حاصل‌ضرب جزئی تولید می‌شود. وزن (ارزش مکانی) هر حاصل‌ضرب جزئی، برابر با حاصل‌ضرب وزن بیت‌های سازنده آن است.
# **کاهش ماتریس (Matrix Reduction):** این مرحله اصلی‌ترین بخش درخت والاس است. حاصل‌ضرب‌های جزئی با استفاده از لایه‌هایی از جمع‌کننده‌ها (Full Adders و Half Adders) کاهش می‌یابند. این روند تا زمانی ادامه می‌یابد که در هر ستون (ارزش مکانی) تنها دو بیت باقی بماند.
# **جمع نهایی:** دو ردیف باقی‌مانده با یک جمع‌کننده سریع معمولی (مانند جمع‌کننده با قابلیت پیش‌بینی رقم نقلی) با هم جمع می‌شوند تا نتیجه نهایی حاصل شود.
در مرحله دوم (کاهش)، هدف این است که تعداد ردیف‌های حاصل‌ضرب‌های جزئی کم شود. برای این کار از قوانین زیر استفاده می‌شود:

* **استفاده از تمام‌جمع‌کننده (Full Adder):** هرجا که در یک ستون (یک ارزش مکانی مشخص) سه بیت وجود داشته باشد، این سه بیت وارد یک تمام‌جمع‌کننده می‌شوند. خروجی شامل یک بیت «مجموع» (Sum) است که در همان ستون باقی می‌ماند و یک بیت «نقلی» (Carry) که به ستون سمت چپ (ارزش مکانی بالاتر) منتقل می‌شود.
* **استفاده از نیم‌جمع‌کننده (Half Adder):** اگر در یک ستون تنها دو بیت وجود داشته باشد، آن‌ها وارد یک نیم‌جمع‌کننده می‌شوند. خروجی شامل یک بیت مجموع (در همان ستون) و یک بیت نقلی (برای ستون سمت چپ) خواهد بود.
* **انتقال مستقیم:** اگر در یک ستون تنها یک بیت باشد، آن بیت بدون تغییر به لایه بعدی منتقل می‌شود.

این عملیات در چندین لایه تکرار می‌شود تا در نهایت برای هر وزن مکانی، حداکثر دو بیت باقی بماند (یک ردیف مجموع و یک ردیف نقلی).

## تحلیل پیچیدگی و سرعت
مزیت اصلی درخت والاس نسبت به ضرب‌کننده‌های ساده (مثل روش آرایه‌ای)، سرعت بالای آن است.

* تعداد مراحل کاهش (ارتفاع درخت) در این روش متناسب با لگاریتم تعداد بیت‌ها است: O(\log n).
* از آنجا که هر لایه کاهش دارای تأخیر انتشار ثابتی است، کل زمان تاخیر ضرب‌کننده نیز متناسب با O(\log n) خواهد بود.
* در مقابل، ضرب‌کننده‌های ساده دارای تاخیری متناسب با O(n) هستند که برای اعداد بزرگ (مثل ۶۴ بیتی یا ۱۲۸ بیتی) بسیار کندتر عمل می‌کنند.

با این حال، پیاده‌سازی سخت‌افزاری درخت والاس به دلیل نامنظم بودن اتصالات سیم‌کشی (Wiring) نسبت به روش‌های دیگر کمی دشوارتر است و فضای فیزیکی بیشتری روی تراشه اشغال می‌کند.
## مثال
برای n=4 و a3a2a1a0 با b3b2b1b0 :

# ابتدا هر بیت را در هر بیت دیگر ضرب می‌کنیم:

* وزن ۱ — a0b0
* وزن ۲ — a0b1 , a1b0
* وزن ۴ — a0b2 , a1b1 , a2b0
* وزن ۸ — a0b3 , a1b2 , a2b1 , a3b0
* وزن ۱۶ — a1b3 , a2b2 , a3b1
* وزن ۳۲ — a2b3 , a3b2
* وزن ۶۴ —a3b3

# لایه کاهش ۱:

* تنها سیم با وزن-۱ را عبور دهید، خروجی: ۱ سیم با وزن-۱
* یک نیم‌جمع‌کننده (Half Adder) برای وزن ۲ اضافه کنید، خروجی‌ها: ۱ سیم با وزن-۲، ۱ سیم با وزن-۴
* یک تمام‌جمع‌کننده (Full Adder) برای وزن ۴ اضافه کنید، خروجی‌ها: ۱ سیم با وزن-۴، ۱ سیم با وزن-۸
* یک تمام‌جمع‌کننده برای وزن ۸ اضافه کنید و سیم باقی‌مانده را عبور دهید، خروجی‌ها: ۲ سیم با وزن-۸، ۱ سیم با وزن-۱۶
* یک تمام‌جمع‌کننده برای وزن ۱۶ اضافه کنید، خروجی‌ها: ۱ سیم با وزن-۱۶، ۱ سیم با وزن-۳۲
* یک نیم‌جمع‌کننده برای وزن ۳۲ اضافه کنید، خروجی‌ها: ۱ سیم با وزن-۳۲، ۱ سیم با وزن-۶۴
* تنها سیم با وزن-۶۴ را عبور دهید، خروجی: ۱ سیم با وزن-۶۴

# سیم‌های موجود در خروجی لایه کاهش ۱:

* وزن ۱ — ۱
* وزن ۲ — ۱
* وزن ۴ — ۲
* وزن ۸ — ۳
* وزن ۱۶ — ۲
* وزن ۳۲ — ۲
* وزن ۶۴ — ۲

# لایه کاهش ۲:

* یک تمام‌جمع‌کننده برای وزن ۸، و نیم‌جمع‌کننده‌هایی برای وزن‌های ۴، ۱۶، ۳۲ و ۶۴ اضافه کنید.

# خروجی‌ها:

* وزن ۱ — ۱
* وزن ۲ — ۱
* وزن ۴ — ۱
* وزن ۸ — ۲
* وزن ۱۶ — ۲
* وزن ۳۲ — ۲
* وزن ۶۴ — ۲
* وزن ۱۲۸ — ۱

# سیم‌ها را در قالب یک جفت عدد صحیح دسته‌بندی کنید و از یک جمع‌کننده برای جمع کردن آن‌ها استفاده کنید.

## جستارهای وابسته

* ضرب‌کننده دودویی
* درخت دادا
* الگوریتم ضرب بوث

## منابع

* 

* 

* 

* 

  منبع در ویکی‌انگلیسی: :en:Wallace tree
رده:علم در ۱۹۶۴ (میلادی)
رده:معرفی‌شده‌های ۱۹۶۴ (میلادی)
رده:حساب رایانه‌ای
رده:ضرب (ریاضی)