Number systems, Boolean algebra and logic gates

Why it matters

Every PLC, microcontroller and sensor interface in a mechatronic system works on binary signals. Reading a register value in hex, deciding whether a limit-switch interlock is wired correctly, or reducing a safety-logic expression to the fewest gates all rest on number systems and Boolean algebra. These ideas are also the starting point for combinational circuits, flip-flops and ADC/DAC codes later in this subject.

Key ideas

Positional number systems. A number in base r with digits dₙ…d₁d₀.d₋₁… has the value Σ dᵢ·rⁱ. The systems used in digital work are:

• Binary (base 2): digits 0 and 1; each digit is a bit. Eight bits make a byte.
• Octal (base 8): digits 0–7; one octal digit is exactly three bits.
• Hexadecimal (base 16): digits 0–9 and A–F (A = 10 … F = 15); one hex digit is exactly four bits, so a byte is two hex digits.
• BCD (binary-coded decimal): each decimal digit coded separately in four bits (0000–1001); 1010–1111 are unused codes.

Conversions.

• Any base to decimal: multiply each digit by its place weight and add.
• Decimal integer to base r: divide repeatedly by r and read the remainders from last to first.
• Decimal fraction to base r: multiply the fraction repeatedly by r and read the integer parts from first to last. Many decimal fractions (0.1, for example) do not terminate in binary.
• Binary to octal or hex: group bits in threes or fours outward from the binary point, padding with zeros at the ends.

Signed numbers. In n-bit 2's complement the MSB has weight −2ⁿ⁻¹, so the range is −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1 (−128 to +127 for 8 bits). To negate a number, invert all bits and add 1. Subtraction A − B is done as A + (2's complement of B), discarding any carry out of the MSB. Overflow occurs only when two numbers of the same sign give a result of the opposite sign. 1's complement and sign-magnitude both have two representations of zero, which is why hardware uses 2's complement.

Boolean algebra. Variables take only the values 0 and 1. The basic operations are AND (·), OR (+) and NOT (′). Important laws:

• Identity, null, idempotent and complement laws (listed in Formulas).
• Commutative, associative and distributive laws; note that OR distributes over AND too: A + B·C = (A + B)(A + C), unlike ordinary algebra.
• Absorption: A + A·B = A, A(A + B) = A, and A + A′B = A + B.
• De Morgan's theorems: (A·B)′ = A′ + B′ and (A + B)′ = A′·B′. To complement an expression, swap AND and OR and complement every literal.
• Consensus: A·B + A′·C + B·C = A·B + A′·C (the term B·C is redundant).
• Duality: any identity stays true if AND and OR, and 0 and 1, are interchanged.

Canonical forms and K-maps. A function can be written as a sum of minterms (SOP, Σm) or a product of maxterms (POS, ΠM). A Karnaugh map arranges the 2ⁿ cells in Gray-code order so adjacent cells differ in one variable. Grouping adjacent 1s in blocks of 1, 2, 4, 8 … (wrapping round the edges) removes one variable per doubling. Use the largest possible groups and the fewest groups; don't-care cells (X) may be included in a group when they help and ignored otherwise. K-maps are practical up to four or five variables.

Logic gates. AND, OR and NOT are the basic gates; NAND and NOR are universal (any function can be built from only NANDs or only NORs); XOR outputs 1 when an odd number of inputs are 1 and is used for adders, parity and comparators; XNOR is the equality detector. A two-level AND-OR (SOP) circuit maps directly onto NAND-NAND, and a two-level OR-AND (POS) circuit onto NOR-NOR.

Formulas

N₁₀ = Σ dᵢ · rⁱ

• dᵢ: digit at position i; r: base (radix); i counts from 0 at the left of the radix point, negative to its right.

