موضوع مقاله: درخت والاس | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت والاس | مقدمه: این مدار از مجموعه‌ای از تمام‌جمع‌کننده‌ها و نیم‌جمع‌کننده‌ها (درخت والاس یا کاهش والاس) استفاده می‌کند تا حاصل‌ضرب‌های جزئی (Partial products) را طی مراحلی جمع کند تا زمانی که تنها دو عدد باقی بمانند. | ## بخش 1: درخت والاس | ضرب‌کننده‌های والاس در هر لایه تا حد امکان عمل کاهش را انجام می‌دهند، در حالی که ضرب‌کننده‌های دادا (Dadda multipliers) سعی می‌کنند با به تعویق انداختن کاهش به لایه‌های بالاتر، تعداد گیت‌های مورد نیاز را به حداقل برسانند. ضرب‌کننده‌های والاس توسط دانشمند رایانه استرالیایی، کریس والاس، در سال ۱۹۶۴ ابداع شدند. درخت والاس دارای سه مرحله است: ضرب هر بیت از یکی از آرگومان‌ها (اعداد ورودی) در هر بیت از آرگومان دیگر. کاهش تعداد حاصل‌ضرب‌های جزئی به دو عدد توسط لایه‌هایی از تمام‌جمع‌کننده‌ها و نیم‌جمع‌کننده‌ها. در مقایسه با روش ساده (Naive) جمع کردن حاصل‌ضرب‌های جزئی با جمع‌کننده‌های معمولی، مزیت درخت والاس سرعت بالاتر آن است. نقطه ضعف درخت والاس در مقایسه با جمع ساده حاصل‌ضرب‌های جزئی، تعداد گیت‌های بسیار بیشتر آن است. این محاسبات تنها تأخیر گیت‌ها (Gate delays) را در نظر می‌گیرند و به تأخیر سیم‌ها نمی‌پردازند، که می‌تواند بسیار قابل توجه باشد. | ## بخش 2: درخت والاس | این روند تا زمانی ادامه می‌یابد که در هر ستون (ارزش مکانی) تنها دو بیت باقی بماند. جمع نهایی: دو ردیف باقی‌مانده با یک جمع‌کننده سریع معمولی (مانند جمع‌کننده با قابلیت پیش‌بینی رقم نقلی) با هم جمع می‌شوند تا نتیجه نهایی حاصل شود. برای این کار از قوانین زیر استفاده می‌شود: استفاده از تمام‌جمع‌کننده (Full Adder): هرجا که در یک ستون (یک ارزش مکانی مشخص) سه بیت وجود داشته باشد، این سه بیت وارد یک تمام‌جمع‌کننده می‌شوند. خروجی شامل یک بیت «مجموع» (Sum) است که در همان ستون باقی می‌ماند و یک بیت «نقلی» (Carry) که به ستون سمت چپ (ارزش مکانی بالاتر) منتقل می‌شود. استفاده از نیم‌جمع‌کننده (Half Adder): اگر در یک ستون تنها دو بیت وجود داشته باشد، آن‌ها وارد یک نیم‌جمع‌کننده می‌شوند. خروجی شامل یک بیت مجموع (در همان ستون) و یک بیت نقلی (برای ستون سمت چپ) خواهد بود. انتقال مستقیم: اگر در یک ستون تنها یک بیت باشد، آن بیت بدون تغییر به لایه بعدی منتقل می‌شود. | ## بخش 3: درخت والاس | این عملیات در چندین لایه تکرار می‌شود تا در نهایت برای هر وزن مکانی، حداکثر دو بیت باقی بماند (یک ردیف مجموع و یک ردیف نقلی). تحلیل پیچیدگی و سرعت مزیت اصلی درخت والاس نسبت به ضرب‌کننده‌های ساده (مثل روش آرایه‌ای)، سرعت بالای آن است. از آنجا که هر لایه کاهش دارای تأخیر انتشار ثابتی است، کل زمان تاخیر ضرب‌کننده نیز متناسب با خواهد بود. در مقابل، ضرب‌کننده‌های ساده دارای تاخیری متناسب با هستند که برای اعداد بزرگ (مثل ۶۴ بیتی یا ۱۲۸ بیتی) بسیار کندتر عمل می‌کنند. با این حال، پیاده‌سازی سخت‌افزاری درخت والاس به دلیل نامنظم بودن اتصالات سیم‌کشی (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) برای وزن ۴ اضافه کنید، خروجی‌ها: ۱ سیم با وزن-۴، ۱ سیم با وزن-۸ یک تمام‌جمع‌کننده برای وزن ۸ اضافه کنید و سیم باقی‌مانده را عبور دهید، خروجی‌ها: ۲ سیم با وزن-۸، ۱ سیم با وزن-۱۶ یک تمام‌جمع‌کننده برای وزن ۱۶ اضافه کنید، خروجی‌ها: ۱ سیم با وزن-۱۶، ۱ سیم با وزن-۳۲ یک نیم‌جمع‌کننده برای وزن ۳۲ اضافه کنید، خروجی‌ها: ۱ سیم با وزن-۳۲، ۱ سیم با وزن-۶۴ تنها سیم با وزن-۶۴ را عبور دهید، خروجی: ۱ سیم با وزن-۶۴ سیم‌های موجود در خروجی لایه کاهش ۱: وزن ۱ — ۱ وزن ۲ — ۱ وزن ۴ — ۲ وزن ۸ — ۳ وزن ۱۶ — ۲ وزن ۳۲ — ۲ وزن ۶۴ — ۲ لایه کاهش ۲: یک تمام‌جمع‌کننده برای وزن ۸، و نیم‌جمع‌کننده‌هایی برای وزن‌های ۴، ۱۶، ۳۲ و ۶۴ اضافه کنید. | ## جمع‌بندی | خروجی‌ها: وزن ۱ — ۱ وزن ۲ — ۱ وزن ۴ — ۱ وزن ۸ — ۲ وزن ۱۶ — ۲ وزن ۳۲ — ۲ وزن ۶۴ — ۲ وزن ۱۲۸ — ۱ سیم‌ها را در قالب یک جفت عدد صحیح دسته‌بندی کنید و از یک جمع‌کننده برای جمع کردن آن‌ها استفاده کنید.