الدرس 14 · Combinational circuits

Adding big numbers: the ripple-carry adder

لم يُترجم بعد؛ يُعرض باللغة الإنجليزية

One full adder adds a single column of bits. Chain four of them, each carry-out wired to the next carry-in, and you can add two 4-bit numbers. Watch 0110 + 0111 = 1101 (6 + 7 = 13) as the carry ripples from adder to adder, see why the waiting makes wide adders slow, and what happens when 9 + 9 does not fit in four bits.

10 دقيقة10 خطوات5 أسئلةIntermediate

شكل 14 · تفاعلي

جارٍ تحميل الرسم…

أو ← →

اختبر نفسك

5 أسئلة سريعة

اختر إجابة لتعرف السبب. تُحفَظ نتيجتك مع تقدّمك.

01In a 4-bit ripple-carry adder, where does each full adder's carry-out go?

Each carry-out is wired to the carry-in of the next, more significant column, just like carrying to the next column on paper.

02The 2s column adds 1 + 1 with a carry-in of 0. What does it output?

1 + 1 = 2, which is 10 in binary: write down 0 and carry 1 to the next column.

03What is 0110 + 0111 in binary?

6 + 7 = 13 = 8 + 4 + 1, which is 1101. The carry ripples out of the 2s column, through the 4s column and into the 8s column.

04Why is a 64-bit ripple-carry adder slow?

The delay grows with the number of bits: N stages, one after another. Faster designs such as carry-lookahead work out the carries together.

05A 4-bit adder adds 9 + 9. What do the four sum bits show?

18 = 10010 needs five bits. The four sum bits keep 0010 = 2, and the carry-out of 1 (worth 16) has nowhere to go: overflow.

المصطلحات الأساسية

المسرد

Full adder: A small circuit that adds three bits (A, B and a carry-in) and gives a sum bit and a carry-out bit.
Carry: The extra 1 a column passes to the next column on its left when its total is 2 or 3.
Ripple-carry adder: N full adders in a chain, each carry-out wired to the next carry-in, that add two N-bit numbers.
Carry-in / carry-out: The carry bit going into a full adder from the column on its right, and the one it sends to the column on its left.
Propagation delay: The time a circuit takes to settle on its answer after its inputs change. In a ripple-carry adder it grows with the number of bits.
Carry-lookahead: A faster adder design that works out all the carries together from the input bits instead of passing them along one stage at a time.
Overflow: When the true result needs more bits than the circuit has, so the top carry is lost and the bits that remain are wrong.

تفاصيل إضافية

الملاحظات والمصادر

A full adder's sum bit is A xor B xor Cin, and its carry-out is (A and B) or (Cin and (A xor B)): 1 whenever at least two of its three inputs are 1 (Harris and Harris, Digital Design and Computer Architecture, section 5.2.1).
An N-bit ripple-carry adder is N full adders in a chain, each carry-out feeding the next carry-in. Its delay grows with N: t = N × t_FA, where t_FA is the delay of one full adder (Harris and Harris, section 5.2.1).
Carry-lookahead and prefix adders are the faster designs Harris and Harris describe for wide adders: they compute carries from generate (A and B) and propagate (A or B) signals for groups of bits instead of waiting for each stage. Even the 4-bit SN74HC283 chip uses look-ahead carry logic inside.
With 4 bits the largest unsigned number is 1111 = 15. 9 + 9 = 18 = 10010 needs five bits; keeping the low four leaves 0010 = 2, and the carry-out of 1 (worth 16) is the sign that the result overflowed (Harris and Harris, section 1.4).
In Python, (a >> i) & 1 reads bit i of a, and ^, & and | on the numbers 0 and 1 work as XOR, AND and OR. Python's own integers never overflow: the 4-bit limit here is the size of the circuit, not of Python.
In a real chip each bit is a high or low voltage on a wire; here a glowing lamp or token shows a 1. A lit wire with moving dashes carries a 1.

اختبار يتاح بعد الخطوة الأخيرة.