جمع‌کننده با قابلیت ذخیره رقم نقلی

جمع‌کننده با قابلیت ذخیره رقم نقلی نوعی از جمع‌کننده دیجیتال است که در ریزمعماری کامپیوتر برای محاسبه جمع ۳ یا بیشتر عدد $n$ -بیتی باینری استفاده می‌شود. تفاوتش با سایر جمع‌کننده‌ها دیجیتال این است که خروجی‌اش دو عدد با ابعاد یکسان به عنوان ورودی است، که یکی دنباله جمع‌ها بیت‌ها جمع است و دیگری دنباله‌ای از بیت‌ها نقلی.

انگیزه

جمع زیر را در نظر بگیرید:

12345678 87654322+ 100000000=.

با استفاده از ریاضیات ساده، از راست به چپ محاسبه می‌کنیم: "۰ = ۲ + ۸ و رقم نقلی ۱"، " ۰ = ۱ + ۲ + ۷ و رقم نقلی ۱"، "۰ = ۱ + ۳ + ۶ و رقم نقلی ۱"، و همین‌طور تا آخر جمع ادامه می‌دهیم. اگرچه ما آخرین رقم حاصل را اولین بار به دست می‌آوریم، اولین رقم را تا زمانی که تمامی جمع‌ها را انجام داده باشیم، نمی‌دانیم؛ و باید تمامی رقم‌ها نقلی را به رقم بعدی‌اش منتقل کرده باشیم. به همین دلیل جمع دو عدد $n$ -بیتی باید زمانی متناسب با $n$ داشته باشد، حتی اگر ماشینی که استفاده می‌کنیم قابلیت انجام تعداد زیادی جمع‌ها موازی داشته باشد.^[۱]^[۲]

به زبان الکترونیک، استفاده از بیت‌ها (رقم‌ها باینری) به این معناست که حتی اگر $n$ جمع‌کننده یک بیتی داشته باشیم، باز هم باید زمانی متناسب با $n$ صبر کنیم تا رقم‌ها نقلی احتمالی از یک سمت عدد به سمت دیگر برسند؛ مگر این که این کار را انجام داده باشیم:

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

یک جمع‌کننده با قابلیت پیش‌بینی رقم نقلی می‌تواند تأخیر را کم کند. به‌طور دقیق‌تر می‌توان تأخیر را تا جایی کم کرد که متناسب با logn باشد، ولی برای اعداد بزرگ این مسئله باز هم مطرح است چون حتی اگر از جمع‌کننده با قابلیت پیش‌بینی رقم نقلی استفاده کنیم، باز هم‌زمانی که طول می‌کشد تا سیگنال‌ها روی تراشه حرکت کنند متناسب با $n$ است و تأخیر پخش رقم نقلی هم با همان نسبت زیاد می‌شود. وقتی که به اعداد ۵۱۲-بیتی تا ۲۰۴۸-بیتی برسیم، جمع‌کننده با قابلیت پیش‌بینی رقم نقلی خیلی به کار نمی‌آید.

مفهوم اولیه

ایده ایجاد تأخیر در رقم نقلی یا ذخیره آن، از جان فون نویمان می‌آید.

در زیر یک مثال از جمع باینری را می‌بینید:

10111010101011011111000000001101 11011110101011011011111011101111+.

ذخیره رقم نقلی به این صورت است که نشان‌گذاری باینری را رها می‌کند در حالی که هنوز در مبنا ۲ کار می‌کند. این روش، حاصل را رقم به رقم حساب می‌کند، به این صورت : 10111010101011011111000000001101 11011110101011011011111011101111+ 21122120202022022122111011102212=.

نشان‌گذاری این جمع غیرمعمول است ولی جوابش مبهم نیست. علاوه بر این، اگر $n$ آدرس داشته باشیم (در این‌جا $n$ را ۳۲ در نظر می‌گیریم)، حاصل می‌تواند بعد از این که ورودی‌ها را به یک جمع‌کننده دادیم محاسبه شود چون هیچ رقمی به رقم دیگر وابسته نیست.

اگر جمع‌کننده برای جمع دو عدد و محاسبه نتیجه لازم است، جمع‌کننده ذخیره رقم نقلی بیهوده است چون حاصل باید دوباره باینری شود و این به این معناست که رقم‌ها نقلی باید از راست به چپ بروند. ولی در محاسبات اعداد طبیعی بزرگ، جمع یک عمل نادر است و جمع‌کننده‌ها معمولاً برای محاسبه جمع‌ها جزئی در ضرب به کار می‌روند.

انباشتگر با ذخیره رقم نقلی

فرض کنید برای ذخیره هر رقم فقط ۲ بیت در اختیار داریم. می‌توانیم از نمایش باینری زائد استفاده کنیم، به این ترتیب که برای هر رقم، ۰، ۱، ۲ یا ۳ را در جایگاهش نگه داریم. واضح است که به این ترتیب، می‌توان بدون این که سرریز رخ بدهد، یک عدد عدد باینری دیگر را به حاصل ذخیره رقم نقلی‌مان اضافه کنیم. اما حالا چه؟

