Data representation and computer arithmetic notes — Unit 1

While Digital Logic Design teaches how to build individual gates and registers, Computer Organisation and Architecture teaches how to connect millions of these registers to form a functioning computer.

⇒1.1 Organisation vs. Architecture

• Computer Architecture: Refers to the attributes of a system visible to a programmer. It defines the conceptual structure and functional behavior. (e.g., Instruction set, number of bits used for data types, I/O mechanisms, addressing techniques).
• Computer Organisation: Refers to the operational units and their interconnections that realize the architectural specifications. (e.g., Hardware details transparent to the programmer, such as control signals, interfaces, memory technology used, and the internal design of the ALU).

Analogy: Architecture is the floor plan and features of a house. Organisation is the plumbing, wiring, and brickwork used to build it.

A CPU only understands 1s and 0s. The hardware must have standard ways to interpret these binary strings as integers, fractions, or characters.

⇒2.1 Fixed-Point Representation

The radix point (decimal point) is assumed to be at a fixed position. Usually, it's assumed to be at the far right, making the number an integer.

To represent negative numbers, three formats exist:

• Sign-Magnitude: The MSB is the sign bit (0=Positive, 1=Negative). The remaining bits are the magnitude. Flaw: Has $+0$ and $-0$. Subtraction requires complex logic.
• 1's Complement: Negative numbers are formed by flipping all bits. Flaw: Still has $+0$ and $-0$. Requires an 'end-around carry' during addition.
• 2's Complement: Negative numbers are the 1's complement $+ 1$. This is the universal standard for integers. Only one representation for zero. Subtraction is just addition with the 2's complement.

Fixed-point cannot represent very large ($10^{30}$) or very small ($10^{-30}$) numbers efficiently. Floating-point solves this using scientific notation: $N = M \times R^E$.

A floating-point binary number is split into three fields:

• Sign ($S$): 1 bit (0 for +, 1 for -).
• Exponent ($E$): Determines the position of the radix point. Stored in a 'biased' format.
• Mantissa / Significand ($M$): The precision bits of the number.

⇒3.1 Normalization

To ensure a unique representation, numbers are normalized so the most significant bit of the mantissa is non-zero. In binary, the leading bit is ALWAYS a 1 (e.g., $1.0110 \times 2^5$). Since it's always 1, IEEE standards don't even store it (saving 1 bit of memory). This is the Hidden Bit.

The universal hardware standard for floating-point math.

⇒4.1 Single Precision (32-bit)

• Sign: 1 bit (Bit 31)
• Biased Exponent: 8 bits (Bits 30-23). Bias = 127.
• Fraction (Mantissa): 23 bits (Bits 22-0).

Value $= (-1)^S \times (1.\text{Fraction}) \times 2^{(\text{Exponent} - 127)}$

⇒4.2 Double Precision (64-bit)

• Sign: 1 bit (Bit 63)
• Biased Exponent: 11 bits (Bits 62-52). Bias = 1023.
• Fraction (Mantissa): 52 bits (Bits 51-0).

Why use Biased Exponents? It allows exponents to be strictly positive integers (ranging from 1 to 254 in single precision), which means a simple integer comparator hardware circuit can compare floating-point numbers quickly.

Addition and Subtraction of 2's complement integers are executed by the same hardware: a Parallel Adder.

⇒5.1 The Hardware Implementation

Consider registers A and B feeding into an $n$-bit adder. We introduce an add/subtract control wire called $M$.

• The bits of register B are passed through XOR gates with $M$.
• $M$ is also connected to the Carry-In ($C_0$) of the adder.
• When $M=0$ (Add): $B \oplus 0 = B$. $C_0 = 0$. The adder computes $A + B$.
• When $M=1$ (Subtract): $B \oplus 1 = B'$ (1's complement). $C_0 = 1$. The adder computes $A + B' + 1$, which is $A - B$.

⇒5.2 Overflow Detection

