ضرب کننده دادا

**ضرب‌کنندهٔ دادا** (به انگلیسی: ***Dadda Multiplier***) نوعی معماری '''ضرب‌کنندهٔ دودویی''' در سخت‌افزارهای دیجیتال است که نخستین‌بار توسط دانشمند رایانه، **[[لوئیجی دادا]]**، در سال ۱۹۶۵ معرفی شد. در این روش، حاصل‌ضرب‌های جزئیِ تولیدشده در ضرب دودویی، طی چند مرحله با استفاده از **[[جمع‌کننده|تمام جمع کننده ها]]** و **[[جمع‌کننده|نیم جمع‌کننده‌ها]]** کاهش می‌یابند تا در نهایت تنها دو ردیف باقی بماند. ساختار کلی این ضرب‌کننده از بسیاری جهات به **[[:en:Wallace_tree|ضرب‌کنندهٔ والاس]]** شباهت دارد، اما روش متفاوتِ کاهش درختی در آن باعث می‌شود تعداد گیت‌های موردنیاز—به‌ویژه در اندازه‌های بزرگ‌تر عملوند—کمتر باشد و در نتیجه سرعت اجرای مدار اندکی بهبود یابد.

هردو ضرب‌کننده‌ی **Dadda** و **Wallace**، برای رشته های دوبیتی w_1 و w_2 با طول های \ell_1 و \ell_2، سه مرحله‌ی یکسان دارند که به ترتیب زیر هستند:

# هر بیت از رشتهٔ w_1 با هر بیت از رشتهٔ w_2 ضرب منطقی (AND) می‌شود. حاصل این مرحله، \ell_1\cdot\ell_2 مقدار است که بر اساس وزن بیتی، در ستون‌های مربوط به خود دسته‌بندی می‌شوند.
# حاصل‌ضرب‌های جزئیِ به‌دست‌آمده، با استفاده از مراحل متوالیِ '''تمام جمع کننده ها''' و '''نیم‌ جمع‌ کننده ها''' کاهش می‌یابند تا در نهایت در هر ستون، بیش از دو بیت باقی نماند.
# دو ردیف باقی‌مانده با کمک یک جمع‌کنندهٔ معمولی ترکیب می‌شوند تا نتیجهٔ نهایی ضرب تولید شود.
همانند **ضرب‌کنندهٔ والاس**، حاصل‌ضرب‌هایی که در مرحلهٔ نخست تولید می‌شوند هرکدام وزن بیتی متفاوتی دارند؛ این وزن‌ها نشان‌دهندهٔ جایگاه و ارزش بیت‌های ورودی در عملیات ضرب هستند. برای نمونه، حاصل‌ضرب بیت‌های a_n b_m دارای وزنی برابر با n+m است.

برخلاف **ضرب‌کنندهٔ والاس** که در هر مرحله تا حد امکان تعداد بیت‌ها را کاهش می‌دهد، **ضرب‌کنندهٔ دادا** با هدف کاهش تعداد گیت‌های مصرفی و بهبود تأخیر ورودی–خروجی عمل می‌کند. به همین دلیل، مرحلهٔ کاهش در **ضرب‌کنندهٔ دادا** از نظر سخت‌افزاری کم‌هزینه‌تر است؛ با این حال، خروجی میانی ممکن است اندکی طولانی‌تر باشد و در نتیجه برای تولید نتیجهٔ نهایی، به یک جمع‌کنندهٔ بزرگ‌تر نیاز خواهد بود.

