01 Chapter 1 - Number Systems & Arithmetic (Merged)

Chapter 1: Number Systems & Arithmetic - Complete Study Notes

NotebookLM Ingestion Compilation

This merged document contains all 3 study notes for Chapter 1: Number Systems & Arithmetic from ECE 2103 Digital Electronics (Sharif Sir).

---

Related Concepts: 02 Base Complements & Non-Decimal Arithmetic | 03 The 8-Bit Two’s Complement Problem | 01 BCD & Weighted Digital Codes

1.01 Advanced Base Conversions

Concept Overview: Base Conversions

Converting a number from decimal to any target base {radix $r$} requires splitting the number into two distinct components: the integer part and the fractional part.

• Integer Part: Computed via successive division by the target base $r$, recording the remainders from bottom (MSB) to top (LSB).
• Fractional Part: Computed via successive multiplication by the target base $r$, recording the integer carries generated from top to bottom.

graph TD
    Input[Decimal Number N] --> Split{Split Number}
    
    Split -->|Integer Part| IntDiv[Successive Division by Base r]
    IntDiv --> CollectRem[Collect Remainders Bottom to Top MSB to LSB]
    
    Split -->|Fractional Part| FracMult[Successive Multiplication by Base r]
    FracMult --> CollectInt[Collect Integer Carries Top to Bottom]
    
    CollectRem & CollectInt --> Combine[Combined Base-r Result]

---

1. Decimal to “Unusual” Bases (Base-3, Base-4, Base-7, Base-12)

While standard conversions to binary, octal, and hexadecimal are common, term exams heavily test conversions to non-standard bases {such as base-3, base-4, base-7, and base-12}.

Major Exam Problem: Convert $249.6_{10}$ to Base-4 and Base-7 (2015, 2016, 2022, 2023, 2025)

Part A: Converting $249.6_{10}$ to Base-4

Step 1: Integer Part ($249_{10}$) — Successive Division by 4

• $249÷4=62\text{remainder }1\text{(LSB)}$
• $62÷4=15\text{remainder }2$
• $15÷4=3\text{remainder }3$
• $3÷4=0\text{remainder }3\text{(MSB)}$

$\text{Integer Result: }(3321{)}_4$

Step 2: Fractional Part ($0.6_{10}$) — Successive Multiplication by 4

• $0.6\times 4=2.4\to \text{integer }2$
• $0.4\times 4=1.6\to \text{integer }1$
• $0.6\times 4=2.4\to \text{integer }2$
• $0.4\times 4=1.6\to \text{integer }1$

$\text{Fractional Result: }(.2121\dots {)}_4$

$\text{Final Base-4 Result: }(3321.2121\dots {)}_4$

---

Part B: Converting $249.6_{10}$ to Base-7

Step 1: Integer Part ($249_{10}$) — Successive Division by 7

• $249÷7=35\text{remainder }4\text{(LSB)}$
• $35÷7=5\text{remainder }0$
• $5÷7=0\text{remainder }5\text{(MSB)}$

$\text{Integer Result: }(504{)}_7$

Step 2: Fractional Part ($0.6_{10}$) — Successive Multiplication by 7

• $0.6\times 7=4.2\to \text{integer }4$
• $0.2\times 7=1.4\to \text{integer }1$
• $0.4\times 7=2.8\to \text{integer }2$
• $0.8\times 7=5.6\to \text{integer }5$

$\text{Fractional Result: }(.4125\dots {)}_7$

$\text{Final Base-7 Result: }(504.4125\dots {)}_7$

---

2. Hexadecimal Fractions to Decimal, Octal, and Binary

Converting between Hexadecimal ($2^4=16$), Octal ($2^3=8$), and Binary ($2^1=2$) is accomplished by grouping binary bit patterns directly.

Major Exam Problem: Convert $2AC5.D_{16}$ to Binary, Octal, and Decimal (2015, 2017, 2025)

graph LR
    Hex[Hexadecimal 2AC5.D] -->|4-Bit Expansion| Binary[Binary 0010 1010 1100 0101 . 1101]
    Binary -->|3-Bit Grouping| Octal[Octal 25305.64]
    Hex -->|Polynomial Expansion| Decimal[Decimal 10949.8125]

