جمع‌کننده با قابلیت پیش‌بینی رقم نقلی

جمع‌کننده با قابلیت پیش‌بینی بیت نقلی(به انگلیسی: A carry-lookahead adder) و به‌طور خلاصه CLA، نوعی مدار جمع‌کننده است که در مدارات منطقی به کار می‌رود. این مدار با کاهش زمان مورد نیاز برای تولید بیت نقلی سرعت جمع زدن را افزایش می‌دهد. در مقابل این نوع جمع‌کننده گونهٔ دیگری از مدار جمع‌کننده وجود دارد که با نام جمع‌کننده با بیت نقلی پله‌ای (در بعضی متون ترجمه شده به فارسی جمع‌کننده با بیت نقلی موج گونه) معروف است(به انگلیسی: Ripple Carry Adder). هرچند که جمع‌کننده با بیت نقلی پله‌ای از لحاظ اجزای مداری ساده تراز جمع‌کننده با پیش‌بینی بیت نقلی می‌باشد اما از لحاظ سرعت انجام عملیات کندتر است چراکه در این گونه از جمع‌کننده‌ها مدارلازم است منتظربماند تابیت نقلی حاصل از جمع دو بیت قبلی محاسبه شده و آنگاه برای محاسبه بیت نقلی حاصل از جمع دو بیت بعدی اقدام کند.
چارلز بابیج خطای تحمیل شده بر عملکرد مدار در اثر رقم نقلی پله‌ای را کشف کرد و در ماشین‌های محاسباتی خویش، ساز وکاری راجهت پیش‌بینی رقم نقلی توسعه داد. جرالد روزنبرگ از شرکت IBM حق اختراع یک جمع‌کننده دودویی با پیش‌بینی رقم نقلی را برای خود در سال ۱۹۵۷ ثبت نمود.

روش پیش بینی رقم نقلی

در منطق پیش‌بینی رقم نقلی از مفاهیم انتقال تولیدی و انتشاری استفاده می‌شود. هرچند در زمینه جمع‌کننده پیش‌بینی رقم نقلی، طبیعی تر این است که تولید و انتشار را در زمینه جمع باینری تصور کنیم، این مفاهیم را می‌توان به‌طور عمومی تری نیز استفاده نمود. در توصیف زیر، کلمه رقم را می‌توان با بیت جایگزین کرد زمانی که به جمع باینری اشاره دارد.
جمع دو ورودی ۱ رقمی A و B همیشه تولیدی است اگر جمع همیشه به صورت نقلی باشد، صرفنظر از اینکه نقل ورود وجود داشته باشد یا نه (بطور هم ارز، صرف نظر از اینکه رقم کم ارزش تر نیز در جمع رقم نقلی وجود دارد یا نه). برای مثال، در جمع دهگانی ۵۲+۶۷، جمع رقم دهگان ۵ و ۶ تولیدی است، زیرا نتیجه آن یک رقم صدگان را نقل می‌کند صرفنظر از اینکه رقم یکان نقل شود یا نه (در این مثال، رقم یکان نقل نمی‌شود (۹=۷+۲)).
در موارد جمع باینری، A+B تولیدی است اگر و تنها اگر هر دوی A و B مقدار ۱ باشد. اگر ما بنویسیم G(A,B) که نمایانگر پیش‌بینی باینری است که در صورت صحیح است که اگر و تنها اگر A+B تولیدی باشد، در نتیجه ما داریم:

G (A, B) = A. B

زمانی جمع دو ورودی ۱ رقمی A و B انتشاری گفته می‌شود که جمع در صورت وجود رقم نقلی رخ دهد (بطور هم ارز، زمانی که رقم کم ارزش تر بعدی در جمع رقم نقلی محسوب شود). برای مثال، در جمع دهگانی ۳۷+۶۲، جمع کردن رقم‌های دهگان ۳ و ۶ انتشاری است زیرا نتیجه آن فقط زمانی به رقم صدگان پخش و منتشر می‌شود که یک منتقل شود (که در این مثال، رقم یکان چنین نیست). توجه شود که انتشار و تولید در رابطه با رقم منفرد در جمع تعیین می‌شود و به سایر رقم‌های موجود در جمع بستگی ندارد.
در جمع باینری، A+B انتشاری است اگر و تنها اگر حداقل یکی از A یا B برابر ۱ باشد. اگر ما بنویسیم P(A,B) که دلالت بر پیش‌بینی باینری دارد که زمانی و تنها زمانی صحیح است که A+B انتشاری باشد، بنابراین خواهیم داشت:

P (A, B) = A + B

گاهی اوقات تعریف نسبتاً متفاوتی از انتشار استفاده می‌شود. طبق این تعریف A+B گفته می‌شود که انتشاری است اگر جمع زمانی انجام شود که یک رقم نقلی وجود داشته باشد، اما اگر رقم نقلی موجود نباشد، جمع صورت نمی‌گیرد. خوشبختانه، به علت شیوه استفاده از بیت‌های تولیدی و انتشاری توسط منطق پیش‌بینی بیت نقلی، مهم نیست که کدام تعریف استفاده شود. در زمان جمع باینری، این تعریف به صورت زیر بیان می‌شود:

P' (A, B) = A ⊕ B

