Arithmetic and Logic Unit

A carry look-ahead adder finds all carries at once. It uses $G_i = A_iB_i$ and $P_i = A_i \oplus B_i$, with $C_{i+1} = G_i + P_iC_i$ and $S_i = P_i \oplus C_i$.

Example: add $A = 1011$ and $B = 0110$ with $C_0 = 0$. Here $G = 0010$ and $P = 1101$ (bit 3 to bit 0). The look-ahead equations give $C_1 = 0$, $C_2 = G_1 = 1$, $C_3 = G_2 + P_2G_1 = 1$ and $C_4 = 1$. The sums $P_i \oplus C_i$ are $S_3S_2S_1S_0 = 0001$, so the result is $10001 = 17$, which equals $11 + 6$.

A look-ahead carry adder finds all carry bits at the same time, directly from the inputs. For each bit $i$ it uses the generate signal $G_i = A_iB_i$ and the propagate signal $P_i = A_i \oplus B_i$. Then:

$$S_i = P_i \oplus C_i \qquad C_{i+1} = G_i + P_iC_i$$

If we replace each carry by the one before it, every carry depends only on $G$, $P$ and $C_0$:

$$C_1 = G_0 + P_0C_0$$

$$C_2 = G_1 + P_1G_0 + P_1P_0C_0$$

$$C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$$

Each of these is a two-level AND-OR circuit. So all carries are ready after two gate delays, and they do not wait for each other.

A ripple carry adder is a chain of full adders. The carry out of each stage is the carry in of the next one. The last sum bit is ready only after the carry has passed through all $n$ stages. For a 4-bit adder with two gate delays per stage, this takes about 8 gate delays.

Comparison

Advantages of the look-ahead adder: it is much faster, and the speed is nearly independent of word length for one block.

Disadvantages: it needs many more gates, so it costs more and uses more power. For long words the AND and OR gates need too many inputs, so in practice the adder is built from 4-bit blocks joined by a second level of look-ahead.

A ripple carry adder is slow, because each stage waits for the carry of the stage before it. A carry look-ahead adder (CLA) finds all the carries at the same time, directly from the inputs.

For each bit $i$ we define two signals. The generate signal $G_i = A_iB_i$ means this stage makes a carry on its own. The propagate signal $P_i = A_i \oplus B_i$ means this stage passes an incoming carry on. Then:

$$S_i = P_i \oplus C_i \qquad C_{i+1} = G_i + P_iC_i$$

Replacing each carry by the equation of the stage before gives the carries of a 4-bit adder in terms of $G$, $P$ and $C_0$ only:

$$C_1 = G_0 + P_0C_0$$

$$C_2 = G_1 + P_1G_0 + P_1P_0C_0$$

$$C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$$

$$C_4 = G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0$$

Each carry is a two-level AND-OR circuit. So all four carries are ready after the same two gate delays.

Design of the 4-bit CLA. The circuit has three layers. The first layer has an AND gate and an XOR gate for each bit. They give $G_i$ and $P_i$. The second layer is the look-ahead logic that makes $C_1$ to $C_4$ from the four equations above. The third layer has four XOR gates that give $S_i = P_i \oplus C_i$.

   A3B3   A2B2   A1B1   A0B0
    |      |      |      |
  [AND,XOR] x4  ->  G3..G0, P3..P0
    |      |      |      |
  +--------------------------+
  | look-ahead carry logic   |<-- C0
  | C1  C2  C3  C4           |
  +--------------------------+
    |C3    |C2    |C1    |C0
  [XOR]  [XOR]  [XOR]  [XOR]
    S3     S2     S1     S0

The delay is about 4 gate delays in total (one for $P,G$, two for the carries, one for the XOR). A 4-bit ripple carry adder needs about 8. The price is more gates, and wider AND-OR gates for longer words. So big adders use 4-bit CLA blocks joined together.

Deriving the carry equations

A full adder adds the bits $A_i$ and $B_i$ and the carry $C_i$. Its carry out is:

$$C_{i+1} = A_iB_i + (A_i \oplus B_i)C_i$$

We give the two parts names. The generate term $G_i = A_iB_i$ means that the stage creates a carry by itself. The propagate term $P_i = A_i \oplus B_i$ means that the stage passes the carry on. The equations become:

$$C_{i+1} = G_i + P_iC_i \qquad S_i = P_i \oplus C_i$$

Now we replace each carry by the equation of the stage before it, one at a time.

$$C_1 = G_0 + P_0C_0$$

$$C_2 = G_1 + P_1C_1 = G_1 + P_1G_0 + P_1P_0C_0$$

$$C_3 = G_2 + P_2C_2 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0$$

$$C_4 = G_3 + P_3G_2 + P_3P_2G_1 + P_3P_2P_1G_0 + P_3P_2P_1P_0C_0$$

After the substitution, no carry depends on another carry. Each one depends only on $G$, $P$ and $C_0$, so all can be built as two-level AND-OR circuits and are ready at the same time.

Block diagram

   A3 B3   A2 B2   A1 B1   A0 B0
    |  |    |  |    |  |    |  |
  [ P/G ] [ P/G ] [ P/G ] [ P/G ]   P = A xor B, G = A.B
    |  |    |  |    |  |    |  |
    |  +----+--+----+--+----+--+--> look-ahead carry unit
    |       |       |       |        (C1, C2, C3, C4 from
    |       |       |       |         all P, G and C0)
  [XOR]   [XOR]   [XOR]   [XOR] <--- C3, C2, C1, C0
    |       |       |       |
    S3      S2      S1      S0          C4 = carry out

Example. Add $A = 0111$ and $B = 0011$ with $C_0 = 1$.

The look-ahead equations give:

$$C_1 = G_0 + P_0C_0 = 1 + 0 = 1$$

$$C_2 = G_1 + P_1G_0 + P_1P_0C_0 = 1 + 0 + 0 = 1$$

$$C_3 = G_2 + P_2G_1 + P_2P_1G_0 + P_2P_1P_0C_0 = 0 + 1 + 0 + 0 = 1$$