Range (n-bit 2's complement) = −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1; Range (n-bit unsigned) = 0 to 2ⁿ − 1

• n: number of bits.

−B = B′ + 1 (2's complement negation)

A + 0 = A, A · 1 = A, A + 1 = 1, A · 0 = 0 A + A = A, A · A = A, A + A′ = 1, A · A′ = 0, (A′)′ = A A + A·B = A, A + A′·B = A + B (A · B)′ = A′ + B′, (A + B)′ = A′ · B′ A ⊕ B = A·B′ + A′·B, (A ⊕ B)′ = A·B + A′·B′

• These hold for every Boolean variable; ⊕ is XOR.

Worked examples

Example 1 (standard: base conversion). Convert 156.625₁₀ to binary, octal and hexadecimal.

1. Integer part, divide by 2: 156 → 78 r0 → 39 r0 → 19 r1 → 9 r1 → 4 r1 → 2 r0 → 1 r0 → 0 r1. Reading upward: 10011100.
2. Fraction, multiply by 2: 0.625 × 2 = 1.25 (1); 0.25 × 2 = 0.5 (0); 0.5 × 2 = 1.0 (1). Reading downward: .101.
3. Binary: 10011100.101₂.
4. Octal, groups of three: 010 011 100 . 101 → 2 3 4 . 5.
5. Hex, groups of four: 1001 1100 . 1010 → 9 C . A.

156.625₁₀ = 10011100.101₂ = 234.5₈ = 9C.A₁₆.

Example 2 (GATE level: K-map minimisation). Minimise F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15) and find the number of two-input gates needed.

1. Plot the 1s. Minterms 0, 2, 8, 10 are the four corners of the map (B = 0, D = 0 in every one).
2. The four corners are mutually adjacent because the map wraps round; they form a quad: B′·D′.
3. Minterms 5, 7, 13, 15 form a square in the middle (B = 1, D = 1 in every one): B·D.
4. F = B′·D′ + B·D, which is the XNOR of B and D.
5. Check one cell not in the list, m = 1 (A B C D = 0 0 0 1): B′D′ = 0, BD = 0, so F = 0, as required.

F = B′·D′ + B·D = (B ⊕ D)′, one two-input XNOR gate; A and C do not affect the output.

Example 3 (GATE level: 2's complement arithmetic). Using 8-bit 2's complement, compute 45 − 60.

1. 45 = 00101101.
2. 60 = 00111100; invert to 11000011 and add 1: −60 = 11000100.
3. Add: 00101101 + 11000100 = 11110001 (no carry out of the MSB).
4. The MSB is 1, so the result is negative. Its magnitude: invert 11110001 → 00001110, add 1 → 00001111 = 15.
5. The operands have opposite signs, so overflow is impossible.

45 − 60 = 11110001₂ = −15.

Common mistakes

• Reading fractional remainders in the wrong order: integer remainders are read bottom-up, fraction digits top-down.
• Grouping bits for hex from the left of an integer instead of from the binary point.
• Applying De Morgan to only part of a term: (A·B·C)′ is A′ + B′ + C′, not A′·B′·C′.
• Writing A + A′B = A; absorption gives A + B.
• Forgetting the wrap-round adjacency of K-map edges and corners, or forming groups of 3 or 6 cells.
• Writing a K-map in plain binary order (00, 01, 10, 11) instead of Gray order (00, 01, 11, 10).
• Treating a carry out of the MSB as overflow in 2's complement arithmetic.

For GATE ME

Expect short questions on base conversion, 2's complement range and arithmetic, simplifying an expression with the Boolean laws or a K-map (often with don't-cares), recognising a function as XOR/XNOR, and counting NAND or NOR gates for a given function. Practise four-variable K-maps with corner groups and don't-cares, and the standard NAND realisations of NOT, AND, OR and XOR.

Quick check

1. Convert 3F₁₆ to decimal.
2. Simplify A + A′·B.
3. What is the range of a 6-bit 2's complement number?
4. Write (A + B·C)′ using De Morgan's theorems.
5. What is the output of a three-input XOR gate when all inputs are 1?

Answers: 1. 63. 2. A + B. 3. −32 to +31. 4. A′·(B′ + C′). 5. 1.