Digital Logic

Pass path: Learn number base conversions and 2’s complement subtraction in Part 1 and Part 2. Top path: Master binary codes (Gray code vs Excess-3) and fractional base conversions in Part 3 and Part 4.

Part 1: Core Concepts (2 Marks)

• ★ Base (Radix) of a Number System: The total number of distinct symbols or digits utilized in that system (Binary: $r=2$, Octal: $r=8$, Decimal: $r=10$, Hexadecimal: $r=16$). A number is evaluated by polynomial expansion: $\sum d_i \times r^i$.
• ★ 2’s Complement of a Binary Number: Obtained by taking the 1’s complement (inverting all bits: $0 \to 1, 1 \to 0$) and adding 1 to the least significant bit (LSB):

  Swipe to see the full formula↔

  $$\text{2's Complement} = \text{1's Complement} + 1$$
• ★ Gray Code (Unit-Distance Code): An unweighted non-arithmetic binary code where consecutive numerical values differ by only a single bit, eliminating multi-bit switching glitches in rotary optical encoders.

Part 2: Structural Frameworks (10 Marks)

1. Binary Subtraction Using 2’s Complement ($M - N$)

When performing subtraction $M - N$ using $n$-bit 2’s complement arithmetic:

1. Express both $M$ and $N$ with the same number of bits ($n$).
2. Compute the 2’s complement of the subtrahend ($N$).
3. Add the 2’s complement of $N$ to the minuend ($M$):

   Swipe to see the full formula↔

   $$\text{Sum} = M + [2^n - N] = M - N + 2^n$$
4. Evaluate the End-Carry Bit:
   • Case 1 (Carry Occurs): If an end-carry of 1 is generated, discard the carry. The result is positive and represented directly in standard binary ($M \ge N$).
   • Case 2 (No Carry): If no end-carry occurs, the result is negative ($M < N$). The true magnitude is obtained by taking the 2’s complement of the resulting sum and appending a negative sign.

Part 3: Distinction Tables

Binary Codes Comparison: BCD (8421) vs. Excess-3 vs. Gray Code

Part 4: Worked Problems & Exam Traps

Solved Ladder: 2’s Complement Subtraction

Problem: Subtract $(23)_{10}$ from $(14)_{10}$ using 8-bit 2’s complement arithmetic.

Step-by-step Solution:

1. Convert to 8-bit binary:
   • Minuend $M = 14 = (00001110)_2$
   • Subtrahend $N = 23 = (00010111)_2$
2. Find 2’s complement of $N$:
   • 1’s complement of $N = 11101000$
   • 2’s complement $= 11101000 + 1 = 11101001$
3. Add $M$ and 2’s complement of $N$:

   Swipe to see the full formula↔

   \begin{array}{r@{\quad}l} & 00001110 \\ + & 11101001 \\ \hline & 11110111 \end{array}
4. End-Carry Evaluation:
   • There is no end-carry $\implies$ The result is negative.
   • Take 2’s complement of $11110111$: 1’s complement $= 00001000$ 2’s complement $= 00001000 + 1 = (00001001)_2 = 9_{10}$
5. Append negative sign: Result is $-9$ (Verifies: $14 - 23 = -9$).

Students lose marks here because when no end-carry occurs, they write down the raw sum as positive instead of taking its 2’s complement to find the negative magnitude.

Binary Complements and Overflow Arithmetic

In $n$-bit signed representation:

• 1’s Complement: Invert every bit ($0 \leftrightarrow 1$).
• 2’s Complement: Take 1’s complement and add $1$.
• Signed Range: For $n$ bits, the range is $[-2^{n-1}, 2^{n-1} - 1]$.
• Arithmetic Overflow: Occurs when adding two numbers of the same sign produces a result of opposite sign. In hardware, overflow is flagged by $V = C_{in} \oplus C_{out}$ at the most significant bit (MSB).