$$C_4 = G_3 + P_3G_2 + \dots = 0$$

The sums are $S_i = P_i \oplus C_i$, so $S_0 = 0 \oplus 1 = 1$, $S_1 = 0 \oplus 1 = 1$, $S_2 = 1 \oplus 1 = 0$ and $S_3 = 0 \oplus 1 = 1$. The result is $S_3S_2S_1S_0 = 1011$ with carry out $0$. Therefore $7 + 3 + 1 = 11 = 1011_2$.

A ripple carry adder is slow because each full adder waits for the carry of the stage before it. For $n$ bits, the delay grows with $n$. A carry look-ahead adder (CLA) removes this wait. It calculates every carry directly from the inputs, at the same time.

For each bit position $i$ we define two signals. The generate signal $G_i = A_i B_i$ says that this stage makes a carry on its own. The propagate signal $P_i = A_i \oplus B_i$ says that this stage passes an incoming carry forward. The sum and the next carry are then:

$$S_i = P_i \oplus C_i$$

$$C_{i+1} = G_i + P_i C_i$$

If we keep replacing the earlier carry in this equation, every carry depends only on $G$, $P$ and $C_0$:

$$C_1 = G_0 + P_0 C_0$$

$$C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0$$

$$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$$

$$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$$

Each of these is a two-level AND-OR circuit. So all four carries appear after the same two gate delays, no matter which bit it is. The 4-bit CLA is built from these parts: four half-adder style gates that make $P_i$ and $G_i$, one look-ahead logic block that holds the four equations above, and four XOR gates that make the sums.

 A3B3  A2B2  A1B1  A0B0
  |     |     |     |
 [P,G] [P,G] [P,G] [P,G]   (AND gate gives G, XOR gives P)
  |     |     |     |
 +-----------------------+
 |  look-ahead carry     |<-- C0
 |  logic (C1, C2, C3,C4)|--> C4
 +-----------------------+
  |C3   |C2   |C1   |C0
 [XOR] [XOR] [XOR] [XOR]    (S = P xor C)
  |     |     |     |
  S3    S2    S1    S0

Example. Add $A = 1011$ and $B = 0110$ with $C_0 = 0$. The bitwise values, from bit 0 to bit 3, are:

Using the look-ahead equations with $C_0 = 0$:

$$C_1 = G_0 + P_0 C_0 = 0$$

$$C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0 = 1$$

$$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0 = 0 + 1 + 0 + 0 = 1$$

$$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + \dots = 0 + 0 + 1 + 0 + 0 = 1$$

The sum bits are $S_i = P_i \oplus C_i$. This gives $S_0 = 1 \oplus 0 = 1$, $S_1 = 0 \oplus 0 = 0$, $S_2 = 1 \oplus 1 = 0$ and $S_3 = 1 \oplus 1 = 0$. With the final carry $C_4 = 1$, the result is $10001$. Therefore $11 + 6 = 17$, which matches.

Speed. Making $P$ and $G$ takes one gate delay, the look-ahead block takes two, and the last XOR takes one. The total is about 4 gate delays for any $n$ that fits in one block. A 4-bit ripple adder needs about 8. The cost is more gates, and the AND-OR gates need more inputs as $n$ grows, so large adders use several 4-bit CLA blocks joined in groups.

A ripple carry adder is slow because each full adder waits for the carry of the stage before it. For $n$ bits, the delay grows with $n$. A carry look-ahead adder (CLA) removes this wait. It calculates every carry directly from the inputs, at the same time.

For each bit position $i$ we define two signals. The generate signal $G_i = A_i B_i$ says that this stage makes a carry on its own. The propagate signal $P_i = A_i \oplus B_i$ says that this stage passes an incoming carry forward. The sum and the next carry are then:

$$S_i = P_i \oplus C_i$$

$$C_{i+1} = G_i + P_i C_i$$

If we keep replacing the earlier carry in this equation, every carry depends only on $G$, $P$ and $C_0$:

$$C_1 = G_0 + P_0 C_0$$

$$C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0$$

$$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$$

$$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$$

Each of these is a two-level AND-OR circuit. So all four carries appear after the same two gate delays, no matter which bit it is. The 4-bit CLA is built from these parts: four half-adder style gates that make $P_i$ and $G_i$, one look-ahead logic block that holds the four equations above, and four XOR gates that make the sums.

 A3B3  A2B2  A1B1  A0B0
  |     |     |     |
 [P,G] [P,G] [P,G] [P,G]   (AND gate gives G, XOR gives P)
  |     |     |     |
 +-----------------------+
 |  look-ahead carry     |<-- C0
 |  logic (C1, C2, C3,C4)|--> C4
 +-----------------------+
  |C3   |C2   |C1   |C0
 [XOR] [XOR] [XOR] [XOR]    (S = P xor C)
  |     |     |     |
  S3    S2    S1    S0

Example. Add $A = 1011$ and $B = 0110$ with $C_0 = 0$. The bitwise values, from bit 0 to bit 3, are:

Using the look-ahead equations with $C_0 = 0$:

$$C_1 = G_0 + P_0 C_0 = 0$$

$$C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0 = 1$$

$$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0 = 0 + 1 + 0 + 0 = 1$$

$$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + \dots = 0 + 0 + 1 + 0 + 0 = 1$$

The sum bits are $S_i = P_i \oplus C_i$. This gives $S_0 = 1 \oplus 0 = 1$, $S_1 = 0 \oplus 0 = 0$, $S_2 = 1 \oplus 1 = 0$ and $S_3 = 1 \oplus 1 = 0$. With the final carry $C_4 = 1$, the result is $10001$. Therefore $11 + 6 = 17$, which matches.

Speed. Making $P$ and $G$ takes one gate delay, the look-ahead block takes two, and the last XOR takes one. The total is about 4 gate delays for any $n$ that fits in one block. A 4-bit ripple adder needs about 8. The cost is more gates, and the AND-OR gates need more inputs as $n$ grows, so large adders use several 4-bit CLA blocks joined in groups.