در جبر باینری، or از xor سریعتر است و اجرای ترانزیستور کمتری را در یک جمع‌کننده پیش‌بینی بیت نقلی چند-سطحی به خود می‌گیرد، بنابراین ساده‌تر این است که از P' (A, B) استفاده شود.
با در نظر گرفتن مفاهیم تولید و انتشار، چه موقع رقم جمع نقل می‌شود؟ دقیقاً زمانی نقل می‌شود که یا جمع یک or تولید کند یا بیت کم ارزش تر بعدی منتقل شود و جمع انتشار یابد. این مطلب در جبر بولی بدین شکل است، با Ci که بیت رقم i را منتقل می‌کند و Pi و Gi که بیت‌های رقم i را به ترتیب منتشر و تولید می‌کنند، داریم:

جزئیات اجرایی (پیاده‌سازی)

برای هر بیتی در یک توالی باینری که بایستی جمع زده شود، منطق پیش‌بینی بیت نقلی تعیین می‌کند که آیا آن جفت بیت نقلی را تولید یا نقلی را منتشر می‌کنند یا نه. این به مدار امکان را می‌دهد که دو عددی که قرار است با هم جمع شوند را «پیش-پردازش» کند و از قبیل بیت نقلی را پیش‌بینی کند. سپس زمانی که جمع واقعی صورت می‌گیرد، تأخیری برای اثر نقل موجی صرف نخواهد شد (یا زمانی که طول می‌کشد تا بیت نقلی از اولین جمع‌کننده گذشته و به آخرین جمع‌کننده کامل برسد). در زیر یک مدار پیش‌بینی بیت نقلی تعمیم دهی شده ۴ بیتی ساده نشان داده شده‌است که با ۴ بیت جمع‌کننده بیت نقلی موجی استفاده شد در بعضی از تعدیل‌های فوق، ترکیب شده‌است:
برای مثال، منطق تولید (g) و انتشار (p) در زیر آمده است. توجه شود که مقادیر عددی تعیین‌کننده سیگنالی هستند که از مدار بالا می‌آید، از صفر شروع شده و در انتهای چپ صفر بوده و در انتهای سمت راست ۳ است.

C1 = G0 + P0. C0
C2 = G1 + P1. C1
C3 = G2 + P2. C2
C4 = G3 + P3. C3
جایگزین کردن C1 در C2، سپس C2 در C3، سپس C3 در C4 موجب حصول بسط معادلات می‌شود:
C1 = G0 + P0. C0
C2 = G1 + G0. P1 + C0. P0. P1
C3 = G2 + G1. P2 + G0. P1. P2 + C0. P0. P1. P2
C4 = G3 + G2. P3 + G1. P2. P3+ G0. P1. P2. P3 + C0. P0. P1. P2. P3
برای تعیین اینکه آیا یک جفت بیت نقلی را تولید می‌کنند، کارهای منطقی پیگیری می‌شوند:

زنجیره بیت نقلی منچستر

زنجیره نقل منچستر گونه‌ای از جمع‌کننده پیش‌بینی بیت نقلی است که از منطق اشتراکی برای کم کردن شمارش ترانزیستوری استفاده می‌کند. همانطور که در بخش اجرا و پیاده‌سازی در بالا دیدیم، منطق تولیدی هر نقل حاوی تمامی منطق‌های مورد استفاده برای تولید نقل قبلی است. زنجیره نقل منچستر ناقل‌های واسطه‌ای را توسط محصور کردن گره‌ها در گیتی که مهم‌ترین مقادیر نقلی را محاسبه می‌کند، تولید می‌کند. هرچند همه اعضای خانواده منطقی دارای این گره‌ها نیستند، یک مثل مهم آن CMOS است. منطق پویا می‌تواند از منطق اشتراکی حمایت کند، همانطور که از منطق گیت انتقال حمایت می‌کند. یکی از مشکلات اصلی زنجیره نقل منچستر این ست که بار ظرفیتی تمامی این خروجی‌ها را به خود می‌گیرد، که با هم مقاومتی در ترانزیستورها تولید می‌شود که منجر به تأخیر در انتشار می‌شود تا هر چه جمع‌کننده با قابلیت پیش‌بینی بیت نقلی(به انگلیسی: A carry-lookahead adder) و به‌طور خلاصه CLA، نوعی مدار جمع‌کننده است که در مدارات منطقی به کار می‌رود. این مدار با کاهش زمان مورد نیاز برای تولید بیت نقلی سرعت جمع زدن را افزایش می‌دهد. در مقابل این نوع جمع‌کننده گونهٔ دیگری از مدار جمع‌کننده وجود دارد که با نام جمع‌کننده با بیت نقلی پله‌ای معروف است(به انگلیسی: Ripple Carry Adder) و به‌طور خلاصه RCA. هرچند که جمع‌کننده با بیت نقلی پله‌ای از لحاظ اجزای مداری ساده تراز جمع‌کننده با پیش‌بینی بیت نقلی می‌باشد اما از لحاظ سرعت انجام عملیات کندتر است چراکه در این گونه از جمع‌کننده‌ها مدارلازم است منتظربماند تابیت نقلی حاصل از جمع دو بیت قبلی محاسبه شده و آنگاه برای محاسبه بیت نقلی حاصل از جمع دو بیت بعدی اقدام کند.
اما جمع‌کننده با پیش‌بینی بیت نقلی می‌تواند پیش از آنکه عمل جمع کردن هر دو بیت متناظر را انجام دهد بیت‌های نقلی مورد نیاز آن دو را محاسبه کرده و در اختیار بگذارد و در نتیجه زمان انتظار برای تولید رقم نقلی مورد نیاز در جمع بیت‌های با ارزش بالاتر کاهش می‌یابد.