Number Representation and Binary Arithmetic for GATE

1. Strategy for Unknown Base Problems

A common type of question in GATE involves an equation with numbers in unknown bases. A direct algebraic solution can sometimes be time-consuming or complex if there are multiple unknowns. A more efficient exam strategy is often to test the given options.

Let's look at a typical problem of this kind from a recent GATE paper.

This problem-solving technique is vital. When you see an equation like $(1235{)}_X=(303{)}_Y$, your first thought should be to assess if a direct solution is faster than checking the 2-3 valid options provided. The video also highlights a useful common-sense check: for a number with more digits to equal a number with fewer digits (e.g., 1235 vs 303), the base of the first number must be smaller than the base of the second. However, in this case, the numbers are different, but the logic about base size vs. digit values still applies. A smaller base requires more digits to represent the same value.

2. Tackling 2's Complement and Overflow

2's complement is the most important topic within this module for the GATE exam. Questions will test your ability to convert, perform arithmetic, and, most importantly, detect overflow conditions.

2.1. Representation and Sign Extension

Before performing arithmetic with numbers of different bit lengths, you must make them the same length. This is done through sign extension, where the sign bit is copied to the new, more significant bit positions.

• For a positive number (sign bit = 0), extend by adding 0s to the left.
• For a negative number (sign bit = 1), extend by adding 1s to the left.

Example Problem (based on GATE '07, Q.38):
X = 01110 (a 5-bit positive number) and Y = 11001 (a 5-bit negative number) are in 2's complement format. We want to calculate their sum, X + Y, and represent it using 6 bits.

Solution Steps:

1. Sign-extend both numbers to 6 bits:
   • X = 01110 becomes 001110 (add a 0 at the front). In decimal, this is $14$.
   • Y = 11001 becomes 111001 (add a 1 at the front). In decimal, this is $-7$.
2. Add the 6-bit numbers:

     001110   (14)
   + 111001   (-7)
   ----------
     000111   (7)  (The carry-out of 1 is discarded)
   

3. The result is $(000111{)}_{2^{\prime }scomplement}$, which is $(7{)}_{10}$. This matches our decimal calculation $(14+(-7)=7)$.

You can find a similar problem (Q.38) in the "GATE SOLVED PAPER - EC" PDF (resource_id: [LINK](https://www.mywbut.com/gate/gate%20chapter%20wise%20solved%20papers/ec/Digital%20Circuits.pdf)).

2.2. Overflow Detection

Overflow is a critical error condition in signed arithmetic. It occurs when the result of an operation is too large to be represented by the available number of bits.

An overflow can only happen when adding two numbers of the same sign. It never occurs when adding numbers with different signs.

There are two primary ways to detect overflow in an N-bit system:

1. Sign-based Rule: Check the sign bits of the operands and the result.

   • An overflow occurs if you add two positive numbers and get a negative result.
   • An overflow occurs if you add two negative numbers and get a positive result.

2. Carry-bit Rule: Compare the carry-in and carry-out of the Most Significant Bit (MSB) column.

   • Let $C_{in}$ be the carry into the MSB (sign bit) column.
   • Let $C_{out}$ be the carry out of the MSB column.
   • Overflow occurs if and only if $C_{in}\ne C_{out}$.

Let's watch a video that formalizes this carry-bit rule.

GATE often asks for the Boolean expression that detects overflow. Let the sign bits of the two numbers being added be $x$ and $y$, and the sign bit of the result be $z$. The condition for overflow is captured by this classic logic expression:

3. Application in Arithmetic Circuits

These concepts aren't just abstract; they are the foundation of how arithmetic circuits like adders and subtractors work. Let's analyze a circuit that performs both addition and subtraction using 2's complement.

This problem connects the theory of 2's complement subtraction (i.e., $A-B=A+(\text{2’s comp of }B)$) to a hardware implementation.

This example shows that understanding 2's complement is not just about manual calculation but also about recognizing its implementation in digital hardware—a key skill for an ECE engineer.

4. Practice Problems for Self-Assessment

To solidify your understanding, try these problems from the provided resources. They cover the key concepts we've discussed.

1. Decimal Conversion: The 2's complement numbers 11001, 1001, and 111001 correspond to which set of decimal numbers? (See Q.72 in the PDF LINK).
2. Range of Representation: What is the range of signed decimal numbers that can be represented by a 6-bit 1's complement representation? (See Q.68 in the PDF LINK). This tests your understanding of the differences between 1's and 2's complement ranges.
3. Subtraction: Two numbers in signed 2's complement are P = 11101101 and Q = 11100110. If Q is subtracted from P, what is the result in signed 2's complement? (See Q.30 in the PDF LINK).

Conclusion

This lesson concludes our module on number systems. You've transitioned from foundational theory to applying that knowledge to solve complex, exam-relevant problems.

Key Takeaways:

• Problem-Solving Strategies: For unknown bases, option substitution is a powerful tool. For arithmetic, always be mindful of sign extension.
• 2's Complement is Key: Master the conversion, arithmetic, and especially the two rules for overflow detection (sign-based and carry-based).
• Hardware Connection: Understand that concepts like 2's complement subtraction are directly implemented in circuits using components like adders and XOR gates.

Next Lesson Preview:
We have built the foundation of how information is represented in digital systems. Now, we will move on to processing that information. In the next module, Boolean Algebra and Logic Gates, you will learn the mathematical principles and the fundamental building blocks (AND, OR, NOT, NAND, NOR gates) that are used to design all digital circuits.