# Arithmetic Circuits

> This part is almost the same NUS CG3207 Lec 04 - Arithmetic for Computers. So, I will combine the information together here.

Arithmetic circuits are the central building blocks of computers. Computers and digital logic perform many arithmetic functions: addition, subtraction, comparisons, shifts, multiplication, and division. This section describes hardware implementations for all of these operations.

## Addition

Addition is one of the most common operations in digital systems. If you still remember, we've introduced [here](https://wenbo-notes.gitbook.io/ddca-notes/textbook/from-zero-to-one/number-systems#recap) that all binary arithmetics can be done using adders! We first consider how to add two 1-bit binary numbers. We then extend to N-bit binary numbers. Adders also illustrate trade-offs between speed and complexity.

### Half Adder&#x20;

We begin by building a 1-bit *half adder*. As shown in Figrue 5.1, the half adder has two inputs, A and B, and two outputs, $$S$$ and $$C\_{\text{out}}$$. $$S$$ is the sum of A and B. If A and B is 1, $$S$$ is 2, which cannot be represented with a single binary digit. Instead, it is indicated with a carry out $$C\_{\text{out}}$$ **in the next column**.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FGysTeVEmNVR8pdBeYbxR%2Fimage.png?alt=media&#x26;token=ed484427-ed71-45d6-be67-2344aca13af8" alt="" width="228"><figcaption></figcaption></figure>

In a multi-bit adder, $$C\_{\text{out}}$$ is added or *carried in* to the next most significant bit (or into the next column). However, the half adder lacks a $$C\_{\text{in}}$$ input to accept $$C\_{\text{out}}$$ of the previous column. The *full adder*, described in the next section, solves this problem.

### Full Adder

A *full adder* accepts the carry in $$C\_{\text{in}}$$ as shown in Figure 5.3. The figure also shows the output equations for $$S$$ and $$C\_{\text{out}}$$.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2F0TpoeSe0ZqT1lZRaDVu1%2Fimage.png?alt=media&#x26;token=2d3d84cf-9948-469d-8b11-36e88da8008e" alt="" width="304"><figcaption></figcaption></figure>

### Carry Propagate Adder

An $$N$$-bit adders sums two $$N$$-bit inputs, A and B, and a carry in $$C\_{\text{in}}$$ to produce an $$N$$-bit result $$S$$ and a carry out $$C\_{\text{out}}$$. It is commonly called a *carry propagate adder* (CPA) because the carry out of one bit propagates into the next bit. The symbol for CPA is shown in Figure 5.4; it is drawn just like a full adder except that A, B, and S are buses rather than single bits. Three common CPA implementations are called

