Related Concepts: 01 Advanced Base Conversions | 03 The 8-Bit Two’s Complement Problem | 04 Error Control, Parity Generators & Checkers

1.02 Base Complements & Non-Decimal Arithmetic

Concept Overview: Complement Arithmetic

Digital hardware utilizes complement arithmetic to eliminate the need for dedicated physical subtractor circuits. By converting subtraction into addition, a single binary adder circuit handles both operations.

For any positive number $N$ represented in base $r$ with an integer part of $n$ digits and a fractional part of $m$ digits, two types of complements are defined:

1. Diminished Radix Complement ($(r-1)$‘s complement): Mathematically defined as: $(r-1)\text{’s Complement}=({\mathbf{r}}^{\mathbf{n}}-{\mathbf{r}}^{-\mathbf{m}})-\mathbf{N}$
   • Binary ($r=2$) with no fraction ($m=0$): $(2^n-1)-N$, which is equivalent to a bitwise NOT operation (1’s complement).
   • Decimal ($r=10$): 9’s complement (subtract each digit from 9).
2. Radix Complement ($r$‘s complement): Mathematically defined as: $r\text{’s Complement}={\mathbf{r}}^{\mathbf{n}}-\mathbf{N}(\text{for }N\ne 0,\text{ and }0\text{ for }N=0)$
   • Note that this is equal to adding $r^{-m}$ (1 to the LSB) to the $(r-1)$‘s complement: $r\text{’s Complement}=(r-1)\text{’s Complement}+r^{-m}$
   • Binary ($r=2$): 2’s complement (1’s complement $+1$ to the LSB).
   • Decimal ($r=10$): 10’s complement (9’s complement $+1$ to the LSB).

---

1. Subtraction Rules using Complements

