Binary Arithmetic and IEEE 754 Floating-Point Representation

1. Fixed-Point Arithmetic and Overflow

As we learned, modern computers almost exclusively use 2's complement representation for signed integers. This is because it simplifies hardware design: subtraction becomes a special case of addition. To compute $A-B$, the ALU simply calculates $A+(\text{2’s complement of }B)$.

While addition itself is a straightforward binary sum, the most important consideration is overflow. Overflow occurs when the result of an arithmetic operation is outside the range of values that can be represented with a given number of bits. For an $n$-bit 2's complement system, the range is from $-2^{n-1}$ to $+(2^{n-1}-1)$.

Detecting Overflow in 2's Complement Addition

There are two simple rules to remember for detecting overflow, which are very frequently tested in GATE:

1. Sign-based detection:

   • If you add two positive numbers and get a negative result, overflow has occurred.
   • If you add two negative numbers and get a positive result, overflow has occurred.
   • Crucially, adding a positive and a negative number can never cause overflow. The result will always be within the representable range.

2. Carry-bit detection: This is the method used by hardware. Overflow occurs if and only if the carry-in to the most significant bit (MSB) column is different from the carry-out from the MSB column. Let's denote them as $C_{in}$ and $C_{out}$ for the MSB. Overflow $⟺C_{in}\ne C_{out}$.

Let's see this with 4-bit examples (Range: -8 to +7).

• Case 1: No Overflow (5 + (-2) = 3)

  • 5 is 0101. -2 is 1110.
  • 0101 + 1110 = (1)0011. The carry-out 1 is discarded. 0011 is +3. Correct.
  • (Positive + Negative cannot overflow).

• Case 2: Positive Overflow (6 + 4 = 10, which is out of range)

  • 6 is 0110. 4 is 0100.
  • 0110 + 0100 = 1010. The result has MSB=1, so it represents -6. This is incorrect.
  • Sign detection: Positive + Positive $\to$ Negative. Overflow.
  • Carry-bit detection: The carry into the MSB column was 1, but the carry out was 0. Since $C_{in}\ne C_{out}$, overflow occurred.

• Case 3: Negative Overflow (-7 + (-3) = -10, which is out of range)

  • -7 is 1001. -3 is 1101.
  • 1001 + 1101 = (1)0110. The carry-out 1 is discarded. 0110 represents +6. This is incorrect.
  • Sign detection: Negative + Negative $\to$ Positive. Overflow.
  • Carry-bit detection: The carry into the MSB was 0, but the carry out was 1. Since $C_{in}\ne C_{out}$, overflow occurred.

Mastering these detection rules is essential for questions on computer arithmetic.

2. From Fixed-Point to Floating-Point

Fixed-point numbers, where the binary point is at a fixed position, are great for integers but have a limited range and precision. They cannot simultaneously represent very large numbers (like the distance to a star) and very small fractions (like the size of an atom).

To solve this, computers use a binary version of scientific notation, known as floating-point representation. This allows the binary point to "float," trading off range and precision as needed.

3. The IEEE 754 Standard

To ensure that floating-point numbers could be exchanged between different computer systems, the Institute of Electrical and Electronics Engineers (IEEE) created the IEEE 754 standard. This is the universal format used today. We'll focus on the two most common types:

• Single-Precision (32 bits): Used for float variables in languages like C/C++/Java.
• Double-Precision (64 bits): Used for double variables.

GATE problems predominantly focus on the 32-bit single-precision format.

A single-precision number is composed of three parts:

1. Sign (S): 1 bit. 0 for positive, 1 for negative.
2. Exponent (E): 8 bits. Represents the exponent in a biased or Excess-127 format.
3. Mantissa/Fraction (M): 23 bits. Represents the significant digits of the number in a normalized form.

The video below explains this structure and the crucial concepts of a biased exponent and normalized mantissa.

Summary of Conversion: Decimal to IEEE 754 Single-Precision

1. Sign (S): Determine the sign bit (0 for positive, 1 for negative).
2. Binary Conversion: Convert the absolute value of the decimal number into binary.
3. Normalization: Adjust the binary point so there is a single leading 1. The number will look like $1.M\times 2^e$. The sequence of bits after the binary point is the mantissa, and e is the true exponent.
4. Exponent (E): Calculate the biased exponent as $E=e+127$. Convert this value to an 8-bit unsigned binary number.
5. Mantissa (M): Take the fractional part from the normalized form and pad it with trailing zeros to fill the 23-bit field. The leading 1 is not stored; it's implicit, giving you 24 bits of precision for the price of 23.
6. Assemble: Combine the three fields in the order S, E, M.

4. Special Values

The IEEE 754 standard reserves certain exponent and mantissa patterns to represent special values. This is why the biased exponent range for normalized numbers is 1 to 254, excluding the all-zeros and all-ones patterns.

• Zero: Represented by an exponent of all 0s and a mantissa of all 0s. The sign bit can be 0 or 1, leading to +0 and -0.
• Infinity: Represented by an exponent of all 1s and a mantissa of all 0s. Used for results of operations like $x/0$.
• NaN (Not a Number): Represented by an exponent of all 1s and a non-zero mantissa. Used for invalid operations like $\sqrt{-1}$ or $0/0$.
• Denormalized Numbers: Represented by an exponent of all 0s and a non-zero mantissa. These represent very tiny numbers close to zero, filling the gap between the smallest normalized number and zero.

The following video gives a very clear and concise summary of these cases, which is perfect for quick revision.

5. Converting IEEE 754 back to Decimal

To complete your understanding, you also need to be able to perform the reverse conversion. The process is a straightforward reversal of the steps we learned.

1. Deconstruct: Separate the 32-bit pattern into S (1 bit), E (8 bits), and M (23 bits).
2. Check for Special Values: If E is all 0s or all 1s, handle it as a special case (Zero, Infinity, NaN, or Denormalized).
3. Calculate True Exponent: For normalized numbers, convert the 8-bit exponent E to a decimal value and subtract the bias: $e=E-127$.
4. Reconstruct Mantissa: Re-insert the implicit leading 1. The full mantissa is $1.M$.
5. Calculate Final Value: The decimal value is given by the formula: $(-1{)}^S\times (1.M)\times 2^e$.

You can see this reverse process in action in the first video we used.

Conclusion

This lesson concludes our journey through Module 4 by covering the practical aspects of how computers handle numbers. We've bridged the gap between the theoretical representation of numbers and their actual manipulation in hardware.

Key Takeaways:

• Fixed-Point Arithmetic: 2's complement is the standard. Subtraction is performed as addition of the negative.
• Overflow Detection: Overflow in 2's complement addition can be detected in two ways: by checking the signs of operands and the result, or by comparing the carry-in and carry-out of the MSB ($C_{in}\ne C_{out}$).
• Floating-Point Necessity: IEEE 754 is the standard solution for representing real numbers, offering a wide dynamic range.
• IEEE 754 Structure: A single-precision number has a 1-bit sign, an 8-bit biased (Excess-127) exponent, and a 23-bit mantissa with a "hidden" leading 1.
• Conversion Process: You should now be comfortable converting between decimal values and their 32-bit IEEE 754 representation, and vice-versa.
• Special Values: Remember the specific bit patterns for Zero, Infinity, and NaN, as these are common sources of conceptual questions.

With this, you have completed the Digital Logic module. The concepts of number representation and arithmetic are the absolute bedrock for the next module, Module 5: Computer Organization & Architecture. Our first lesson there will be on Machine Instructions & Instruction Formats, where you'll see how the CPU uses opcodes and operands—encoded as binary numbers—to perform the very arithmetic operations we discussed today.