از گیت تا مدار: ساخت نیم‌جمع‌کننده

تا اینجا گیت‌ها را تک‌تک شناختی. حالا وقت آن است که با آن‌ها چیزی بسازی که واقعاً کاری انجام می‌دهد: مداری که دو عدد را با هم جمع می‌کند. جالب است بدانی هستهٔ حساب هر پردازنده‌ای در جهان، چیزی جز زنجیره‌ای از همین مدار ساده نیست.

جمع در مبنای دو

جمع تک‌رقمی در مبنای دو فقط چهار حالت دارد: ۰ بعلاوهٔ ۰ می‌شود ۰؛ ۰ بعلاوهٔ ۱ می‌شود ۱؛ ۱ بعلاوهٔ ۰ می‌شود ۱؛ و ۱ بعلاوهٔ ۱ می‌شود ۱۰ در مبنای دو، یعنی رقم مجموع ۰ و یک رقم نقلی به مرتبهٔ بالاتر. پس هر مرتبه به دو خروجی نیاز دارد: بیت مجموع و رقم نقلی.

نیم‌جمع‌کننده

ستون مجموع را با جدول XOR مقایسه کن: هر چهار سطر دقیقاً یکسان‌اند، پس بیت مجموع برابر XOR دو ورودی است. حالا ستون نقلی را با جدول AND مقایسه کن: نقلی فقط وقتی ۱ است که هر دو ورودی ۱ باشند، یعنی همان ضرب منطقی. بنابراین کل مدار جمع یک‌بیتی تنها با یک گیت XOR و یک گیت AND ساخته می‌شود. به این مدار نیم‌جمع‌کننده می‌گویند، چون یک نقص مهم دارد: ورودی‌ای برای رقم نقلیِ آمده از مرتبهٔ قبل ندارد و به همین دلیل به‌تنهایی برای جمع اعداد چندبیتی به درد نمی‌خورد.

جمع‌کنندهٔ کامل

برای جمع اعداد چندبیتی، هر مرتبه باید سه بیت را با هم جمع کند: بیت A، بیت B و نقلی ورودی. مدار حاصل جمع‌کنندهٔ کامل نام دارد و از دو نیم‌جمع‌کننده به‌علاوهٔ یک گیت OR ساخته می‌شود. بیت مجموع برابر XOR هر سه ورودی است و نقلی خروجی وقتی ۱ می‌شود که دست‌کم دو تا از سه ورودی ۱ باشند.

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

مثال عددی حل‌شده

عدد ۱۰۱۱ را با ۰۱۱۰ در یک جمع‌کنندهٔ چهاربیتی جمع کن؛ ارزش ده‌دهی این دو عدد ۱۱ و ۶ است. از کم‌ارزش‌ترین مرتبه شروع کن. مرتبهٔ صفر: ۱ بعلاوهٔ ۰ بعلاوهٔ نقلی ورودی ۰ می‌شود مجموع ۱ و نقلی ۰. مرتبهٔ یک: ۱ بعلاوهٔ ۱ بعلاوهٔ ۰ می‌شود مجموع ۰ و نقلی ۱. مرتبهٔ دو: ۰ بعلاوهٔ ۱ بعلاوهٔ نقلی ۱ می‌شود مجموع ۰ و نقلی ۱. مرتبهٔ سه: ۱ بعلاوهٔ ۰ بعلاوهٔ نقلی ۱ می‌شود مجموع ۰ و نقلی ۱. پس چهار بیت خروجی ۰۰۰۱ است و رقم نقلی نهایی ۱. اگر نقلی نهایی را به‌عنوان بیت پنجم بنویسی، عدد ۱۰۰۰۱ به دست می‌آید که برابر ۱۶ + ۱ یعنی ۱۷ است و دقیقاً حاصل ۱۱ بعلاوهٔ ۶ می‌شود. اما اگر مدار تو فقط چهار بیت خروجی داشته باشد، عددی که می‌خوانی ۱ خواهد بود؛ به این پدیده سرریز می‌گویند و پرچم نقلی خروجی دقیقاً برای هشدار دادن دربارهٔ همین وضعیت وجود دارد.

تأخیر و کاربرد واقعی

در ساختار «موج نقلی»، هر مرتبه باید منتظر نقلی مرتبهٔ قبل بماند. اگر تولید نقلی در هر جمع‌کنندهٔ کامل ۶ نانوثانیه طول بکشد، جمع‌کنندهٔ چهاربیتی در بدترین حالت ۴ ضربدر ۶ یعنی ۲۴ نانوثانیه زمان می‌برد و نسخهٔ هشت‌بیتی ۴۸ نانوثانیه. به همین دلیل در پردازنده‌های واقعی از ساختارهای سریع‌تری مانند «نقلی پیش‌بین» استفاده می‌کنند که نقلی مرتبه‌های بالا را به‌طور موازی حساب می‌کند. حتی تفریق هم با جمع‌کردن «مکمل دو» انجام می‌شود و ضرب چیزی جز مجموعه‌ای از جمع‌های شیفت‌یافته نیست؛ پس با همان یک XOR و یک AND، مسیر رسیدن به یک پردازندهٔ کامل باز می‌شود.