موضوع مقاله: جمع‌کنندهٔ ذخیرهٔ رقم نقلی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # جمع‌کنندهٔ ذخیرهٔ رقم نقلی | مقدمه: جمع‌کننده با قابلیت ذخیره رقم نقلی نوعی از جمع‌کننده دیجیتال است که در ریزمعماری کامپیوتر برای محاسبه جمع ۳ یا بیشتر عدد -بیتی باینری استفاده می‌شود. | ## بخش 1: جمع‌کنندهٔ ذخیرهٔ رقم نقلی | تفاوتش با سایر جمع‌کننده‌ها دیجیتال این است که خروجی‌اش دو عدد با ابعاد یکسان به عنوان ورودی است، که یکی دنباله جمع‌ها بیت‌ها جمع است و دیگری دنباله‌ای از بیت‌ها نقلی. با استفاده از ریاضیات ساده، از راست به چپ محاسبه می‌کنیم: "۰ = ۲ + ۸ و رقم نقلی ۱"، " ۰ = ۱ + ۲ + ۷ و رقم نقلی ۱"، "۰ = ۱ + ۳ + ۶ و رقم نقلی ۱"، و همین‌طور تا آخر جمع ادامه می‌دهیم. اگرچه ما آخرین رقم حاصل را اولین بار به دست می‌آوریم، اولین رقم را تا زمانی که تمامی جمع‌ها را انجام داده باشیم، نمی‌دانیم؛ و باید تمامی رقم‌ها نقلی را به رقم بعدی‌اش منتقل کرده باشیم. به همین دلیل جمع دو عدد -بیتی باید زمانی متناسب با داشته باشد، حتی اگر ماشینی که استفاده می‌کنیم قابلیت انجام تعداد زیادی جمع‌ها موازی داشته باشد. به زبان الکترونیک، استفاده از بیت‌ها (رقم‌ها باینری) به این معناست که حتی اگر جمع‌کننده یک بیتی داشته باشیم، باز هم باید زمانی متناسب با صبر کنیم تا رقم‌ها نقلی احتمالی از یک سمت عدد به سمت دیگر برسند؛ مگر این که این کار را انجام داده باشیم: حاصل جمع را نمی‌دانیم. نمی‌دانیم حاصل جمع از یک عدد داده شده بزرگتر یا کوچکتر است (مثلاً نمی‌دانیم عدد مثبت است یا منفی) یک جمع‌کننده با قابلیت پیش‌بینی رقم نقلی می‌تواند تأخیر را کم کند. به‌طور دقیق‌تر می‌توان تأخیر را تا جایی کم کرد که متناسب با logn باشد، ولی برای اعداد بزرگ این مسئله باز هم مطرح است چون حتی اگر از جمع‌کننده با قابلیت پیش‌بینی رقم نقلی استفاده کنیم، باز هم‌زمانی که طول می‌کشد تا سیگنال‌ها روی تراشه حرکت کنند متناسب با است و تأخیر پخش رقم نقلی هم با همان نسبت زیاد می‌شود. وقتی که به اعداد ۵۱۲-بیتی تا ۲۰۴۸-بیتی برسیم، جمع‌کننده با قابلیت پیش‌بینی رقم نقلی خیلی به کار نمی‌آید. | ## بخش 2: جمع‌کنندهٔ ذخیرهٔ رقم نقلی | ذخیره رقم نقلی به این صورت است که نشان‌گذاری باینری را رها می‌کند در حالی که هنوز در مبنا ۲ کار می‌کند. علاوه بر این، اگر آدرس داشته باشیم (در این‌جا را ۳۲ در نظر می‌گیریم)، حاصل می‌تواند بعد از این که ورودی‌ها را به یک جمع‌کننده دادیم محاسبه شود چون هیچ رقمی به رقم دیگر وابسته نیست. اگر جمع‌کننده برای جمع دو عدد و محاسبه نتیجه لازم است، جمع‌کننده ذخیره رقم نقلی بیهوده است چون حاصل باید دوباره باینری شود و این به این معناست که رقم‌ها نقلی باید از راست به چپ بروند. ولی در محاسبات اعداد طبیعی بزرگ، جمع یک عمل نادر است و جمع‌کننده‌ها معمولاً برای محاسبه جمع‌ها جزئی در ضرب به کار می‌روند. انباشتگر با ذخیره رقم نقلی فرض کنید برای ذخیره هر رقم فقط ۲ بیت در اختیار داریم. می‌توانیم از نمایش باینری زائد استفاده کنیم، به این ترتیب که برای هر رقم، ۰، ۱، ۲ یا ۳ را در جایگاهش نگه داریم. واضح است که به این ترتیب، می‌توان بدون این که سرریز رخ بدهد، یک عدد عدد باینری دیگر را به حاصل ذخیره رقم نقلی‌مان اضافه کنیم. کلید موفقیت این است که اکنون در هر جمع جزئی، ۳ بیت را جمع می‌زنیم ۰ یا ۱ از عددی که داریم آن را جمع می‌زنیم ۰ اگر عددی که ذخیره کرده بودیم، صفر یا ۲ بوده و ۱ اگر عددمان ۱ یا ۳ بوده ۰ اگر رقم سمت راستش صفر یا ۱ است و ۱ اگر رقم سمت راستش، ۲ یا ۳ است به معنا دیگر، ما داریم از رقم سمت راستمان یک رقم نقلی می‌گیریم و این رقم نقلی را به سمت چپمان منتقل می‌کنیم؛ درست مانند جمع عادی با این تفاوت که رقم نقلی‌ای که داریم به سمت چپ حواله می‌دهیم، از جمع قبلی آمده، نه جمع فعلی. | ## بخش 3: جمع‌کنندهٔ ذخیرهٔ رقم نقلی | در هر سیگنال ساعت، رقم‌ها نقلی فقط باید یک مرحله جابه‌جا شوند، نه مرحله (مانند جمع عادی). چون سیگنال‌ها لازم نیست مقدار زیادی جلو بروند، سیگنال ساعت می‌تواند سریع‌تر جلو رود. که به این معناست که رقم‌ها نقلی در طول جمع حرکت کنند (مانند جمع‌کننده عادی) ولی اگر برای یک ضرب ۵۱۲-بیتی، ۵۱۲ جمع انجام داده‌ایم، هزینه تبدیل نهایی در ۵۱۲ جمع قبلی سرشکن می‌شود، یعنی هر جمع ۱/۵۱۲ هزینه را مصرف کرده‌است. مشکلات در هر مرحله جمع با ذخیره رقم نقلی، حاصل را می‌دانیم هنوز نمی‌دانیم که حاصل جمع از یک عدد داده شده بزرگتر یا کوچکتر است یا نه (مثلاً نمی‌دانیم مثبت است یا منفی) مورد دوم هنگام انجام ضرب‌ها مبنایی مشکل‌ساز است، چون لازم است بدانیم که حاصل از مبنایمان بزرگتر شده یا نه. روش کاهش مونتگمری که بر اساس راست‌ترین مقدار حاصل کار می‌کند، راه حلی برای این مشکل است؛ گرچه مانند روش جمع با ذخیره رقم نقلی، مقدار ثابتی حافظه مصرف می‌کند. به همین دلیل یک سری از آن‌ها ممکن است زمان ذخیره کند ولی یک ضرب این کار را نمی‌کند. جزئیات فنی واحد ذخیره رقم نقلی از جمع‌کننده کامل استفاده می‌کند که هر کدام فقط روی ۳ ورودی فعلی محاسبات انجام می‌دهند. | ## جمع‌بندی | اگر سه عدد -بیتی ، و داشته باشیم، یک جمع جزئی ps و یک رقم نقلی sc را به صورت زیر تولید می‌کند: درنهایت حاصل به صورت زیر محاسبه می‌شود: sc را یک واحد به چپ شیفت منطقی می‌دهیم.