Step 1: Hexadecimal to Binary (4-Bit Expansion)

Expand each Hex digit into its 4-bit binary equivalent using positional weights ($8,4,2,1$):

• $2_{16}=0010_2$
• $A_{16}(10_{10})=1010_2$
• $C_{16}(12_{10})=1100_2$
• $5_{16}=0101_2$
• $D_{16}(13_{10})=1101_2$

$\text{Binary Result: }(0010101011000101.1101{)}_2$

Step 2: Binary to Octal (3-Bit Grouping)

Group the binary bits into 3-bit clusters starting outward from the binary point:

• Integer Grouping (Left of point): $(010)(101)(011)(000)(101)⟹25305$
• Fractional Grouping (Right of point): $(110)(100)⟹.64\text{*(padded with two zeros at the end)*}$

$\text{Octal Result: }(25305.64{)}_8$

Step 3: Hexadecimal to Decimal (Polynomial Expansion)

Multiply each digit by its positional weight ($16^k$): $=(2\times 16^3)+(10\times 16^2)+(12\times 16^1)+(5\times 16^0)+(13\times 16^{-1})$ $=2(4096)+10(256)+12(16)+5(1)+13(0.0625)$ $=8192+2560+192+5+0.8125$

$\text{Decimal Result: }(10949.8125{)}_{10}$

---

3. Fractional Binary Equivalence & Precision Analysis

Major Exam Word Problem: The "2/3" Fraction Analysis (2021, 2023)

Question: Calculate the binary equivalent of $2/3$ out to eight places. Convert the binary result back to decimal. How close is the result to $2/3$? Convert the binary result into hexadecimal, then convert that result to decimal. Is the answer the same?

Solution:

Part A: Binary Equivalent of $2/3$ to 8 Places

Decimal $2/3\approx 0.6666\dots$ Multiply the fraction $2/3$ by $2$ successively:

1. $\frac{2}{3}\times 2=\frac{4}{3}=1+\frac{1}{3}⟹a_{-1}=1$
2. $\frac{1}{3}\times 2=\frac{2}{3}=0+\frac{2}{3}⟹a_{-2}=0$
3. $\frac{2}{3}\times 2=\frac{4}{3}=1+\frac{1}{3}⟹a_{-3}=1$
4. $\frac{1}{3}\times 2=\frac{2}{3}=0+\frac{2}{3}⟹a_{-4}=0$

$\text{8-Bit Binary Fraction: }(0.10101010{)}_2$

Part B: Convert Binary back to Decimal & Quantify Error

$0.10101010_2=(1\times 2^{-1})+(0\times 2^{-2})+(1\times 2^{-3})+(0\times 2^{-4})+(1\times 2^{-5})+(0\times 2^{-6})+(1\times 2^{-7})+(0\times 2^{-8})$ $=\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\frac{1}{128}=0.5+0.125+0.03125+0.0078125=0.6640625_{10}$

• Precision Loss (Error Calculation): $\text{Exact Value}-\text{Approximated Value}=0.666666\cdots -0.6640625=\mathrm{0.00260416...}$

Part C: Convert Binary to Hexadecimal & Back to Decimal

• Group the 8-bit binary fraction into 4-bit nibbles: $(0.10101010{)}_2⟹(0.AA{)}_{16}\text{*(since }1010_2=10_{10}=A_{16}\text{)}$

• Convert Hexadecimal $(0.AA{)}_{16}$ to Decimal: $=(10\times 16^{-1})+(10\times 16^{-2})=\frac{10}{16}+\frac{10}{256}=0.625+0.0390625=0.6640625_{10}$

• Conclusion: Yes, the converted decimal answer ($0.6640625_{10}$) is identical! $■$

---

Past Year Questions (PYQs)

• [PYQ 2015, 2016, 2022, 2023, 2025]: Convert integer/fraction decimals to base-3, base-4, base-7, base-12.
• [PYQ 2015, 2017, 2025]: Convert hexadecimal with fractions to decimal, octal, binary.
• [PYQ 2021, 2023]: Calculate binary equivalent of fractions (e.g., $2/3$ out to 8 places) and verify accuracy through hex conversions.