کلید موفقیت این است که اکنون در هر جمع جزئی، ۳ بیت را جمع می‌زنیم

۰ یا ۱ از عددی که داریم آن را جمع می‌زنیم
۰ اگر عددی که ذخیره کرده بودیم، صفر یا ۲ بوده و ۱ اگر عددمان ۱ یا ۳ بوده
۰ اگر رقم سمت راستش صفر یا ۱ است و ۱ اگر رقم سمت راستش، ۲ یا ۳ است

به معنا دیگر، ما داریم از رقم سمت راستمان یک رقم نقلی می‌گیریم و این رقم نقلی را به سمت چپمان منتقل می‌کنیم؛ درست مانند جمع عادی با این تفاوت که رقم نقلی‌ای که داریم به سمت چپ حواله می‌دهیم، از جمع قبلی آمده، نه جمع فعلی. در هر سیگنال ساعت، رقم‌ها نقلی فقط باید یک مرحله جابه‌جا شوند، نه $n$ مرحله (مانند جمع عادی). چون سیگنال‌ها لازم نیست مقدار زیادی جلو بروند، سیگنال ساعت می‌تواند سریع‌تر جلو رود.

هنوز لازم است که حاصل را در پایان جمع به باینری تبدیل کنیم. که به این معناست که رقم‌ها نقلی در طول جمع حرکت کنند (مانند جمع‌کننده عادی) ولی اگر برای یک ضرب ۵۱۲-بیتی، ۵۱۲ جمع انجام داده‌ایم، هزینه تبدیل نهایی در ۵۱۲ جمع قبلی سرشکن می‌شود، یعنی هر جمع ۱/۵۱۲ هزینه را مصرف کرده‌است.

مشکلات

در هر مرحله جمع با ذخیره رقم نقلی،

حاصل را می‌دانیم
هنوز نمی‌دانیم که حاصل جمع از یک عدد داده شده بزرگتر یا کوچکتر است یا نه (مثلاً نمی‌دانیم مثبت است یا منفی)

مورد دوم هنگام انجام ضرب‌ها مبنایی مشکل‌ساز است، چون لازم است بدانیم که حاصل از مبنایمان بزرگتر شده یا نه.

روش کاهش مونتگمری که بر اساس راست‌ترین مقدار حاصل کار می‌کند، راه حلی برای این مشکل است؛ گرچه مانند روش جمع با ذخیره رقم نقلی، مقدار ثابتی حافظه مصرف می‌کند. به همین دلیل یک سری از آن‌ها ممکن است زمان ذخیره کند ولی یک ضرب این کار را نمی‌کند. خوش بختانه به توان رساندن که یک سری ضرب است، پرکاربردترین عمل در رمزنگاری است.

جزئیات فنی

واحد ذخیره رقم نقلی از $n$ جمع‌کننده کامل استفاده می‌کند که هر کدام فقط روی ۳ ورودی فعلی محاسبات انجام می‌دهند. اگر سه عدد $n$ -بیتی $b$ ، $a$ و $c$ داشته باشیم، یک جمع جزئی ps و یک رقم نقلی sc را به صورت زیر تولید می‌کند:

ps_{i}=a_{i}\oplus b_{i}\oplus c_{i}

sc_{i}=(a_{i}\wedge b_{i})\vee (a_{i}\wedge c_{i})\vee (b_{i}\wedge c_{i})

درنهایت حاصل به صورت زیر محاسبه می‌شود:

sc را یک واحد به چپ شیفت منطقی می‌دهیم.
یک ۰ در جایگاه پراهمیت‌ترین بیت ps می‌گذاریم.
از یک جمع‌کننده برای محاسبه حاصل جمع عدد 1+ $n$ -بیتی‌مان استفاده می‌کنیم.

منابع

↑ Parhami, Behrooz (2010). Computer arithmetic: algorithms and hardware designs (2nd ed.). New York: Oxford University Press. ISBN 978-0-19-532848-6. OCLC 428033168.
↑ Lyakhov, P.; Valueva, M.; Valuev, G.; Nagornov, N. (2020). "High-Performance Digital Filtering on Truncated Multiply-Accumulate Units in the Residue Number System". IEEE Access. 8: 209181–209190. doi:10.1109/ACCESS.2020.3038496. ISSN 2169-3536.

[1] Parhami, Behrooz (2010). Computer arithmetic: algorithms and hardware designs (2nd ed.). New York: Oxford University Press. ISBN 978-0-19-532848-6. OCLC 428033168.

[2] Lyakhov, P.; Valueva, M.; Valuev, G.; Nagornov, N. (2020). "High-Performance Digital Filtering on Truncated Multiply-Accumulate Units in the Residue Number System". IEEE Access. 8: 209181–209190. doi:10.1109/ACCESS.2020.3038496. ISSN 2169-3536.

[۱]

[۲]