Booth's algorithm multiplies signed 2's complement numbers. For each bit pair $Q_0Q_{-1}$: $10$ subtracts $M$, $01$ adds $M$, otherwise nothing. Then it shifts right (ASR).

Here $M = -5 = 1011$, $-M = 0101$ and $Q = 3 = 0011$.

$AQ = 11110001 = -15$. Therefore $(-5) \times 3 = -15$.

An array multiplier makes all the partial products at the same time with AND gates, and adds them with a regular array of adders. Here $A = 1101$ ($13$) is the multiplicand and $B = 1011$ ($11$) is the multiplier.

Each bit of $B$ is ANDed with every bit of $A$. If the multiplier bit is 1, the row is a copy of $A$. If it is 0, the row is all zeros. Each row is shifted one place left from the one above it:

Now the rows are added column by column. In hardware, this is done by full adders and half adders arranged in a grid. The carry of each adder goes to the next column, and the sum goes to the adder in the row below.

$$00001101 + 00011010 = 00100111$$

$$00100111 + 00000000 = 00100111$$

$$00100111 + 01101000 = 10001111$$

Therefore $1101 \times 1011 = 10001111_2$, which is $128 + 8 + 4 + 2 + 1 = 143$. Check: $13 \times 11 = 143$.

Structure. For an $n \times n$ multiplier, the array needs $n^2$ AND gates and about $n(n-1)$ adders. For 4 bits this means 16 AND gates and 12 adders (a mix of full adders and half adders). All partial products are formed in one gate delay. The total delay is the time for a carry and a sum to pass through the array, which grows in proportion to $n$.

Advantages. The design is regular and easy to lay out on a chip. It needs no clock or control unit, since it is purely combinational. It is much faster than the shift-and-add method, which needs $n$ clock cycles.

Disadvantage. The hardware grows as $n^2$, so large multipliers need a lot of area.

Booth's algorithm multiplies two signed numbers in 2's complement form. Its idea is that a run of 1s in the multiplier, such as $0111100$, equals a difference of two powers of 2:

$$2^{6} - 2^{2} = 64 - 4 = 60 = 0111100_2$$

So instead of adding $M$ for every 1 bit, we subtract $M$ at the start of the run and add $M$ after its end.

Procedure. The multiplicand is kept in $M$. The multiplier is kept in $Q$, with an extra bit $Q_{-1} = 0$ on its right. $A$ is cleared to 0. We repeat the following $n$ times, once for each bit of the multiplier. If $Q_0Q_{-1}$ is $10$, we do $A = A - M$. If it is $01$, we do $A = A + M$. If it is $00$ or $11$, we do nothing. Then we shift $A$, $Q$ and $Q_{-1}$ right by one place, keeping the sign of $A$ (arithmetic shift right, ASR). At the end, $AQ$ holds the $2n$-bit product.

Example. Multiply $(+7) \times (-3)$ with 4-bit registers. Here $M = 0111$, $-M = 1001$ and $Q = 1101$.

So $AQ = 11101011$. The leading bit is 1, so the product is negative. Its 2's complement is $00010101 = 21$. Therefore $(+7) \times (-3) = -21$.

How it optimises multiplication. Long runs of equal bits in the multiplier need no additions at all, only shifts. For example, a multiplier with eight 1s in a row needs only one subtraction and one addition, instead of eight additions.

Advantages over the traditional method.

• It handles positive and negative numbers with the same circuit, so no separate sign logic is needed.
• It works directly on 2's complement numbers, so no correction step is needed for a negative multiplier.
• It is faster when the multiplier has long runs of 1s.
• The control is simple, with one add or subtract and one shift per cycle.

The worst case is a multiplier with alternating bits, like $0101$, where every cycle needs an add or subtract. Then Booth's method is no faster than shift-and-add.

Signed operand multiplication means multiplying numbers that may be positive or negative. There are three common ways.

Sign-magnitude method. The sign and the magnitude are handled separately. The sign of the product is the XOR of the two signs. The magnitudes are multiplied by the shift-and-add method. For example, $5 \times (-3)$: the magnitudes are $101$ and $011$. Adding the shifted copies gives:

$$101 + 1010 = 1111 = 15$$

The signs are $0 \oplus 1 = 1$, so the product is negative. Therefore $5 \times (-3) = -15$.

2's complement method. The numbers are kept in 2's complement form. The multiplicand is first sign-extended to the length of the product. If the multiplier is negative, its leftmost bit has the negative weight $-2^{n-1}$. So the partial product made by that bit is subtracted and not added. For $5 \times (-3)$, the multiplier is $1101$, and the multiplicand is $0101$. The bit weights are $-8, +4, 0, +1$, so:

$$5 \times (-3) = 5 \times 1 + 5 \times 4 - 5 \times 8 = 5 + 20 - 40 = -15$$

This avoids converting the multiplier to a positive number.

Booth's algorithm. It handles signed multipliers in a single uniform procedure. Each cycle checks the pair $Q_0Q_{-1}$. The pair $10$ subtracts the multiplicand, the pair $01$ adds it, and the pairs $00$ and $11$ do nothing. After each cycle $A$, $Q$ and $Q_{-1}$ are shifted right with the sign of $A$ kept. After $n$ cycles, the $2n$-bit product is in $AQ$. It needs no separate sign logic, and it skips runs of equal bits.

Comparison

In all methods the product of two $n$-bit numbers needs $2n$ bits. Hardware multipliers usually use Booth's algorithm or its improved form, because it is simple and works for both signs.

A multiplier is the circuit or method that multiplies two binary numbers. The main types are:

• Shift-and-add (sequential) multiplier: it adds the multiplicand to a partial product once for each 1 bit of the multiplier, and shifts after each step.
• Booth multiplier: it works on signed 2's complement numbers and skips strings of 0s and 1s.
• Array multiplier: it uses a grid of AND gates and adders to make the product in one pass.
• Wallace tree multiplier: it adds the partial products with a tree of carry-save adders, which is faster.

