Back to Subject

Practice MCQ

Unit 3 - Notes

ECE249

Unit 3: Introduction to number system and logic gates

1. Number Systems

A number system defines a set of values used to represent quantity.

1.1 Classification of Number Systems

System	Base (Radix)	Symbols Used	Example
Binary	2	0, 1	$(1011)_2$
Octal	8	0, 1, 2, 3, 4, 5, 6, 7	$(75)_8$
Decimal	10	0, 1, 2, 3, 4, 5, 6, 7, 8, 9	$(98)_{10}$
Hexadecimal	16	0-9, A(10), B(11), C(12), D(13), E(14), F(15)	$(1A)_ {16}$

1.2 Number System Conversions

Decimal to Any Base (r)

Integer Part: Perform repeated division by the destination base $r$ and record the remainders. Read remainders from bottom to top.
Fractional Part: Perform repeated multiplication by the destination base $r$ and record the integer part. Read integers from top to bottom.

Example: $(25.625)_{10} \rightarrow (\dots)_2$

Integer (25):
- $25 / 2 = 12$ (rem 1)
- $12 / 2 = 6$ (rem 0)
- $6 / 2 = 3$ (rem 0)
- $3 / 2 = 1$ (rem 1)
- $1 / 2 = 0$ (rem 1) $\rightarrow$ Read up: $11001$
Fraction (0.625):
- $0.625 \times 2 = 1.25$ (Int: 1)
- $0.25 \times 2 = 0.5$ (Int: 0)
- $0.5 \times 2 = 1.0$ (Int: 1) $\rightarrow$ Read down: $.101$
- Result: $(11001.101)_2$

Any Base (r) to Decimal

Use the Positional Weight Method. Sum the product of each digit and its positional weight ( $r^n$ ).

Example: $(1A)_{16} \rightarrow (\dots)_{10}$

$= 1 \times 16^1 + 10 \times 16^0$ (Note: A=10)
$= 16 + 10$
$= 26_{10}$

Binary to Octal / Hexadecimal

Binary to Octal: Group bits in 3s starting from the radix point (L-R for fractions, R-L for integers).
- Ex: $110110_2 \rightarrow (110)(110) \rightarrow 66_8$
Binary to Hex: Group bits in 4s.
- Ex: $110110_2 \rightarrow (0011)(0110) \rightarrow 36_{16}$

2. Binary Codes

2.1 BCD (Binary Coded Decimal / 8421 Code)

Each decimal digit (0-9) is represented by a 4-bit binary group.
Valid codes: 0000 to 1001.
Invalid codes: 1010 to 1111 (10 to 15).
Example: $(25)_{10}$ in BCD is $0010 \space 0101$ . (In pure binary, it is $11001$).

2.2 Excess-3 Code (XS-3)

A non-weighted code.
Derived by adding 3 ( $0011_2$ ) to the BCD code of each digit.
Self-complementing property: The 9's complement of a decimal number can be obtained by inverting the bits of its Excess-3 code.
Example: Convert decimal 4 to XS-3.
- $4 \rightarrow \text{BCD } 0100$
- $0100 + 0011 = 0111$ (XS-3)

2.3 Gray Code (Reflected Code)

Unit Distance Code: Only one bit changes between successive numbers.
Used in rotary encoders and error correction.
Unweighted code.

Binary to Gray Conversion (B to G)

Rule:

Record the MSB (Most Significant Bit) as is.
Add the MSB of binary to the next bit of binary (perform XOR operation).
Continue for all bits.
- $G_n = B_n$ (MSB)
- $G_{n-1} = B_n \oplus B_{n-1}$

Example: Convert Binary $1011$ to Gray

MSB: 1
$1 \oplus 0 = 1$
$0 \oplus 1 = 1$
$1 \oplus 1 = 0$
Result: $1110$ (Gray)

Gray to Binary Conversion (G to B)

Rule:

Record the MSB of Gray as the MSB of Binary.
XOR the previous binary bit calculated with the current Gray bit.
- $B_n = G_n$ (MSB)
- $B_{n-1} = B_n \oplus G_{n-1}$

Example: Convert Gray $1110$ to Binary

MSB: 1
$1 (\text{prev binary}) \oplus 1 (\text{curr gray}) = 0$
$0 (\text{prev binary}) \oplus 1 (\text{curr gray}) = 1$
$1 (\text{prev binary}) \oplus 0 (\text{curr gray}) = 1$
Result: $1011$ (Binary)

3. Complements and Binary Arithmetic

3.1 Types of Complements

1's Complement: Invert every bit (0 becomes 1, 1 becomes 0).
- Ex: $1010 \rightarrow 0101$
2's Complement: 1's Complement + 1.
- Ex: $1010 \rightarrow 0101 + 1 = 0110$

3.2 Binary Arithmetic

Binary Addition Rules

$0 + 0 = 0$
$0 + 1 = 1$
$1 + 0 = 1$
$1 + 1 = 10$ (Sum 0, Carry 1)
$1 + 1 + 1 = 11$ (Sum 1, Carry 1)

Subtraction using 2's Complement

