Digital systems process data in binary (r=2), but human interfaces use decimal (r=10). Practical interfaces also employ octal (r=8) and hexadecimal (r=16) to condense long binary strings. Understanding the mathematical foundations of positional notation and conversion algorithms is essential for digital logic design.
1. Positional Radix r Number Theory
A positional number system represents numbers by a sequence of digits. The position of each digit determines its weight, which is a power of the base (or radix) r.
1.1 The Positional Expansion Theorem
Mathematical Definition
Any real number N in a base r positional number system is represented as:
N=(an−1an−2…a1a0⋅a−1a−2…a−m)r
Where:
The dot (⋅) represents the radix point (decimal point in base 10, binary point in base 2).
n is the number of integer digits, and m is the number of fractional digits.
The digits/coefficients ai must satisfy:
0≤ai<r
The quantitative decimal value of N is obtained by summing each digit multiplied by its position weight:
For example, in decimal (r=10), digits are {0,1,…,9}. In binary (r=2), digits are strictly {0,1}. In hexadecimal (r=16), the alphanumeric symbols {0−9,A−F} represent decimal values {0−15}.
2. Base Conversion Mechanics (Pencil-and-Paper Tutorial)
When converting numbers from decimal (base 10) to a target base r, the conversion is split into two distinct algorithms for the integer and fractional components.
graph TD
Input["Decimal Number N"] --> Split{"Split into Components"}
Split -->|Integer Component| IntDiv["Successive Division by Base r"]
IntDiv --> CollectRem["Collect Remainders Bottom to Top (MSB to LSB)"]
Split -->|Fractional Component| FracMult["Successive Multiplication by Base r"]
FracMult --> CollectInt["Collect Integer Carries Top to Bottom (MSB to LSB)"]
CollectRem & CollectInt --> Combine["Combined Base-r Result"]
Part A: Converting Integers (Successive Division Method)
To convert a decimal integer to a target base r:
Divide the decimal number by the target radix r.
Record the remainder (this becomes a digit of the result, starting from the Least Significant Bit (LSB)).
Take the integer quotient and divide it by r again.
Repeat this process until the quotient becomes 0. The last remainder recorded is the Most Significant Bit (MSB).
Successive Division: Convert 2510 to Binary (r=2)
25÷2=12remainder 1(LSB)
12÷2=6remainder 0
6÷2=3remainder 0
3÷2=1remainder 1
1÷2=0remainder 1(MSB)
Reading the remainders from bottom to top: 110012
Part B: Converting Fractions (Successive Multiplication Method)
To convert a decimal fraction to a target base r:
Multiply the decimal fraction by the target radix r.
Record the integer part of the resulting product (this becomes a digit of the result, starting from the MSB).
Take the remaining fractional part of the product and multiply it by r again.
Repeat until the fractional part becomes 0 (or until you reach the desired bit precision).
Successive Multiplication: Convert 0.62510 to Binary (r=2)
0.625×2=1.25→Record 1(MSB)
0.250×2=0.50→Record 0
0.500×2=1.00→Record 1(LSB, stop)
Reading the integer parts from top to bottom: 0.1012
Part C: Comparison of Conversion Methods
Feature
Successive Division Method
Successive Multiplication Method
Target Component
Integer part of the decimal number.
Fractional part of the decimal number.
Mathematical Operation
Division by target base r.
Multiplication by target base r.
Result Extraction
Remainders of the division.
Integer carries of the multiplication.
Reading Direction
Bottom-to-top (First remainder is LSB, last is MSB).
Top-to-bottom (First carry is MSB, last is LSB).
Termination Condition
Integer quotient becomes 0.
Fractional part becomes 0 or desired precision is met.
Paper-and-pencil binary multiplication and division are foundational mathematical topics required to understand computer arithmetic circuits (like multipliers and dividers in Chapter 5), but they are rarely tested directly as calculation problems in ECE 2103 examinations.
To build arithmetic logic units (ALUs), we must understand paper-and-pencil multiplication and division for unsigned binary numbers.
Unsigned binary multiplication is identical to decimal long multiplication. Since binary digits are only 0 or 1, the partial products are either equal to the multiplicand or zero.
Step-by-Step Algorithm:
Align the multiplicand and multiplier.
For each bit of the multiplier, from Least Significant Bit (LSB) to Most Significant Bit (MSB):
If the multiplier bit is 1, write down the multiplicand as a partial product, shifted left according to the bit position.
If the multiplier bit is 0, write down a row of 0s (or simply shift the next partial product).
Sum all the partial products using binary addition rules.
Unsigned Multiplication: Multiply 1110 by 510 (10112×01012) [Syllabus Week 2]
Binary division is performed using long division, matching the decimal algorithm.
Step-by-Step Algorithm:
Align the divisor with the most significant bits of the dividend.
Compare the divisor with the selected portion of the dividend:
If the dividend portion ≥ divisor, write 1 in the quotient, subtract the divisor from the dividend portion, and bring down the next bit of the dividend.
If the dividend portion < divisor, write 0 in the quotient and bring down the next bit.
Repeat this process until all bits of the dividend are processed.
Unsigned Division: Divide 4510 by 910 (1011012÷10012) [Syllabus Week 2]
000101 (Quotient = 5_10) _________ 1001 | 101101 (Dividend = 45_10) - 1001 (1011 >= 1001 -> Quotient bit = 1, subtract 1001) ------ 00100 (Remainder is 0010; bring down next dividend bit '0') - 00000 (0100 < 1001 -> Quotient bit = 0, subtract 0) ------- 1001 (Remainder is 0100; bring down next dividend bit '1') - 1001 (1001 >= 1001 -> Quotient bit = 1, subtract 1001) ------ 0000 (Remainder = 0; Stop. Result: Quotient = 101_2 = 5_10)
Converting decimal fractions to binary can introduce precision errors (quantization noise), as non-terminating binary fractions must be truncated.
Worked Exam Problem: The "2/3" Fraction Analysis (2021, 2023 - 13 Marks)
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?
Complement arithmetic allows computers to perform subtraction using only addition operations. This eliminates the need for physical subtraction circuitry, enabling a single binary adder circuit to perform both addition and subtraction.
1. Formal Mathematics of Complements
For a positive number N represented in base r with an integer part of n digits and a fractional part of m digits, we define two types of complements.
1.1 The Radix Complement (r‘s Complement)
The radix complement (r‘s complement) of a number N in base r is defined as:
Compr(N)={rn−N0for N=0for N=0
Binary Implementation (2’s Complement, r=2)
For a binary integer (m=0), the 2’s complement of an n-bit number N is 2n−N.
Pencil-and-Paper Shortcut: Starting from the right (Least Significant Bit), copy all bits up to and including the first 1 exactly as they are. Then, invert all remaining bits to the left.
Decimal Implementation (10’s Complement, r=10)
For a decimal integer, the 10’s complement of N is 10n−N.
Pencil-and-Paper Shortcut: Subtract the least significant non-zero digit from 10, and subtract all other digits to the left from 9.
1.2 The Diminished Radix Complement ((r−1)‘s Complement)
The diminished radix complement ((r−1)‘s complement) of a number N in base r is defined as:
Compr−1(N)=rn−r−m−N
If N has no fractional part (m=0), this simplifies to:
Compr−1(N)=rn−1−N
Binary Implementation (1’s Complement, r=2)
For a binary integer, the 1’s complement of N is (2n−1)−N.
Pencil-and-Paper Shortcut: Simply invert every single bit of the binary string (0→1 and 1→0).
Decimal Implementation (9’s Complement, r=10)
For a decimal integer, the 9’s complement of N is (10n−1)−N.
Pencil-and-Paper Shortcut: Subtract each individual digit of the number from 9.
Key Relationship:
Compr(N)=Compr−1(N)+r−m(For integers, r‘s complement is simply the (r−1)‘s complement plus 1 in the LSB position).
1.3 Comparison Table: Radix vs. Diminished Radix Complements
Feature
Radix (r‘s) Complement
Diminished Radix ((r−1)‘s) Complement
Mathematical Definition
rn−N (for N=0)
rn−r−m−N
Binary Equivalent (r=2)
2’s Complement
1’s Complement
Decimal Equivalent (r=10)
10’s Complement
9’s Complement
Mathematical Relationship
r’s Complement = (r−1)‘s Complement +r−m
(r−1)‘s Complement = r‘s Complement −r−m
Ease of Hardware Generation
Slightly harder (requires an addition step +1 in the LSB).
Very easy (requires only inverting NOT gates in binary).
Complement Subtraction Carry Action
Discard overflow carry (Cout=1).
End-Around Carry (add Cout=1 back to LSB).
Representation of Zero in Binary
Single unique representation (0000...0000).
Two representations: +0 (0000...0000) and −0 (1111...1111).
Subtraction of two numbers M−N in base r is executed by adding the complement of the subtrahend (N) to the minuend (M).
graph TD
Sub["Subtraction M - N"] --> Pad["Pad M and N to Equal n-bit Length"]
Pad --> Method{"Complement Type"}
Method -->|r's Complement| Add2["Add M + r's Comp of N"]
Add2 --> Carry2{"Carry generated?"}
Carry2 -->|Yes: Cout = 1| Disc2["Discard Carry. Result is Positive & in True Form"]
Carry2 -->|No: Cout = 0| Neg2["Result is Negative. Take r's Comp of Sum & add - sign"]
Method -->|r-1's Complement| Add1["Add M + (r-1)'s Comp of N"]
Add1 --> Carry1{"Carry generated?"}
Carry1 -->|Yes: Cout = 1| EndAround["End-Around Carry: Add 1 to LSB. Result is Positive"]
Carry1 -->|No: Cout = 0| Neg1["Result is Negative. Take (r-1)'s Comp of Sum & add - sign"]
2.1 The Radix (r‘s) Complement Subtraction Algorithm (M−N)
Pad both M and N with leading zeros so they have the exact same number of digits (n).
Compute the r‘s complement of the subtrahend N: Compr(N)=rn−N.
Add the minuend M to the complement:
Sum=M+(rn−N)=M−N+rn
Check the end carry digit (Cout):
Case A: Carry Occurs (Cout=1)
Discard the carry (which mathematically subtracts rn). The remaining digits represent the correct positive result:
Result=Sum−rn=M−N
Case B: No Carry Occurs (Cout=0)
The result is negative. The remaining digits are in their complemented form. To find the true magnitude, take the r‘s complement of the sum and prefix a negative sign:
Result=−Compr(Sum)=−(rn−(M−N+rn))=−(N−M)
3. Step-by-Step Worked Subtraction Examples
Worked Exam Problem: Perform (100−110000)2 using 1's and 2's Complement, verified by Straight Subtraction (2015, 2018, 2019 - 10 Marks)
Let M=1002 (Decimal 4) and N=1100002 (Decimal 48).
Step 1: Pad to equal bit length (8-bit standard):M=000001002N=001100002
Part A: Subtraction Using 2’s Complement (r‘s complement)
Find 2’s Complement of N (001100002):
1’s complement = 110011112
Add 1 to LSB = 110100002
Add M+2’s Comp of N:
00000100 (M) + 11010000 (2's Comp of N) ---------- 0 11010100 (Sum) ^ Cout = 0 (No Carry)
Evaluate Result:
Since Cout=0, the result is negative and in 2’s complement form.
Take 2’s complement of the sum (110101002):
1’s complement = 001010112
Add 1 to LSB = 001011002 (Decimal 44)
Prefix a negative sign.
Final Result=−001011002(−4410)
Part B: Subtraction Using 1’s Complement ((r−1)‘s complement)
Find 1’s Complement of N (001100002):
1’s complement = 110011112
Add M+1’s Comp of N:
00000100 (M) + 11001111 (1's Comp of N) ---------- 0 11010011 (Sum) ^ Cout = 0 (No Carry)
Evaluate Result:
Since Cout=0, the result is negative.
Take 1’s complement of the sum (110100112):
1’s complement = 001011002 (Decimal 44)
Prefix a negative sign.
Final Result=−001011002(−4410)
Part C: Verification by Straight Subtraction
Since M<N, perform −(N−M) using direct binary borrowing:
Prefixing the negative sign and padding to 8-bit gives −001011002. All three methods yield the same result. ■
4. Non-Decimal Base Multiplication
Performing arithmetic directly in bases other than decimal is a common exam requirement.
Worked Exam Problem: Multiply (367)8×(715)8 directly in Base-8 without converting to Decimal (2024 - 08 Marks)
Direct Octal Arithmetic Rule:
Perform standard digit-by-digit multiplication. When a product exceeds the base (r=8), divide the product by 8. Record the remainder in the current column and carry the quotient to the next column.
Step-by-Step Multiplication:
Multiply (367)8 by 58 (first digit of multiplier):
5×7=3510⟹35÷8=4 with remainder 3 (write 3, carry 4)
5×6=3010+4=3410⟹34÷8=4 with remainder 2 (write 2, carry 4)
5×3=1510+4=1910⟹19÷8=2 with remainder 3 (write 3, carry 2)
First partial product:23238
Multiply (367)8 by 18 (second digit of multiplier):
Second partial product:36708 (shifted left one space)
Multiply (367)8 by 78 (third digit of multiplier):
7×7=4910⟹49÷8=6 with remainder 1 (write 1, carry 6)
7×6=4210+6=4810⟹48÷8=6 with remainder 0 (write 0, carry 6)
7×3=2110+6=2710⟹27÷8=3 with remainder 3 (write 3, carry 3)
Third partial product:3301008 (shifted left two spaces)
Add the partial products in Base-8:
002323 003670 + 330100 -------- 336313
Column 0: 3+0+0=38
Column 1: 2+7+0=910⟹9÷8=1 rem 1 (write 1, carry 1)
Column 2: 3+6+1+1 (carry)=1110⟹11÷8=1 rem 3 (write 3, carry 1)
Column 3: 2+3+0+1 (carry)=68 (write 6)
Column 4: 38 (write 3)
Column 5: 38 (write 3)
Final Product: (336313)8■
Past Year Questions (PYQs)
[PYQ 2015, 2018, 2019]: Subtraction of binary numbers using 1’s and 2’s complement verified by straight subtraction. (10 Marks)
[PYQ 2024]: Direct non-decimal multiplication in base-6 and base-8 without converting to decimal. (08 Marks)
1.03 Signed Representation, Overflow & Two’s Complement
Overview
Since physical circuits cannot store ”+” or ”-” characters, digital systems dedicate the Most Significant Bit (MSB) of a binary word to represent the sign of a number. The universally adopted system for signed integers in computers is the Signed 2’s Complement System.
1. Signed Binary Representations and Ranges
For an n-bit binary word, there are three primary methods used to represent positive and negative integers:
Sign-Magnitude Representation:
The MSB is the sign bit (0 for positive, 1 for negative). The remaining n−1 bits store the absolute magnitude in true binary.
Range:[−(2n−1−1) to +(2n−1−1)]
Drawback: Dual representation of zero (+0 is 000…02 and −0 is 100…02), complicating arithmetic logic.
Signed 1’s Complement Representation:
Positive numbers are identical to Sign-Magnitude. Negative numbers are created by inverting all bits of their positive counterpart.
Range:[−(2n−1−1) to +(2n−1−1)]
Drawback: Still has dual representation of zero (+0=00…02 and −0=11…12).
Signed 2’s Complement Representation:
Positive numbers are written in true binary. Negative numbers are represented by taking the 2’s complement of the positive value.
Range:[−2n−1 to +(2n−1−1)]
Benefit: Unique representation of zero (000…02). It also enables subtraction to be handled by standard addition hardware.
1.1 Differences between Signed Binary Representations
Feature
Sign-Magnitude
Signed 1’s Complement
Signed 2’s Complement
MSB Function
0 = Positive, 1 = Negative
0 = Positive, 1 = Negative
0 = Positive, 1 = Negative
Negative Number Formula
Keep MSB as 1, copy magnitude.
Invert all bits of positive number.
Take 2’s complement of positive number.
Range (for n bits)
[−(2n−1−1) to +(2n−1−1)]
[−(2n−1−1) to +(2n−1−1)]
[−2n−1 to +(2n−1−1)]
Representation of Zero
Two representations: +0 (00...0) and −0 (10...0).
Two representations: +0 (00...0) and −0 (11...1).
One unique representation: 00...0 (always positive).
Hardware Arithmetic Complexity
High. Requires separate addition and subtraction circuits.
Medium. Requires “End-Around Carry” addition.
Low. Single standard adder handles both addition and subtraction.
Mathematical Asymmetry
Symmetric range around zero.
Symmetric range around zero.
Asymmetric. Has one extra negative number (e.g. −8 in 4-bit).
1.2 Comparison Table (n=4 bits)
Decimal
Sign-Magnitude
Signed 1’s Complement
Signed 2’s Complement
+7
0111
0111
0111
+1
0001
0001
0001
+0
0000
0000
0000
−0
1000
1111
(not defined)
−1
1001
1110
1111
−7
1111
1000
1001
−8
(not defined)
(not defined)
1000
2. 8-Bit Signed Arithmetic Tutorial
In an 8-bit computer register, addition and subtraction are handled by standard 8-bit binary addition. Any carry beyond the 8th bit (the sign bit) is discarded.
graph TD
Start["Setup Operands"] --> trueA["Write +A in 8-bit Binary"]
Start --> trueB["Write +B in 8-bit Binary"]
trueA --> compA["Find -A (2's Comp of +A)"]
trueB --> compB["Find -B (2's Comp of +B)"]
compA & compB & trueA & trueB --> Add["Perform 8-bit Addition Only"]
Add --> Carry{"Carry-out from 8th bit?"}
Carry -->|Yes| Disc["Discard Carry"]
Carry -->|No| Check["Check MSB of Sum"]
Disc --> Check
Check -->|MSB = 0| Pos["Result is Positive. Convert directly to Decimal"]
Check -->|MSB = 1| Neg["Result is Negative. Take 2's Comp to read magnitude"]
Worked Exam Problem: Signed Arithmetic (2016, 2017, 2020, 2021, 2025 - 13 Marks)
Question: Given the decimal integers A=25 and B=−48, show how an 8-bit signed 2’s complement computer computes:
(i) A+B, (ii) A−B, (iii) B−A, and (iv) −A−B.
Step 0: Pre-Calculation Operand Setup
Convert the absolute magnitudes to 8-bit binary first:
∣2510∣=000110012
∣4810∣=001100002
Now write the four required operands:
A=+2510⟹000110012
−A=−2510⟹2’s Comp of +25=111001112
B=−4810⟹2’s Comp of +48=110100002
−B=+4810⟹001100002
Case 1: Compute A+B (i.e. 25+(−48))
00011001_2 \quad (+25) \\
+ 11010000_2 \quad (-48) \\
\hline
11101001_2
\end{array}$$
- **Evaluation:** No end carry. The MSB is `1`, indicating a **negative** result.
- **Find Magnitude:** Take the 2's complement of the sum $11101001_2$:
- 1's complement = $00010110_2$
- Add 1 = $00010111_2$ ($23_{10}$)
- **Answer:** **$-23_{10}$** (Verifies: $25 - 48 = -23$).
---
### Case 2: Compute $A - B$ (i.e. $25 - (-48) = 25 + 48$)
$$\begin{array}{r@{\quad}l}
00011001_2 \quad (+25) \\
+ 00110000_2 \quad (+48) \\
\hline
01001001_2
\end{array}$$
- **Evaluation:** No end carry. The MSB is `0`, indicating a **positive** result.
- **Find Magnitude:** Convert $01001001_2$ directly to decimal:
- $64 + 8 + 1 = 73_{10}$
- **Answer:** **$+73_{10}$** (Verifies: $25 - (-48) = 73$).
---
### Case 3: Compute $B - A$ (i.e. $-48 - 25$)
$$\begin{array}{r@{\quad}l}
11010000_2 \quad (-48) \\
+ 11100111_2 \quad (-25) \\
\hline
(1)\ 10110111_2
\end{array}$$
- **Evaluation:** Carry occurs. Discard the end carry.
- The remaining 8-bit sum is $10110111_2$. MSB is `1` $\implies$ **negative** result.
- **Find Magnitude:** Take the 2's complement of $10110111_2$:
- 1's complement = $01001000_2$
- Add 1 = $01001001_2$ ($73_{10}$)
- **Answer:** **$-73_{10}$** (Verifies: $-48 - 25 = -73$).
---
### Case 4: Compute $-A - B$ (i.e. $-25 - (-48) = -25 + 48$)
$$\begin{array}{r@{\quad}l}
11100111_2 \quad (-25) \\
+ 00110000_2 \quad (+48) \\
\hline
(1)\ 00010111_2
\end{array}$$
- **Evaluation:** Carry occurs. Discard the end carry.
- The remaining 8-bit sum is $00010111_2$. MSB is `0` $\implies$ **positive** result.
- **Find Magnitude:** Convert $00010111_2$ directly to decimal:
- $16 + 4 + 2 + 1 = 23_{10}$
- **Answer:** **$+23_{10}$** (Verifies: $-25 + 48 = 23$). $\blacksquare$
---
## 3. Arithmetic Overflow Conditions
When performing signed arithmetic inside an $n$-bit register, the result can exceed the range of representable values:
$$\text{Range Limit} = [-2^{n-1} \quad \text{to} \quad +2^{n-1}-1]$$
For an 8-bit system, the valid range is **$-128$ to $+127$**. If the true algebraic sum of two numbers falls outside this range, an **Overflow** occurs, corrupting the sign bit.
### 3.1 The Sign-Bit Check Rule
Overflow can **only** occur when adding numbers of the same sign:
1. Adding two positive numbers yields a negative result:
$$(+X) + (+Y) = -Z \implies \text{Overflow}$$
2. Adding two negative numbers yields a positive result:
$$(-X) + (-Y) = +Z \implies \text{Overflow}$$
> [!note] Why Adding Opposite Signs Never Causes Overflow
>
> For an 8-bit signed system:
> - Positive range: $[0 \text{ to } +127]$
> - Negative range: $[-1 \text{ to } -128]$
>
> Adding any positive $X$ to negative $Y$ is bounded by:
> - Maximum possible sum: $(+127) + (-1) = +126$ (safe)
> - Minimum possible sum: $(0) + (-128) = -128$ (safe)
>
> The result is mathematically guaranteed to remain within the $[-128, +127]$ range, making overflow physically impossible.
---
### 3.2 ALU Hardware Detection of Overflow
In the Arithmetic Logic Unit (ALU), overflow ($V$) is detected instantly by monitoring the carry bits of the sign-bit position (MSB) using a single XOR gate.
```text
Carry-out (Cout)
^
|
+----+----+
| XOR Gate| ----> Overflow Flag (V = Cin ⊕ Cout)
+----+----+
^
|
Operand A --->| (MSB)
Operand B --->| (MSB)
|
^
Carry-in (Cin)
```
> [!abstract] Overflow Logic Equation
>
>
> $$\mathbf{V = C_{in} \oplus C_{out}}$$
>
> Where:
> * $C_{in}$ is the carry-in to the sign-bit position (the carry from column $n-2$ to the MSB column $n-1$).
> * $C_{out}$ is the carry-out from the sign-bit position (the final carry beyond the MSB).
> * If **$V = 1$**, the sign of the result is incorrect, indicating an **Overflow Error**.
---
> [!question] Past Year Questions (PYQs)
>
> * **[PYQ 2016, 2017, 2020, 2021, 2025]:** Given decimal integers $A = 25$ and $B = -48$, show how an 8-bit two's complement computer computes $A+B$, $A-B$, $B-A$, and $-A-B$. (13 Marks)
---