We use 6-bit registers, because $-18$ needs 6 bits in 2's complement. The numbers are:

$$M = -12 = 110100 \qquad -M = +12 = 001100 \qquad Q = -18 = 101110$$

$A$ and $Q_{-1}$ start at 0. In each cycle we read the pair $Q_0Q_{-1}$. The pair $10$ means $A = A - M$. The pair $01$ means $A = A + M$. The pairs $00$ and $11$ mean no operation. Then $A$, $Q$ and $Q_{-1}$ shift one place right with the sign bit of $A$ copied (arithmetic shift right, ASR). There are 6 cycles.

The product is in $AQ$ joined:

$$AQ = 000011011000$$

The leading bit is 0, so the product is positive. Its value is:

$$2^7 + 2^6 + 2^4 + 2^3 = 128 + 64 + 16 + 8 = 216$$

Therefore $(-12) \times (-18) = +216$.

Check: $12 \times 18 = 216$, and two negative numbers give a positive product, so the answer is correct. Booth's algorithm gave the correct sign without any separate sign handling, because it works on 2's complement numbers directly. Cycles 1, 3 and 4 needed no addition or subtraction, so the multiplier $101110$ was handled with only three arithmetic operations instead of four.

Both numbers need 5 bits in 2's complement. The numbers are:

$$M = -15 = 10001 \qquad -M = +15 = 01111 \qquad Q = -16 = 10000$$

$A$ starts at $00000$ and $Q_{-1}$ at 0. In every cycle we look at the pair $Q_0Q_{-1}$. The pair $10$ means $A = A - M$. The pair $01$ means $A = A + M$. The pairs $00$ and $11$ mean no operation. After that, $A$, $Q$ and $Q_{-1}$ shift one place right together, and the sign bit of $A$ is copied (arithmetic shift right, ASR). The loop runs 5 times, once for each bit of the multiplier. After the 5 cycles, the 10-bit product is ready, because two 5-bit numbers give a result of at most 10 bits.

The product is in $AQ$ joined:

$$AQ = 0011110000$$

The leading bit is 0, so the result is positive. Its value is:

$$2^7 + 2^6 + 2^5 + 2^4 = 128 + 64 + 32 + 16 = 240$$

Therefore $(-15) \times (-16) = +240$.

This example is short because the multiplier $-16 = 10000$ has four zeros in a row at the right. In the first four cycles the pair is $00$, so only shifts happen. In cycle 5, the pair is $10$, since the lowest 1 has reached $Q_0$ while $Q_{-1}$ is 0. So $M$ is subtracted. Subtracting $M = -15$ means adding $+15$, which gives $A = 01111$. After the last shift, this becomes $00111$.

The multiplier is worth a single signed digit $-1$ at bit position 4, that is $-16$. So the product is $(-15) \times (-16) = +240$, with the factor $2^4$ coming from the shifts. The sign comes out positive on its own, with no separate sign logic. Every cycle of the table works on 2's complement numbers directly, so negative multiplicands and multipliers need no special treatment, unlike sign-magnitude multiplication. If the multiplier is read as $-16$, only one subtraction is needed, so Booth's method is very efficient for such numbers. The check is $15 \times 16 = 240$ and the two negative signs give a positive result, so the answer is correct.

We need 5-bit registers, because $-15$ needs 5 bits in 2's complement. The numbers are:

$$M = +13 = 01101 \qquad -M = 10011 \qquad Q = -15 = 10001$$

$A$ starts at $00000$ and $Q_{-1}$ at 0. In each cycle, we look at $Q_0$ and $Q_{-1}$. The pair $10$ means $A = A - M$ (we add $-M$). The pair $01$ means $A = A + M$. The pairs $00$ and $11$ mean no operation. Then $A$, $Q$ and $Q_{-1}$ shift one place right as a whole, and the sign bit of $A$ is copied (arithmetic shift right, ASR). There are 5 cycles, one for each multiplier bit.

The product is in $AQ$ joined:

$$AQ = 1100111101$$

The leading bit is 1, so the result is negative. Take the 2's complement to find its size:

$$\overline{1100111101} + 1 = 0011000010 + 1 = 0011000011 = 195$$

Therefore $(+13) \times (-15) = -195$.

We can also read $AQ$ directly as a 10-bit signed number, where the leftmost bit has the weight $-512$:

$$-512 + 256 + 32 + 16 + 8 + 4 + 1 = -195$$

The shift is an arithmetic shift, so the sign of the partial product is never lost. When $A - M$ makes $A$ negative, the copied sign bit keeps it negative after the shift.

The method works because the pairs of bits turn the multiplier into signed digits. Here $Q = 10001$ becomes the digits $-1$ at bit 0, $+1$ at bit 1 and $-1$ at bit 4, so its value is:

$$-16 + 2 - 1 = -15$$

In the table, cycle 1 subtracts $M$ (digit $-1$), cycle 2 adds $M$ (digit $+1$), and cycle 5 subtracts $M$ again, but now it counts $16$ times as much because of the shifts. The cycles 3 and 4 only shift. Adding these shifted copies of $M$ gives $13 \times (-15)$.

The check is $13 \times 15 = 195$ and the signs differ, so the sign is negative. The result agrees.

We use 6-bit registers, because $-19$ needs 6 bits in 2's complement. The numbers are:

$$M = +20 = 010100 \qquad -M = 101100 \qquad Q = -19 = 101101$$

$A$ starts at $000000$ and $Q_{-1}$ starts at 0. In each cycle we read the pair $Q_0 Q_{-1}$. The pair $10$ means subtract $M$ from $A$. The pair $01$ means add $M$ to $A$. The pairs $00$ and $11$ mean no operation. After that, $A$, $Q$ and $Q_{-1}$ are shifted one place right, and the sign bit of $A$ is copied (arithmetic shift right, ASR). The process runs for 6 cycles, one for each bit of the multiplier.

The product is in the joined register $AQ$:

$$AQ = 111010000100$$

The leftmost bit is 1, so the answer is negative. To find its size, take the 2's complement:

