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

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

12345678
87654322+
100000000=.

با استفاده از ریاضیات ساده، از راست به چپ محاسبه می‌کنیم :‌ "0 = 2 + 8 و رقم نقلی 1"، " 0 = 1 + 2 + 7 و رقم نقلی 1"، "0 = 1 + 3 + 6 و رقم نقلی 1"، و همین طور تا آخر جمع ادامه می‌دهیم. اگرچه ما آخرین رقم حاصل را اولین بار به دست می‌آوریم، اولین رقم را تا زمانی که تمامی جمع‌ها را انجام داده باشیم، نمی دانیم؛ و باید تمامی رقم‌ها نقلی را به رقم بعدی‌اش منتقل کرده باشیم. به همین دلیل جمع دو عدد ${\displaystyle n}$

به زبان الکترونیک، استفاده از بیت‌ها(رقم‌ها باینری) به این معناست که حتی اگر ${\displaystyle n}$

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

یک جمع‌کننده با قابلیت پیش‌بینی رقم نقلی می‌تواند تأخیر را کم کند. به‌طور دقیق‌تر می‌توان تأخیر را تا جایی کم کرد که متناسب با logn باشد، ولی برای اعداد بزرگ این مسئله باز هم مطرح است چون حتی اگر از جمع‌کننده با قابلیت پیش‌بینی رقم نقلی استفاده کنیم، باز هم‌زمانی که طول می‌کشد تا سیگنال‌ها روی تراشه حرکت کنند متناسب با ${\displaystyle n}$

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

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

10111010101011011111000000001101
11011110101011011011111011101111+.

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

نشان‌گذاری این جمع غیرمعمول است ولی جوابش مبهم نیست. علاوه بر این، اگر ${\displaystyle n}$

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

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

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

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

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

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

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

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

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

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

واحد ذخیره رقم نقلی از ${\displaystyle n}$

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

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

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

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