An overflow occurs when the sum of two $n$-bit numbers requires $n+1$ bits. In 2's complement, an overflow happens if adding two positive numbers yields a negative result, or adding two negative numbers yields a positive result.

Hardware detection: $V = C_{n-1} \oplus C_n$. If the carry INTO the sign bit differs from the carry OUT OF the sign bit, an overflow has occurred ($V=1$).

Multiplication is inherently a process of repeated addition and shifting.

⇒6.1 Shift-and-Add Algorithm

To multiply two $n$-bit unsigned integers (Multiplicand $M$, Multiplier $Q$), we need a $2n$-bit register to hold the product. We use three registers: $A$ (initially 0), $Q$ (holds multiplier), and $M$ (holds multiplicand).

• 1. Check the LSB of the multiplier, $Q_0$.
• 2. If $Q_0 = 1$, add the Multiplicand $M$ to $A$. ($A \leftarrow A + M$).
• 3. If $Q_0 = 0$, do nothing.
• 4. Shift the combined registers $A$ and $Q$ to the RIGHT by 1 bit. (The LSB of $A$ shifts into the MSB of $Q$. $Q_0$ drops off).
• 5. Repeat $n$ times.

The final product is the combined $2n$-bit value in registers $A$ and $Q$.

The Shift-and-Add algorithm fails for negative numbers (2's complement). Booth's Algorithm elegantly multiplies signed numbers without needing to convert them to positive first.

⇒7.1 The Theory

Booth's algorithm looks at strings of 1s in the multiplier. A string like `011110` (decimal 30) can be computed as $2^5 - 2^1$ (32 - 2). This means we can replace four additions with one subtraction and one addition, speeding up the process.

⇒7.2 Hardware Setup

• $M$: Multiplicand.
• $Q$: Multiplier.
• $A$: Accumulator (initially 0).
• $Q_{-1}$: A 1-bit register appended to the right of $Q_0$ (initially 0).
• Count: Set to $n$.

The algorithm examines the pair of bits $Q_0$ and $Q_{-1}$.

⇒8.1 Operation Steps

• If $Q_0Q_{-1} = 10$: Subtract $M$ from $A$ ($A \leftarrow A - M$). This marks the beginning of a string of 1s.
• If $Q_0Q_{-1} = 01$: Add $M$ to $A$ ($A \leftarrow A + M$). This marks the end of a string of 1s.
• If $Q_0Q_{-1} = 00$ or $11$: Do nothing. (We are in the middle of a string of 0s or 1s).

After performing the arithmetic (if any), perform an Arithmetic Shift Right (ASR) on the combined register $AQ Q_{-1}$.

Note on ASR: When shifting right, the MSB (the sign bit of $A$) remains unchanged, preserving the sign of the number. The old MSB also shifts right.

Decrement Count. Repeat until Count is 0. The final signed product is in $A$ and $Q$.

Division is the most complex arithmetic operation in a CPU. It is essentially repeated subtraction and shifting. We divide a $2n$-bit Dividend by an $n$-bit Divisor, producing an $n$-bit Quotient and an $n$-bit Remainder.

⇒9.1 Hardware Setup

• $M$: Divisor.
• $A, Q$: The $2n$-bit Dividend is loaded across $A$ (upper half) and $Q$ (lower half). If the dividend is only $n$ bits, it goes into $Q$, and $A$ is zeroed.
• Count: Set to $n$.

There are two main algorithms for binary division: Restoring and Non-Restoring.

This algorithm tries to subtract the divisor. If the result is negative, it "restores" the value by adding the divisor back.

⇒10.1 Algorithm Steps

• 1. Shift combined registers $A$ and $Q$ LEFT by 1 bit.
• 2. Subtract Divisor $M$ from $A$ ($A \leftarrow A - M$).
• 3. Check the sign bit of $A$ (the MSB).
• 4. If $A$ is Positive (MSB=0): The subtraction was successful. Set $Q_0 = 1$.
• 5. If $A$ is Negative (MSB=1): The subtraction failed. Set $Q_0 = 0$. Restore $A$ by adding $M$ back ($A \leftarrow A + M$).
• 6. Decrement Count. If Count $\neq 0$, loop back to step 1.

After $n$ loops, the Quotient is in $Q$, and the Remainder is in $A$.

Flaw: The restoration step ($A \leftarrow A + M$) wastes a clock cycle whenever the subtraction fails.

This algorithm optimizes division by eliminating the wasteful "restore" step. Instead of restoring $A$ and shifting, it shifts first and then adds.

⇒11.1 The Logic

If $A$ becomes negative, we essentially subtracted $M$ when we shouldn't have. In the next step, we shift left (multiplying the error by 2, becoming $-2M$) and then add $M$.
$(-2M) + M = -M$.
This yields the exact same mathematical result as if we had restored $A$ ($+M$), shifted left ($\times 2$), and then subtracted $M$ ($-M$).

⇒11.2 Algorithm Steps

• 1. Shift $A$ and $Q$ LEFT.
• 2. If sign of $A$ is 0 (positive): Subtract $M$ from $A$.
  If sign of $A$ is 1 (negative): Add $M$ to $A$.
• 3. If new sign of $A$ is 0: Set $Q_0 = 1$.
  If new sign of $A$ is 1: Set $Q_0 = 0$.
• 4. Decrement count and loop.
• 5. Final Correction: After $n$ loops, if $A$ is negative, add $M$ to $A$ one last time to get the true positive remainder.

Adding and multiplying floating-point numbers requires coordination between the mantissas and the exponents.

⇒12.1 Floating-Point Addition/Subtraction

You cannot add mantissas if the exponents are different (just like you can't add $1.5 \times 10^3$ to $2.0 \times 10^2$ directly).

• 1. Compare exponents.
• 2. Shift the mantissa of the smaller number to the RIGHT until the exponents match. (e.g., $2.0 \times 10^2 \to 0.2 \times 10^3$).
• 3. Add/Subtract the mantissas.
• 4. Normalize the result (shift the mantissa and adjust the exponent) so it fits the IEEE 754 format.

Multiplication of floating-point numbers is actually simpler than addition because alignment isn't required.

⇒13.1 Steps for FP Multiplication

• 1. Add Exponents: Because the exponents are biased ($E = e + 127$), simply adding them yields double bias: $(e_1 + 127) + (e_2 + 127) = e_1 + e_2 + 254$. We must subtract the bias (127) once to get the correct new exponent.
• 2. Multiply Mantissas: Use unsigned hardware multiplication.
• 3. Determine Sign: XOR the two sign bits. ($S_1 \oplus S_2$).
• 4. Normalize: If the multiplied mantissa is $\ge 2.0$, shift it right 1 bit and increment the exponent.

Modern GPUs are essentially massive arrays of hardware built specifically to execute these floating-point operations in parallel.

Unit 1 connects abstract math to physical logic circuits.

⇒14.1 University Exam Checklist

• Convert $(-12.625)_{10}$ into IEEE 754 Single Precision format. Show the Sign, Biased Exponent in binary, and Mantissa.
• Explain the flaw of the Restoring division algorithm and how Non-Restoring division fixes it.
• Trace Booth's Multiplication Algorithm to multiply $(-5) \times (7)$ using 4-bit registers. Show the contents of A, Q, and Q-1 at each step.
• Draw the block diagram of a hardware adder/subtractor and explain the role of the V (overflow) flag.
• List the steps required for floating-point addition.

⇒14.2 Systems Programming Interview Focus

• Why is checking for equality (`a == b`) with floating-point numbers in C/C++/Java a bad idea? (Answer: Due to precision loss during normalization and truncation, $0.1 + 0.2$ often equals $0.30000000000000004$ in IEEE 754).