$$\overline{111010000100} + 1 = 000101111011 + 1 = 000101111100 = 380$$

Therefore $(+20) \times (-19) = -380$.

The result is correct because $20 \times 19 = 380$, and the signs differ. Booth's method gave the right sign automatically, and we did not need to treat the sign separately. This is the main strength of the algorithm. It works directly on numbers in 2's complement form. It also skips over strings of 0s and 1s in the multiplier, so it uses fewer additions when the multiplier has long runs of equal bits.

In this example the multiplier $101101$ has no long runs, so only the pair $11$ in cycle 4 causes a skip.

The table can be understood in another way. The pairs of bits turn the multiplier into the signed digits $-1, +1, 0, -1, +1, -1$ (from the leftmost bit down). So the multiplier is worth:

$$-32 + 16 + 0 - 4 + 2 - 1 = -19$$

Each digit decides whether we subtract $M$, add $M$, or do nothing at that bit position. Adding up the shifted copies gives $20 \times (-19) = -380$.

The numbers are two 8-bit unsigned integers, $10110011 = 179$ and $11010101 = 213$. Booth's algorithm works on signed numbers. So we first add a 0 on the left of each number. That makes them 9-bit non-negative numbers with the same value. The product then needs 18 bits.

The multiplicand is $M = 010110011$ and the multiplier is $Q = 011010101$. We also need $-M$, found by taking the 2's complement of $M$:

$$-M = 101001101$$

Registers $A$ (9 bits) and $Q_{-1}$ start at 0. In each cycle we look at the pair $Q_0 Q_{-1}$. If it is $10$, we do $A = A - M$. If it is $01$, we do $A = A + M$. If it is $00$ or $11$, we do nothing. Then we shift $A$, $Q$ and $Q_{-1}$ one place right, keeping the sign bit of $A$ (arithmetic shift right, ASR). We repeat this 9 times.

After 9 cycles, the product is held in $A$ and $Q$ joined together:

$$AQ = 001001010,011101111$$

This is the 18-bit number $001001010011101111_2$. Its value is:

$$2^{15} + 2^{12} + 2^{10} + 2^{7} + 2^{6} + 2^{5} + 2^{3} + 2^{2} + 2^{1} + 2^{0} = 38127$$

Therefore $10110011 \times 11010101 = 38127$. Check: $179 \times 213 = 38127$, so the working is correct.

The reason Booth's method helps here is that runs of 1s in the multiplier are handled by one subtraction at the start of the run and one addition after its end. The multiplier $011010101$ has many isolated 1s, so there are many operations. Even so, the answer is correct for every pattern.

A floating point number stores a real number as a sign, an exponent and a fraction, in the form $(-1)^s \times 1.f \times 2^{e}$.

Its components are:

• Sign bit: 0 for positive and 1 for negative.
• Exponent: the power of 2, stored with a bias so it is always positive. IEEE 754 single precision has 8 exponent bits and bias 127.
• Fraction (mantissa): the digits after the implied leading 1. Single precision has 23 fraction bits.

The exponent sets the range and the fraction sets the accuracy.

Floating point numbers are stored as sign, exponent and mantissa, so their arithmetic needs extra steps on the exponents.

Addition and subtraction. (1) Compare the exponents. (2) Shift the mantissa of the smaller number right, and raise its exponent by 1 for every shift, until the exponents are equal. (3) Add or subtract the mantissas. (4) Normalise the result so it is again in the form $1.f$, and adjust the exponent. (5) Round the result and check for overflow or underflow.

Multiplication. Add the exponents, subtract the bias, multiply the mantissas, and normalise. The sign is the XOR of the signs.

Division. Subtract the exponents, add the bias, divide the mantissas, and normalise.

Example: $5.75 + (-2.5)$ in IEEE 754 single precision

In binary, $5.75 = 101.11_2 = 1.0111_2 \times 2^{2}$ and $2.5 = 10.1_2 = 1.01_2 \times 2^{1}$. The stored exponents are $2 + 127 = 129 = 10000001$ and $1 + 127 = 128 = 10000000$. So:

The exponents differ by 1, so shift the mantissa of $-2.5$ one place right. It becomes $-0.101_2 \times 2^{2}$.

The signs differ, so this is a subtraction of the mantissas:

$$1.0111 - 0.1010 = 0.1101$$

The result is $0.1101_2 \times 2^{2}$. It is not normalised, so shift left by one place and reduce the exponent by 1:

$$0.1101_2 \times 2^{2} = 1.101_2 \times 2^{1}$$

The sign is $0$, the stored exponent is $1 + 127 = 128 = 10000000$, and the fraction is $10100000000000000000000$.

In hexadecimal this is $\text{0x40500000}$. The value is $1.101_2 \times 2 = 11.01_2 = 3.25$. Therefore $5.75 + (-2.5) = 3.25$, which is correct.

Floating point representation stores a real number using a sign, a power of 2 and a fraction, like scientific notation. A number is written as $(-1)^s \times 1.f \times 2^{e}$.

It has three fields: the sign bit $s$, the biased exponent $E = e + \text{bias}$, and the fraction (mantissa) $f$. In IEEE 754 single precision, 32 bits are split as 1, 8 and 23, with bias 127. Moving the binary point changes the exponent, so the same bits can hold very large and very small numbers. For example, $6.5 = 1.101_2 \times 2^2$.

(I) Biased representation of exponents

A 7-bit exponent field holds $2^7 = 128$ values, from 0 to 127. With bias 64, the stored value is the true exponent plus 64:

$$E = e + 64$$

The true exponents $-64$ to $+63$ are therefore stored as 0 to 127. The list runs in order, so each exponent has the 7-bit binary form of $e + 64$. Some key values:

All the other exponents follow the same rule. Negative exponents begin with 0 and non-negative exponents begin with 1.

(II) Addition of exponents

Let the two true exponents be $e_1$ and $e_2$. Their biased forms are $E_1 = e_1 + 64$ and $E_2 = e_2 + 64$. Adding the stored values gives:

