Number systems, codes and Boolean algebra notes — Unit 1

The physical world operates on analog signals, but modern computers process digital signals. Understanding the difference is the first step in digital logic.

⇒1.1 Analog Signals

Analog signals are continuous in both time and amplitude. They can take an infinite number of values within a given range.

• Examples: Temperature variations, human voice, a mercury thermometer.
• Drawbacks: Highly susceptible to noise and degradation over long distances. Hard to store accurately.

⇒1.2 Digital Signals

Digital signals are discrete in both time and amplitude. They only take specific, finite values (usually just two: High and Low, or 1 and 0).

• Examples: Data in a computer's RAM, a digital watch.
• Advantages: Immune to noise (a slightly degraded '1' is still read as a '1'). Easy to store, copy, and process perfectly.

A number system defines how numbers are represented using a set of distinct symbols. The number of distinct symbols is called the Base or Radix ($r$).

⇒2.1 Positional Number Systems

In a positional system, the value of a digit depends on its position. A number $N$ is represented as:

$N = d_n r^n + d_{n-1} r^{n-1} + \dots + d_1 r^1 + d_0 r^0 + d_{-1} r^{-1} + \dots$

⇒2.2 Common Number Systems in Computing

• Decimal (Base-10): Symbols: 0 to 9. Used by humans.
• Binary (Base-2): Symbols: 0, 1. Used by digital hardware because it perfectly maps to ON/OFF transistor states.
• Octal (Base-8): Symbols: 0 to 7. Used as a shorthand for binary (groups of 3 bits).
• Hexadecimal (Base-16): Symbols: 0-9, A-F (where A=10, F=15). Used as a more compact shorthand for binary (groups of 4 bits), heavily used in memory addresses and color codes.

To convert a number from any base $r$ to Decimal (Base-10), we use the Polynomial Expansion Method (multiplying each digit by its positional weight).

⇒3.1 Binary to Decimal

Convert $(1011.01)_2$ to Decimal:

• $= 1 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 + 0 \cdot 2^{-1} + 1 \cdot 2^{-2}$
• $= 8 + 0 + 2 + 1 + 0 + 0.25$
• $= (11.25)_{10}$

⇒3.2 Hexadecimal to Decimal

Convert $(1A3)_{16}$ to Decimal:

• $= 1 \cdot 16^2 + 10 \cdot 16^1 + 3 \cdot 16^0$
• $= 256 + 160 + 3$
• $= (419)_{10}$

To convert from Decimal (Base-10) to any other base $r$, we use the Repeated Division Method for the integer part and the Repeated Multiplication Method for the fractional part.

⇒4.1 Decimal to Binary (Integer part)

Convert $(13)_{10}$ to Binary:

• 13 ÷ 2 = 6, Remainder = 1 (LSB - Least Significant Bit)
• 6 ÷ 2 = 3, Remainder = 0
• 3 ÷ 2 = 1, Remainder = 1
• 1 ÷ 2 = 0, Remainder = 1 (MSB - Most Significant Bit)

Read remainders from bottom to top: $(1101)_2$.

⇒4.2 Decimal to Binary (Fractional part)

Convert $(0.625)_{10}$ to Binary:

• 0.625 × 2 = 1.25 (Record integer part 1)
• 0.25 × 2 = 0.50 (Record integer part 0)
• 0.50 × 2 = 1.00 (Record integer part 1. Since fractional part is 0, stop).

Read integers from top to bottom: $(0.101)_2$.

Because 8 ($2^3$) and 16 ($2^4$) are powers of 2, conversions between Binary, Octal, and Hexadecimal do not require going through Decimal. We use direct grouping.

⇒5.1 Binary to Octal

Group bits into sets of 3, starting from the binary point. Pad with leading/trailing zeros if necessary.

$(11010.11)_2$ $\to$ Grouping: `011` `010` . `110` $\to$ Convert each group: $(32.6)_8$.

⇒5.2 Binary to Hexadecimal

Group bits into sets of 4, starting from the binary point.

$(1101011.1)_2$ $\to$ Grouping: `0110` `1011` . `1000` $\to$ Convert: $(6B.8)_{16}$.

⇒5.3 Octal ↔ Hexadecimal

The easiest way is to convert Octal to Binary first, regroup the bits into 4s, and then convert to Hexadecimal (and vice versa).

Digital circuits perform arithmetic directly in binary.

⇒6.1 Binary Addition Rules

• $0 + 0 = 0$
• $0 + 1 = 1$
• $1 + 0 = 1$
• $1 + 1 = 0$ (with a carry of 1 to the next column)
• $1 + 1 + 1$ (from previous carry) $= 1$ (with a carry of 1)

⇒6.2 Binary Subtraction Rules

• $0 - 0 = 0$
• $1 - 0 = 1$
• $1 - 1 = 0$
• $0 - 1 = 1$ (with a borrow of 1 from the next column)