## '''توضیحات'''
[بندانگشتی|یک نمونه از مدار '''[جمع‌کننده|تمام جمع‌کننده**.]]
برای دستیابی به یک خروجی بهینه‌تر، روند کاهش در **ضرب‌کنندهٔ دادا** بر پایهٔ مجموعه‌ای از قوانین ساختاریِ دقیق‌تر—نسبت به آنچه در **ضرب‌کنندهٔ والاس** به‌کار می‌رود—سازمان‌دهی می‌شود.

فرآیند کاهش در **ضرب‌کنندهٔ دادا** با تکیه بر یک توالی ارتفاع‌های بیشینه‌ کنترل می‌شود که با <math>d_j</math> نمایش داده می‌شود و به‌صورت زیر تعریف می‌گردد:

<math>d_{j+1} = \operatorname{floor}(1.5 d_j).</math> and , <math>d_1 = 2</math>

این تعریف در نهایت به دنباله‌ای با شکل کلیِ زیر منتهی می‌شود:

<math>d_1=2, d_2=3, d_3=4, d_4=6, d_5=9, d_6=13, \ldots </math>

برای آغاز فرایند، مقدار اولیهٔ **j** به‌گونه‌ای انتخاب می‌شود که بزرگ‌ترین مقدار ممکن باشد، به شرط آن‌که <math>d_j < \min{(n_1, n_2)}</math> برقرار باشد؛ جایی که <math>n_1</math> و <math>n_2</math> به‌ترتیب تعداد بیت‌های مضروب و مضرب ورودی هستند. حداقلِ این دو مقدار همان حداکثر ارتفاعی است که هر ستونِ وزن پس از مرحلهٔ نخست ضرب می‌تواند داشته باشد. در هر گام از کاهش با اندیس **j**، هدف الگوریتم آن است که ارتفاع هر ستون به مقداری کمتر یا مساوی <math>d_j</math> کاهش یابد.

برای هر یک از مراحل کاهش از **j** تا1،ستون‌ها باید از کم‌وزن‌ترین ستون—یعنی <math>c_0</math>—شروع شده و بر اساس **قوانین زیر** کاهش یابند:

# اگر ارتفاع ستون <math>c_{i}</math> کمتر یا برابر با <math>d_j</math>  باشد، نیازی به کاهش ندارد و می‌توان مستقیماً به ستون بعدی، یعنی<math>c_{i+1}</math>، رفت.
# اگر ارتفاع ستون برابر با <math>d_j + 1</math> باشد، دو بیت بالایی با استفاده از **نیم‌جمع‌کننده** ترکیب می‌شوند؛ بیت حاصل در پایین همان ستون قرار می‌گیرد و رقم نقلی نیز در پایین ستون بعدی،<math>c_{i+1}</math> ،جای‌گذاری می‌شود. پس از آن، پردازش ستون بعدی ادامه می‌یابد.
# در صورتی که ارتفاع ستون بزرگ‌تر از این مقدار باشد، سه بیت بالایی با استفاده از یک **تمام جمع کننده** فشرده می‌شوند؛ حاصل جمع در پایین ستون <math>c_{i}</math> و رقم نقلی در پایین ستون <math>c_{i+1}</math> قرار می‌گیرد. سپس دوباره به ستون <math>c_{i}</math>  بازمی‌گردیم و این فرایند از مرحلهٔ نخست تکرار می‌شود تا ارتفاع ستون به حد مطلوب برسد.

=== ساختار درختی دادا ===
در یک ضرب‌کنندهٔ دودویی ۸×۸، حاصل‌ضرب‌های جزئی را می‌توان به صورت یک ماتریس در نظر گرفت که در آن هر ستون مجموعه‌ای از بیت‌ها با وزن بیتی یکسان را شامل می‌شود. در مرحلهٔ نخست، تعداد بیت‌های هر ستون از یک تا هشت متغیر است و ستون‌های میانی ارتفاع بیش‌تری دارند.

در الگوریتم دادا، این ماتریس در چند مرحلهٔ متوالی کاهش می‌یابد. در هر مرحله، ستون‌هایی که ارتفاع آن‌ها بیش‌تر از حد مجاز <math>d_j</math> است، با استفاده از نیم‌جمع‌کننده‌ها و تمام‌جمع‌کننده‌ها فشرده می‌شوند تا ارتفاع ستون به مقدار مجاز برسد. ستون‌هایی که ارتفاع آن‌ها از ابتدا کمتر یا مساوی <math>d_j</math> باشد، دست‌نخورده به مرحلهٔ بعد منتقل می‌شوند.

به‌طور شهودی، می‌توان این فرایند را یک «درخت کاهش» دانست که در گام‌های متوالی، تعداد گره‌ها (بیت‌ها) در هر سطح را کاهش می‌دهد تا در نهایت ماتریسی با ۱۵ ستون و حداکثر دو بیت در هر ستون باقی بماند. این دو ردیف نهایی، ورودی یک [[جمع‌کننده دودویی|جمع‌کنندهٔ دودویی معمولی]] را تشکیل می‌دهند.

== مقایسه با ضرب‌کنندهٔ والاس ==
معمولاً ضرب‌کننده‌های **والاس** و **دادا** به عنوان دو معماری استاندارد برای کاهش حاصل‌ضرب‌های جزئی مقایسه می‌شوند. هر دو از درختی از نیم‌جمع‌کننده‌ها و تمام‌جمع‌کننده‌ها استفاده می‌کنند، اما راهبرد کاهش در آن‌ها متفاوت است.



درخت والاس در هر مرحله، تا حد امکان بیت‌های هر ستون را با استفاده از تمام‌جمع‌کننده‌ها و نیم‌جمع‌کننده‌ها کاهش می‌دهد؛ بنابراین عمق منطق نسبتاً کم است، اما تعداد گیت‌ها و سیم‌کشی‌ها بیشتر می‌شود. در مقابل، درخت دادا با تعریف دنبالهٔ <math>d_j</math> مقدار کاهش در هر مرحله را محدود می‌کند و به این ترتیب، با کمی افزایش در عمق مدار، به کاهش قابل‌توجه در تعداد گیت‌ها و مصرف توان دست می‌یابد. در طراحی‌های [[VLSI]] که مساحت و توان معیارهای مهمی هستند، این مزیت می‌تواند تعیین‌کننده باشد.

== مثال الگوریتم ==
[[پرونده:Dadda_tree_8x8.svg|بندانگشتی|در یک ماتریس ضربِ جزئیِ ۸×۸، فرایند کاهشِ چهارمرحله‌ایِ دادا با استفاده از **۷ نیم‌جمع‌کننده** (نمایش داده‌شده با دو نقطه) و **۳۵ تمام جمع کننده** (نمایش داده‌شده با سه نقطه) انجام می‌شود. هر نقطه در یک ستون نشان‌دهندهٔ یک بیت با وزن بیتی یکسان است؛ ستون‌های سمت راست بیت‌هایی با وزن کمتر را شامل می‌شوند و وزن ستون‌ها به‌تدریج در سمت چپ افزایش می‌یابد.]]
نمونهٔ نشان‌داده‌شده در تصویر کنار، مراحل کاهش را برای ضربِ عدد ۸ در ۸ نمایش می‌دهد؛ همان مثالی که در این بخش به آن پرداخته شده است.

در این مثال، مقدار آغازین <math>j = 4</math> انتخاب شده است، زیرا <math>d_4 = 6</math> بزرگ‌ترین ارتفاعی است که هنوز از مقدار ۸ کمتر است.

***در مرحلهٔ <math>j=4</math> مقدار مجاز حداکثر ارتفاع برابر با <math>d_4 = 6</math> در نظر گرفته می‌شود:***

* ارتفاع ستون‌های <math>c_{0}</math>  تا <math>c_{5}</math> همگی شش بیت یا کمتر است؛ بنابراین در این مرحله نیازی به اعمال هیچ تغییری وجود ندارد.
* ارتفاع ستون <math>c_{6}</math> برابر با <math>d_4 + 1 = 7</math> است؛ بنابراین باید یک **نیم‌جمع‌کننده** بر روی آن اعمال شود تا ارتفاع ستون به شش بیت کاهش یابد و رقمِ نقلیِ حاصل به ستون بعدی، یعنی <math>c_{7}</math> اضافه شود.
* ارتفاع ستون <math>c_{7}</math> با در نظر گرفتن رقمِ نقلیِ انتقال‌یافته از <math>c_{6}</math>، برابر با ۹ بیت است؛ بنابراین برای کاهش آن به شش بیت، یک **تمام جمع کننده** و سپس یک **نیم‌جمع‌کننده** به‌کار گرفته می‌شود.
* ارتفاع ستون <math>c_{8}</math> با احتساب دو رقم نقلی منتقل‌شده از <math>c_{7}</math>، به ۹ بیت می‌رسد؛ بنابراین همانند مرحلهٔ قبل، برای کاهش ارتفاع آن به شش بیت، ابتدا یک **تمام جمع کننده** و سپس یک **نیم‌جمع‌کننده** استفاده می‌شود.
* ارتفاع ستون <math>c_9</math>  با در نظر گرفتن دو رقم نقلی که از <math>c_{8}</math> منتقل شده‌اند، برابر با ۸ بیت است؛ بنابراین با به‌کارگیری یک **تمام جمع کننده**، ارتفاع آن به شش بیت کاهش داده می‌شود.
***در مرحلهٔ <math>j=3</math> ، حداکثر ارتفاع مجاز ستون‌ها برابر با <math>d_3 = 4</math>*** ***در نظر گرفته می‌شود:***

* ارتفاع ستون‌های **c_{0}** تا <math>c_{3}</math> همگی بیش از چهار بیت نیست؛ بنابراین در این مرحله نیازی به هیچ تغییری وجود ندارد.
* ارتفاع ستون <math>c_{4}</math> برابر با <math>d_3 + 1 = 5</math> است؛ بنابراین یک **نیم‌جمع‌کننده** روی آن اعمال می‌شود تا ارتفاع ستون به چهار بیت کاهش یابد و رقمِ نقلیِ حاصل به ستون بعدی، یعنی **c_{5}**، منتقل شود.
* ارتفاع ستون **c_{5}** با احتساب رقمِ نقلی منتقل‌شده از **c_{4}** به ۷ بیت می‌رسد؛ بنابراین برای کاهش ارتفاع آن به چهار بیت، ابتدا یک **تمام جمع کننده** و سپس یک **نیم‌جمع‌کننده** مورد استفاده قرار می‌گیرد.
* ارتفاع ستون‌های **c_{6}** تا **c_{10}** با در نظر گرفتن تمام رقم‌های نقلیِ مراحل قبل، برابر با ۸ بیت است؛ بنابراین برای کاهش ارتفاع هر یک از این ستون‌ها به چهار بیت، از دو **تمام جمع کننده** استفاده می‌شود.
* ارتفاع ستون **c_{11}** با احتساب رقم‌های نقلی مرحله‌های پیشین، به ۶ بیت می‌رسد؛ بنابراین یک **تمام جمع کننده** به‌کار گرفته می‌شود تا ارتفاع آن به چهار بیت کاهش یابد.
* ارتفاع ستون‌های **c_{12}** تا **c_{14}** با در نظر گرفتن تمام رقم‌های نقلی، چهار بیت یا کمتر است؛ بنابراین در این مرحله نیازی به اعمال هیچ تغییری نیست.
***در مرحلهٔ <math>j=2</math> ، حداکثر ارتفاع مجاز ستون‌ها برابر با <math>d_2 = 3</math> در نظر گرفته می‌شود:***

* ارتفاع ستون‌های **c_{0}** تا **c_{2}** همگی سه بیت یا کمتر هستند؛ بنابراین در این مرحله نیازی به هیچ‌گونه تغییری وجود ندارد.
* ارتفاع ستون **c_{3}** برابر با  <math>d_2 + 1 = 4</math> است؛ بنابراین یک **نیم‌جمع‌کننده** روی آن اعمال می‌شود تا ارتفاع ستون به سه بیت کاهش یابد و رقمِ نقلیِ حاصل به ستون بعدی، یعنی **c_{4}** ،منتقل شود.
* ارتفاع ستون‌های **c_{4}** تا **c_{12}** با در نظر گرفتن رقم‌های نقلی مراحل قبل، به ۵ بیت می‌رسد؛ بنابراین برای کاهش ارتفاع هر ستون به سه بیت، از یک **تمام جمع کننده** استفاده می‌شود.
* ارتفاع ستون‌های **c_{13}** تا **c_{14}** با احتساب رقم‌های نقلی، سه بیت یا کمتر است؛ بنابراین در این مرحله نیازی به انجام هیچ تغییری نیست.
***در مرحلهٔ <math>j=1</math>،*** ***حداکثر ارتفاع مجاز ستون‌ها برابر با <math>d_1 = 2</math> در نظر گرفته می‌شود:***

* ارتفاع ستون‌های **c_{0}** تا **c_{1}** در حد دو بیت یا کمتر است؛ بنابراین در این مرحله نیازی به اعمال هیچ تغییری وجود ندارد.
* ارتفاع ستون **c_{2}** برابر با <math>d_1 + 1 = 3</math> است؛ بنابراین یک **نیم‌جمع‌کننده** روی آن اعمال می‌شود تا ارتفاع ستون به دو بیت کاهش یابد و رقمِ نقلیِ حاصل به ستون بعدی، یعنی **c_{3}**، منتقل شود.
* ارتفاع ستون‌های **c_{3}** تا **c_{13}** با در نظر گرفتن رقم‌های نقلیِ مراحل قبلی، به ۴ بیت می‌رسد؛ بنابراین برای رساندن ارتفاع هر ستون به دو بیت، از یک **تمام جمع کننده** استفاده می‌شود.
* ارتفاع ستون **c_{14}** با احتساب رقمِ نقلی منتقل‌شده از **c_{13}**، دو بیت است؛ بنابراین در این مرحله نیازی به هیچ تغییری وجود ندارد.

=== علاوه بر این ===
در پایان آخرین مرحله، ۱۵ ستون باقی می‌ماند که ارتفاع هرکدام دو بیت یا کمتر است؛ این ستون‌ها در نهایت می‌توانند مستقیماً وارد یک **جمع‌کنندهٔ استاندارد''' شوند تا نتیجهٔ نهایی ضرب به‌دست آید.

## همچنین ببینید
* الگوریتم ضرب بوث
* ضرب-جمع ترکیبی
* درخت والاس
* الگوریتم BKM برای لگاریتم‌های مختلط و نمایی
* ضرب کوچانسکی برای ضرب مدولار

## منابع

## مطالعه بیشتر
* 

رده:حساب رایانه‌ای
رده:ضرب (ریاضی)
رده:معرفی‌شده‌های ۱۹۶۵ (میلادی)
رده:علوم رایانه در ۱۹۶۵ (میلادی)