Number systems and Boolean algebra

Electronics and Communication Engineering (B.E./B.Tech) · Digital electronics · free study notes for exams, placements and interviews

In short

This topic covers how digital hardware represents numbers (positional radix systems, signed formats, codes) and how it manipulates logic (Boolean algebra, canonical forms and minimisation). Every later block - adders, counters, state machines, ALUs, memories - is built on these two foundations, so examiners treat it as compulsory. It is the highest-yield unit in GATE EC/EE/CS (conversions, 2's complement arithmetic, K-maps, gate-count questions appear almost every year), in ESE/ISRO/DRDO/BEL recruitment papers and in university Digital Electronics papers. In placement tests for Intel, Qualcomm, NXP, Texas Instruments, Samsung SRI-B, Bosch, Cadence and Synopsys, the first-round questions are usually a 2's complement/overflow problem and a Boolean simplification.

Explained

Positional number systems and conversions

A positional number in radix (base) r uses digits 0 to r−1; the digit at place i carries weight r^i. Common radices: decimal (10), binary (2), octal (8), hexadecimal (16, with A-F = 10-15).
Binary matches two-state hardware; octal and hex are shorthand - one octal digit = 3 bits, one hex digit = 4 bits, so grouping/ungrouping around the radix point converts them instantly.
Any radix → decimal: multiply each digit by its weight and add (positional expansion).
Decimal integer → radix r: repeatedly divide by r, collect remainders, read bottom to top.
Decimal fraction → radix r: repeatedly multiply the fraction by r, collect the integer parts, read top to bottom; stop at the required precision (many fractions, e.g. 0.1₁₀, never terminate in binary - a source of rounding error).
Binary ↔ octal/hex: group bits in 3s/4s from the radix point, padding the outer ends with zeros. Octal ↔ hex: go through binary.
Terms: bit, nibble (4 bits), byte (8 bits), word (machine-dependent: 16/32/64 bits). Per IEC 60027-2 / ISO-IEC 80000-13, 1 kibibyte (KiB) = 1024 bytes while 1 kB = 1000 bytes; Indian datasheets and syllabi still often write KB for 1024.
Radix economy: n bits give 2ⁿ distinct codes; to hold decimal numbers 0…D you need ceil(log₂(D+1)) bits.

Signed numbers and binary arithmetic

Unsigned n-bit: 0 to 2ⁿ−1. Three signed schemes:
- Sign-magnitude: MSB = sign, rest = magnitude; range ±(2ⁿ⁻¹−1); two zeros (+0, −0); needs magnitude comparison before adding.
- 1's complement: negate by inverting all bits; range ±(2ⁿ⁻¹−1); two zeros; addition needs an end-around carry (add the carry-out back to the LSB).
- 2's complement: invert all bits and add 1 (equivalently 2ⁿ − N, or "copy bits up to and including the first 1 from the right, invert the rest"). Range −2ⁿ⁻¹ to +2ⁿ⁻¹−1, single zero, and subtraction is just addition - which is why all practical ALUs use it.
Subtraction A − B in 2's complement = A + (2's complement of B); the final carry-out is discarded.
Overflow (signed result outside the range) is detected by V = C_n ⊕ C_(n−1) (carry into MSB differs from carry out), or equivalently: adding two positives gives a negative, or two negatives give a positive. Overflow and carry are different flags - carry-out alone means nothing in signed arithmetic.
Sign extension: widening a 2's complement number copies the MSB leftwards; zero-extension is used for unsigned.
Multiplication/division: shifting left by 1 multiplies by 2, arithmetic shift right by 1 divides by 2 (with sign preserved). Booth's algorithm handles signed multiplication; unsigned multiply is repeated shift-add.
(r−1)'s and r's complement generalise this: 9's complement of a decimal digit = 9 − digit; 10's complement = 9's complement + 1; same logic in any radix.
Floating point (IEEE 754-2019): single precision = 1 sign + 8 exponent (bias 127) + 23 fraction bits, with an implied leading 1; double = 1 + 11 (bias 1023) + 52. Exponent all-0s encodes zero/subnormals, all-1s encodes ±infinity and NaN.

