Number Systems, Codes and Boolean Algebra

Number systems, codes and Boolean algebra are the language of digital design and the entry point to the ~9-mark Digital Circuits section. GATE EC tests base conversion, complements, code properties and Boolean simplification (1–2 marks).

Key results

• Base conversion: repeated division (integer) / multiplication (fraction). Hex↔binary in 4-bit groups; octal in 3-bit groups.
• Signed representations: sign-magnitude, 1's complement, 2's complement (most used). 2's complement of N-bit: invert bits + 1; range −2^{n−1} to 2^{n−1}−1.
• Codes: BCD (8421), Excess-3, Gray code (single-bit change between successive values, used to avoid glitches).
• Boolean laws: De Morgan (A+B)' = A'B', (AB)' = A'+B'; distributive, absorption A+AB=A.
• SOP/POS forms; minterms/maxterms.

Item	Key fact
2's complement	invert + 1; unique zero
Gray code	one bit changes at a time
BCD	4-bit decimal (0–9 valid)
De Morgan	(A+B)'=A'B'
Range (2's comp, n)	−2^{n−1} … 2^{n−1}−1

Exam Tricks & Tips

• 🎯 2's complement = 1's complement + 1; it has a single zero and directly supports subtraction by addition.
• 🎯 Gray code changes only ONE bit between consecutive numbers — ideal for encoders/K-maps to avoid glitches.
• 🎯 De Morgan's theorems let you convert AND↔OR through bubbles: (A+B)'=A'B', (AB)'=A'+B'.
• 🎯 Hex ↔ binary conversion in nibbles (4 bits); octal in 3-bit groups — no decimal detour needed.
• 🎯 Binary → Gray: G = B XOR (B>>1). Gray → binary: cumulative XOR from MSB.
• ❌ Common mistake: forgetting the "+1" step when forming a 2's complement (that's just 1's complement).

Expected exam pattern

1–2 marks: base conversions, 2's-complement arithmetic/range, code conversion (Gray/BCD), or Boolean simplification via laws/De Morgan.

Quick recap

Convert via nibble/triplet grouping. 2's comp = invert+1 (range −2^{n−1}…2^{n−1}−1). Gray = single-bit change (B XOR B>>1). De Morgan flips AND/OR with complements. SOP = minterms, POS = maxterms.

Cover the answer, recall, then check. 12 cards on number systems, codes and Boolean algebra for GATE EC.

Q1. How do you form the 2's complement of a binary number?
A1. Invert all bits (1's complement) and add 1.

Q2. Range of an n-bit 2's-complement number?
A2. From −2^{n−1} to +2^{n−1} − 1.

Q3. Key property of Gray code?
A3. Only one bit changes between consecutive values (reduces switching glitches).

Q4. State De Morgan's theorems.
A4. (A + B)' = A'·B' and (A·B)' = A' + B'.

Q5. How do you convert binary to Gray code?
A5. G_i = B_i XOR B_{i+1}; MSB unchanged (G = B XOR (B >> 1)).

Q6. How do you group binary bits for hex and octal?
A6. Hex: groups of 4 bits (nibbles); octal: groups of 3 bits.

Q7. What is BCD (8421) code?
A7. Each decimal digit encoded in 4 bits (0000–1001); 1010–1111 are invalid.

Q8. Why is 2's complement preferred for arithmetic?
A8. It has a single representation of zero and lets subtraction be done by addition.

Q9. State the absorption law.
A9. A + A·B = A and A·(A + B) = A.

Q10. What are minterms and maxterms?
A10. A minterm is an AND of all variables (for SOP); a maxterm is an OR of all variables (for POS).

Q11. Convert decimal 13 to 4-bit 2's complement of −13... i.e. represent −13 in 5 bits.
A11. +13 = 01101 → invert 10010 → +1 = 10011 (−13 in 5-bit 2's complement).

Q12. What is Excess-3 code?
A12. A BCD code where each digit is stored as its value plus 3 (self-complementing).

Digital design starts with two fundamentals: how numbers are represented (binary, hex, signed, BCD, Gray) and how logic is manipulated (Boolean algebra). Get fluent here and radix conversion, 2's-complement arithmetic, and expression simplification become instant. GATE reliably opens Digital with a conversion or a Boolean-identity question.

Core concept: Numbers are encoded in positional and special codes; Boolean algebra provides the axioms (De Morgan, distributivity) to manipulate and minimise logic expressions.

The theory

Beginner — number systems and conversion

Positional value: each digit weighted by radix^position. Convert decimal→binary by repeated division (integer part) and multiplication (fraction). Hex (base 16) groups 4 bits; octal groups 3 bits. Key codes:

• BCD: each decimal digit as 4 bits (0000–1001); wastes 6 combinations.
• Gray code: successive values differ in exactly one bit — used to avoid glitches in encoders. Binary→Gray: G = B XOR (B>>1).
• ASCII: 7-bit character code.

Intermediate — signed numbers and arithmetic

• 2's complement is the standard for signed integers: negate by inverting all bits and adding 1. Range for n bits: −2^(n−1) to +2^(n−1) − 1.
• Addition/subtraction use the same adder; overflow occurs when two same-sign operands give an opposite-sign result (carry-in ≠ carry-out of the MSB).
• 1's complement has two zeros (+0, −0); 2's complement has a single zero — the reason it's preferred.

Advanced — Boolean algebra

Axioms and theorems that drive simplification:

• Identity: A+0 = A, A·1 = A; Null: A+1 = 1, A·0 = 0.
• Complement: A + A' = 1, A·A' = 0; Idempotent: A+A = A.
• De Morgan: (A+B)' = A'·B', (A·B)' = A'+B' — the workhorse for pushing bubbles.
• Consensus: AB + A'C + BC = AB + A'C (the BC term is redundant).
• Absorption: A + AB = A, A + A'B = A + B.
  Functions are written in canonical SOP (sum of minterms, Σm) or POS (product of maxterms, ΠM) forms; NAND and NOR are functionally complete (any function from just one gate type).

Worked example

Convert decimal −20 to 8-bit 2's complement, and simplify F = A + A'B.
−20: +20 = 0001 0100. Invert → 1110 1011. Add 1 → 1110 1100 (= 0xEC).
Simplify: F = A + A'B = (A + A')(A + B) = 1·(A + B) = A + B (absorption theorem).

GATE relevance

1–2 mark NAT/MCQ: radix conversions, 2's-complement arithmetic and overflow, BCD/Gray/excess-3 codes, Boolean simplification via De Morgan/consensus/absorption, and functional completeness of NAND/NOR. Foundation for everything downstream.

Exam tricks and shortcuts

• 2's complement negate: invert + 1; overflow = sign of result wrong (Cin ≠ Cout at MSB).
• Binary→Gray: XOR each bit with the bit to its left (G = B XOR B>>1).
• De Morgan: break the bar, change the operator; A + A'B = A + B.
• NAND and NOR are each functionally complete.
• Mnemonic: "Invert-and-add-one" for 2's complement.

Key formulas

• Base conversion: decimal value = Σ dᵢ·baseⁱ.
• 2's complement: invert bits + 1; range for n bits: −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1.
• Boolean identities: A + AB = A; A + A'B = A + B; De Morgan (AB)' = A' + B', (A+B)' = A'B'.
• Gray code: successive values differ by one bit.
• BCD: each decimal digit → 4 bits.

Boolean algebra simplifies logic; 2's complement enables signed arithmetic with a single adder.

Worked Example

Problem: (a) Convert the decimal number 45.625 to binary. (b) Using 4-bit two's-complement arithmetic, compute 5 − 3 and verify the result.

Solution:
(a) Split into integer and fractional parts.
Integer 45 by repeated division by 2 (remainders bottom-up):
45→22 r1, 22→11 r0, 11→5 r1, 5→2 r1, 2→1 r0, 1→0 r1 ⇒ 101101.
Fraction 0.625 by repeated multiplication by 2 (carries top-down):
0.625×2 = 1.25 → 1, 0.25×2 = 0.5 → 0, 0.5×2 = 1.0 → 1 ⇒ .101.
So 45.625₁₀ = 101101.101₂.

(b) Represent in 4 bits: 5 = 0101, 3 = 0011.
Two's complement of 3: invert 0011 → 1100, add 1 → 1101 (= −3).
Add: 0101 + 1101 = 1 0010.
Discard the carry-out of the 4-bit field → 0010 = 2.
The carry-out being discarded (with no overflow, since signs differ) confirms the answer is correct: 5 − 3 = 2.

Answer: 45.625₁₀ = 101101.101₂; and 5 − 3 = 0010₂ = 2.