Number systems, codes and Boolean algebra

Why it matters

Every reading an instrument takes ends up as a pattern of bits: an ADC output, a register in a microcontroller, a code from a shaft encoder. You must be able to move between binary, hexadecimal and decimal without thinking, know which code a device is sending you, and simplify the logic that processes those bits. Boolean algebra is the tool that turns a word specification into the smallest gate circuit.

Key ideas

Positional number systems. A number written in base (radix) r with digits dₙ…d₁d₀.d₋₁… has the value Σ dᵢ·rⁱ. Each digit must be smaller than r.

• Binary (r = 2): digits 0, 1. The natural language of two-state switches.
• Octal (r = 8): one octal digit = exactly 3 bits.
• Hexadecimal (r = 16): digits 0–9, A–F (A = 10 … F = 15); one hex digit = exactly 4 bits, so hex is the compact way to write bytes and addresses.

Conversions. Decimal integer → base r: divide repeatedly by r and read the remainders from last to first. Decimal fraction → base r: multiply repeatedly by r and read the integer parts from first to last (some fractions, such as 0.1₁₀, never terminate in binary). Binary ↔ octal/hex: group bits in 3s or 4s starting from the binary point.

Signed numbers. With n bits:

• Sign-magnitude: MSB is the sign; two zeros; range −(2ⁿ⁻¹ − 1) to +(2ⁿ⁻¹ − 1).
• 1's complement: invert all bits to negate; also two zeros.
• 2's complement: invert all bits and add 1. One zero, range −2ⁿ⁻¹ to +(2ⁿ⁻¹ − 1). The MSB carries weight −2ⁿ⁻¹. Subtraction becomes addition, which is why every processor uses it.
• Overflow in 2's complement addition happens only when two numbers of the same sign give a result of the opposite sign (equivalently, carry into MSB ≠ carry out of MSB).

Codes.

• BCD (8421): each decimal digit coded separately in 4 bits; 1010–1111 are invalid. Used by displays and digital meters. When a BCD sum digit exceeds 9 (or produces a carry), add 0110 to correct it.
• Excess-3: BCD + 0011; self-complementing (the 9's complement is obtained by inverting bits).
• Gray code: adjacent values differ in exactly one bit. Binary → Gray: g_{n−1} = b_{n−1}, gᵢ = bᵢ₊₁ ⊕ bᵢ. Gray → binary: b_{n−1} = g_{n−1}, bᵢ = bᵢ₊₁ ⊕ gᵢ. Used in absolute shaft encoders and K-map ordering because a misaligned reading can be wrong by at most one count. Gray code is not an error-correcting code.
• ASCII: 7-bit character code ('0' = 30H, 'A' = 41H).
• Parity: one extra bit makes the count of 1s even (or odd); detects any single-bit error, corrects none.

Boolean algebra. Variables take values 0 or 1; operations are AND (·), OR (+) and NOT ('). Key laws: identity, null, idempotent, complement, involution, commutative, associative, distributive (both A(B + C) = AB + AC and A + BC = (A + B)(A + C)), absorption, De Morgan and consensus. Every law has a dual obtained by swapping + with · and 0 with 1.

Canonical forms. A minterm is a product containing every variable once (true for exactly one input row); a maxterm is a sum that is false for exactly one row. Any function is a sum of its minterms (SOP, Σm) or a product of its maxterms (POS, ΠM); the two lists are complementary. NAND and NOR are each universal: any function can be built from only one of them.

This topic feeds directly into K-map minimisation, adders (2's complement arithmetic) and ADC output codes.

Formulas

N = Σ dᵢ · rⁱ

• N: decimal value; dᵢ: digit at position i; r: radix. Applies to integer (i ≥ 0) and fractional (i < 0) positions.

−X (2's complement, n bits) = 2ⁿ − X

• n: word length in bits. Range of n-bit 2's complement: −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1.

gᵢ = bᵢ₊₁ ⊕ bᵢ (MSB copied unchanged)

• Binary to Gray conversion; bᵢ: binary bit, gᵢ: Gray bit.

A + AB = A and A(A + B) = A (absorption)

A + A'B = A + B

(A + B)' = A'·B' and (A·B)' = A' + B' (De Morgan)

AB + A'C + BC = AB + A'C (consensus)

A ⊕ B = A'B + AB'

Number of distinct Boolean functions of n variables = 2^(2ⁿ).

Worked examples

Example 1 (standard). Convert 156₁₀ to binary, octal and hexadecimal.

1. Repeated division by 2 gives remainders (LSB first) 0, 0, 1, 1, 1, 0, 0, 1.
2. Read last to first: 156₁₀ = 10011100₂. Check: 128 + 16 + 8 + 4 = 156.
3. Group in 3s from the right: 010 011 100 → 234₈.
4. Group in 4s: 1001 1100 → 9C₁₆.

Answer: 156₁₀ = 10011100₂ = 234₈ = 9C₁₆

Example 2 (GATE level). (a) The number 123 in an unknown base b equals 83 in decimal. Find b. (b) Add −45 and +27 using 8-bit 2's complement and state whether overflow occurs.

1. (a) Value = 1·b² + 2·b + 3 = 83 → b² + 2b − 80 = 0 → (b + 10)(b − 8) = 0 → b = 8. The digits 1, 2, 3 are all less than 8, so the base is valid.
2. (b) +45 = 00101101. Invert: 11010010; add 1: 11010011 = −45.
3. +27 = 00011011.
4. Add: 11010011 + 00011011 = 11101110. No carry out of the MSB.
5. The operands have opposite signs, so overflow is impossible. The result is negative (MSB = 1); its magnitude is 2's complement of 11101110 = 00010010 = 18.

Answer: (a) b = 8; (b) 11101110 = −18, no overflow

Example 3 (Boolean simplification). Simplify F = AB + A'C + BC + AB'C.

1. By consensus, BC is redundant given AB and A'C: F = AB + A'C + AB'C.
2. AB + AB'C = A(B + B'C) = A(B + C) = AB + AC.
3. F = AB + AC + A'C = AB + C(A + A') = AB + C.

Answer: F = AB + C

Common mistakes

• Reading division remainders in the wrong order (the first remainder is the LSB).
• Grouping bits for hex from the left instead of from the binary point.
• Forgetting that the 8-bit 2's complement range is −128 to +127, not −127 to +127, and calling a carry-out "overflow" (in signed addition the carry-out is simply discarded).
• Treating BCD as plain binary: 0001 0010 in BCD is 12, not 18.
• Applying De Morgan to only part of a bracket, or forgetting to swap AND and OR.
• Calling Gray code "error-correcting": it only limits transition errors to one count.

For GATE IN

Expect quick conversions between bases (including unknown-base equations), 2's complement range and overflow, Gray/BCD conversions, counting minterms or functions, and simplifying an expression or checking whether two expressions are equal. Practise doing conversions by grouping bits rather than via decimal, and verify simplifications with a truth table for a few rows.

Quick check

1. Convert 1011₂ to decimal.
2. Simplify A + AB.
3. What is the Gray code of binary 1101?
4. What decimal value does the 8-bit 2's complement word 11101100 represent?
5. How many distinct Boolean functions of 3 variables exist?

Answers: 1. 11 2. A 3. 1011 4. −20 5. 256