$$E_1 + E_2 = e_1 + e_2 + 128$$

The correct biased sum of the exponents must be $(e_1 + e_2) + 64$. The result above is 64 too large. So we subtract 64:

$$E_1 + E_2 - 64 = e_1 + e_2 + 64$$

This is the biased form of $e_1 + e_2$. This is the exponent step in floating point multiplication.

(III) Subtraction of exponents

Subtracting the stored values gives:

$$E_1 - E_2 = (e_1 + 64) - (e_2 + 64) = e_1 - e_2$$

The bias has cancelled out. But the biased form of $e_1 - e_2$ must be $(e_1 - e_2) + 64$. The result is 64 too small, so we add 64:

$$E_1 - E_2 + 64 = (e_1 - e_2) + 64$$

This is the exponent step in floating point division.

Check with numbers. Take $e_1 = 5$ and $e_2 = -3$. Then $E_1 = 69$ and $E_2 = 61$. The sum is $69 + 61 - 64 = 66 = 2 + 64$, which is the biased form of $5 + (-3) = 2$. The difference is $69 - 61 + 64 = 72 = 8 + 64$, which is the biased form of $5 - (-3) = 8$. Both agree. The result is valid only if the true result stays between $-64$ and $+63$. Otherwise there is exponent overflow or underflow.

This is why a biased exponent is useful. All stored exponents are plain positive numbers, so the sign of the exponent never needs special handling. The only extra work is the single correction of 64 after each addition or subtraction, which is a cheap operation for the hardware.

