جمع‌کننده با قابلیت ذخیره رقم نقلی
جمع‌کننده با قابلیت ذخیره‌ رقم نقلی نوعی از جمع‌کننده دیجیتال است که در ریزمعماری کامپیوتر برای محاسبه جمع ۳ یا بیشتر عدد formula_1-بیتی باینری استفاده می‌شود. تفاوتش با سایر جمع‌کننده‌ها دیجیتال این است که خروجی‌اش دو عدد با ابعاد یکسان به عنوان ورودی است، که یکی دنباله جمع‌ها بیت‌ها جمع است و دیگری دنباله‌ای از بیت‌ها نقلی.
جمع زیر را در نظر بگیرید :
codice_1.
با استفاده از ریاضیات ساده، از راست به چپ محاسبه می‌کنیم :‌ "0 = 2 + 8 و رقم نقلی 1"، " 0 = 1 + 2 + 7 و رقم نقلی 1"، "0 = 1 + 3 + 6 و رقم نقلی 1"، و همین طور تا آخر جمع ادامه می‌دهیم. اگرچه ما آخرین رقم حاصل را اولین بار به دست می‌آوریم، اولین رقم را تا زمانی که تمامی جمع‌ها را انجام داده باشیم، نمی دانیم؛ و باید تمامی رقم‌ها نقلی را به رقم بعدی‌اش منتقل کرده باشیم. به همین دلیل جمع دو عدد formula_1-بیتی باید زمانی متناسب با formula_1 داشته باشد، حتی اگر ماشینی که استفاده می‌کنیم قابلیت انجام تعداد زیادی جمع‌ها موازی داشته باشد.
به زبان الکترونیک، استفاده از بیت‌ها(رقم‌ها باینری) به این معناست که حتی اگر formula_1 جمع‌کننده یک بیتی داشته باشیم، باز هم باید زمانی متناسب با formula_1 صبر کنیم تا رقم‌ها نقلی احتمالی از یک سمت عدد به سمت دیگر برسند؛ مگر این که این کار را انجام داده باشیم :
یک جمع‌کننده با قابلیت پیش‌بینی رقم نقلی می‌تواند تأخیر را کم کند. به‌طور دقیق‌تر می‌توان تأخیر را تا جایی کم کرد که متناسب با log"n" باشد، ولی برای اعداد بزرگ این مسئله باز هم مطرح است چون حتی اگر از جمع‌کننده با قابلیت پیش‌بینی رقم نقلی استفاده کنیم، باز هم‌زمانی که طول می‌کشد تا سیگنال‌ها روی تراشه حرکت کنند متناسب با formula_1 است و تأخیر پخش رقم نقلی هم با همان نسبت زیاد می‌شود. وقتی که به اعداد ۵۱۲-بیتی تا ۲۰۴۸-بیتی برسیم، جمع‌کننده با قابلیت پیش‌بینی رقم نقلی خیلی به کار نمی‌آید.
ایده ایجاد تأخیر در رقم نقلی یا ذخیره آن، از جان فون نویمان می‌آید.
در زیر یک مثال از جمع باینری را می‌بینید :
codice_2.
ذخیره رقم نقلی به این صورت است که نشان‌گذاری باینری را رها می‌کند در حالی که هنوز در مبنا ۲ کار می‌کند. این روش، حاصل را رقم به رقم حساب می‌کند، به این صورت : codice_3.
نشان‌گذاری این جمع غیرمعمول است ولی جوابش مبهم نیست. علاوه بر این، اگر formula_1 آدرس داشته باشیم(در این جا formula_1 را ۳۲ در نظر می‌گیریم)، حاصل می‌تواند بعد از این که ورودی‌ها را به یک جمع‌کننده دادیم محاسبه شود چون هیچ رقمی به رقم دیگر وابسته نیست.
اگر جمع‌کننده برای جمع دو عدد و محاسبه نتیجه لازم است، جمع‌کننده ذخیره رقم نقلی بیهوده است چون حاصل باید دوباره باینری شود و این به این معناست که رقم‌ها نقلی باید از راست به چپ بروند. ولی در محاسبات اعداد طبیعی بزرگ، جمع یک عمل نادر است و جمع‌کننده‌ها معمولاً برای محاسبه جمع‌ها جزئی در ضرب به کار می‌روند.
فرض کنید برای ذخیره هر رقم فقط ۲ بیت در اختیار داریم. می‌توانیم از نمایش باینری زائد استفاده کنیم، به این ترتیب که برای هر رقم، 0، 1، 2 یا 3 را در جایگاهش نگه داریم. واضح است که به این ترتیب، می‌توان بدون این که سر‌ریز رخ بدهد، یک عدد عدد باینری دیگر را به حاصل ذخیره رقم نقلی‌مان اضافه کنیم. اما حالا چه؟
کلید موفقیت این است که اکنون در هر جمع جزئی، ۳ بیت را جمع می‌زنیم
به معنا دیگر، ما داریم از رقم سمت راستمان یک رقم نقلی می‌گیریم و این رقم نقلی را به سمت چپمان منتقل می‌کنیم؛ درست مانند جمع عادی با این تفاوت که رقم نقلی‌ای که داریم به سمت چپ حواله می‌دهیم، از جمع "قبلی" آمده، نه جمع فعلی. در هر سیگنال ساعت، رقم‌ها نقلی فقط باید یک مرحله جا به جا شوند، نه formula_1 مرحله(مانند جمع عادی). چون سیگنال‌ها لازم نیست مقدار زیادی جلو بروند، سیگنال ساعت می‌تواند سریع‌تر جلو رود.
هنوز لازم است که حاصل را در پایان جمع به باینری تبدیل کنیم. که به این معناست که رقم‌ها نقلی در طول جمع حرکت کنند(مانند جمع‌کننده عادی) ولی اگر برای یک ضرب ۵۱۲-بیتی، ۵۱۲ جمع انجام داده ایم، هزینه‌ تبدیل نهایی در ۵۱۲ جمع قبلی سرشکن می‌شود، یعنی هر جمع ۱/۵۱۲ هزینه را مصرف کرده‌است.
در هر مرحله جمع با ذخیره رقم نقلی،
مورد دوم هنگام انجام ضرب‌ها مبنایی مشکل‌ساز است، چون لازم است بدانیم که حاصل از مبنایمان بزرگتر شده یا نه.
روش کاهش مونتگمری که بر اساس راست‌ترین مقدار حاصل کار می‌کند، راه حلی برای این مشکل است؛ گرچه مانند روش جمع با ذخیره رقم نقلی، مقدار ثابتی حافظه مصرف می‌کند. به همین دلیل یک سری از آن‌ها ممکن است زمان ذخیره کند ولی یک ضرب این کار را نمی‌کند. خوش بختانه به توان رساندن که یک سری ضرب است، پرکاربردترین عمل در رمزنگاری است.
واحد ذخیره رقم نقلی از formula_1جمع‌کننده کامل استفاده می‌کند که هر کدام فقط روی ۳ ورودی فعلی محاسبات انجام می‌دهند. اگر سه عدد formula_1-بیتی formula_12، formula_13 و formula_14 داشته باشیم، یک جمع جزئی ps و یک رقم نقلی sc را به صورت زیر تولید می‌کند : درنهایت حاصل به صورت زیر محاسبه می‌شود :