Binary codes

Weighted BCD (8421): each decimal digit coded in 4 bits; 1010-1111 are invalid. Easy for displays and meters, but wastes 17% of the code space (log₂10/4 ≈ 83% efficient) and needs correction in arithmetic.
BCD addition rule: add nibbles as binary; if a nibble exceeds 9 or produces a carry, add 0110 (6) and carry 1 to the next digit.
Excess-3: BCD + 3; unweighted and self-complementing (9's complement = bitwise complement), so it simplifies subtraction; no all-zero code, which helps distinguish "blank" from 0.
2421 (Aiken) and 84-2-1 are weighted and also self-complementing.
Gray code: unweighted, unit distance - successive codes differ in exactly one bit, and it is cyclic (last to first also differs by one). Used in shaft/rotary encoders and in K-map row/column ordering to avoid multiple-bit transitions and reading glitches.
Alphanumeric codes: ASCII (7-bit, 128 characters; '0' = 30H, 'A' = 41H, 'a' = 61H), extended ASCII (8-bit), EBCDIC (IBM mainframes), Unicode/UTF-8 (multilingual). India's own standard is ISCII (IS 13194:1991, BIS) for Indian-script text, now largely superseded by Unicode blocks for Devanagari, Malayalam, Tamil etc. with the INSCRIPT keyboard layout.
Error detection and correction: a single parity bit (even or odd) detects any odd number of bit errors but cannot correct or locate them. Hamming distance = number of differing bit positions; a code with minimum distance d detects d−1 errors and corrects floor((d−1)/2). Hamming (SEC) code places parity bits at positions 1, 2, 4, 8…; k parity bits protect m data bits if 2^k ≥ m + k + 1. Checksums and CRC are used in links and memories; ECC DRAM uses SEC-DED.

Logic gates and Boolean postulates

Boolean (switching) algebra works on {0,1} with three operations: AND (·), OR (+), NOT ('). Huntington postulates: closure, identity (A+0=A, A·1=A), commutative, distributive both ways (A(B+C)=AB+AC and A+BC=(A+B)(A+C) - the second has no arithmetic analogue), and complement (A+A'=1, A·A'=0).
Gates: AND, OR, NOT, NAND, NOR, XOR, XNOR, buffer. NAND and NOR are universal - each alone can realise NOT, AND and OR, so standard cell libraries are built around them (NAND is also faster in CMOS than NOR for the same drive).
Functionally complete sets: {AND, OR, NOT}, {NAND}, {NOR}, {AND, XOR, 1}, {implication, 0}. {AND, OR} alone is not complete (no way to complement).
XOR properties: A⊕0=A; A⊕1=A'; A⊕A=0; A⊕A'=1; associative and commutative; A⊕B⊕C = 1 when an odd number of inputs are 1 (so XOR trees generate parity). XOR is also the controlled inverter used in adders/subtractors.
Positive vs negative logic: which voltage level means 1 is a convention; a positive-logic AND gate is the same hardware as a negative-logic OR gate (duality in the physical sense).
A function of n variables has 2ⁿ input rows, so there are 2^2ⁿ distinct functions - 16 functions of two variables, 256 of three.

Boolean theorems, De Morgan and duality

Idempotent: A+A=A, A·A=A. Null/dominance: A+1=1, A·0=0. Involution: (A')'=A.
Associative: A+(B+C)=(A+B)+C; A(BC)=(AB)C.
Absorption: A+AB=A; A(A+B)=A. Absorption with complement: A+A'B=A+B; A(A'+B)=AB.
Consensus (redundancy): AB + A'C + BC = AB + A'C - the BC term is redundant. Dual: (A+B)(A'+C)(B+C) = (A+B)(A'+C).
De Morgan: (A+B)' = A'·B'; (A·B)' = A'+B'; extends to n variables. Practically: "break the bar, change the sign" - this is how you convert any AND-OR network into NAND-NAND or NOR-NOR form.
Duality principle: interchange AND↔OR and 0↔1 (variables unchanged) and a valid identity stays valid. The complement of a function = its dual with every variable complemented. A self-dual function equals its own dual (e.g. the majority function AB+BC+CA).
Shannon expansion: F = A·F(A=1) + A'·F(A=0) - the basis of multiplexer-based realisation and BDDs.
Algebraic simplification is not unique and gives no guarantee of minimality, which is why graphical/tabular methods are used.

Canonical and standard forms

Minterm (m_i): an AND term containing every variable once, true for exactly one input combination (variable as-is for 1, complemented for 0). Maxterm (M_i): an OR term, false for exactly one combination - note M_i = (m_i)'.
Canonical SOP: F = Σm(indices of 1-rows). Canonical POS: F = ΠM(indices of 0-rows). The two index sets are complementary, so conversion needs only the truth table: F = Σm(S) = ΠM(all indices not in S).
Standard (non-canonical) forms are the simplified SOP/POS after minimisation; "two-level" means AND-OR or OR-AND depth.
F' from SOP: F' = Σm(0-rows) = ΠM(1-rows) - useful when the complement is cheaper to build.
Incompletely specified functions have don't-care rows (d), written Σm(…) + d(…); they may be treated as 0 or 1, whichever helps minimisation.

Minimisation: Karnaugh maps and Quine-McCluskey

K-map = truth table on a grid whose rows/columns are in Gray-code order, so physically adjacent cells differ in one variable and can be combined (A + A' = 1 eliminates that variable). Maps wrap around at the edges (and the 5-variable map is two 4-variable maps, adjacent cell-to-cell).
Steps: (1) plot 1s (and d's); (2) form the largest possible groups of 1, 2, 4, 8, 16 cells - groups must be rectangular and a power of two, may overlap, may not include a 0; (3) a group of 2^k cells in an n-variable map leaves n−k literals; (4) identify essential prime implicants (those covering a 1 no other PI covers); (5) add the fewest remaining PIs to cover all 1s. For POS, group the 0s and read each group in complemented (sum) form.
Implicant / prime implicant / essential PI: a product term implying F / one that cannot be enlarged further / one that is the sole cover of some minterm. Redundant PIs can be dropped; a non-essential PI may still be needed in a minimal cover.
Static hazards: a minimal expression can glitch; adding the consensus term back (a redundant cover) removes a static-1 hazard - minimum gate count and glitch-free are not the same goal.
Quine-McCluskey (tabular) is the systematic, programmable alternative for more than 5-6 variables: list minterms grouped by number of 1s, combine terms differing in one bit (mark the position with a dash), repeat until no combination is possible, then build a prime implicant chart and select a minimum cover (Petrick's method for cyclic charts). Complexity grows exponentially, so industrial tools use Espresso-style heuristics inside synthesis.
Variable-entered maps and multiplexer realisations via Shannon expansion reduce map size; multi-output minimisation shares terms between functions.

Key points

Radix weight - digit at position i has weight rⁱ; positional expansion converts any base to decimal.
Grouping rule - 1 octal digit = 3 bits, 1 hex digit = 4 bits, grouped outward from the radix point.
Decimal to binary - divide-by-2 for the integer part (remainders bottom-up), multiply-by-2 for the fraction (top-down).
2's complement - invert and add 1, or 2ⁿ − N; range −2ⁿ⁻¹ to 2ⁿ⁻¹−1 with one zero; used by every real ALU.
Subtraction = addition of the 2's complement; the final carry-out is ignored.
Overflow - V = C_n ⊕ C_(n−1); cannot occur when adding numbers of opposite sign.
BCD correction - add 6 (0110) to any nibble that exceeds 9 or carries out.
Excess-3 and 2421 - unweighted/weighted but self-complementing, easing 9's-complement subtraction.
Gray code - unit-distance and cyclic; used in encoders and to order K-map axes.
IEEE 754 single - 1+8+23 bits, exponent bias 127, hidden leading 1.
De Morgan - (AB)' = A'+B', (A+B)' = A'B'; the route to all-NAND or all-NOR circuits.
Duality - swap AND↔OR and 0↔1; complement = dual with variables complemented.
Consensus theorem - AB + A'C + BC = AB + A'C; the covered middle term is redundant.
Minterm/maxterm - F = Σm(1-rows) = ΠM(0-rows); M_i = (m_i)'.
Universal gates - NAND and NOR each realise any function; {AND, OR} alone cannot.
XOR - odd-parity detector; A⊕A=0, A⊕1=A', associative.
K-map grouping - groups of 2^k cells remove k literals; edges wrap; don't-cares are free.
Quine-McCluskey - exhaustive, algorithmic minimisation; essential PIs first, then minimum cover.

Formulas and examples

N = Σ d_i · rⁱ (d_i = digit, r = radix, i = position index; negative i for fraction digits)
2's complement of n-bit N = 2ⁿ − N; 1's complement = (2ⁿ − 1) − N; generally r's complement = rⁿ − N
Ranges: unsigned 0 … 2ⁿ−1; 2's complement −2ⁿ⁻¹ … +2ⁿ⁻¹−1; sign-magnitude and 1's complement ±(2ⁿ⁻¹−1)
Signed-add overflow V = C_n ⊕ C_(n−1) (C_n = carry out of MSB, C_(n−1) = carry into MSB)
Binary → Gray: g_(n−1) = b_(n−1), g_i = b_(i+1) ⊕ b_i; Gray → binary: b_(n−1) = g_(n−1), b_i = b_(i+1) ⊕ g_i
Minterms of n variables = 2ⁿ; distinct Boolean functions of n variables = 2^2ⁿ
De Morgan: (A+B)' = A'B'; (AB)' = A'+B'; Consensus: AB + A'C + BC = AB + A'C
IEEE 754 single: value = (−1)^s × 1.f × 2^E−127, E = 8-bit biased exponent, f = 23-bit fraction
Hamming SEC: 2^k ≥ m + k + 1 (m = data bits, k = parity bits); distance-d code detects d−1, corrects ⌊(d−1)/2⌋ errors

Dec	Binary	BCD (8421)	Excess-3	Gray	2421
0	0000	0000	0011	0000	0000
1	0001	0001	0100	0001	0001
2	0010	0010	0101	0011	0010
3	0011	0011	0110	0010	0011
4	0100	0100	0111	0110	0100
5	0101	0101	1000	0111	1011
6	0110	0110	1001	0101	1100
7	0111	0111	1010	0100	1101
8	1000	1000	1011	1100	1110
9	1001	1001	1100	1101	1111

Example 1 - mixed-radix conversion of (347.625)₁₀

Integer: 347 = 256+64+16+8+2+1 → 101011011₂.
Fraction: 0.625×2 = 1.25 → 1; 0.25×2 = 0.5 → 0; 0.5×2 = 1.0 → 1, stop → .101₂.
So 347.625₁₀ = 101011011.101₂.
Octal (group 3s): 101 011 011 . 101 → 533.5₈ (check 5×64 + 3×8 + 3 = 347; 5/8 = 0.625).
Hex (group 4s, pad left): 0001 0101 1011 . 1010 → 15B.A₁₆ (check 256 + 80 + 11 = 347; 10/16 = 0.625).

Example 2 - 8-bit 2's complement subtraction and overflow

(a) 45 − 78: 45 = 00101101; 78 = 01001110 → 2's complement = 10110001 + 1 = 10110010.
- 00101101 + 10110010 = 11011111, carry-out 0 (discard). MSB = 1 → negative; magnitude = 2's complement of 11011111 = 00100000 + 1 = 00100001 = 33 → answer −33 ✓. Operand signs differ, so overflow is impossible.
(b) 100 + 50: 01100100 + 00110010 = 10010110. Unsigned this is 150; as 8-bit signed it reads 150 − 256 = −106. Carry into MSB = 1, carry out = 0 → V = 1, so the signed result has overflowed (150 > +127). Nine bits, or 16-bit words, are needed.

Example 3 - K-map minimisation F(A,B,C,D) = Σm(0,1,2,4,5,6,8,9,12,13,14), A = MSB. Equivalently F = ΠM(3,7,10,11,15).

All eight minterms with C = 0 (0,1,4,5,8,9,12,13) are 1 → group of eight gives C' (essential: it alone covers m1, m5, m8, m9, m13).
Remaining 1s are 2, 6, 14 (C = 1, D = 0). Group {0,2,4,6} = A'D' (prime; cannot grow to D' because m10 = 0, nor to A' because m3, m7 = 0) - covers m2 and m6.
Group {4,6,12,14} = BD' (prime) - covers m14.
Minimum SOP: F = C' + A'D' + BD' = C' + (A'+B)D'. Three terms, five literals; no group includes a 0, and the union is exactly the given minterm list.

Example 4 - BCD addition and Gray conversion

47 + 35 in BCD: 0100 0111 + 0011 0101. Units 0111 + 0101 = 1100 = 12 > 9 → add 0110 → 1 0010, i.e. digit 0010 with carry 1. Tens 0100 + 0011 + 1 = 1000. Result 1000 0010 = 82₁₀ ✓.
Binary 1011 → Gray: g3 = 1; g2 = 1⊕0 = 1; g1 = 0⊕1 = 1; g0 = 1⊕1 = 0 → 1110. Back: b3 = 1; b2 = 1⊕1 = 0; b1 = 0⊕1 = 1; b0 = 1⊕0 = 1 → 1011 ✓.

Example 5 - IEEE 754 single precision for −12.75

12.75₁₀ = 1100.11₂ = 1.10011 × 2³ → sign s = 1, exponent E = 3 + 127 = 130 = 10000010, fraction f = 10011 followed by 18 zeros.
Bit pattern 1 10000010 10011000000000000000000 → nibbles 1100 0001 0100 1100 0000 … → 0xC14C0000.

Feature	Sign-magnitude	1's complement	2's complement
Negation	Flip MSB	Invert all bits	Invert + 1
Zeros	Two (+0, −0)	Two	One
8-bit range	−127 … +127	−127 … +127	−128 … +127
Addition hardware	Compare + add/sub	Adder + end-around carry	Plain adder
Use today	Floating-point mantissa	Legacy, checksums	All integer ALUs

Where it is used

VLSI and ASIC design: Boolean minimisation and De Morgan transforms are the core of RTL coding and logic synthesis (Synopsys Design Compiler, Cadence Genus) at Intel Bengaluru, Qualcomm, NXP, TI India, Samsung SRI-B, Nvidia and Indian design services firms.
Processor and ALU design: 2's complement arithmetic, carry/overflow flags, shift-based multiply, IEEE 754 units - also the exam territory of Computer Organisation and of C-level bit manipulation rounds.
Embedded firmware: hex masks, bit-set/clear/toggle with AND/OR/XOR, BCD registers in RTCs (DS1307), 7-segment and LCD drivers, packing sensor data.
Instrumentation and automation: BCD outputs of digital panel meters and weighing machines; Gray-coded absolute shaft encoders on CNC machines and robot joints; PLC ladder logic is Boolean algebra in another notation.
Communication and storage: parity, Hamming/CRC in UART framing, memory ECC, and in ISRO/DRDO telemetry links where single-event upsets must be corrected.
Text and language computing: ASCII/Unicode handling, and ISCII (IS 13194) legacy data in Indian-language government records.
Job roles: digital design, verification, physical design, embedded C, FPGA and test engineers - plus every public-sector technical exam (ESE, ISRO, BEL, BHEL, DRDO, SSC-JE).

Interview questions

Q: Why do computers use 2's complement instead of sign-magnitude? A: It has a single representation of zero and lets the same adder perform subtraction (A + 2's complement of B), so no separate comparison or subtract hardware is needed.
Q: How do you take the 2's complement quickly by hand? A: Scan from the LSB, copy bits up to and including the first 1, then invert everything to the left.
Q: What is the difference between carry and overflow? A: Carry is the bit out of the MSB and signals unsigned range violation; overflow means the signed result is out of range and equals C_n ⊕ C_(n−1).
Q: What is the 8-bit 2's complement range, and why is it asymmetric? A: −128 to +127; one bit pattern (10000000) is freed up because zero has only one encoding, and it is assigned to the extra negative value.
Q: Why is BCD used when binary is more efficient? A: Decimal digits map one-to-one to 4-bit groups, so display, keypad entry and decimal-exact financial or metering arithmetic need no binary-to-decimal conversion; the cost is wasted codes and correction logic.
Q: Why is a Gray code used in a shaft encoder? A: Only one bit changes between adjacent positions, so a misaligned read cannot produce a wildly wrong value - unlike binary, where 0111→1000 changes four bits at once.
Q: State and use De Morgan's theorem. A: (AB)' = A'+B' and (A+B)' = A'B'; it converts AND-OR logic to NAND-NAND or NOR-NOR form so a circuit can be built from one universal gate type.
Q: What is duality, and is it the same as complementation? A: The dual swaps AND with OR and 0 with 1 but leaves variables unchanged; the complement is the dual with every variable also complemented - so they are not the same.
Q: What is an essential prime implicant? A: A prime implicant that is the only one covering some minterm, so it must appear in every minimal cover.
Q: Why might you keep a redundant term in a minimised expression? A: To remove a static hazard - the consensus term holds the output steady while one input changes along paths of unequal delay, at the cost of an extra gate.
Q: How many different Boolean functions of 3 variables exist? A: 2^2³ = 256, since the truth table has 8 rows and each can be 0 or 1.
Q: 0.1 cannot be stored exactly in a float - why? A: 0.1 in binary is a non-terminating recurring fraction, so IEEE 754 stores a rounded value; comparing floats for equality is therefore unsafe.
Q: Which is faster in CMOS, NAND or NOR, and why does it matter here? A: NAND, because its series transistors are NMOS (higher mobility) while NOR stacks PMOS; so synthesis tools prefer NAND-based decompositions of the same Boolean function.

Common mistakes

Reading divide-by-r remainders top-down instead of bottom-up, or multiply-by-r integers bottom-up instead of top-down.
Forgetting to pad the left of the integer part and the right of the fraction with zeros before grouping bits into octal/hex digits.
Taking the 1's complement and forgetting the +1, or adding the end-around carry in a 2's complement sum where the carry-out must simply be dropped.
Declaring overflow whenever a carry appears - carry out of the MSB is normal and harmless when adding numbers of opposite sign.
Adding BCD numbers as plain binary without the +6 correction, or treating 1010-1111 as valid BCD digits.
Applying A + BC = (A+B)(A+C) in reverse by arithmetic intuition, or writing (A+B)' = A'+B' - the classic De Morgan slip.
On K-maps: labelling axes in binary count order instead of Gray order, using non-power-of-two or L-shaped groups, missing the wrap-around adjacencies, or grouping the 1s and then reading the answer as a POS.
Treating don't-cares as 1s in the final answer (they must never be *required* to be covered) or assuming the minimal expression is unique.