1. [Ripple-carry adders](#ripple-carry-adder)
2. [Carry-lookahead adders](#carry-lookahead-adder)
3. Prefix adders (FYI)

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FmEoid4hpVy90Z8S41hmc%2Fimage.png?alt=media&#x26;token=2b1e70f6-f334-4091-8004-034ebd7948fa" alt=""><figcaption></figcaption></figure>

#### Ripple-Carry Adder

The simplest way to build an N-bit carry propagate adder is to chain together N full adders. The $$C\_{\text{out}}$$ of one stage acts as the $$C\_{\text{in}}$$ of the next stage, as shown in Figure 5.5 for 32-bit addition. This is called a **ripple-carry adder**.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FIRJf4acP3oBLY52o8GHh%2Fimage.png?alt=media&#x26;token=fa0bfc65-16c9-4ace-bbeb-0db90b62e429" alt=""><figcaption></figcaption></figure>

The ripple-carry adder has the disadvantage of being **slow** when N is large. As $$S\_{31}$$ depends on $$C\_{30}$$, which depends on $$C\_{29}$$, and so forth all the way back to $$C\_{\text{in}}$$. We say that the carry *ripples* through the carry chain. The delay of the adder, $$t\_{\text{ripple}}$$ grows directly with the number of bits, as given in Equation 5.1, where $$t\_{\text{FA}}$$ is the delay of a full adder,

$$
t\_{\text{ripple}}=Nt\_{\text{FA}}
$$

> In Ripple-Carry Adder, the main disadvantage is that the **carry** propagates very slow. Can we accelerate the process of knowing the carry of an adder? Here comes the **carry-lookahead adder**.

#### Carry-Lookahead Adder

A **carry-lookahead adder** (CLA) is another type of carry propogate adder that solves the problem caused by ripple-carry adder by dividing the adder into **blocks** and providing circuitry to quickly determine the **carry out** of a [**block**](#user-content-fn-1)[^1] as soon as the [**carry in**](#user-content-fn-2)[^2] is known. Thus it is said to *look ahead* across the blocks rather than waiting to ripple through all the full adders inside a block.

CLAs use bit-level **generate** ($$g$$) and **propagate** ($$p$$) signals to determine carry behavior for individual bit positions, which are then combined into **block-level** signals ($$G$$ and $$P$$) to determine the carry out for larger multi-bit groups.

* The $$i$$-th column of an adder is said to *generate* a carry if it produces a carry out independent of the carry in. Hence, we have $$g\_i=A\_iB\_i$$.
* The $$i$$-th column of an adder is said to *propagate* a carry it is produces a carry [whenever there is a carry in](#user-content-fn-3)[^3]. Thus, we have $$p\_i=A\_i+B\_i$$.

{% hint style="success" %}
One great advantage here is that both $$g\_i$$ and $$p\_i$$ depend only on the two inputs number $$A\_i$$ and $$B\_i$$, instead of the need of knowing the "carry-in" ($$C\_{i-1}$$) of that block.
{% endhint %}

Using the $$g\_i$$ and $$p\_i$$, we can rewrite the carry out for each block of full adder ($$C\_i$$)

$$
\begin{align\*}
C\_1&=p\_0C\_0+g\_0 \\
C\_2&=p\_1C\_1+g\_1=p\_1p\_0C\_0+p\_1g\_0+g\_1\\
\cdots\\
C\_i&=p\_iC\_{i-1}+g\_i
\end{align\*}
$$

Let's say we want to build a 32-bit carry-lookahead adder. Doing the above manipulation for 32 stages is cumbersome. However, we can divide them into four blocks first (a.k.a, implement a 4-bit carry-lookahead adder first as the fundamental block).

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FGtP4AroPHOYjnZ2diIPR%2Fimage.png?alt=media&#x26;token=fb12b995-445a-485f-a63d-5e776430100e" alt="" width="563"><figcaption></figcaption></figure>

Using this fundamental block (4-bit carry-lookahead adder), we can build bigger adders. Figure 5.6 (a) shows a 32-bit carry-lookahead adder composed of **eight** 4-bit blocks. Each block contains a 4-bit ripple-carry adder and some lookahead logic to compute the carry out of the block given the carry in, as shown in Figure 5.6 (b).&#x20;

{% hint style="success" %}
C<sub>1</sub>, C<sub>2</sub>, C<sub>3</sub> and C<sub>4</sub> are the four carries that we've looked ahead!
{% endhint %}

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2Ft5filu0shdFU7xkKwV8D%2Fimage.png?alt=media&#x26;token=5fb0bb32-dc49-44a9-b949-833d93966bb2" alt=""><figcaption></figcaption></figure>

{% hint style="success" %}

#### Image Explanation

1. The AND and OR gates needed to compute the single-bit generate and propagate signals, $$G\_i$$ and $$P\_i$$, from $$A\_i$$ and $$B\_i$$ are left out for brevity.
2. The block propagate ($$p\_i$$) and generate ($$g\_i$$) signals for 4-bit blocks ($$i$$ refers to the block number here),
   1. $$P\_0=p\_3p\_2p\_1p\_0$$, $$P\_0$$ is the same as $$P\_{\[3:0]}$$ shown in the figure above
   2. $$G\_0=g\_3+p\_3(g2+p2(g1+p1g\_0))$$, $$G\_0$$ is the same as $$G\_{\[3:0]}$$ shown in the figure above.
3. The ripple effect is avoided within a block, but the ripple carry effect will be present between blocks. Nevertheless, the delays are significantly lower than the orginal ripple carry adder.
   {% endhint %}

### Putting it all together

HDLs provide the `+` operation to specify a CPA. HDL Example 5.1 describes a CPA with carries in and out

{% tabs %}
{% tab title="SystemVerilog" %}
{% code title="Example 5.1 Adder" lineNumbers="true" %}

```verilog
module adder #(parameter N = 8)
              (input  logic [N-1:0] a, b,
               input  logic         cin,
               output logic [N-1:0] s,
               output logic         cout);
  assign {cout, s} = a + b + cin;
endmodule
```

{% endcode %}
{% endtab %}

{% tab title="Verilog" %}
{% code title="Example 5.1 Adder" lineNumbers="true" %}

```verilog
module adder #(parameter N = 8)
              (input  [N-1:0] a, b,
               input          cin,
               output [N-1:0] s,
               output         cout);
  assign {cout, s} = a + b + cin;
endmodule
```

{% endcode %}
{% endtab %}
{% endtabs %}

## Subtraction

Recall from [previous part](https://wenbo-notes.gitbook.io/ddca-notes/textbook/from-zero-to-one/number-systems#signed-binary-number-representation) that adders can add positive and negative numbers using [two's complement number representation](https://wenbo-notes.gitbook.io/ddca-notes/textbook/from-zero-to-one/number-systems#id-2s-complement). Substraction is almost as easy as:

1. flip the sign of the second number
2. then add it

{% hint style="warning" %}
Flipping the sign of a two's complement number is done by inverting the bits then adding 1.
{% endhint %}

Thus, subtraction is performed with a single CPA by adding $$A+\bar B$$ with $$C\_{\text{in}}=1$$. Figure 5.9 shows the symbol for a subtractor and the underlying hardware for performing $$Y=A-B$$.&#x20;

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FUzBDPZBeG2RXk7XAEfwC%2Fimage.png?alt=media&#x26;token=ecc973d5-10ad-4367-802a-94119e118393" alt=""><figcaption></figcaption></figure>

{% hint style="danger" %}
An N-bit subtractor needs **N NOT gates**. This is tricky! Don't just see from the figure and then deduce that only one NOT gate is needed!
{% endhint %}

HDL Example 5.2 describes a subtractor.

{% tabs %}
{% tab title="SystemVerilog" %}
{% code title="Example 5.2 Subtractor" lineNumbers="true" %}

```verilog
module subtractor #(parameter N = 8)
                   (input  logic [N-1:0] a, b,
                    output logic [N-1:0] y);
  assign y = a - b;
endmodule
```

{% endcode %}
{% endtab %}

{% tab title="Verilog" %}
{% code title="Example 5.2 Subtractor" lineNumbers="true" %}

```verilog
module subtractor #(parameter N = 8)
                   (input  [N-1:0] a, b,
                    output [N-1:0] y);
  assign y = a - b;
endmodule
```

{% endcode %}
{% endtab %}
{% endtabs %}

### Signed Addition/Subtraction

In the signed addition/subtraction, we have four flags, **N**(egative), **Z**(ero), **C**(array), **V**(Overflow), to indicate the status of our result. The following part will explain when each certain flag is set,

{% hint style="warning" %}
Before that, let's make some clarifications or conventions first.

1. We denote that the LSB is at bit 0 or 0-th bit, so on and so forth for all the remaining bits.
2. When we add two N-bit numbers, we will get a N+1 bit number. However, we treat the MSB (the N-th bit) as the **carry bit**, and the remaining N bits are the **result**. So, again when we say the MSB of the **result**, we are referring to the (N-1)-th bit actually.
   {% endhint %}

#### Signed Addition

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FNGXDNY3f8x1FG9Cvo3B1%2Fimage.png?alt=media&#x26;token=a6d7603b-51a0-412c-ae20-1407b2a27578" alt="" width="563"><figcaption></figcaption></figure>

By observing the addition examples above, we may find out that

1. For *unsigned addition*, `carry = 1` indicates that the result is **wrong**.
2. For *signed addition*,
   1. Overflow occurs when (+ve) + (+ve) = (-ve) or (-ve) + (-ve) = (+ve), a.k.a, two negative number addition gives out a positive number or two positive number addition gives a negative number
      1. To determine the overflow flag, we always treat the two operands as **signed**! So, this process is just to see that if the sign bits (MSB) of the **operands** are the same, and is different from that of the **result** (the (N-1)-th bit), there is an overflow.
      2. Overflow can never occur when you add two numbers of different signs
      3. Carry and overflow are **unrelated** (However, carry is sometime called "unsigned overflow")
   2. Carry flag is set when the value in the <mark style="color:blue;">blue rectangle</mark> is one.
   3. Negative flag is determined by only looking at the MSB of the result (the (N-1)-th bit actually).
   4. Zero flag is determined by only looking at the N bits result.

{% hint style="success" %}

#### Notes

1. In addition, there are some small tips
   1. N flag and Z flag cannot be 1 simultaneously.
   2. Z flag and V flag can be set simultaneously. e.g., 1000+1000=0000 with carry out 1, and the interpretation of the result to be 0.
2. The hardware as well as the instruction used for performing both signed and unsigned addition are the same
   1. The hardware doesn't know and doesn't care if we are dealing with signed or unsigned.
   2. Only the *interpretation* of the result and/or the way the *condition codes* are used are different.
   3. So, first use signed/unsigned to write out the two operands, then just do the binary addition on these two operands and derive the flags.
      {% endhint %}

#### Signed Subtraction

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FWT7CFd6M09hCLqo2aCvc%2Fimage.png?alt=media&#x26;token=38331dc0-cff8-400a-b351-ca6451b02b04" alt="" width="563"><figcaption></figcaption></figure>

By observing the subtraction examples above, we can find out that

1. For *unsigned* subtraction, **borrow** indicates that the result is wrong.
   1. In ARM, **carry** is just **NOT borrow**. However, in Intel, **carry** is **borrow**, but in subtraction, it will flip the carry bit to get the carry flag when it is subtraction.
2. For *signed* subtrcation,
   1. Overflow occurs at when (+ve) - (-ve) = (-ve) or (-ve) - (+ve) = (+ve).
      1. And similar to the signed addition, we always treat the two operands as **signed**. So, if the sign bits (MSB) of the **operands** are different, and the **result** has a sign same as that of the second operand, there is an overflow.
      2. Overflow can never occur in subtraction when operands are of the **same sign**.
   2. In hardware, the Carry flag simply reflects the ALU's carry-out signal. Conceptually, during subtraction, this signal acts as the **inverse of the borrow** used in pen-n-paper arithmetic.

{% hint style="success" %}

#### Notes

1. The hardware as well as the instruction used for performing both signed and unsigned subtraction are the same
   1. The hardware doesn't know and doesn't care if we are dealing with signed or unsigned.
   2. Only the *interpretation* of the result and/or the way the *condition codes* are used are different.
   3. So, first use signed/unsigned to write out the two operands, then just do the binary subtraction on these two operands and derive the flags.
      {% endhint %}

***

In summary, we know the following points from the human interpretation side,

1. When C = 1, it indicates the **unsigned addition result** is wrong.
2. When C = 0, it indicates that the **unsigned subtraction** **result** is wrong.
3. When V = 1, it indicates that both **signed addition** and **signed subtraction** result are wrong.

***

For RISC-V, NZCV is **irrelevant** only when ALU does the **addition**. But, it is still recommended to go through how each flag of the NZCV is generated during [addition](#signed-addition).

Instead, in RISC-V, NZCV is **relevant** when ALU does the **subtraction**. Again, it is important to go through how NZCV is generated during [subtraction](#signed-subtraction). In RISC-V, the subtraction can be done in

* `sub`
* branch/slt variants

In pure `sub` instruction, the NZCV may not be that useful. But in branch/slt variants, this NZCV flag, which is not stored as bits for use by future instructions, becomes much more useful. The different comparisons, like `eq`, etc, are implemented using these NZCV flags.

| Comparison | Signed/Unsigned | Condition | Implemented as | Uses                  |
| ---------- | --------------- | --------- | -------------- | --------------------- |
| eq         | Both            | A == B    | Z              | Z flag                |
| ne         | Both            | A ≠ B     | ¬Z             | Z flag                |
| lt         | Signed          | A < B     | N ⊕ V          | Signed overflow logic |
| ge         | Signed          | A ≥ B     | ¬(N ⊕ V)       | Signed overflow logic |
| ltu        | Unsigned        | A < B     | ¬C             | Borrow logic          |
| geu        | Unsigned        | A ≥ B     | C              | Borrow logic          |

{% hint style="success" %}

#### Table Explanation

1. For the `lt` and `ge`, whch are for signed numbers, we must first make sure there is **no overflow**, then check the N flag.
2. For the `ltu` and `geu`, use the ARM borrow logic to understand. If `A<B`, then A-B will need a borrow, thus the carry flag is 0, and vice versa.
3. `sltu` is useful to check whether the subtraction of two numbers will need a **borrow** or not.
   {% endhint %}

<details>

<summary>Multi-word arithmetic in RISC-V</summary>

Suppose we want to do 64-bit addition and subtraction in RISC-V. We use `[t0:t1]` to store the 64-bit number A and `[t2:t3]` to store the 64-bit number B. And `[t4:t5]` to store the final result.

For the addition, we have,

{% code lineNumbers="true" %}

```riscv
add   t4, t0, t2        # low  word sum
sltu  t6, t4, t0        # carry = (sum < t0)
add   t5, t1, t3        # high word sum
add   t5, t5, t6        # add carry
```

{% endcode %}

For the subtraction, we have,

{% code lineNumbers="true" %}

```riscv
sub   t4, t0, t2        # low  word diff
sltu  t6, t0, t2        # borrow = (t0 < t2)
sub   t5, t1, t3        # high word diff
sub   t5, t5, t6        # subtract the borrow
```

{% endcode %}

So, in summary, we have

| Operation   | Condition for carry/borrow | Equivalent test            | RISC-V instruction |
| ----------- | -------------------------- | -------------------------- | ------------------ |
| Addition    | carry                      | `(sum < A)` or `(sum < B)` | `sltu t6, t4, t0`  |
| Subtraction | borrow                     | `(A < B)`                  | `sltu t6, t0, t2`  |

</details>

## Comparators

A **comparator** determines whether two binary numbers are equal or if one is greater or less than the other. A comparator receives two N-bit binary numbers A and B. There are two common types of comparators.

* An *equality comparator* produces a single output indicating whether A is equal to B (`A==B`).
* A *magnitude comparator* produces one or more outputs indicating the relative values of A and B.

{% stepper %}
{% step %}
**Equality comparator**

The eqaulity comparator is the simpler piece of hardware. Figure 5.11 shows the symbol and implementation of a 4-bit equality comparator. It first checks to determine whether the corresponding btis in each column of A and B are equal using XNOR gates. The numbers are equal if all of the columns are equal.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FOiYp0h6ygglMDNRuzxz3%2Fimage.png?alt=media&#x26;token=21af657d-8a1f-4daf-adc5-26037c5ee68f" alt=""><figcaption></figcaption></figure>
{% endstep %}

{% step %}
**Magnitude comparator**

Magnitude comparison is usually done by computing `A-B` and looking at the sign (most significant bit) of the resulf as shown in Figure 5.12. If the result is negative (e.g., the sign bit is 1), then A is less than B. Otherwise A is greater than or equal to B.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FAq7Zq2GlrBr2MMOwzpls%2Fimage.png?alt=media&#x26;token=44b66815-cc5d-42c9-9e2a-f98f864b018e" alt=""><figcaption></figcaption></figure>

{% hint style="success" %}
Here, the \[N-1] means the output is the $$(N-1)^{\text{th}}$$ bit of the result N.&#x20;
{% endhint %}
{% endstep %}
{% endstepper %}

HDL Example 5.3 shows how to ues various comparison operations.

{% tabs %}
{% tab title="SystemVerilog" %}
{% code title="Example 5.3 Comparators" lineNumbers="true" %}

```verilog
module comparator #(parameter N = 8)
                   (input  logic [N-1:0] a, b,
                    output logic        eq, neq, lt, lte, gt, gte);
  assign eq  = (a == b);
  assign neq = (a != b);
  assign lt  = (a < b);
  assign lte = (a <= b);
  assign gt  = (a > b);
  assign gte = (a >= b);
endmodule
```

{% endcode %}
{% endtab %}

{% tab title="Verilog" %}
{% code title="Example 5.3 Comparators" lineNumbers="true" %}

```verilog
module comparators #(parameter N = 8)
                    (input  [N-1:0] a, b,
                     output         eq, neq,
                     output         lt, lte,
                     output         gt, gte);
  assign eq  = (a == b);
  assign neq = (a != b);
  assign lt  = (a < b);
  assign lte = (a <= b);
  assign gt  = (a > b);
  assign gte = (a >= b);
endmodule
```

{% endcode %}
{% endtab %}
{% endtabs %}

## ALU

An **Arithmetic/Logical Unit** (ALU) combines a variety of mathematical and logical operations into a single unit. For example, a typical ALU might perform addition, subtraction, magnitude comparison, AND, and OR operations. The ALU forms the heart of most computer systems.

Figure 5.14 shows the symbol for an N-bit ALU with N-bit inputs and outputs.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FVWsxFshdo7xhDXxQBY3i%2Fimage.png?alt=media&#x26;token=01eb2e7e-ed3b-4ec3-90f6-1ff47adb0892" alt=""><figcaption></figcaption></figure>

The ALU receives a control signal F that specifies which function to perform. Table 5.1 lists typical functions that the ALU can perform.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FEjJwn9nEjayg4QnIhmSM%2Fimage.png?alt=media&#x26;token=0edce841-3b87-492f-a118-4805124807f7" alt="" width="394"><figcaption></figcaption></figure>

Figure 5.15 shows an implementation of the ALU.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FRdqMWUtNxReqwz9M91bw%2Fimage.png?alt=media&#x26;token=d60fdb72-a7bb-446c-92b6-c6172eb561cc" alt=""><figcaption></figcaption></figure>

{% hint style="success" %}

#### Image Explanation

1. $$F\_2$$ is also the carry in to the adder.
2. In two's complement arithmetic, $$\bar B+1=-B$$.
3. When $$F\_{\text{\[2:0]}}=111$$, the ALU performs the *set if less than* (SLT) operation. When $$A\<B$$, $$Y=1$$. Otherwise, $$Y=0$$. In other words, Y is set to 1 if A is less than B.
   1. SLT is performed by computing `S=A-B`. If S is negative (e.g., the sign bit is set), A is less than B. The *zero extend unit* produces an N-bit output by concatenating is 1-bit input with 0's in the most significant bits. The sign bit ( $$(N-1)^{\text{th}}$$ bit) of S is the input to the zero extend unit.
4. The AND and OR gate shown in the figure above both need **32 2-input** AND/OR gate to implement! **NOT One!**
5. The multiplexer to select whether one of the input sources is the $$N$$-bit $$\bar B$$ or $$B$$ can be implemented using $$N$$ 2-input [XOR gates](https://wenbo-notes.gitbook.io/ddca-notes/lab/resources/verilog-lifesaver#hint), where one input of the XOR gate is 1-bit from the $$N$$-bit $$B$$, the other is from the 1-bit signal $$F\_2$$.
   {% endhint %}

Some ALUs produce extra outputs, called *flags*, that indicate information about the ALU output. For example, an *overflow flag* indicates that the result of the adder overflowed. A *zero flag* indicates that teh ALU output is 0.

### HDL Implementation

The HDL for an $$N$$-bit ALU is shown as follows

{% tabs %}
{% tab title="SystemVerilog" %}
{% code lineNumbers="true" %}

```verilog
module alu32(input  logic [31:0] A, B,
             input  logic [2:0]  F,
             output logic [31:0] Y);
  logic [31:0] S, Bout;
  
  assign Bout = F[2] ? ~B : B;
  assign S = A + Bout + F[2];
  
  always_comb
    case (F[1:0])
      2'b00: Y <= A & Bout;
      2'b01: Y <= A | Bout;
      2'b10: Y <= S;
      2'b11: Y <= S[31];
    endcase
endmodule
```

{% endcode %}
{% endtab %}

{% tab title="Verilog" %}

> **TODO:** Wait for adding LOL.
> {% endtab %}
> {% endtabs %}

## Shifters and Rotators

**Shifters** and **rotators** move bits and multiply or divide by powers of 2. There are several kinds of commonly used shifters:

{% stepper %}
{% step %}

#### **Logical shifter**

It shifts the number to the left (LSL) or right (LSR) and fills empty spots with 0's. For example,

```
11001 LSR 2 = 00110; 11001 LSL 2 = 00100;
```

{% endstep %}

{% step %}

#### **Arithmetic shifter**

It is the same as logical shifter, but on right shifts fills the most significant bits with a **copy of the old most significant bit** (msb). This is useful for multiplying and dividing signed numbers. Arithmetic shift left (ASL) is the same as logical shift left (LSL) because we will fill the empty spots at **right** with 0, this doesn't matter much. For example,

```
11001 ASR 2 = 11110; 11001 ASL 2 = 00100;
```

{% endstep %}

{% step %}

#### **Rotator**

It rotates number in **circle** such that empty spots are filled with bits shifted off the other end.

```
11001 ROR 2 = 01110; 11001 ROL 2 = 00111;
```

{% endstep %}
{% endstepper %}

A N-bit shifter can be built from N N:1 multiplexers. The input is shifted by 0 to $$N-1$$ bits, depending on the value of the $$\log\_2N$$-bit select lines (`shamt`). Figure 5.16 shows the symbol and hardware of 4-bit shifters. The operators `<<`, `>>`, and `>>>` typically indicate shift left, logical shift right, and arithmetic shift right, respectively.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FPY8V6rTBN2hk1PxBqnQM%2Fimage.png?alt=media&#x26;token=351bf188-cbba-47a8-9e6e-fd0a91410430" alt=""><figcaption></figcaption></figure>

{% hint style="success" %}

#### Image Explanation

1. For the Figure 5.16(b), which is about `srl` (shift right logical), we can divide it into four cases
   1. `shamt = 00` (no shift), then output $$Y\_{\[3:0]}=A\_{\[3:0]}$$.
   2. `shamt = 01` (srl 1 bit), then output $$Y\_{\[3:0]}={0,\~A\_{\[3:1]}}$$
   3. `shamt = 10` (srl 2 bits), then output $$Y\_{\[3:0]}={00,\~A\_{\[3:2]}}$$
   4. `shamt = 11` (srl 3 bits),  then output $$Y\_{\[3:0]}={000,\~A\_3}$$
2. Such a shifter shown in the Figure 5.16 which can combinationally shift an input by an arbitrary amount is called a **barrel shifter**.
3. Shift by a **fixed amount** (e.g., 1 bit, 2 bits, etc) onlys needs **rewiring**! It doesn't need any multiplexer.
   {% endhint %}

If we want to use this idea to build a [32-bit shifter](#user-content-fn-4)[^4], we need 32 32:1 multiplexer, which has a very high hardware usage. To solve this problem, let's introduce the [hardware-efficient shifter](#hardware-efficient-shifter).

### Hardware-efficient Shifter

This hardware-efficient shifter only needs 5 x 32 2:1 multiplexer. And below is the implementation for the 32-bit `srl` shifter.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FX1viMzxVkVcfFYzLrhyo%2FScreenshot%202025-10-07%20105522.png?alt=media&#x26;token=b8607543-5457-436e-b523-f3061591ca79" alt=""><figcaption></figcaption></figure>

This shifter uses a **logarithmic, staged design** that decomposes any shift amount into a combination of small, power-of-two shifts. Each stage doubles the shift capacity, making the circuit both elegant and efficient.

To add support for `sll` and `sra`, the easiest way is to implement a 3-to-1 multiplexer, controlled by the shift type info from the instruction.

{% code overflow="wrap" lineNumbers="true" %}

```verilog
module shiftByNPowerOf2
//module Shifter
#(
    parameter i = 0
)  // exponent
(
    input [1:0] Sh,
    input flagShift,
    input [31:0] ShTempIn,
    output reg [31:0] ShTempOut
);

    always @(Sh, ShTempIn, flagShift) begin
        if (flagShift)
            case (Sh)
                2'b00:   ShTempOut = {ShTempIn[31-2**i:0], {2 ** i{1'b0}}};  // SLL
                2'b10:   ShTempOut = {{2 ** i{1'b0}}, ShTempIn[31:2**i]};  // SRL    
                2'b11:   ShTempOut = {{2 ** i{ShTempIn[31]}}, ShTempIn[31:2**i]};  // SRA
                //2'b01: ShTempOut = { ShTempIn[2**i-1:0], ShTempIn[31:2**i] } ;  	// ROR is not supported by RISC-V
                default: ShTempOut = ShTempIn;  // invalid
            endcase
        else ShTempOut = ShTempIn;
    end

endmodule

```

{% endcode %}

However, more efficient ways to combine the shifts exist though. For example, when $$\text{shamt5}\_4=1$$, the input can be from another small "multiplexer[^5]" that gives

* {16{0}. ShIn<sub>31:16</sub>} for `srl`
* {16{ShIn<sub>31</sub>}. ShIn<sub>31:16</sub>} for `sra`

{% hint style="info" %}
**Hint:** To implement this, we only need **1** 1-bit 2:1 multiplexer to select whether the MSB should be 0 or ShIn<sub>31</sub> and then duplicate it 16 times, we can get the result we want.
{% endhint %}

```verilog
// Improved code for uploading!
```

## Multiplication

In the [previous part](https://wenbo-notes.gitbook.io/ddca-notes/textbook/from-zero-to-one/number-systems#multiplication), we have seen that multiplication is nothing but shift then add. By shifting, we form the *partial products*.

In general, a NxN multiplier multiplies two N-bit numbers and produces a 2N-bit result. Multiplication of 1-bit binary numbers is equivalent to the AND operation, so AND gates are used to form the partial products.

### Array Multiplier

Figure 5.18 shows the symbol, function, and implementation of an **unsigned** 4x4 multiplier.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FP33CNqGYAqNj4Vvkjv59%2Fimage.png?alt=media&#x26;token=58788fde-8faa-4258-90ab-fc67f1d9b67e" alt=""><figcaption></figcaption></figure>

The unsigned multiplier receives the multiplicand and multiplier, $$A$$ and $$B$$, and produces the product $$P$$. Figure 5.18(b) shows how partial products are formed. Each partial product is a single multipler bit ($$B\_3,B\_2,B\_1,\text{ or }B\_0$$) AND the mutiplicand bits ($$A\_3,A\_2,A\_1,A\_0$$). With $$N$$-bit operands, there are $$N$$ partial products and $$N-1$$ stages of 1-bit adders. For example, for a 4x4 multiplier, the partial product of the first row is $$B\_0$$ AND ($$A\_3,A\_2,A\_1,A\_0$$). This partial product is added to the shifted second partial product, $$B\_1$$ AND ($$A\_3,A\_2,A\_1,A\_0$$). Subsequent rows of AND gates and adders form and add the remaining partial products.

This array multiplier is **combinational** because the whole multiplication (all ANDs and adds) happens in **one clock cycle**. Maybe [this video](https://www.youtube.com/watch?v=lf8wcTRb8NY) will be good on explaining the critical path and hardware analysis of the array multiplier.

<details>

<summary>The pros and cons of using array multiplier</summary>

In the array multiplier, we have the following two **advantages**

1. the multiplication is done in **one cycle**, thus it uses less cycle.
2. the bits are constructed in **parallel** by using the AND gates and then "ripple" through the adder. Thus it provides better parallelizability.

However, an array multiplier has the following **disadvantages**

1. The clock cycle depends on the **critical path**, which may thus slower the clock speed.
2. The hardware usage is **high** and increases in O(n<sup>2</sup>).

</details>

### Sequential Multiplier

Suppose that we may not want to do the mutiplication in one single cycle, we can use the **sequential multiplier**. Its workflow is given as follows,

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FkFjTQhfH4BfVf31ElYxI%2FScreenshot%202025-10-07%20114148.png?alt=media&#x26;token=8fbd25d0-e7c4-4f08-81b1-2db59d534049" alt=""><figcaption></figcaption></figure>

To understand it better, let's step through an example. Let `S=000000, A=011, B=101` (initial values)

1. $$B\_0=1$$ (original $$B\_0=1$$)
   1. add: `S = S + A = 000000 + 000011 = 000011`
   2. `A = A << 1;` Thus `A = 000110`
   3. `B = B >> 1;` Thus `B = 010`
2. $$B\_0=0$$ (original $$B\_1=0$$)
   1. no addition required here
   2. `A = A << 1;` Thus `A = 001100`
   3. `B = B >> 1;` Thus `B = 001`
3. $$B\_0=1$$ (original $$B\_2=1$$)
   1. add: `S = S + A = 000011 + 001100 = 001111`

{% hint style="success" %}
The hardware complexity increases **linearly** as we increase the bits to be multiplied.
{% endhint %}

#### Improved Sequential Multiplier

The idea is to always align $$A$$ to the "high-side" (3 most significant bits of S in 3-bit multiplication) and then perform the addition. Then shift S to the right and do not shift A. And the least significant bits of S populated with B, which keeps getting shifted to the right with S (avoids the need for an extra register for B). Its workflow is shown as follows,

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2F95riVQJevPUx3LPzAu9c%2Fimage.png?alt=media&#x26;token=51782eaf-8ada-4333-bfd2-f5eed717784c" alt="" width="563"><figcaption></figcaption></figure>

Again, stepping through an example will make it easier to understand. Let `S = 0000101 (000B), A = 011` (initial values)

1. $$S\_0=1$$ (original $$B\_0=1$$)
   1. add `S = S + A000 = 000101 + 011000 = 011101`
   2. `S = S >> 1;` Thus `S = 001110`
2. $$S\_0=0$$ (original $$B\_1=0$$)
   1. no addition required
   2. `S = S >> 1;` Thus `S = 000111`
3. $$S\_0=1$$ (original $$B\_2=1$$)
   1. add `S = S + A000 = 000111 + 011000 = 011111`
   2. `S = S >> 1;` Thus `S = 001111`, which is the final result

{% hint style="warning" %}
But there is a problem with the improved sequential multiplier, what if the 32-bit ALU generates a carry out? Where should the carry out go?

***

**Ans**: The carry-out effectively becomes the new MSB (Bit 63) of the 64-bit Product after the shift occurs.
{% endhint %}

<details>

<summary>The trade-off between array multiplier and sequential multipler</summary>

1. **Clock speed**: As we have seen from above, the array multiplier uses only **one cycle** but likely the cycle will take longer time, thus slowering the clock speed while the sequential multiplier uses **more cycles** but likely each cycle takes a shorter time and thus the clock speed is faster.
2. **Hardware cost**: The array multiplier usually uses **more hardware** than the sequential multiplier.

As a hardware designer, we need to always think about this kind of **trade-off** to achieve what we want. The following table summarizes the cost and latency analysis of a n-bit multiplier built using the carry propagate adder.

| Multiplier Type       | Cost (Hardware Area)   | Latency (Speed)        |
| --------------------- | ---------------------- | ---------------------- |
| Sequential Multiplier | $$O(n)$$ (Linear)      | $$O(n^2)$$ (Quadratic) |
| Array Multiplier      | $$O(n^2)$$ (Quadratic) | $$O(n)$$ (Linear)      |

</details>

### HDL Implementation

The HDL for a multiplier is in HDL Example 5.4. As with adders, the synthesis tools may pick the most appropriate design given the timing constraints.

{% tabs %}
{% tab title="SystemVerilog" %}
{% code title="Example 5.4 Multiplier" lineNumbers="true" %}

```verilog
module multiplier #(parameter N = 8)
                   (input  logic [N-1:0]    a, b,
                    output logic [2*N-1:0] y);
  assign y = a * b;
endmodule
```

{% endcode %}
{% endtab %}

{% tab title="Verilog" %}
{% code title="Example 5.4 Multiplier" lineNumbers="true" %}

```verilog
module multiplier #(parameter N = 8)
                   (input  [N-1:0]    a, b,
                    output [2*N-1:0] y);
  assign y = a * b;
endmodule
```

{% endcode %}
{% endtab %}
{% endtabs %}

## Division

{% hint style="success" %}
Before we continue this section, let's make some conventions first. Given $$A\div B = Q+R$$, we say that

* $$A$$ is the dividend
* $$B$$ is the divisor
* $$Q$$ is the quotient
* $$R$$ is the remainder
  {% endhint %}

Binary division can be performed using the following algorithm for $$N$$-bit unsigned numbers in the range $$\[0,\~2^N-1]$$.

{% code lineNumbers="true" %}

```
R' = 0
for i = N-1 to 0
    R = {R' << 1, A_i}
    D = R - B
    if D < 0 then Q_i = 0, R' = R // R < B
    else          Q_i = 1, R' = D // R >= B
R = R'
```

{% endcode %}

1. The *partial remainder* $$R$$ is initialized to 0 ($$R'=0$$), and the most significant bit of the **dividend** $$A$$ becomes the least significant bit of $$R$$ ($$R={R'<<1,\~ A\_i}$$).
2. The **divisor** $$B$$ is subtracted from this partial remainder to determine whether it fits ($$D = R-B$$).
   1. If the difference $$D$$ is negative (e.g., the sign bit of $$D$$ is 1), then the quotient bit $$Q\_i$$ is 0 and the difference is discarded.
   2. Else, the difference $$D$$ is positive. Then the quotient bit $$Q\_i$$ is 1 and the remainder $$R$$ becomes $$D$$.
   3. In any event, the partial remainder is then doubled (left-shited by one column), the next most significant bit of $$A$$ becomes the least significant bit of $$R$$, and the process repeats.
3. The process (step 2) repeats and the result satisfies $$\frac{A}{B}=Q+\frac{R}{B}$$.

{% hint style="success" %}
$$N$$-bit operands yield $$N$$-bit quotient and remainder. Here, we want to show that the divisor and quotient and remainder shares the same bit-width, but actually the dividend can have $$2N$$ bits.
{% endhint %}

Below is a more straight-forward example,

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2Fjn9OfUEODRFzdkHUq3Nl%2Fimage.png?alt=media&#x26;token=87809914-a594-4822-9432-937faacc0371" alt="" width="365"><figcaption></figcaption></figure>

This approach is called **long division approach**, which is basically similar to what we have seen above, but in a more straight-forward way

1. If divisor $$\leq$$ dividend bits
   1. 1 bit in quotient, subtract
2. Otherwise
   1. 0 bit in quotient, bring down next dividend bit

{% hint style="warning" %}
This illustration is more straight-forward, but less complete. Thus it is good for doing the hand-by-hand calculation. But for the systematic approach to implement in the hardware, please go reviewing the pseudocode above.
{% endhint %}

### Array Divider

Figure 5.22 shows a schematic of a 4-bit array divider. The divider computes $$A/B$$ and produces a quotient $$Q$$ and a remainder $$R$$. The legend shows the symbol and schematic for each block in the array divider.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FaEcAGlAV7pUJekoiPnHY%2Fimage.png?alt=media&#x26;token=9a2a603e-a0c3-4049-b7a1-457c73e7e024" alt=""><figcaption></figcaption></figure>

1. Each row performs one iteration of the division algorithm. Specifically, each row calculates the difference $$D = R-B$$. (Recall that $$R+\bar B+1=R-B$$).
2. The multiplexer select signal, $$N$$ ( for **N**egative), receives 1 when a row's difference $$D$$ is negative. So $$N$$ is driven by the most significant bit of $$D$$.
3. Each quotient bit ($$Q\_i$$) is 0 when $$D$$ is negative and 1 otherwise. The multiplexer passes $$R$$ to the next row if the difference is negative and $$D$$ otherwise. (In the legend)
4. The following row shifts the new partial remainder left by one bit (a good example to show that "shifting is just rewiring"), appends the next most significant bit of $$A$$, and then repeats the process.

The delay of an $$N$$-bit array divider increases proportionally to $$N^2$$ because the carry must ripple through all $$N$$ stages in a row before the sign is determined and the multiplexer can select $$R$$ or $$D$$. This repeats for all $$N$$ rows.

### Sequential Divider

> The sequential divider here just follows the pseudocode mentioned [above](#division), which is about **unsigned division**. To convert it to **signed**, only minor changes are needed. (For more information on this, can go to [Lab 03](https://wenbo-notes.gitbook.io/ddca-notes/lab/lab-03-multiply-and-divide#implementation-details))

Similar to the [#sequential-multiplier](#sequential-multiplier "mention"), we can also do the divider sequentially,

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2Fgd18FOzOQCXMeEJbQj6W%2FScreenshot%202025-10-08%20102943.png?alt=media&#x26;token=d39a333c-f3ea-497c-892c-eb22379a22d7" alt=""><figcaption></figcaption></figure>

To understand it better, again, let's step through an example. For example, 00000111 (dividend) is divided by 0010 (divisor).

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FeBXcMvvsML2HFO6GtGVH%2Fimage.png?alt=media&#x26;token=96e3d001-15d0-4b12-b5f3-f64ba93b3cfd" alt=""><figcaption></figcaption></figure>

In the Hennessy & Patterson's textbook, they mention an improved version of the division algorithm above, it is shown as follows,

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FGTmCxNy0pOXceupUzYWQ%2Fimage.png?alt=media&#x26;token=e98208fa-562c-498d-ab65-aba74964a61d" alt="" width="563"><figcaption></figcaption></figure>

### Signed Multiplication/Division

{% stepper %}
{% step %}

#### Signed vs. Unsigned Multiplication

When you multiply two **n-bit numbers**,

* the **lowest n bits** (the *least significant half*) of the product are **identical** no matter the numbers are interpreted as signed or unsigned.
* Only the **upper n bits** differ (because sign extension affects those).

That’s why:

* `MUL` (in RISC-V) gives just the *lower n bits*.
* `MULH` / `MULHU` (RISC-V) give the *upper n bits*, for signed/unsigned respectively.
  {% endstep %}

{% step %}

#### Macro-op fusion

“Macro-op fusion” means the processor can **fuse** `mul` and `mulh` internally and perform **a single 64-bit multiply**, returning both halves if needed.

We know that RISC-V has **separate instructions** for multiplication:

* `mul` → lower 32 bits of product
* `mulh` → upper 32 bits (signed × signed)
* `mulhu` → upper 32 bits (unsigned × unsigned)
* `mulhsu` → upper 32 bits (signed × unsigned)

If we implement them *literally*, it looks like three separate multipliers are needed. But **in hardware**, we don’t have to do three full multiplications. Instead, we can compute *one 64-bit result* internally and just output different parts or interpret sign bits differently.

So, even though RISC-V has multiple `mul` variants, we don’t necessarily perform multiple physical multiplications.
{% endstep %}

{% step %}

#### Signed/Unsigned always matters in Division

**Unlike multiplication**, signed and unsigned division *don’t share any bits* of result. We can’t reuse the same division result for both. For example,

| Dividend | Divisor | Signed?            | Result                                                                       | Notes           |
| -------- | ------- | ------------------ | ---------------------------------------------------------------------------- | --------------- |
| 6        | 3       | signed or unsigned | 2                                                                            | Same either way |
| 6        | -3      | signed             | -2                                                                           | (because sign)  |
| 6        | -3      | unsigned           | invalid (divisor interpreted as 4294967293 if 32-bit!)                       |                 |
| -6       | 3       | signed             | -2                                                                           | okay            |
| -6       | 3       | unsigned           | big number ≈ 0x55555554 (because -6 -> 0xFFFFFFFA interpreted as 4294967290) |                 |

So **division results** sometimes **completely change** depending on whether you treat numbers as signed or unsigned — even if you use the same bit pattern.
{% endstep %}

{% step %}

#### Simple trick for signed multiplication/division

Signed division (and signed multiplication) can be done using the same *unsigned* operation unit if you:

1. Record the sign of both operands.
2. Take their absolute values (convert negatives to positives).
3. Perform **unsigned division** (or multiplication).
4. If exactly one operand was negative, negate the result.

But there are some wierd scenarios. For example, if we want to do the following multiplication,

$$
-2^{31}\times-1=2^{31}
$$

The result cannot fit into a 32-bit register. This is an overflow (same trick to detect overflow as we have discussed in [signed addition/subtraction](#signed-addition))!
{% endstep %}
{% endstepper %}

## Number Systems

Computers operate on both integers and fractions. So far, we have only considered representing signed or unsigned integers. This section introduces fixed- and floating-point number systems that can represent **rational numbers**.

* [Fixed-point numbers](#fixed-point-number-systems) are analogous to decimals; some of the bits represent the integer part, and the rest represent the fraction
* [Floating-point numbers](#floating-point-number-systems) are analogous to scientific notation, with a mantissa and an exponent.

{% hint style="warning" %}
If we have $$N$$ bits, we can only represent 2<sup>N</sup> patterns. Using different number systems won't change the number of patterns, but can change the distribution of the numbers it represents.
{% endhint %}

### Fixed-Point Number Systems

*Fixed-point notation* has an implied *binary point* between the integer and fraction bits, analogus to the decimal point between the integer and fraction digits of an ordinary decimal number. For example, Figure 5.23(a) shows a fixed-point number with four integer bits and four fraction bits. Figure 5.23(b) shows the implied binary point in blue, and Figure 5.23(c) shows the equivalent decimal value.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FpdSlCfWd5GEopieOTlyF%2Fimage.png?alt=media&#x26;token=889a70ec-fa37-4809-83c9-da1e692df85f" alt=""><figcaption></figcaption></figure>

{% hint style="success" %}

#### Notes

1. This notation is not so standard.
2. The position of the binary point affects the *range* (difference between the largest and smallest representable numbers) and *precision* (smallest possible difference between any two numbers)
   {% endhint %}

#### Signed Fixed-Point

Signed fixed-point numbers can use either two's complement or sign/magnitude notation. Figure 5.24 shows the fixed-point representation of $$-2.375$$ using both notations with four integer and four fraction bits.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FfmP0Je4JLv7DXLScQ9PE%2Fimage.png?alt=media&#x26;token=012ed653-6591-4864-a5d6-071f675e5978" alt=""><figcaption></figcaption></figure>

{% hint style="success" %}
The implicit binary point is shown in <mark style="color:blue;">blue</mark> for clarity.
{% endhint %}

* In **sign/magnitude form**, the most significant bit is used to indicate the sign.
* The **two's complement representation** is formed by inverting the bits of the **absolute value** and adding 1 to the least significant (righmost) bit. In this case, the least significant bit position is in the $$2^{-4}$$ column.
  * In this example, we have: 00100110 -> 11011001 -> 11011010

{% hint style="success" %}
In general, we use *Ua.b* to denote an **unsigned fixed-point number** with *a* integer bits and *b* fraction bits. *Qa.b* denotes a **signed** (two's complement) fixed point number with *a* integer bits (including the sign bit) and *b* fractional bits.
{% endhint %}

<details>

<summary>A trick to quickly find the binary representation of a fraction using fixed-point notation</summary>

1. First, write the fraction is to $$\frac{A}{B}$$, where $$A$$ is any integer, and $$B$$ is an integer which is $$2^n$$.
2. Use binary to represent $$A$$ and find out $$n$$.
3. Move the binary point from behind the rightmost bit $$n$$ bits forward.

For example, we want to calculate $$0.625$$,

1. $$0.625=\frac{5}{8}=\frac{5}{2^3}$$
2. $$5=101$$
3. $$0.625=0.101$$
4. Fit into eight bit representation, it will become 0000.1010

</details>

#### Fixed-Point Calculation

> Fixed-point **addition** and **subtraction** is simple because the position of the binary point won't change. But **multiplication** and **division** are a bit tedious. So, here we will only talk about the fixed-point number **multiplication** and **division**.

Actually, from the small [trick](#a-trick-to-quickly-find-the-binary-representation-of-a-fraction-using-fixed-point-notation) we mentioned above, we've seen that fixed-point notation has an implicit **scale factor**, which is $$2^{\text{number of fraction bits}}$$.

For example, If we have **2 fractional bits**, the scale factor is $$2^2=4$$. That means every stored integer actually represents $$\text{stored/4}$$. So, `00000110₂ = 6` actually means $$6/4=1.5$$.

Knowing this, we can clearly see that when we multiply two numbers in fixed-point, both are *already scaled*. For example, let's compute

| Variable | Actual value | Stored (binary) | Decimal equivalent (stored) |
| -------- | ------------ | --------------- | --------------------------- |
| a        | 1.5          | 00000110        | 6                           |
| b        | 2.5          | 00001010        | 10                          |

When we do `a*b`, we will have `00111100₂`. Since we scaled each input by $$2^2=4$$, the product is scaled by $$4\*4=16=2^4$$. So to get back to the same scalor factor, which is 2 fractional bits, we must divide the product by 4 (shift right by 2 bits). Thus, we have `00111100₂ >> 2 = 00001111₂`. This gives our stored value to be 15 and our actual value to be $$15/4=3.75$$.

> But, in the above scenario, we assumed a short multiply, e.g., n-bit × n-bit = n-bit.

When we want to do a long multiplication,

* an **overflow** may happen, which basically is that our result bits cannot fit the multiplication result.
* an **underflow** may also happen, which means the multiplication result is representable, but **not accurately**, because our fractional bits are too few.

### Floating-Point Number Systems

Floating-point numbers are analogous to scientific notation. They circumvent the limitation of having a constant number of integer and fraction bits, allowing the representation of very large and very small numbers. Like scientific notation, floating-point numbers have a sign, mantissa (M), base (B), and exponent (E), as shown below:

$$
\pm M\times B^E
$$

For example, the number $$4.1×10^3$$ is the decimal scientific notation for 4100. It has a mantissa of 4.1, a base of 10, and an exponent of 3. The decimal point floats to the position right after the most significant digit. Floating-point numbers are base 2 with a binary mantissa. 32 bits are used to represent 1 sign bit, 8 exponent bits, and 23 mantissa bits.

The exponent needs to represent both positive and negative exponents. To do so, floating-point uses a biased exponent, which is the original exponent plus a constant bias. In 32-bit floating-point representation, the bias is 127. For example, for the exponent 7, the biased exponent is 7 + 127 = 134 = 10000110₂. For the exponent -4, the biased exponent is -4 + 127 = 123 = 01111011₂.

{% hint style="success" %}
This notation conforms to the IEEE 754 floating-point standard. In this notation, the first bit of the fraction/mantissa is **always** 1.
{% endhint %}

To put it all together, let's examine two examples:

{% stepper %}
{% step %}

#### Represent unsigned number in IEEE 754

Suppose we want to represent 228<sub>10</sub> = 11100100<sub>2</sub> = 1.11001<sub>2</sub> x 2<sup>7</sup> using floating point system, it will be as follows,

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2F0286PvNtQvAWGWE7iqXE%2Fimage.png?alt=media&#x26;token=25be8530-a5ac-48f4-b366-0dbbf19fbb97" alt=""><figcaption></figcaption></figure>
{% endstep %}

{% step %}

#### Represent signed number in IEEE 754

Suppose we want to write -58.25<sub>10</sub> in floating point (IEEE 754)

1. Convert decimal to binary: 58.25<sub>10</sub> = 111010.01<sub>2</sub>
2. Write in binary scientific notation: 1.1101001 x 2<sup>5</sup>
3. Fill in fields: Sign bit = 1, Biased Expoenent = 5 + 127 = 10000100<sub>2</sub>, 23 fraction bits = 110 1001 0000 0000 0000 0000.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FDSQxZi5feSI1FjJ3tTC8%2Fimage.png?alt=media&#x26;token=7fc6c89d-9088-4e7c-9bc6-4832629f16ab" alt=""><figcaption></figcaption></figure>
{% endstep %}
{% endstepper %}

#### Special Cases

The IEEE floating-point standard has special cases to represent numbers&#x20;such as zero, infinity, and illegal results.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FunAYhFIkz5VCCFsyBtQq%2Fimage.png?alt=media&#x26;token=1c679751-dbb2-49ef-9bbf-f994c6c02263" alt=""><figcaption></figcaption></figure>

#### More formats

So far, we have examined 32-bit floating-point numbers. This format is also called *single-precision*, *single*, or *float*. The IEEE 754 standard also defines 64-bit *double-precision* numbers (also called *doubles*) and 128-bit *quadruple-precision numbers* (also called *quads*) that provide greater precision and greater range. Table 5.5 shows the number of bits used for the fields in each format.

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FM80a8mKVr47FzgEMxwnN%2Fimage.png?alt=media&#x26;token=5a64ae4f-47d8-4de6-bf13-fde30fb3fbf1" alt=""><figcaption></figcaption></figure>

#### Rounding

Arithmetic results that fall outside of the available precision must round&#x20;to a neighboring number. The rounding modes are

1. round down,
2. round   &#x20;up,
3. [round toward zero](#user-content-fn-6)[^6], and
4. round to nearest.

The default rounding mode is **round to nearest**. In the round-to-nearest mode, if two numbers are equally near, the one with a 0 in the least significant position of the fraction is chosen.

For example, we want to round 1.100101 (1.578125) to only 3 fraction bits

1. round down: 1.100
2. round up: 1.101
3. round toward zero: 1.100
4. round to nearest: 1.101 (1.625 is close to 1.578125 than 1.5 is)

{% hint style="success" %}

#### Notes

1. A number *overflows* when its magnitude is too large to   &#x20;be represented.
2. A number *underflows* when it is too tiny to be   &#x20;represented.

In round-to-nearest mode, **overflows** are rounded up to $$\pm\infty$$&#x20;and **underflows** are rounded down to 0.
{% endhint %}

#### Floating-Point Calculation

{% stepper %}
{% step %}

#### Addition

The steps for adding floating-point numbers with the same sign are as follows:

1. Extract exponent and fraction bits.
2. Prepend leading 1 to form the mantissa.
3. Compare exponents.
4. Shift smaller mantissa if necessary.
5. Add mantissas.
6. Normalize mantissa and adjust exponent if necessary.
7. Check whether have overflow or underflow then round result.
8. Assemble exponent and fraction back into floating-point number.

For example,

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2FJOf3dbiXb4eAb2olv7c4%2Fimage.png?alt=media&#x26;token=bb77a3b2-3ec5-49bd-a213-d2801a40e639" alt="" width="563"><figcaption></figcaption></figure>

{% hint style="success" %}

#### Notes

1. For **subtraction**, just change step 5 to -> Subtract the mantissas.
   1. If two mantissa A - B, and A is smaller, just do B - A and add a **negative sign** to the final result and then normalize the mantissa.
2. If Step 3 the **shift amount** is **negative**, shift the upper mantissa to the **right**.
3. Step 7 to check overflow and underflow is **important**! The idea is to check whether the final result's exponent is between \[-126, 127] for single-precision floating point number. If < -126, **underflow** and if > 127, **overflow**.
   {% endhint %}
   {% endstep %}

{% step %}

#### Multiplication

Floating point multiplication follows the steps shown as follows:

<figure><img src="https://4009084806-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FjTJFBPtKk6NwweAooH53%2Fuploads%2Fpsd1YEJVNniQyzHZBugy%2Fimage.png?alt=media&#x26;token=b650602e-0984-4d95-af46-688dcab0cb37" alt="" width="369"><figcaption></figcaption></figure>

For example, using the above steps to multiply the numbers 0.5<sub>10</sub> and -0.4375<sub>10</sub>.

1. **In binary**, the task is multiplying 1.000<sub>2</sub> x 2<sup>-1</sup> by -1.110<sub>2</sub>  x 2<sup>-2</sup>.
2. **Adding the exponents without bias:**
   1. -1 + -2 = -3. The exponenet will be -3 + 127 = 124
3. **Multiplying the significands:**
   1. 1.000 x -1.110 = 1.110 x 2<sup>-3</sup>
4. **Checking Overflow and underflow:**
   1. As -3 is within \[-127, 126], no overflow and underflow
5. **Rounding the product:**
   1. No need in this case
6. **Adding the sign to the final product:**
   1. Since the signs of the original operands differ, make the sign of the product negative. Hence the product is, -1.110 x 2<sup>-3</sup>.

{% hint style="success" %}

#### Notes

1. For the **division**, change step 1 to **add bias to the difference of the two exponents**. Step 2 is to use **long division** to **divide the two significands**.
   {% endhint %}
   {% endstep %}
   {% endstepper %}

[^1]: A "Block" acts as a "super-adder." For example, a 4-bit block looks at inputs $$A\_{0-3}$$ and $$B\_{0-3}$$ simultaneously.

[^2]: Here, the “carry-in” refers to the **initial** carry input of the adder. Each adder has only one carry-in signal; for multi-bit adders, this single carry-in propagates through the stages of the adder to produce carries for subsequent bits.

[^3]: This means, when there is a carry in, the column will always produce a carry out, which **propagates** the carry in it receives.

[^4]: Input and output of the shifter is a 32-bit number, and thus the select line `shamt` will be $$\log\_232=5$$ bits.

[^5]: the actual implementation is to use AND gates.

[^6]: It's just simply *chop off* (truncate) the extra fraction bits starting from the last bit in interest (See the example below). No rounding up at all, no matter whether it’s positive or negative.
