# Unit 1: Fundamental Concepts This unit covers the foundational building blocks of digital systems: number systems, data representation, binary arithmetic, binary codes, basic logic gates, and the postulates/theorems of Boolean algebra. --- ## 1. Number Systems and Base Conversions Digital systems process binary data ($0$ and $1$). However, humans use decimal, and programmers often use octal or hexadecimal for brevity. A number system with base (or radix) $r$ uses $r$ unique symbols. | Number System | Radix ($r$) | Allowed Digits / Symbols | Example | | :--- | :--- | :--- | :--- | | **Binary** | $2$ | $0, 1$ | $1011.01_2$ | | **Octal** | $8$ | $0, 1, 2, 3, 4, 5, 6, 7$ | $74.5_8$ | | **Decimal** | $10$ | $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ | $98.6_{10}$ | | **Hexadecimal** | $16$ | $0\text{-}9$, $\text{A}(10), \text{B}(11), \text{C}(12), \text{D}(13), \text{E}(14), \text{F}(15)$ | $3\text{A}.\text{C}_{16}$ | ### 1.1 Base Conversions 1. **Any Base to Decimal**: Sum the digits multiplied by their positional weight $r^i$. $$\text{Value} = \sum_{i=-m}^{n-1} d_i \cdot r^i$$ *Example:* $101.11_2 = (1 \cdot 2^2) + (0 \cdot 2^1) + (1 \cdot 2^0) + (1 \cdot 2^{-1}) + (1 \cdot 2^{-2}) = 4 + 0 + 1 + 0.5 + 0.25 = 5.75_{10}$. 2. **Decimal to Any Base**: - **Integer part**: Successive division by target base $r$, collecting remainders from bottom to top (LSB to MSB). - **Fractional part**: Successive multiplication by target base $r$, collecting integer carries from top to bottom. 3. **Binary $\leftrightarrow$ Octal / Hexadecimal**: Group binary bits in sets of $3$ (for octal) or $4$ (for hex) starting from the radix point, moving left for integers and right for fractions. Pad with zeros if necessary. --- ## 2. Signed Number Representations In digital hardware, negative numbers are represented using binary signs. There are three primary formats for representing signed integers using $n$ bits: ### 2.1 Sign and Magnitude (SM) - **MSB (Most Significant Bit)**: $0$ for positive ($+$), $1$ for negative ($-$). - **Remaining $n-1$ bits**: Represent the absolute magnitude of the number. - **Range**: $-(2^{n-1} - 1)$ to $+(2^{n-1} - 1)$. - **Pitfall**: Dual representation of zero ($+0 = 000...0$, $-0 = 100...0$), which complicates ALU design. ### 2.2 1's Complement Notation - **Positive Numbers**: Same as sign-magnitude with MSB = $0$. - **Negative Numbers**: Obtained by bitwise inverting (NOT operation) all bits of the positive counterpart. - **Range**: $-(2^{n-1} - 1)$ to $+(2^{n-1} - 1)$. - **Pitfall**: Still has dual representation of zero ($+0 = 000...0$, $-0 = 111...1$). ### 2.3 2's Complement Notation (Standard in Modern ALUs) - **Positive Numbers**: Same as sign-magnitude with MSB = $0$. - **Negative Numbers**: Obtained by adding $1$ to the 1's complement of the number: $$\text{2's Complement} = \text{1's Complement} + 1$$ - **Range**: $-2^{n-1}$ to $+(2^{n-1} - 1)$. - **Advantages**: - Unique representation of zero ($000...0$). - Simple subtraction: $A - B$ is computed as $A + (-B)$ using the same adder hardware. | Decimal (for $n=4$) | Sign-Magnitude | 1's Complement | 2's Complement | | :--- | :--- | :--- | :--- | | $+7$ | $0111$ | $0111$ | $0111$ | | $+0$ | $0000$ | $0000$ | $0000$ | | $-0$ | $1000$ | $1111$ | N/A | | $-7$ | $1111$ | $1000$ | $1001$ | | $-8$ | N/A | N/A | $1000$ | --- ## 3. Fixed-Point vs. Floating-Point Representation - **Fixed-Point**: The position of the binary point is pre-determined (usually at the end for integers, or after the MSB for fractions). - Simple hardware, limited range, fixed precision. - **Floating-Point**: Represents numbers as $\pm M \times r^E$, where $M$ is the mantissa, $r$ is the base, and $E$ is the exponent. Standardized by IEEE 754 (Single Precision: 32-bit, Double Precision: 64-bit). - High dynamic range, complex hardware, variable precision. --- ## 4. Binary Codes ### 4.1 Classification of Codes 1. **Weighted Codes**: Each bit position has a specific weight. - *Examples*: BCD (8421), 2421, 84-2-1. 2. **Non-Weighted Codes**: Position has no arithmetic weight. - *Examples*: Excess-3, Gray Code. 3. **Self-Complementing Codes**: A code where the 1's complement of a codeword represents the 9's complement of its decimal digit. - *Examples*: Excess-3, 2421. (Note: 8421 BCD is **not** self-complementing). 4. **Reflected/Unit-Distance Codes**: Only one bit changes between consecutive numbers. - *Example*: Gray Code. Essential for reducing glitches in mechanical shafts and asynchronous transitions. ### 4.2 Gray Code Conversions - **Binary to Gray**: - $G_{n-1} = B_{n-1}$ (Keep MSB) - $G_i = B_{i+1} \oplus B_i$ for $i < n-1$ - **Gray to Binary**: - $B_{n-1} = G_{n-1}$ (Keep MSB) - $B_i = B_{i+1} \oplus G_i$ for $i < n-1$ ### 4.3 BCD Addition Rule If the sum of two BCD digits is greater than $9$ ($1001_2$) or if a carry is generated from the digit position: - Add $6$ ($0110_2$) to that digit group to skip the 6 invalid states ($1010$ to $1111$), and propagate the carry to the next higher digit. --- ## 5. Basic Logic Gates Logic gates are physical electronic devices implementing Boolean functions. ``` AND OR NOT +-----+ +-----+ +---+ A ---| \ A ---\ \ | | | & )--- Y | \ )--- Y A -----| >o|--- Y B ---| / B ---/ / | | +-----+ +-----+ +---+ Y = A • B Y = A + B Y = A' NAND NOR XOR +-----+o +-----+o +---+ A ---| \ A ---\ \ A | \ \ | & )--- Y | \ )--- Y | | )--- Y B ---| / B ---/ / B | / / +-----+o +-----+o +---+ Y = (A • B)' Y = (A + B)' Y = A ⊕ B = AB'+A'B ``` ### 5.1 Universal Gates **NAND** and **NOR** are universal gates because any Boolean expression can be realized using only NAND or only NOR gates. - *Minimum gates for standard functions*: | Target Function | NAND Gate Count | NOR Gate Count | | :--- | :---: | :---: | | **NOT** | $1$ | $1$ | | **AND** | $2$ | $3$ | | **OR** | $3$ | $2$ | | **XOR** | $4$ | $5$ | | **XNOR** | $5$ | $4$ | --- ## 6. Boolean Algebra: Postulates & Theorems Boolean algebra operates on a set $\{0, 1\}$ with operators $+$ (OR), $\cdot$ (AND), and $'$ (NOT). ### 6.1 Huntington's Postulates 1. **Closure**: For any $a, b \in B$, $a+b \in B$ and $a \cdot b \in B$. 2. **Identity**: $a + 0 = a$ and $a \cdot 1 = a$. 3. **Commutative**: $a + b = b + a$ and $a \cdot b = b \cdot a$. 4. **Distributive**: - $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ - $a + (b \cdot c) = (a + b) \cdot (a + c)$ *(Highly tested in exams)* 5. **Complement**: $a + a' = 1$ and $a \cdot a' = 0$. ### 6.2 Key Theorems of Boolean Algebra * **Idempotent Law**: $A + A = A$, $A \cdot A = A$. * **Boundedness (Dominance)**: $A + 1 = 1$, $A \cdot 0 = 0$. * **Involution Law**: $(A')' = A$. * **Absorption Law**: - $A + AB = A$ - $A(A + B) = A$ - $A + A'B = A + B$ *(Simplification powerhouse!)* * **Demorgan's Laws**: - $(A + B)' = A' \cdot B'$ (The complement of a sum is the product of complements) - $(A \cdot B)' = A' + B'$ (The complement of a product is the sum of complements) * **Consensus Theorem**: - $AB + A'C + BC = AB + A'C$ - $(A+B)(A'+C)(B+C) = (A+B)(A'+C)$ - *Proof*: $BC = BC(A+A') = ABC + A'BC$. Substitute this back: $AB + A'C + ABC + A'BC = AB(1+C) + A'C(1+B) = AB + A'C$. * **Shannon's Expansion Theorem**: - $F(A, B, C, ...) = A \cdot F(1, B, C, ...) + A' \cdot F(0, B, C, ...)$ --- ## 7. Exam Tips & Common Pitfalls > [!WARNING] > - **Overflow in 2's Complement**: Arithmetic overflow occurs only when adding two numbers of the same sign and getting a result with the opposite sign. Formally: $V = C_{in} \oplus C_{out}$ at the MSB adder stage. If $V=1$, overflow occurred. > - **Distributive Law Trap**: Students often forget that OR distributes over AND: $A + BC = (A+B)(A+C)$. > - **Consensus Theorem Identification**: Look for three terms, where each of three variables ($A, B, C$) appears twice, and one variable appears in both complemented and uncomplemented forms. The term containing only uncomplemented/complemented counterparts of the other two variables is redundant.