While direct binary subtraction is possible, modern computers do not use it. They use Complements (specifically 2's complement) to turn subtraction into an addition problem, allowing the ALU to only need an Adder circuit.

Complements are used in digital computers to simplify the subtraction operation and to represent negative numbers.

⇒7.1 1's Complement

The 1's complement of a binary number is found by flipping every bit: changing all 1s to 0s, and all 0s to 1s.

Example: 1's complement of `10110` is `01001`.

⇒7.2 2's Complement

The 2's complement of a binary number is found by taking its 1's complement and adding 1 to the Least Significant Bit (LSB).

Example: Find 2's complement of `10110`.

• Step 1 (1's comp): `01001`
• Step 2 (Add 1): `01001` + `1` = `01010`.

Shortcut: Starting from the right (LSB), leave all zeros and the first '1' unchanged. Then flip all remaining bits to the left.

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

⇒8.1 Subtraction rules using 2's Complement

• Find the 2's complement of the subtrahend ($B$).
• Add it to the minuend ($A$).
• If a final carry is generated, discard it. The result is positive and in true binary form.
• If NO final carry is generated, the result is negative and is in its 2's complement form. To find the magnitude, take the 2's complement of the result and attach a negative sign.

Example: Perform $7 - 4$ using 4-bit 2's complement.

• $A = 7 = (0111)_2$
• $B = 4 = (0100)_2$. 2's complement of $B = 1100$.
• Add $A$ and 2's comp of $B$: `0111 + 1100 = 1 0011`.
• Discard the end carry (1). Result is `0011` (which is $+3$ in decimal). Correct!

In BCD (specifically 8421 BCD), each decimal digit is represented by a 4-bit binary equivalent.

Example: Decimal $396$ in BCD is `0011` `1001` `0110`.

Note: BCD is NOT the same as direct binary conversion. $(396)_{10} = (110001100)_2$ in pure binary, which is only 9 bits. BCD uses 12 bits. BCD is less efficient in memory but easier for hardware to map to decimal displays (like 7-segment displays).

⇒9.1 BCD Addition

• Add the two BCD numbers using regular binary addition.
• If a 4-bit group sum is $\le 9$ and no carry was generated out of that group, the result is valid.
• If a 4-bit group sum is $> 9$ (invalid BCD code, e.g., 1010) OR if a carry was generated out of that group, the result is invalid.
• Correction: Add `0110` (decimal 6) to the invalid 4-bit group to correct it and propagate any resulting carry to the next group.

⇒10.1 Gray Code

Gray code is an unweighted code where successive numbers differ by exactly one bit.

Binary sequence: `000, 001, 010, 011` (Notice from 001 to 010, two bits change).
Gray Code sequence: `000, 001, 011, 010` (Only one bit changes per step).

Application: Used in rotary encoders, Karnaugh maps, and error reduction in digital communications (because a single bit error only shifts the value by one increment).

⇒10.2 ASCII (American Standard Code for Information Interchange)

A 7-bit alphanumeric code used to represent text in computers. (128 characters: A-Z, a-z, 0-9, punctuation, and control characters like newline/CR). An 8th bit is often added for parity (error checking).

Boolean algebra is the mathematics of digital logic. It operates on binary variables (which take values 0 or 1) and three fundamental logic operations: AND ($\cdot$), OR ($+$), and NOT ($'$).

⇒11.1 Huntington Postulates

The formal foundation of Boolean algebra.

• Closure: Results of operations are within the set $\{0, 1\}$.
• Identity: $x + 0 = x$ and $x \cdot 1 = x$.
• Commutative: $x + y = y + x$ and $x \cdot y = y \cdot x$.
• Distributive: $x \cdot (y + z) = (x \cdot y) + (x \cdot z)$ AND $x + (y \cdot z) = (x + y) \cdot (x + z)$. (Notice the second one is unique to Boolean algebra, it doesn't work in standard algebra).
• Complement: For every $x$, there is an $x'$ such that $x + x' = 1$ and $x \cdot x' = 0$.

These theorems are used to minimize logic expressions, directly reducing the number of logic gates needed in a hardware circuit.

• Idempotent Law: $x + x = x$ and $x \cdot x = x$.
• Null (Dominance) Law: $x + 1 = 1$ and $x \cdot 0 = 0$.
• Involution Law: $(x')' = x$.
• Absorption Law: $x + (x \cdot y) = x$ and $x \cdot (x + y) = x$.

⇒12.1 De Morgan's Theorems

The most important tool for manipulating negated logic:

• Theorem 1: $(x + y)' = x' \cdot y'$ (NOR is equivalent to Bubbled AND).
• Theorem 2: $(x \cdot y)' = x' + y'$ (NAND is equivalent to Bubbled OR).

Mnemonic: "Break the line, change the sign."

Logic gates are the physical hardware implementation of Boolean functions. They are built using transistors.

⇒13.1 Basic Gates

• AND Gate: Output is 1 only if ALL inputs are 1.
• OR Gate: Output is 1 if AT LEAST ONE input is 1.
• NOT Gate (Inverter): Output is the inverse of the input.

⇒13.2 Universal Gates

NAND and NOR are called Universal Gates because any boolean function (and any other gate) can be implemented using only NAND gates, or only NOR gates.

⇒13.3 Exclusive Gates

• XOR (Exclusive-OR): Output is 1 if inputs are DIFFERENT (an odd-parity detector). $A \oplus B = A'B + AB'$.
• XNOR (Exclusive-NOR): Output is 1 if inputs are the SAME (an equality detector).

Unit 1 sets the hardware-level vocabulary.

⇒14.1 University Exam Checklist

• Convert $(101.11)_2$ to Decimal, Octal, and Hexadecimal.
• Perform $(45)_{10} - (62)_{10}$ using 8-bit 2's complement arithmetic.
• Explain the rules of BCD addition. Why is $0110$ added to invalid sums?
• State De Morgan’s Theorems and prove them using a truth table.
• Minimize the Boolean expression $F = A'B'C + A'BC + AB'C + ABC$ using Boolean algebra theorems.
• Why are NAND and NOR called Universal Gates? Prove it by constructing AND, OR, and NOT gates using only NAND gates.

⇒14.2 Placement Interview Focus

• Bitwise operations in C/C++ (`&`, `|`, `^`, `~`) map directly to these logic gates. How would you use XOR to swap two variables without a temporary variable?
• Why do computers use 2's complement instead of 1's complement to represent negative numbers? (Answer: 1's complement has two representations for zero, $+0$ and $-0$, which complicates ALU design).