Understanding Subtraction with (r-1)'s Complement

Subtracting two positive numbers, M and N (where M − N), can be efficiently performed using the (r−1)'s complement method in digital systems. This method converts subtraction into an addition operation, simplifying the logic required. The base 'r' determines the type of complement used (e.g., for base 10, it's 9's complement; for base 2, it's 1's complement).

The general idea is to add the minuend (M) to the (r−1)'s complement of the substrahend (N). The way the result is interpreted depends on whether an 'end carry' is generated during the addition.

Analyzing the Given Steps for (r-1)'s Complement Subtraction

Let's look at the steps provided and see how they fit into the (r−1)'s complement subtraction process.

• (A) Add the minuend M to the (r−1)'s complement of the substrahend N.

  This is the initial and crucial step. Instead of directly subtracting N from M, we add M to the (r−1)'s complement of N. This conversion is fundamental to the method.

  \( \text{Result} = M + (r-1)'s \text{ complement of } N \)

  This step is always performed first.

• (B) If an end carry occurs, add 1 to the least significant bit.

  An end carry occurs when the result of the addition in step (A) exceeds the number of bits/digits allocated, generating a carry-out from the most significant position. This typically happens when \(M \ge N\). If an end carry occurs, it signifies a positive result. In the (r−1)'s complement method, this end carry is added back to the least significant bit of the sum. This is called an 'end-around carry'.

  \( \text{Final Result} = \text{Sum (from A)} + 1 \quad (\text{if end carry occurs}) \)

  This step is performed conditionally after step (A) if there is an end carry.

• (C) If end carry does not occur, take the (r−1)'s complement of the number obtained in step A and place negative sign in front.

  If no end carry occurs after the addition in step (A), it usually means \(M < N\), and the result M − N is negative. The sum obtained in step (A) in this case is the (r−1)'s complement of the magnitude of the actual difference (N − M). To get the actual magnitude of the difference, you need to take the (r−1)'s complement of the result from step (A). Since the original difference (M − N) was negative, a negative sign is placed in front of this magnitude.

  \( \text{Final Result} = - ((r-1)'s \text{ complement of Sum from A}) \quad (\text{if no end carry occurs}) \)

  This step is performed conditionally after step (A) if there is no end carry.

• (D) Take (r−1)'s complement of the number obtained in step B on step C.

  This step is confusing and incorrect in the standard (r−1)'s complement subtraction process. Step (B) applies when you have a positive result (after adding the end carry), and step (C) applies when you have a negative result (and you take the complement to find the magnitude). Taking the complement of the result from step (B) (a positive number) is not part of finding the difference M-N. Similarly, step (C) already involves taking the complement to find the magnitude of a negative result; performing another complement based on some combination of step B and C is not the correct procedure.

  This step is not a valid part of the standard (r−1)'s complement subtraction method.

Applying the Steps: Two Cases in (r-1)'s Complement

Based on the analysis, the process flows from step (A), and then either step (B) or step (C) is applied depending on the outcome of (A).

Case 1: \( M \ge N \) (Result is positive)

1. Perform Step (A): Add M to the (r−1)'s complement of N.
2. An end carry occurs.
3. Perform Step (B): Add the end carry (1) to the sum obtained in step (A). This gives the correct positive result.

Case 2: \( M < N \) (Result is negative)

1. Perform Step (A): Add M to the (r−1)'s complement of N.
2. No end carry occurs.
3. Perform Step (C): Take the (r−1)'s complement of the sum obtained in step (A) and place a negative sign in front. This gives the correct negative result.

Step (D) is not used in either case.

Identifying the Correct Steps for Subtraction

The steps involved in the (r−1)'s complement method for subtracting M−N are primarily step (A), followed by either step (B) or step (C), depending on the end carry. Step (D) is not a standard or correct procedure within this method.

Therefore, the correct steps described in the options that are part of the (r−1)'s complement subtraction method are (A), (B), and (C).

Conclusion on Steps for (r-1)'s Complement

The correct steps that constitute the (r−1)'s complement method for subtracting two positive numbers are those described in (A), (B), and (C). Step (D) is not part of this standard procedure.

Revision Table: (r-1)'s Complement Subtraction

Additional Information: Related Concepts in Computer Arithmetic

Understanding (r−1)'s complement is essential in computer arithmetic and digital logic. It's closely related to other complement systems:

• r's Complement: Another system for subtraction and negative number representation. For base r, it's \(r^n - N\). Subtraction M − N is \(M + (\text{r's complement of } N)\). If an end carry occurs, it is simply discarded. If no end carry occurs, the result is negative, and the sum from the addition is the r's complement of the magnitude. r's complement is generally preferred in systems because it avoids the end-around carry step required by (r−1)'s complement.
• 1's Complement (for Binary): This is the (r−1)'s complement when r=2. It's found by inverting all bits (0 becomes 1, 1 becomes 0).
• 2's Complement (for Binary): This is the r's complement when r=2. It's found by taking the 1's complement and adding 1 to the least significant bit. 2's complement is the most widely used method for signed number representation and arithmetic in modern computers because it has only one representation for zero and simplifies addition/subtraction logic.

Both (r−1)'s complement and r's complement provide ways to perform subtraction using addition circuits, which is a key concept in the design of Arithmetic Logic Units (ALUs).