graph TD
    Sub[Binary Subtraction M - N] --> Pad[Pad M and N to Equal Bit Length]
    Pad --> Method{Choice of Complement}
    
    Method -->|2's Complement| Add2[Add M + 2's Comp of N]
    Add2 --> Carry2{End Carry Occurred?}
    Carry2 -->|Yes| Disc2[Discard Carry -> Result is Positive]
    Carry2 -->|No| Neg2[Result is Negative -> Take 2's Comp of Sum and Prefix -]
    
    Method -->|1's Complement| Add1[Add M + 1's Comp of N]
    Add1 --> Carry1{End Carry Occurred?}
    Carry1 -->|Yes| EndAround[End-Around Carry -> Add 1 to LSB -> Result Positive]
    Carry1 -->|No| Neg1[Result is Negative -> Take 1's Comp of Sum and Prefix -]

A. Subtraction Using 2’s Complement Method

1. Pad minuend ($M$) and subtrahend ($N$) to equal bit length {e.g., 8-bit standard}.
2. Calculate 2’s complement of subtrahend ($N$).
3. Add $M+(\text{2’s comp of }N)$.
4. Evaluate Carry:
   • If End Carry occurs: Discard the carry bit. The remaining sum is positive and in true binary form.
   • If NO End Carry occurs: The result is negative. The sum is in 2’s complement form. Take the 2’s complement of the sum and attach a negative sign ($-$).

B. Subtraction Using 1’s Complement Method

1. Pad $M$ and $N$ to equal bit length.
2. Calculate 1’s complement of subtrahend ($N$).
3. Add $M+(\text{1’s comp of }N)$.
4. Evaluate Carry:
   • If End Carry occurs: Add $1$ to the LSB {End-Around Carry}. The result is positive.
   • If NO End Carry occurs: The result is negative. Take the 1’s complement of the sum and attach a negative sign ($-$).

---

2. PYQ Master Problem: Subtraction Verification

Major Exam Problem: Perform $(100-110000{)}_2$ using 1's & 2's Complement, verified by Straight Subtraction (2015, 2018, 2019)

Let $M=100_2$ (Decimal $4$) and $N=110000_2$ (Decimal $48$). Pad to 8-bit representation:

• $M=00000100_2$
• $N=00110000_2$

Part 1: Subtraction Using 2’s Complement

• $\text{1’s complement of }N=11001111_2$
• $\text{2’s complement of }N=11001111+1=11010000_2$

$\text{Add }M+(\text{2’s comp of }N):$

00000100_2 \\ + 11010000_2 \\ \hline 11010100_2 \end{array}$$ * **Analysis:** No end carry generated $\implies$ Result is **negative**. * **Magnitude:** Take 2's complement of the sum ($11010100_2$): $$\text{1's comp} = 00101011_2 \implies \text{2's comp} = 00101100_2 \quad (44_{10})$$ $$\mathbf{\text{Final Answer: } -00101100_2 \quad (-44_{10})}$$ --- ### Part 2: Subtraction Using 1's Complement * $\text{1's complement of } N = 11001111_2$ $$\text{Add } M + (\text{1's comp of } N):$$ $$\begin{array}{r@{\quad}l} 00000100_2 \\ + 11001111_2 \\ \hline 11010011_2 \end{array}$$ * **Analysis:** No end carry generated $\implies$ Result is **negative**. * **Magnitude:** Take 1's complement of the sum ($11010011_2$): $$\text{1's comp} = 00101100_2 \quad (44_{10})$$ $$\mathbf{\text{Final Answer: } -00101100_2 \quad (-44_{10})}$$ --- ### Part 3: Verification by Straight Subtraction Since $M < N$, perform $-(N - M)$ using direct binary borrowing: $$\begin{array}{r@{\quad}l} 110000_2 \\ -\ 000100_2 \\ \hline 101100_2 \end{array}$$ $$\mathbf{\text{Padded 8-Bit Result: } -00101100_2} \quad \blacksquare$$ --- ## 3. Non-Decimal Base Multiplication > [!example] Major Exam Problem: Multiply $(367)_8 \times (715)_8$ directly in Base-8 without converting to Decimal (2024 - 8 Marks) > * **Rule:** Perform digit-by-digit multiplication. When a product exceeds the base ($r=8$), divide by $8$: the **remainder** is written down, and the **quotient** is carried to the next column. ### Column Step-by-Step Multiplication: 1. **Multiply $(367)_8$ by $5_8$:** * $5 \times 7 = 35_{10} \implies 35 \div 8 = 4 \text{ rem } \mathbf{3} \quad (\text{write } 3, \text{ carry } 4)$ * $5 \times 6 = 30_{10} + 4 = 34_{10} \implies 34 \div 8 = 4 \text{ rem } \mathbf{2} \quad (\text{write } 2, \text{ carry } 4)$ * $5 \times 3 = 15_{10} + 4 = 19_{10} \implies 19 \div 8 = 2 \text{ rem } \mathbf{3} \quad (\text{write } 3, \text{ carry } 2)$ * **Row 1:** $2323_8$ 2. **Multiply $(367)_8$ by $1_8$:** * **Row 2:** $3670_8$ *(shifted left)* 3. **Multiply $(367)_8$ by $7_8$:** * $7 \times 7 = 49_{10} \implies 49 \div 8 = 6 \text{ rem } \mathbf{1} \quad (\text{write } 1, \text{ carry } 6)$ * $7 \times 6 = 42_{10} + 6 = 48_{10} \implies 48 \div 8 = 6 \text{ rem } \mathbf{0} \quad (\text{write } 0, \text{ carry } 6)$ * $7 \times 3 = 21_{10} + 6 = 27_{10} \implies 27 \div 8 = 3 \text{ rem } \mathbf{3} \quad (\text{write } 3, \text{ carry } 3)$ * **Row 3:** $330100_8$ *(shifted 2 spaces left)* 4. **Add Rows in Base-8:** $$\begin{array}{r@{\quad}l} 002323_8 \\ 003670_8 \\ + 330100_8 \\ \hline \mathbf{336313_8} \end{array}$$ $$\mathbf{\text{Final Product: } (336313)_8} \quad \blacksquare$$ --- > [!question] Past Year Questions (PYQs) > > * **[PYQ 2015, 2018, 2019]:** Subtraction of binary numbers using 1's and 2's complement verified by straight subtraction. > * **[PYQ 2024]:** Non-decimal multiplication in base-6 and base-8 without converting to decimal.