To perform $A - B$ , we perform $A + (2\text{'s complement of } B)$ .

Steps:

Ensure both numbers have the same number of bits (pad with 0s if necessary).
Find the 2's complement of the subtrahend (B).
Add A to the 2's complement of B.
Check for Carry:
- If a carry is generated: The result is Positive. Discard the carry.
- If NO carry is generated: The result is Negative. Take the 2's complement of the sum to get the magnitude and add a negative sign.

Example 1: $7 - 5$ (Result Positive)

$7 = 0111$ , $5 = 0101$
2's comp of 5: $1010 + 1 = 1011$
Add: $0111 + 1011 = \mathbf{1}0010$
Carry generated ($1$). Discard it.
Result: $0010$ ( $+2$ )

Example 2: $5 - 7$ (Result Negative)

$5 = 0101$ , $7 = 0111$
2's comp of 7: $1000 + 1 = 1001$
Add: $0101 + 1001 = 1110$
No carry. Result is negative.
Magnitude = 2's comp of $1110 = 0001 + 1 = 0010$ .
Result: $-0010$ ( $-2$ )

4. Boolean Algebra and Logic Gates

4.1 Basic Logic Gates

Gate	Symbol	Expression	Logic
AND	D-shape	$Y = A \cdot B$	Output high only if all inputs are high.
OR	Curved back	$Y = A + B$	Output high if any input is high.
NOT	Triangle + bubble	$Y = \bar{A}$	Inverter. Output opposite of input.

4.2 Universal Gates

Gates that can implement any Boolean function without using other types of gates.

NAND (NOT-AND):
- Expression: $Y = \overline{A \cdot B}$
- Output is low only if all inputs are high.
NOR (NOT-OR):
- Expression: $Y = \overline{A + B}$
- Output is high only if all inputs are low.

4.3 Special Gates

XOR (Exclusive-OR):
- Expression: $Y = A \oplus B = \bar{A}B + A\bar{B}$
- Output high if inputs are different (odd number of 1s).
XNOR (Exclusive-NOR):
- Expression: $Y = \overline{A \oplus B} = AB + \bar{A}\bar{B}$
- Output high if inputs are the same (Equality detector).

4.4 Boolean Algebra Laws

Identity: $A + 0 = A$ ; $A \cdot 1 = A$
Null: $A + 1 = 1$ ; $A \cdot 0 = 0$
Idempotent: $A + A = A$ ; $A \cdot A = A$
Inverse: $A + \bar{A} = 1$ ; $A \cdot \bar{A} = 0$
Commutative: $A + B = B + A$
Associative: $A + (B + C) = (A + B) + C$
Distributive: $A(B + C) = AB + AC$ ; $A + BC = (A+B)(A+C)$

4.5 De Morgan's Theorems

Used to simplify boolean expressions and convert between NAND/NOR logic.

Theorem 1: The complement of a product is the sum of the complements.
- $\overline{A \cdot B} = \overline{A} + \overline{B}$
Theorem 2: The complement of a sum is the product of the complements.
- $\overline{A + B} = \overline{A} \cdot \overline{B}$

5. SOP and POS Forms

5.1 Sum of Products (SOP)

The expression is a sum (OR) of product (AND) terms.
Canonical SOP: Each product term contains all variables (Minterms).
Minterm ( $m$ ): A product term where variables corresponding to logic 1 are written as $A$ and logic 0 as $\bar{A}$ .
Example: means output is 1 at indices 1 and 3.
- $Y = \bar{A}\bar{B}C + \bar{A}BC$

5.2 Product of Sums (POS)

The expression is a product (AND) of sum (OR) terms.
Canonical POS: Each sum term contains all variables (Maxterms).
Maxterm ( $M$ ): A sum term where variables corresponding to logic 0 are written as $A$ and logic 1 as $\bar{A}$ .
Example: .
- $Y = (A+B+C)(A+\bar{B}+C)$

6. Karnaugh Maps (K-Map)

K-Map is a graphical method to minimize Boolean expressions. It arranges truth table values so that adjacent cells differ by only one bit (Gray Code ordering).

6.1 Structure

2-Variable ( $2^2=4$ cells): Variables A, B.
3-Variable ( $2^3=8$ cells): Variables A, B, C.
4-Variable ( $2^4=16$ cells): Variables A, B, C, D.

4-Variable Cell Numbering (Format AB \ CD):	AB \ CD	00	01	11
00	0	1	3	2
01	4	5	7	6
11	12	13	15	14
10	8	9	11	10

6.2 Grouping Rules

Group adjacent 1s (for SOP) or 0s (for POS).
Group sizes must be powers of 2 (1, 2, 4, 8, 16).
Pair (2): Eliminates 1 variable.
Quad (4): Eliminates 2 variables.
Octet (8): Eliminates 3 variables.
Rolling: The map wraps around (top connects to bottom, left connects to right).
Overlapping: Groups can overlap to create larger groups.

6.3 Don't Care Conditions (X or d)

Input combinations that never occur or where the output doesn't matter.
Can be treated as 1 or 0 to help form larger groups for better simplification.
Do not group 'X's if they don't help cover a '1'.

6.4 Steps to Solve K-Map

Draw the grid based on the number of variables.
Fill the cells with 1s (for SOP) based on the minterms given.
Fill 'X' for don't cares.
Form the largest possible groups of 1s (using X if helpful).
Write the simplified expression for each group (write the variables that do not change state within the group).
Sum the expressions.

Example (SOP):
Given $Y = \sum m(0, 1, 4, 5, 12)$ for 4 variables ( $A,B,C,D$ ).

Cells 0, 1, 4, 5 form a Quad. Variables constant: $\bar{A}\bar{C}$ .
Cell 12 ($1100$) stands alone? No, combine with 4 ($0100$). Pair: $B\bar{C}\bar{D}$ .
Better yet, if 8 and 13 are not used, check for corners or edges.
Assuming standard grouping: Quad (0,1,4,5) is $\bar{A}\bar{C}$ . Pair (4, 12) is $B\bar{C}\bar{D}$ .
Simplified: $Y = \bar{A}\bar{C} + B\bar{C}\bar{D}$ .