---

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 base $r$, two types of complements exist:

1. Radix Complement ($r$‘s complement): In binary ($r=2$), this is the 2’s Complement {formed by taking the 1’s complement and adding 1 to the LSB}.
2. Diminished Radix Complement ($(r-1)$‘s complement): In binary ($r=2$), this is the 1’s Complement {formed by bitwise inversion: $0\to 1,1\to 0$}.

---

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. --- <!-- START OF NOTE: 1.03 The 8-Bit Two's Complement Problem.md --> **Related Concepts:** [[02 Base Complements & Non-Decimal Arithmetic]] | [[01 Advanced Base Conversions]] | [[04 Error Control, Parity Generators & Checkers]] # 1.03 The 8-Bit Two's Complement Problem > [!abstract] Concept Overview: Signed Binary Systems > > In computer hardware, there are no physical plus ($+$) or minus ($-$) signs. Signed numbers are represented by setting the **Most Significant Bit (MSB)** as the sign bit: > * **`0` in the MSB** = Positive Number. > * **`1` in the MSB** = Negative Number. > > The **Signed 2's Complement System** is the universal standard for computer arithmetic because subtraction is executed by adding the 2's complement of the subtrahend: > $$ (\pm A) - (+B) = (\pm A) + (-B) $$ > $$ (\pm A) - (-B) = (\pm A) + (+B) $$ ```mermaid graph TD Setup[Step 0: Setup Phase] --> DefineA[Define +A in 8-bit True Binary] Setup --> DefineNegA[Define -A via 2's Comp of +A] Setup --> DefineB[Define +B or -B in 8-bit Format] Setup --> DefineNegB[Define -B via 2's Comp of +B] DefineA & DefineNegA & DefineB & DefineNegB --> Addition[Perform 8-bit ADDITION ONLY] Addition --> CarryCheck{9th Bit Carry Generated?} CarryCheck -->|Yes| Discard[Discard 9th Bit] CarryCheck -->|No| CheckMSB Discard --> CheckMSB{Check 8th Bit MSB} CheckMSB -->|MSB = 0| PosResult[Result is Positive -> Convert Directly to Decimal] CheckMSB -->|MSB = 1| NegResult[Result is Negative -> Take 2's Comp of Sum and Add - Sign] ``` --- ## 1. The Pre-Calculation Setup Methodology > [!example] Major Exam Problem: Computer Arithmetic ($A = +25_{10}$, $B = -48_{10}$) (2016, 2017, 2020, 2021, 2025 - 13 Marks) > ### Step 0: Pre-Calculation Operand Setup Before computing the four cases ($A+B, A-B, B-A, -A-B$), express all four required terms ($A, -A, B, -B$) in clean 8-bit 2's complement notation: 1. **Magnitudes in 8-bit Binary:** * $|25_{10}| = 00011001_2$ * $|48_{10}| = 00110000_2$ 2. **Determining the 4 Operands:** * **$A = +25_{10} \implies \mathbf{00011001_2}$** *(MSB = 0, positive)* * **$-A = -25_{10} \implies$** Take 2's comp of $+25$: $$\text{1's comp} = 11100110_2 \implies \text{2's comp} = \mathbf{11100111_2}$$ * **$B = -48_{10} \implies$** Take 2's comp of $+48$: $$\text{1's comp} = 11001111_2 \implies \text{2's comp} = \mathbf{11010000_2}$$ * **$-B = -(-48_{10}) = +48_{10} \implies \mathbf{00110000_2}$** *(MSB = 0, positive)* --- ## 2. Step-by-Step Solution for the 4 Arithmetic Cases > [!important] Output Evaluation Rules > > 1. **Discard 9th Bit:** Any carry produced past the 8th bit *{sign bit}* is discarded. > 2. **MSB Interpretation:** > * **MSB = 0:** Result is **positive**. Convert directly from binary to decimal. > * **MSB = 1:** Result is **negative**. Take the 2's complement of the sum to find magnitude, then attach a negative sign. ### Case 1: Compute $A + B$ $$\text{Add } A \ (00011001_2) + B \ (11010000_2):$$ $$\begin{array}{r@{\quad}l} 00011001_2 \quad (+25) \\ + 11010000_2 \quad (-48) \\ \hline \mathbf{11101001_2} \end{array}$$ * **Evaluation:** No 9th bit. MSB is **1** $\implies$ Result is **negative**. * **Magnitude:** Take 2's complement of $11101001_2$: $$\text{1's comp} = 00010110_2 \implies \text{2's comp} = 00010111_2 \quad (23_{10})$$ $$\mathbf{\text{Final Answer: } -23_{10}} \quad \text{*(Verification: } 25 + (-48) = -23\text{*)}$$ --- ### Case 2: Compute $A - B$ Express as $A + (-B) \implies \text{Add } A \ (00011001_2) + (-B) \ (00110000_2)$: $$\begin{array}{r@{\quad}l} 00011001_2 \quad (+25) \\ + 00110000_2 \quad (+48) \\ \hline \mathbf{01001001_2} \end{array}$$ * **Evaluation:** MSB is **0** $\implies$ Result is **positive**. * **Magnitude:** Direct conversion: $01001001_2 = 64 + 8 + 1 = 73_{10}$. $$\mathbf{\text{Final Answer: } +73_{10}} \quad \text{*(Verification: } 25 - (-48) = 73\text{*)}$$ --- ### Case 3: Compute $B - A$ Express as $B + (-A) \implies \text{Add } B \ (11010000_2) + (-A) \ (11100111_2)$: $$\begin{array}{r@{\quad}l} 11010000_2 \quad (-48) \\ + 11100111_2 \quad (-25) \\ \hline (1)\ \mathbf{10110111_2} \end{array}$$ * **Evaluation:** 9th bit carry generated $\implies$ **Discard 9th bit**. * Remaining 8-bit sum is $10110111_2$. MSB is **1** $\implies$ Result is **negative**. * **Magnitude:** Take 2's complement of $10110111_2$: $$\text{1's comp} = 01001000_2 \implies \text{2's comp} = 01001001_2 \quad (73_{10})$$ $$\mathbf{\text{Final Answer: } -73_{10}} \quad \text{*(Verification: } -48 - 25 = -73\text{*)}$$ --- ### Case 4: Compute $-A - B$ Express as $(-A) + (-B) \implies \text{Add } (-A) \ (11100111_2) + (-B) \ (00110000_2)$: $$\begin{array}{r@{\quad}l} 11100111_2 \quad (-25) \\ + 00110000_2 \quad (+48) \\ \hline (1)\ \mathbf{00010111_2} \end{array}$$ * **Evaluation:** 9th bit carry generated $\implies$ **Discard 9th bit**. * Remaining 8-bit sum is $00010111_2$. MSB is **0** $\implies$ Result is **positive**. * **Magnitude:** Direct conversion: $00010111_2 = 16 + 4 + 2 + 1 = 23_{10}$. $$\mathbf{\text{Final Answer: } +23_{10}} \quad \text{*(Verification: } -25 - (-48) = 23\text{*)} \quad \blacksquare$$ --- ## 3. Arithmetic Overflow Detection Rules > [!warning] Hardware Overflow Conditions > > An 8-bit signed system can only represent numbers in the range **$-128$ to $+127$**. If an operation produces a value outside this range, an **Overflow** occurs. > > **Detection Rules:** > 1. Adding two **positive** numbers ($MSB_1 = 0, MSB_2 = 0$) yields a **negative** sum ($MSB_{sum} = 1$). > 2. Adding two **negative** numbers ($MSB_1 = 1, MSB_2 = 1$) yields a **positive** sum ($MSB_{sum} = 0$). > 3. *Note:* Adding numbers of opposite signs can **never** cause an overflow. --- > [!question] Past Year Questions (PYQs) > > * **[PYQ 2016, 2017, 2020, 2021, 2025]:** Given integer variables $A = (25)_{10}$ and $B = -(48)_{10}$ (or $A=25, B=-46$), show how an 8-bit two's complement computer computes $A+B$, $A-B$, $B-A$, and $-A-B$. (12 to 13 Marks) ---