The ALU is a combinational circuit that performs arithmetic and logic micro-operations on two $n$-bit inputs. The design is made one bit at a time. Each bit has a 1-bit slice, and $n$ slices are joined side by side. The carry of one slice goes to the next.

        A_i        B_i
         |          |
         |   +------+------+
         |   | logic for B  |<-- S1 S0 (select B, B', 0, 1)
         |   +------+------+
         |          |
      +--+----------+--+
      |   full adder    |<-- C_i
      +--+--------------+--> C_i+1
         |
      +--+------------------+
      | logic gates AND,OR, |<-- S3 S2 (select)
      | XOR, NOT on A_i,B_i |
      +--+------------------+
         |
      [4:1 MUX] --> F_i

The arithmetic part is a parallel adder. A set of gates on the $B$ input decides what the adder sees. They can pass $B$, pass $\overline{B}$, or pass all 0s or all 1s. With the carry input $C_0$, this gives the different operations.

The logic part applies a gate to each bit pair separately. It gives AND, OR, XOR and complement (NOT). No carry moves between the bits.

A multiplexer (MUX) in each slice chooses between the arithmetic result and the logic result, using the select lines. The ALU also gives status flags: carry $C$, sign $S$, zero $Z$ and overflow $V$. Overflow is $V = C_n \oplus C_{n-1}$, the XOR of the last two carries.

Operations performed

• Arithmetic: addition, subtraction, increment, decrement and transfer.
• Logical: AND, OR, XOR, NOT.
• Shift: logical shift and arithmetic shift left or right, and rotate.

The control unit gives the select code that picks the operation. The result goes to a register, and the flags are stored in the status register for conditional branches.

The arithmetic and logic unit (ALU) is the part of the processor that does all the calculations and the decisions on data.

It performs arithmetic operations such as add, subtract, increment and compare, and logic operations such as AND, OR, NOT, XOR and shifts. The control unit sends select signals that choose the operation. The ALU takes its operands from registers or the accumulator, produces the result, and sets status flags such as zero, carry, sign and overflow. The program uses these flags for branching.

A 4-bit incrementer adds 1 to a 4-bit number $A_3A_2A_1A_0$. We use four full adders in a ripple chain. The second input $B$ of every adder is tied to 0. The carry input of the first adder is tied to 1, and this 1 is what gets added.

 A3     A2     A1     A0
  |      |      |      |
[FA3]<-[FA2]<-[FA1]<-[FA0]<-- C0 = 1   (B inputs = 0)
  |      |      |      |
 S3     S2     S1     S0

The first adder gives $S_0 = \overline{A_0}$ and carry $A_0$, and the carry moves up the chain. The output is $A + 1$. The last carry shows that $A$ was $1111$.

The register holds $A = 10011101$. The leftmost bit is the sign bit.

Arithmetic shift right. Every bit moves one place right, the sign bit is kept, and the lowest bit is lost. Therefore:

$$10011101 \rightarrow 11001110$$

This is the value $-99$ halved to $-50$.

Arithmetic shift left. Every bit moves one place left and a 0 enters at the right:

$$10011101 \rightarrow 00111010$$

The sign bit has changed from 1 to 0. This is an overflow, because the true result $-198$ does not fit in 8 bits. The overflow flag is set whenever the sign bit before the shift and the bit that replaces it are different.

To subtract a smaller number from a larger one with 2's complement, we add the 2's complement of the smaller number to the larger number. The final carry out is thrown away.

The 2's complement of $101011$ is found by inverting every bit, which gives $010100$, and then adding 1:

$$010100 + 1 = 010101$$

Now add this to the larger number:

$$111001 + 010101 = 1,001110$$

The extra carry bit $1$ on the left is discarded. Therefore the answer is $001110$, which is $14$. Check: $57 - 43 = 14$.

IEEE 754 single precision uses 32 bits: 1 sign bit, 8 exponent bits with bias 127, and 23 fraction bits. A number is stored as $(-1)^s \times 1.f \times 2^{e}$, with the stored exponent $E = e + 127$. The leading 1 is implied, so it is not stored.

The method has three parts. First, convert the number to binary. Second, normalise it to the form $1.f \times 2^e$ by moving the binary point. Third, add the bias to $e$ and write the sign, exponent and fraction in order. The bias of 127 makes the stored exponent a positive number even for small values.

(i) 85.125

The number is positive, so $s = 0$. The integer part is $85 = 1010101_2$, and the fraction is exact, since $0.125 = 0.001_2$. So:

$$85.125 = 1010101.001_2 = 1.010101001_2 \times 2^{6}$$

The stored exponent is:

$$E = 6 + 127 = 133 = 10000101_2$$

The fraction $010101001$ is padded with zeros to 23 bits. Therefore:

In hexadecimal this is $\text{0x42AA4000}$.

(ii) -307.1875

The number is negative, so $s = 1$. The integer part is $307 = 100110011_2$ and $0.1875 = 0.0011_2$. So:

$$307.1875 = 100110011.0011_2 = 1.001100110011_2 \times 2^{8}$$

The stored exponent is:

$$E = 8 + 127 = 135 = 10000111_2$$

The fraction $001100110011$ is padded with zeros to 23 bits. Therefore:

In hexadecimal this is $\text{0xC3999800}$.

Both numbers have short binary fractions, so both are stored exactly with no rounding error.

To check the first answer, decode it: $E = 133$ gives $e = 6$. The value is $1.010101001_2 \times 2^6 = 1010101.001_2 = 85 + 0.125 = 85.125$. The second answer decodes in the same way to $-(256 + 32 + 16 + 2 + 1) - 0.1875 = -307.1875$, which matches.

IEEE 754 is the standard format for real numbers in almost every computer. A number is stored as $(-1)^s \times 1.f \times 2^{e}$ in three fields: the sign bit $s$ (0 for positive, 1 for negative), the biased exponent $E = e + \text{bias}$, and the fraction $f$. The leading 1 is implied and not stored.

The bias keeps the stored exponent positive, so numbers can be compared like integers. The all-0 and all-1 exponent patterns are kept for special values.

Normal numbers use the stored exponents 1 to 254 in single precision and 1 to 2046 in double precision. Rounding to the nearest value is the default way to fit a long fraction into the fraction field, and it keeps the error below half of the last bit.

Representing 314.175

The number is positive, so $s = 0$. The integer part is $314 = 100111010_2$. For the fraction, we double $0.175$ again and again and note the digits:

$$0.175 = 0.001011,0011,0011\ldots_2$$

So the number is $100111010.0010110011\ldots_2$. Move the point 8 places left to normalise:

$$314.175 = 1.001110100010110011\ldots_2 \times 2^{8}$$

The true exponent is $e = 8$. The fraction starts with $00111010$ (from the integer part) and then continues with the digits of $0.175$.

Single precision. The stored exponent is:

$$E = 8 + 127 = 135 = 10000111_2$$

The fraction takes 23 bits. The bits after the 23rd are $0110\ldots$, which are less than half, so we round down. Therefore:

In hexadecimal this is $\text{0x439D1666}$.

Double precision. The stored exponent is:

$$E = 8 + 1023 = 1031 = 10000000111_2$$

The fraction takes 52 bits. The bits after the 52nd are $1100\ldots$, which is more than half, so the last bit is rounded up. Therefore:

In hexadecimal this is $\text{0x4073A2CCCCCCCCCD}$.

Neither answer is exact, because $0.175$ has a repeating binary fraction. The error is about $10^{-5}$ in single precision and about $10^{-14}$ in double precision. To check the single answer, decode it: $E = 135$ gives $e = 8$, and the value is $1.00111010001011001100110_2 \times 2^8 \approx 314.17499$.

Biasing means adding a fixed constant, called the bias, to the true exponent before storing it. The stored value is then always a positive (unsigned) number, so no sign bit is needed for the exponent. It also lets us compare two floating point numbers using plain integer comparison.

In IEEE 754 single precision the bias is 127, so $E = e + 127$. In double precision the bias is 1023. For example, a true exponent of $-3$ is stored as $-3 + 127 = 124$, and a true exponent of $5$ is stored as $132$.

IEEE 754 is the standard way to store real numbers in a computer. A number is written in the form $(-1)^s \times 1.f \times 2^{e}$ and stored in three fields: a sign bit $s$, a biased exponent $E$, and a fraction $f$ (also called the mantissa). The leading 1 is implied, so it is not stored.

The stored exponent is $E = e + \text{bias}$. The bias lets the exponent field hold negative powers of 2 without its own sign. Single precision covers magnitudes from about $1.2 \times 10^{-38}$ to $3.4 \times 10^{38}$. The all-0 and all-1 exponent patterns are kept for zero, denormal numbers, infinity and NaN.

Representing -1460.125

The number is negative, so the sign bit is $1$. Convert the magnitude to binary. The integer part is $1460 = 10110110100_2$. The fraction is exact, since $0.125 = 0.001_2$. So:

$$1460.125 = 10110110100.001_2$$

Move the binary point 10 places left to normalise:

$$1460.125 = 1.0110110100001_2 \times 2^{10}$$

The fraction is $0110110100001$, and the true exponent is $e = 10$.

Single precision. The stored exponent is:

$$E = 10 + 127 = 137 = 10001001_2$$

The fraction is padded with zeros to 23 bits. Therefore:

In hexadecimal this is $\text{0xC4B68400}$.

Double precision. The stored exponent is:

$$E = 10 + 1023 = 1033 = 10000001001_2$$

The fraction is padded with zeros to 52 bits. Therefore:

In hexadecimal this is $\text{0xC096D08000000000}$.

Special values. The reserved exponent patterns give the following meanings:

Check. To decode the single precision answer, read $E = 137$, so $e = 137 - 127 = 10$. The value is $-1.0110110100001_2 \times 2^{10}$. Shifting the point 10 places right gives $-10110110100.001_2$, which is $-1460.125$. So the encoding is correct.

Both representations are exact, because the number needs only 13 fraction bits. Double precision stores the same value but has a wider range and about 15 to 16 decimal digits of accuracy, against about 7 for single precision.

IEEE 754 single precision uses 32 bits: 1 sign bit, 8 exponent bits (bias 127) and 23 fraction bits. A normalised number is written as $(-1)^s \times 1.f \times 2^{e}$. The stored exponent is $E = e + 127$. The leading 1 is not stored, because every normalised number starts with 1, so keeping it would waste a bit.

The bias 127 is added so that the exponent field is always a positive number. This lets two floating point numbers be compared like plain integers. The exponent patterns $00000000$ and $11111111$ are kept for zero, denormal numbers, infinity and NaN (not a number). So normal numbers use stored exponents from 1 to 254.

The method has three parts. First, convert the number to binary. Second, normalise it to the form $1.f \times 2^e$. Third, find $E = e + 127$ and write the sign, exponent and fraction in order.

(i) 65.175

The number is positive, so the sign bit is $0$. Convert the integer and fraction parts separately. The integer part is $65 = 1000001_2$. For the fraction, multiply by 2 again and again and note the integer parts:

$$0.175 = 0.001011,0011,0011\ldots_2$$

The first digits come from $0.175 \times 2 = 0.35$ (digit 0), $0.35 \times 2 = 0.7$ (digit 0), $0.7 \times 2 = 1.4$ (digit 1), then $0.4 \times 2 = 0.8$ (digit 0), and so on. The pattern $0011$ repeats forever, so the fraction never ends.

So the number is $1000001.001011001100\ldots_2$. Move the binary point 6 places left to normalise:

$$65.175 = 1.000001001011001100\ldots_2 \times 2^{6}$$

The stored exponent is:

$$E = 6 + 127 = 133 = 10000101_2$$

The fraction needs 23 bits. We take the digits after the leading 1 and round the last bit, because the next digits are $1001\ldots$, which is more than half. The fraction is $00000100101100110011010$. Therefore:

In hexadecimal this is $\text{0x4282599A}$.

(ii) -307.1875

The number is negative, so the sign bit is $1$. The integer part is $307 = 100110011_2$. The fraction is exact:

$$0.1875 = 0.0011_2$$

So the number is $100110011.0011_2$. Move the point 8 places left:

$$307.1875 = 1.001100110011_2 \times 2^{8}$$

The stored exponent is:

$$E = 8 + 127 = 135 = 10000111_2$$

The fraction is $001100110011$ followed by 11 zeros to fill 23 bits. Therefore:

In hexadecimal this is $\text{0xC3999800}$.

To check, decode the second answer: $-1.001100110011_2 \times 2^{8} = -1.1999\ldots \times 256 = -307.1875$. The first answer is the nearest 32-bit value to $65.175$, so it has a tiny rounding error of the order of $10^{-6}$. This is normal, because $0.175$ cannot be written exactly in binary.

An array multiplier forms all partial products at the same time with AND gates, and then adds them with an array of adders. Let the multiplicand be $A = a_1a_0$ and the multiplier be $B = b_1b_0$. The product $P = p_3p_2p_1p_0$ has 4 bits.

Each partial product bit is one AND gate: $a_0b_0$, $a_1b_0$, $a_0b_1$ and $a_1b_1$. They are arranged like paper multiplication:

Column $2^0$ has one bit, so $p_0 = a_0b_0$. Column $2^1$ has two bits, which a half adder (HA1) adds: the sum is $p_1$ and the carry $c_1$ goes to the next column. Column $2^2$ has $a_1b_1$ and $c_1$, which a second half adder (HA2) adds: the sum is $p_2$ and the carry is $p_3$.

$$p_0 = a_0b_0 \qquad p_1 = a_1b_0 \oplus a_0b_1$$

$$p_2 = a_1b_1 \oplus (a_1b_0 \cdot a_0b_1) \qquad p_3 = a_1b_1 \cdot a_1b_0 \cdot a_0b_1$$

 a1b0 a0b1        a0b0 ----------------------> p0
   \   /
   [HA1] --sum-----------------------------> p1
     | c1
 a1b1 +--> [HA2] --sum----------------------> p2
              \--carry---------------------> p3

The circuit needs 4 AND gates and 2 half adders. For $A = 11$ and $B = 11$ (that is $3 \times 3$), the four AND outputs are all 1. Then $p_0 = 1$, $p_1 = 0$ with $c_1 = 1$, $p_2 = 1 \oplus 1 = 0$ and $p_3 = 1$. The product is $1001 = 9$.

Flowchart for division of signed magnitude numbers. The sign and the magnitude are handled separately. The dividend is in $A$ and $Q$ joined, the divisor is in $B$, and the sign bits are $A_s$, $B_s$ and $Q_s$.

 START
   |
 Qs = As xor Bs ; SC = n-1
   |
 EA = A + (not B) + 1       (try A - B)
   |
 E = 1 ?--yes--> DIVIDE OVERFLOW (stop)
   | no
 shift left AQ ; EA = A + (not B) + 1
   |
 E = 1 ? --yes--> Qn = 1 ; A = EA
   | no
 Qn = 0   (A stays, so no restore needed)
   |
 SC = SC - 1 ; SC = 0 ? --no--> back to shift
   | yes
 END : Q = quotient, A = remainder

The first subtraction checks that the quotient fits in $n$ bits. If $A \ge B$ already, the divide overflows. After that, each cycle shifts left, subtracts $B$ by adding its 2's complement, and checks the carry $E$. A carry of 1 means the subtraction succeeded, so the quotient bit is 1 and $A$ takes the new value. A carry of 0 means it failed, so the quotient bit is 0 and $A$ keeps its old value. After $n-1$ cycles $Q$ holds the quotient and $A$ the remainder. The quotient sign is $A_s \oplus B_s$, and the remainder takes the sign of the dividend.

The restoring method is a way of dividing two binary numbers by repeated subtraction and shifting. Register $A$ starts at 0, $Q$ holds the dividend and $M$ holds the divisor.

In each of $n$ cycles, we shift $A$ and $Q$ left by one bit. Then we subtract $M$ from $A$. If the result is negative, the subtraction was too large. So we set $Q_0 = 0$ and add $M$ back to $A$, which restores the old value. If the result is not negative, we set $Q_0 = 1$.

After $n$ cycles, $Q$ holds the quotient and $A$ holds the remainder. For example, $7 \div 3$ gives quotient $2$ and remainder $1$.