calculusphile

Unit I — Number System & Boolean Algebra

Glossary — Key Terms & Definitions

Term Meaning
Radix (Base) The number of unique digits in a number system. Decimal has radix 10, binary has radix 2.
Radix Point The dot (.) that separates the integer part from the fractional part in any number system. In decimal it is called the “decimal point”; in binary, the “binary point.”
MSB (Most Significant Bit) The leftmost bit in a binary number — it carries the highest positional weight. In signed numbers, the MSB indicates the sign (0 = positive, 1 = negative).
LSB (Least Significant Bit) The rightmost bit — it carries the lowest positional weight ($2^0 = 1$).
Complement A way to represent negative numbers in binary. The “1’s complement” inverts every bit; the “2’s complement” inverts all bits and adds 1.
Overflow Occurs when the result of an arithmetic operation exceeds the range representable by the given number of bits.
Boolean Algebra A branch of algebra where variables take only two values: 0 (false) and 1 (true). Used to analyze and simplify digital logic circuits.
Truth Table A table listing every possible combination of input values alongside the corresponding output(s) for a logic function.
Logic Gate A physical or virtual device that performs a basic Boolean operation (AND, OR, NOT, etc.) on one or more binary inputs.
Universal Gate A gate (NAND or NOR) that can implement ANY Boolean function on its own.
Minterm A product (AND) term in which every variable appears exactly once, in either true or complemented form. Equals 1 for exactly one input combination. Denoted $m_i$.
Maxterm A sum (OR) term in which every variable appears exactly once. Equals 0 for exactly one input combination. Denoted $M_i$.
SOP (Sum of Products) A Boolean expression written as an OR of AND terms. Example: $AB + \overline{A}C$.
POS (Product of Sums) A Boolean expression written as an AND of OR terms. Example: $(A+B)(\overline{A}+C)$.
Canonical Form An SOP/POS in which every term contains ALL variables. Every minterm/maxterm is fully expanded.
K-Map (Karnaugh Map) A visual grid used to simplify Boolean expressions by grouping adjacent 1s (SOP) or 0s (POS).
Prime Implicant A group in a K-Map that cannot be combined with another group to make a larger group.
Essential Prime Implicant A prime implicant that is the ONLY group covering at least one minterm. It MUST appear in the simplified expression.
Don’t-Care Condition An input combination for which the output can be either 0 or 1 (e.g., invalid BCD inputs 1010–1111). Marked X in truth tables and K-Maps.
Combinational Circuit A circuit whose output depends only on the current inputs (no memory). Examples: adders, MUX, decoders.
Sequential Circuit A circuit whose output depends on current inputs AND past history (has memory). Examples: flip-flops, counters, registers.
Propagation Delay The time it takes for a change in input to produce a change at the output of a gate or circuit.
MUX (Multiplexer) A data selector — routes one of several inputs to a single output based on select lines.
DEMUX (Demultiplexer) A data distributor — routes a single input to one of several outputs based on select lines.
Encoder Converts $2^n$ input lines (one-hot) into an $n$-bit binary code.
Decoder Converts an $n$-bit binary code into $2^n$ output lines (one-hot).
BCD (Binary Coded Decimal) A code where each decimal digit (0–9) is represented by its own 4-bit binary equivalent.
Gray Code A binary code where consecutive values differ by exactly one bit. Used in K-Maps and rotary encoders.
Borrow In subtraction, when the top bit is smaller than the bottom bit, a borrow is taken from the next higher bit position (analogous to carry in addition).
Ripple Carry The propagation of carry from the LSB full adder to the MSB full adder in a parallel adder. Each stage must wait for the previous carry.

UNIT I — Number System & Boolean Algebra

1.1 Number Systems & Conversions

A number system is a way to represent quantities using a fixed set of symbols (digits) and positional notation (each digit’s value depends on its position).

Radix = the base of a number system (how many unique digits it uses).
Radix point = the dot (.) separating the integer part from the fractional part. In decimal, we call it the “decimal point” (3.14). In binary, it’s the “binary point” (101.11).

Bases at a Glance

System Base Digits Prefix/Suffix
Decimal 10 0–9 —
Binary 2 0, 1 0b or subscript ₂
Octal 8 0–7 subscript ₈
Hexadecimal 16 0–9, A–F 0x or subscript ₁₆

Positional Value

Any number $N$ in base $r$ with $n$ integer digits and $m$ fraction digits:

\[N = d_{n-1} \cdot r^{n-1} + d_{n-2} \cdot r^{n-2} + \cdots + d_1 \cdot r^1 + d_0 \cdot r^0 + d_{-1} \cdot r^{-1} + \cdots + d_{-m} \cdot r^{-m}\]

Conversion Methods

Decimal → Binary (Repeated Division by 2)

Convert (25)₁₀ to Binary:

Step Quotient Remainder
25 ÷ 2 12 1 (LSB)
12 ÷ 2 6 0
6 ÷ 2 3 0
3 ÷ 2 1 1
1 ÷ 2 0 1 (MSB)

Result: \((25)_{10} = (11001)_2\)

Convert (100)₁₀ to Binary:

Step Quotient Remainder
100 ÷ 2 50 0 (LSB)
50 ÷ 2 25 0
25 ÷ 2 12 1
12 ÷ 2 6 0
6 ÷ 2 3 0
3 ÷ 2 1 1
1 ÷ 2 0 1 (MSB)

Result: \((100)_{10} = (1100100)_2\)

Convert (57)₁₀ to Binary:

Step Quotient Remainder
57 ÷ 2 28 1 (LSB)
28 ÷ 2 14 0
14 ÷ 2 7 0
7 ÷ 2 3 1
3 ÷ 2 1 1
1 ÷ 2 0 1 (MSB)

Result: \((57)_{10} = (111001)_2\)

Decimal Fraction → Binary (Repeated Multiplication by 2)

Convert (0.625)₁₀ to Binary:

Step Product Integer Part
0.625 × 2 1.25 1 (MSB)
0.25 × 2 0.50 0
0.50 × 2 1.00 1 (LSB)

Result: \((0.625)_{10} = (0.101)_2\)

Convert (0.8125)₁₀ to Binary:

Step Product Integer Part
0.8125 × 2 1.625 1 (MSB)
0.625 × 2 1.25 1
0.25 × 2 0.50 0
0.50 × 2 1.00 1 (LSB)

Result: \((0.8125)_{10} = (0.1101)_2\)

Convert (0.3)₁₀ to Binary (first 6 bits — this is a non-terminating fraction):

Step Product Integer Part
0.3 × 2 0.6 0
0.6 × 2 1.2 1
0.2 × 2 0.4 0
0.4 × 2 0.8 0
0.8 × 2 1.6 1
0.6 × 2 1.2 1 (repeats)

Result: \((0.3)_{10} \approx (0.010011...)_2\) — the pattern 0011 repeats infinitely.

Note: Not all decimal fractions convert to terminating binary fractions. This is why floating-point arithmetic in computers sometimes has tiny rounding errors.

Binary ↔ Octal (Group of 3 bits)

Group binary digits in sets of 3 from the radix point (the dot separating integer and fraction) outward. Pad with leading/trailing zeros if needed.

Example 1: \((110\ 101\ 011)_2 = (653)_8\) Split: 110 = 6, 101 = 5, 011 = 3

Example 2: Convert \((10110001)_2\) to Octal
Group from right: 010 110 001 → 2, 6, 1 → \((261)_8\)

Example 3: Convert \((101.1101)_2\) to Octal
Integer: 101 = 5; Fraction: 110 100 (pad trailing zero) = 6, 4 → \((5.64)_8\)

Binary ↔ Hexadecimal (Group of 4 bits)

Group binary digits in sets of 4 from the radix point outward. Pad with leading/trailing zeros if needed.

Example 1: \((0001\ 1010\ 1011)_2 = (1AB)_{16}\) Split: 0001 = 1, 1010 = A, 1011 = B

Example 2: Convert \((11111110)_2\) to Hex
Group: 1111 1110 → F, E → \((FE)_{16}\)

Example 3: Convert \((110.10111)_2\) to Hex
Integer: 0110 = 6; Fraction: 1011 1000 (pad) = B, 8 → \((6.B8)_{16}\)

Octal ↔ Hexadecimal

Convert via binary as intermediate — never go through decimal.

Convert \((372)_8\) to Hexadecimal:
Octal → Binary: 3 = 011, 7 = 111, 2 = 010 → 011111010
Regroup in 4s from right: 0 1111 1010 → pad: 0000 1111 1010 → 0, F, A
\((372)_8 = (FA)_{16}\)

Convert \((2F)_{16}\) to Octal:
Hex → Binary: 2 = 0010, F = 1111 → 00101111
Regroup in 3s from right: 000 101 111 → 0, 5, 7 → \((57)_8\)

Convert \((1A3)_{16}\) to Octal:
Hex → Binary: 1 = 0001, A = 1010, 3 = 0011 → 000110100011
Regroup in 3s: 000 110 100 011 → 0, 6, 4, 3 → \((643)_8\)

Shortcut: You never need to go through decimal for Octal ↔ Hex. Always use binary as the bridge.
Octal → Binary (3-bit groups) → Hex (4-bit groups)

1.2 Binary Weighted Codes

What is a “Weighted Code”?

Before we jump into specific codes, let’s understand what “weighted” means.

In any positional number system, each digit position has a weight — a multiplier that tells you how much that position is “worth.” You already know this from everyday decimal numbers:

In the decimal number 395, the 3 is in the hundreds place (weight 100), the 9 in the tens place (weight 10), and the 5 in the ones place (weight 1).
Value = 3×100 + 9×10 + 5×1 = 395.

A binary weighted code works exactly the same way but with 4 binary bits (each bit is 0 or 1). Each of the four bit positions is assigned a fixed weight. To find the decimal value, you multiply each bit by its weight and add up the results.

Different codes use different sets of weights — and that’s what gives each code its name.

Summary of Common Weighted Codes

Code Weights (left → right) How to get the decimal value Example for decimal 5
8421 (BCD) 8, 4, 2, 1 Multiply each bit by its weight and add 0101 → 0×8 + 1×4 + 0×2 + 1×1 = 5
2421 2, 4, 2, 1 Multiply each bit by its weight and add 1011 → 1×2 + 0×4 + 1×2 + 1×1 = 5
Excess-3 Not weighted — derived from BCD Take BCD code and add 3 BCD of 5 is 0101 → 0101+0011 = 1000

Now let’s understand each one in depth.

8421 Code (BCD — Binary Coded Decimal)

What does “8421” mean?

The name “8421” literally tells you the weight of each bit position from left to right:

Bit position:   b₃    b₂    b₁    b₀
Weight:          8      4      2      1

To find the decimal value of any 4-bit 8421 code, you compute:

\[\text{Decimal value} = b_3 \times 8 + b_2 \times 4 + b_1 \times 2 + b_0 \times 1\]

Let’s decode 0101 in 8421:

Bit $b_3$ $b_2$ $b_1$ $b_0$
Value 0 1 0 1
Weight 8 4 2 1
Bit × Weight 0×8 = 0 1×4 = 4 0×2 = 0 1×1 = 1

Sum = 0 + 4 + 0 + 1 = 5 ✓

Why is 8421 also called “BCD”?

Because 8, 4, 2, 1 happen to be the natural binary weights ($2^3, 2^2, 2^1, 2^0$). So 8421 code is exactly the same as the first ten values of regular binary (0000 through 1001). Since it’s used to represent decimal digits (0–9) one at a time, we call it Binary Coded Decimal (BCD).

Key idea of BCD

Instead of converting an entire decimal number into one long binary string, BCD encodes each decimal digit separately as its own 4-bit group.

Decimal 47 in pure binary vs BCD:

Pure binary: 47 = 101111 (one number, 6 bits)
BCD: 4 → 0100, 7 → 0111 → combined: 0100 0111 (two groups of 4 bits)

Notice BCD uses more bits, but each group directly maps to a decimal digit — it’s easy to read!

Complete 8421 / BCD Table

Each decimal digit (0–9) is separately encoded as a 4-bit binary number:

Decimal 8421 BCD How it works
0 0000 0×8 + 0×4 + 0×2 + 0×1 = 0
1 0001 0×8 + 0×4 + 0×2 + 1×1 = 1
2 0010 0×8 + 0×4 + 1×2 + 0×1 = 2
3 0011 0×8 + 0×4 + 1×2 + 1×1 = 3
4 0100 0×8 + 1×4 + 0×2 + 0×1 = 4
5 0101 0×8 + 1×4 + 0×2 + 1×1 = 5
6 0110 0×8 + 1×4 + 1×2 + 0×1 = 6
7 0111 0×8 + 1×4 + 1×2 + 1×1 = 7
8 1000 1×8 + 0×4 + 0×2 + 0×1 = 8
9 1001 1×8 + 0×4 + 0×2 + 1×1 = 9

Example 1 — Convert (294)₁₀ to BCD:
Split into individual digits: 2, 9, 4
2 → 0010, 9 → 1001, 4 → 0100
BCD: 0010 1001 0100

Example 2 — Convert (805)₁₀ to BCD:
8 → 1000, 0 → 0000, 5 → 0101
BCD: 1000 0000 0101

Example 3 — Convert BCD 0100 0111 0011 back to Decimal:
0100 → 4, 0111 → 7, 0011 → 3
Decimal: 473

Important: Only values 0000 through 1001 (i.e., 0 through 9) are valid in BCD. The 4-bit combinations 1010 through 1111 (10 through 15) are invalid — they don’t represent any decimal digit. For example, 1011 0110 is NOT valid BCD because 1011 (=11) exceeds 9.

Why use BCD at all? BCD is heavily used in digital clocks, calculators, and voltmeters — any device that needs to display decimal digits. Converting BCD to a decimal display is trivial (each 4-bit group maps to one digit), while converting a long binary number to decimal requires repeated division.

Binary to BCD — Direct Conversion (Double Dabble Algorithm)

So far we’ve converted decimal → BCD (easy: just encode each digit). But what if you have a pure binary number and need to get its BCD representation directly — without first converting to decimal in your head?

This is exactly what the Double Dabble (also called “Shift and Add-3”) algorithm does. It’s the method that digital circuits actually use internally.

The Algorithm — Step by Step
  1. Set up: Write the binary number on the right. Create empty BCD columns on the left (one 4-bit group per expected decimal digit).
  2. Shift left the entire register (binary + BCD columns) by 1 bit.
  3. Check each BCD group: After each shift, if any 4-bit BCD group is ≥ 5 (i.e., 0101 or more), add 3 (0011) to that group.
  4. Repeat steps 2–3 for as many shifts as there are binary bits.
  5. The BCD columns now hold the BCD result.
Why add 3 when ≥ 5?

This is the key insight. When we shift left, we’re essentially multiplying by 2. In BCD, each 4-bit group can only hold 0–9. If a group is 5 or more before a shift, doubling it would give 10 or more — which overflows a single BCD digit. Adding 3 before the next shift pre-corrects for this: when the value $\geq 5$ gets doubled, the +3 correction makes it “carry over” properly into the next BCD digit.

Think of it this way: in a 4-bit group, 5 should become 10 (i.e., carry 1 to next digit, leave 0). But binary doubling of 0101 gives 1010 (=10 in binary, which is invalid BCD). Adding 3 first: 0101+0011=1000, then doubling gives 1→0000, which is carry 1, digit 0. Exactly right!

Convert binary 11111111 (=255₁₀) to BCD using Double Dabble:

We have 8 binary bits, so we need up to 3 BCD digit groups (hundreds, tens, ones).

Setup: BCD columns Binary bits 
Hundreds  Tens    Ones   | Binary
 0000     0000    0000   | 11111111

Shift 1: Shift everything left by 1

 0000     0000    0001   | 1111111_

All BCD groups < 5, no correction needed.

Shift 2:

 0000     0000    0011   | 111111__

Still < 5.

Shift 3:

 0000     0000    0111   | 11111___

Ones group = 0111 (=7) ≥ 5 → Add 3: 0111 + 0011 = 1010

 0000     0000    1010   | 11111___

Shift 4:

 0000     0001    0101   | 1111____

Ones group = 0101 (=5) ≥ 5 → Add 3: 0101 + 0011 = 1000

 0000     0001    1000   | 1111____

Shift 5:

 0000     0011    0001   | 111_____

All < 5.

Shift 6:

 0000     0110    0011   | 11______

Tens group = 0110 (=6) ≥ 5 → Add 3: 0110 + 0011 = 1001

 0000     1001    0011   | 11______

Shift 7:

 0001     0010    0111   | 1_______

Ones group = 0111 (=7) ≥ 5 → Add 3: 0111 + 0011 = 1010

 0001     0010    1010   | 1_______

Shift 8 (final):

 0010     0101    0101   | ________

Result: 0010 0101 0101 → BCD for 255 ✓

Simpler example — Convert binary 1101 (=13₁₀) to BCD:

4 binary bits, need 2 BCD groups (tens, ones).

 Tens    Ones  | Binary
 0000    0000  | 1101

Shift 1: 0000    0001  | 101_     (all < 5)
Shift 2: 0000    0011  | 01__     (all < 5)
Shift 3: 0000    0110  | 1___     (Ones=6 ≥ 5 → +3)
   +3:   0000    1001  | 1___
Shift 4: 0001    0011  | ____

Result: 0001 0011 → BCD for 13 ✓

When to use which method?

  • Small numbers or exams with simple values: Convert binary → decimal mentally, then decimal → BCD (faster in your head)
  • Large numbers or hardware design: Use Double Dabble (systematic, no mental decimal arithmetic needed)
  • In actual circuits: Double Dabble is implemented in hardware using shift registers and add-3 modules — it’s how BCD converters physically work

Exam tip: If a question says “convert binary to BCD directly (without converting to decimal first),” they want the Double Dabble algorithm. If they just say “convert to BCD,” the decimal→BCD method is fine.

BCD Arithmetic — Addition, Subtraction & Multiplication

Now that we know how to represent numbers in BCD, the natural next question is: how do we do math in BCD? This is one of the most frequently tested topics in exams, and the source of many silly mistakes. Let’s build up from first principles.

BCD Addition — The Core Rules

The fundamental problem: When we add two BCD digits (each 0–9) using a standard 4-bit binary adder, the sum can range from 0 to 19 (max: 9 + 9 + 1 carry = 19). But BCD only allows 0–9 per digit. So we sometimes get invalid BCD results that need correction.

The rule is simple:

\[\boxed{\text{If the 4-bit sum} > 9 \text{ (i.e., } \geq 1010\text{) or there's a carry out, add } 0110 \text{ (=6) to correct it.}}\]

Why add 6? BCD skips 6 codes (1010 through 1111) that binary uses. When a BCD sum overflows past 9, adding 6 jumps over those 6 invalid codes to land on the correct BCD value.

Three cases to understand
Case Sum range Carry out? Sum > 9? Correction BCD carry to next digit?
1. Sum ≤ 9 0–9 No No None needed — already valid BCD No
2. Sum 10–15 10–15 No Yes Add 0110 Yes (always produces carry)
3. Sum 16–19 16–19 Yes N/A Add 0110 Yes

Case 1 — No correction needed: 3 + 4

  0011   (BCD for 3)
+ 0100   (BCD for 4)
------
  0111   (= 7)

Sum = 7 ≤ 9, no carry out → No correction needed

Result: 0111 = BCD 7 ✓

Case 2 — Sum > 9, no carry: 7 + 6

  0111   (BCD for 7)
+ 0110   (BCD for 6)
------
  1101   (= 13 in binary)

Sum = 13 > 9 but no carry out → Add 6 correction:

  1101
+ 0110   (correction)
------
 10011

Split into: 1 (carry to tens) and 0011 (ones digit = 3)

Result: 0001 0011 = BCD 13 ✓

Verify: 7 + 6 = 13 ✓

Case 3 — Carry out from binary addition: 9 + 8

  1001   (BCD for 9)
+ 1000   (BCD for 8)
------
 10001   (= 17, carry out = 1)

Carry out = 1 → Add 6 correction to the lower 4 bits:

  0001   (lower 4 bits of sum)
+ 0110   (correction)
------
  0111

Carry from initial addition = 1

Result: 0001 0111 = BCD 17 ✓

Verify: 9 + 8 = 17 ✓

Case 3 — Another: 9 + 9

  1001   (BCD for 9)
+ 1001   (BCD for 9)
------
 10010   (= 18, carry out = 1)

Carry out = 1 → Add 6 to lower 4 bits:

  0010
+ 0110
------
  1000

Result: 0001 1000 = BCD 18 ✓

Multi-Digit BCD Addition

For numbers with multiple BCD digits, add column by column from right to left, just like normal decimal addition — but in BCD. Carry from one BCD digit propagates to the next.

Add BCD: 68 + 49

Write each digit as a 4-bit BCD group:

  • 68 → 0110 1000
  • 49 → 0100 1001

Step 1 — Add ones column (8 + 9):

  1000   (BCD 8)
+ 1001   (BCD 9)
------
 10001   (= 17, carry out = 1)

Carry out = 1 → Add 6: $0001 + 0110 = 0111$
Ones digit = 0111 (7), carry = 1 to tens column

Step 2 — Add tens column (6 + 4 + carry 1):

  0110   (BCD 6)
+ 0100   (BCD 4)
+ 0001   (carry)
------
  1011   (= 11 > 9)

Sum > 9 → Add 6: $1011 + 0110 = 10001$
Tens digit = 0001 (1), carry = 1 to hundreds column

Step 3 — Hundreds column (just the carry): Hundreds digit = 0001 (1)

Final result: 0001 0001 0111 = BCD 117 ✓
Verify: 68 + 49 = 117 ✓

Add BCD: 285 + 748

  • 285 → 0010 1000 0101
  • 748 → 0111 0100 1000

Ones: 5 + 8

  0101 + 1000 = 1101 (=13 > 9)  → +6: 1101 + 0110 = 10011

Ones = 0011 (3), carry = 1

Tens: 8 + 4 + 1

  1000 + 0100 + 0001 = 1101 (=13 > 9)  → +6: 1101 + 0110 = 10011

Tens = 0011 (3), carry = 1

Hundreds: 2 + 7 + 1

  0010 + 0111 + 0001 = 1010 (=10 > 9)  → +6: 1010 + 0110 = 10000

Hundreds = 0000 (0), carry = 1

Thousands: carry = 1 Thousands = 0001 (1)

Final result: 0001 0000 0011 0011 = BCD 1033 ✓
Verify: 285 + 748 = 1033 ✓

Quick mental check: After each column addition, if the binary sum ≥ 10 (1010) or has carry, add 6 (0110). The corrected sum’s lower 4 bits become the BCD digit, and any carry goes to the next column.

BCD Subtraction — Using Complements

Just as binary subtraction uses 2’s complement, BCD subtraction uses the 10’s complement (or 9’s complement) method. This avoids the need for a separate subtraction circuit — you can subtract by adding the complement.

9’s Complement of a BCD Number

To find the 9’s complement, subtract each decimal digit from 9.

\[\text{9's complement of } N = \underbrace{999...9}_{n \text{ digits}} - N\]

9’s complement of 47:
9 − 4 = 5, 9 − 7 = 2 → 9’s complement = 52

9’s complement of 285:
9 − 2 = 7, 9 − 8 = 1, 9 − 5 = 4 → 9’s complement = 714

10’s Complement of a BCD Number
\[\text{10's complement of } N = 10^n - N = \text{9's complement} + 1\]

10’s complement of 47:
9’s complement = 52, add 1 → 10’s complement = 53

10’s complement of 285:
9’s complement = 714, add 1 → 10’s complement = 715

Verify: 1000 − 285 = 715 ✓

BCD Subtraction Method (A − B)

Step 1: Find the 10’s complement of B (each digit in BCD).
Step 2: Add A + (10’s complement of B) in BCD (using the BCD addition rules above).
Step 3: If there is a carry out from the MSB, discard the carry — the result is the positive answer.
Step 4: If there is NO carry, the result is negative. Take the 10’s complement of the sum to get the magnitude, and add a minus sign.

BCD Subtraction: 83 − 27

Step 1 — 10’s complement of 27:

  • 9’s complement: 9−2=7, 9−7=2 → 72
  • Add 1: 72 + 1 = 73
  • In BCD: 0111 0011

Step 2 — Add 83 + 73 in BCD:

Ones: 3 + 3

  0011 + 0011 = 0110 (=6 ≤ 9) → No correction

Ones = 0110 (6), carry = 0

Tens: 8 + 7

  1000 + 0111 = 1111 (=15 > 9) → +6: 1111 + 0110 = 10101

Tens = 0101 (5), carry = 1

Step 3 — Carry out = 1 → Discard it. Result is positive.

Result: 0101 0110 = BCD 56 ✓
Verify: 83 − 27 = 56 ✓

BCD Subtraction: 32 − 59 (result is negative)

Step 1 — 10’s complement of 59:

  • 9’s complement: 9−5=4, 9−9=0 → 40
  • Add 1: 40 + 1 = 41
  • In BCD: 0100 0001

Step 2 — Add 32 + 41 in BCD:

Ones: 2 + 1

  0010 + 0001 = 0011 (=3 ≤ 9) → No correction

Ones = 0011 (3), carry = 0

Tens: 3 + 4

  0011 + 0100 = 0111 (=7 ≤ 9) → No correction

Tens = 0111 (7), carry = 0

Step 3 — No carry out → Result is negative.

Step 4 — Take 10’s complement of the result (73) to find magnitude:

  • 9’s complement of 73: 9−7=2, 9−3=6 → 26
  • Add 1: 26 + 1 = 27

Result: −27 (in BCD: 0010 0111 with a sign indicator)
Verify: 32 − 59 = −27 ✓

BCD Subtraction: 500 − 168

Step 1 — 10’s complement of 168:

  • 9’s complement: 9−1=8, 9−6=3, 9−8=1 → 831
  • Add 1: 831 + 1 = 832
  • In BCD: 1000 0011 0010

Step 2 — Add 500 + 832 in BCD:

Ones: 0 + 2

  0000 + 0010 = 0010 (=2 ≤ 9) → No correction

Ones = 0010 (2), carry = 0

Tens: 0 + 3

  0000 + 0011 = 0011 (=3 ≤ 9) → No correction

Tens = 0011 (3), carry = 0

Hundreds: 5 + 8

  0101 + 1000 = 1101 (=13 > 9) → +6: 1101 + 0110 = 10011

Hundreds = 0011 (3), carry = 1

Step 3 — Carry out = 1 → Discard. Result is positive.

Result: 0011 0011 0010 = BCD 332 ✓
Verify: 500 − 168 = 332 ✓

BCD Multiplication

BCD multiplication is built on top of BCD addition. The idea mirrors how you multiply decimal numbers by hand: multiply digit by digit and accumulate partial products using BCD addition.

Method
  1. Multiply one BCD digit of the multiplier with the entire multiplicand (treating each as binary, then correcting to BCD).
  2. For each partial product, if any 4-bit result > 9, apply the +6 correction.
  3. Shift partial products left (just like decimal multiplication) and add all partial products using BCD addition.

BCD Multiplication: 7 × 6 (single digit × single digit)

Step 1 — Binary multiply:

  0111 × 0110 = 101010  (= 42 in binary)

Step 2 — Convert result to BCD: 42₁₀ = 0100 0010 (BCD)

Shortcut method — Use repeated BCD addition: 7 × 6 = 7 + 7 + 7 + 7 + 7 + 7, or more practically: 7 × 6 = (7 × 2) × 3 = 14 × 3

But the most exam-friendly approach: just compute 7 × 6 = 42 in decimal, then BCD encode: 0100 0010 ✓

BCD Multiplication: 12 × 7 (multi-digit × single digit)

Think of this as decimal long multiplication:

    1 2   (multiplicand)
  ×   7   (multiplier)
  -----
    8 4

Column by column in BCD:

Ones: 2 × 7 = 14 In BCD: 14 = 0001 0100 → ones digit = 4, carry = 1 to tens column

Tens: 1 × 7 = 7, plus carry 1 = 8 In BCD: 8 = 1000 → tens digit = 8, no carry

Result: 1000 0100 = BCD 84 ✓
Verify: 12 × 7 = 84 ✓

BCD Multiplication: 25 × 13 (multi-digit × multi-digit)

Use standard long multiplication in decimal, then encode in BCD:

      2 5
    × 1 3
    -----
      7 5   (25 × 3 = 75, first partial product)
    2 5 0   (25 × 1 = 25, shifted left, second partial product)
    -----
    3 2 5

Now express in BCD using BCD addition for the partial products:

Partial Product 1: 75 → 0111 0101
Partial Product 2: 250 → 0010 0101 0000

BCD Addition of 75 + 250:

Ones: 5 + 0

  0101 + 0000 = 0101 (=5 ≤ 9) → No correction

Ones = 0101 (5)

Tens: 7 + 5

  0111 + 0101 = 1100 (=12 > 9) → +6: 1100 + 0110 = 10010

Tens = 0010 (2), carry = 1

Hundreds: 0 + 2 + 1(carry)

  0000 + 0010 + 0001 = 0011 (=3 ≤ 9) → No correction

Hundreds = 0011 (3)

Final result: 0011 0010 0101 = BCD 325 ✓
Verify: 25 × 13 = 325 ✓

Exam strategy for BCD multiplication:

  • For single-digit × single-digit: just compute the product mentally, then encode in BCD.
  • For multi-digit: use decimal long multiplication, then verify each intermediate step is valid BCD (apply +6 corrections as needed during addition of partial products).
  • The key skill tested is usually the BCD addition with carry and correction — the multiplication itself is just decimal.

Summary — BCD Arithmetic Quick Reference

Operation Method Key Rule
Addition Add 4-bit groups column by column If sum > 9 or carry out → add 0110 (6)
Subtraction (A−B) Add A + 10’s complement of B Carry = positive result; no carry = negative (take 10’s complement)
Multiplication Decimal long multiplication, BCD-encode partial products, add using BCD addition Each intermediate addition follows the +6 correction rule
9’s complement Subtract each digit from 9 Used as step toward 10’s complement
10’s complement 9’s complement + 1 Used for BCD subtraction

Common mistakes to avoid:

  1. Forgetting to correct when carry out = 1 — Even if the lower 4 bits look fine (e.g., 0001 from 9+8=10001), the carry means correction is needed.
  2. Correcting when not needed — If the sum is ≤ 9 with no carry, do NOT add 6.
  3. Wrong complement — In subtraction, take the complement of the subtrahend (the number being subtracted), not the minuend.
  4. Forgetting to add 1 — 10’s complement = 9’s complement + 1. Missing this gives wrong answers.
  5. Not propagating carries between BCD digits — In multi-digit addition, the carry from the correction (+6) goes to the next BCD digit column.

2421 Code

What does “2421” mean?

Just like 8421, the name “2421” tells you the weight of each bit position:

Bit position:   b₃    b₂    b₁    b₀
Weight:          2      4      2      1

To decode: $\text{Decimal value} = b_3 \times 2 + b_2 \times 4 + b_1 \times 2 + b_0 \times 1$

Notice: The leftmost bit has weight 2 (not 8). The second bit has weight 4. The third bit also has weight 2. So the same decimal value can sometimes be represented in more than one way — but there is a standard assignment (see table below).

Why does 2421 exist?

The 2421 code has a beautiful property: it is self-complementing. This means if you take the 9’s complement of a decimal digit (i.e., $9 - d$) and look up its 2421 code, you get exactly the bitwise complement (flip 0↔1) of the original code.

Self-complementing example:
Decimal 3 in 2421 = 0011
Decimal 6 (which is 9 − 3) in 2421 = 1100
Notice: 0011 flipped = 1100 ✓

This makes subtraction circuits much simpler to design!

Complete 2421 Code Table

Decimal 2421 Code Verification ($b_3$×2 + $b_2$×4 + $b_1$×2 + $b_0$×1) 9’s Complement pair
0 0000 0+0+0+0 = 0 ↔ 9 (1111)
1 0001 0+0+0+1 = 1 ↔ 8 (1110)
2 0010 0+0+2+0 = 2 ↔ 7 (1101)
3 0011 0+0+2+1 = 3 ↔ 6 (1100)
4 0100 0+4+0+0 = 4 ↔ 5 (1011)
5 1011 2+0+2+1 = 5 ↔ 4 (0100)
6 1100 2+4+0+0 = 6 ↔ 3 (0011)
7 1101 2+4+0+1 = 7 ↔ 2 (0010)
8 1110 2+4+2+0 = 8 ↔ 1 (0001)
9 1111 2+4+2+1 = 9 ↔ 0 (0000)

Example — Decode 2421 code 1011:

Bit $b_3$ $b_2$ $b_1$ $b_0$
Value 1 0 1 1
Weight 2 4 2 1
Bit × Weight 1×2 = 2 0×4 = 0 1×2 = 2 1×1 = 1

Sum = 2 + 0 + 2 + 1 = 5 ✓

Example — Verify self-complementing for 2 and 7:

  • 2 in 2421 = 0010 → flip all bits → 1101
  • 7 in 2421 = 1101 ✓
  • 9 − 2 = 7 ✓ — the complement relationship holds!

Key point: In 2421 code, digits 0–4 always start with 0 in the MSB, and digits 5–9 always start with 1 in the MSB. This is a quick way to tell which half of the decimal range a code falls in.

Excess-3 Code (XS-3)

What is Excess-3?

Excess-3 is a non-weighted code (the bit positions do NOT have fixed weights). Instead, it is derived from BCD by a simple rule:

Excess-3 code of a digit = BCD code of that digit + 3

That’s it! Take the BCD (8421) code of any decimal digit and add binary 0011 (which is decimal 3) to it.

Why is it called “Excess-3”?

Because every code word is in “excess” (i.e., 3 more than) the BCD value. If you see an Excess-3 code and want the decimal digit, just subtract 3.

\(\text{Excess-3 code} = \text{BCD code} + 0011\) \(\text{Decimal digit} = \text{Excess-3 interpreted as binary} - 3\)

How to build the table step by step

Let’s compute Excess-3 for decimal 0:
BCD of 0 = 0000
Add 3: 0000 + 0011 = 0011 ← Excess-3 of 0

For decimal 5:
BCD of 5 = 0101
Add 3: 0101 + 0011 = 1000 ← Excess-3 of 5

For decimal 9:
BCD of 9 = 1001
Add 3: 1001 + 0011 = 1100 ← Excess-3 of 9

Complete Excess-3 Table

Decimal BCD (8421) + 3 (0011) = Excess-3 Verify: XS3 value − 3
0 0000 + 0011 0011 3 − 3 = 0 ✓
1 0001 + 0011 0100 4 − 3 = 1 ✓
2 0010 + 0011 0101 5 − 3 = 2 ✓
3 0011 + 0011 0110 6 − 3 = 3 ✓
4 0100 + 0011 0111 7 − 3 = 4 ✓
5 0101 + 0011 1000 8 − 3 = 5 ✓
6 0110 + 0011 1001 9 − 3 = 6 ✓
7 0111 + 0011 1010 10 − 3 = 7 ✓
8 1000 + 0011 1011 11 − 3 = 8 ✓
9 1001 + 0011 1100 12 − 3 = 9 ✓

Excess-3 is also self-complementing! Just like 2421, if you flip all 4 bits of an Excess-3 code, you get the Excess-3 code of the 9’s complement.

Example: Excess-3 of 4 = 0111 → flip → 1000 = Excess-3 of 5 → and 9−4 = 5 ✓

Example — Convert decimal 47 to Excess-3:
Digit 4: BCD = 0100 → 0100 + 0011 = 0111
Digit 7: BCD = 0111 → 0111 + 0011 = 1010
Excess-3 of 47 = 0111 1010

Example — Convert Excess-3 code 1001 0100 back to Decimal:
First group: 1001 → in decimal = 9 → subtract 3 → 6
Second group: 0100 → in decimal = 4 → subtract 3 → 1
Decimal: 61

Invalid Excess-3 values: Since valid Excess-3 codes range from 0011 (for digit 0) to 1100 (for digit 9), the codes 0000, 0001, 0010, 1101, 1110, and 1111 are invalid in Excess-3.

Quick Comparison: 8421 vs 2421 vs Excess-3

Property 8421 (BCD) 2421 Excess-3
Type Weighted Weighted Non-weighted
Weights 8, 4, 2, 1 2, 4, 2, 1 None (BCD + 3)
Self-complementing? No ✗ Yes ✓ Yes ✓
Code for 0 0000 0000 0011
Code for 9 1001 1111 1100
All 0s valid? Yes (=0) Yes (=0) No (invalid)
Main advantage Simple, natural binary Easy subtraction via complement Easy subtraction via complement
Used in Calculators, displays, digital clocks Arithmetic circuits Arithmetic circuits

Exam tip: When a question says “self-complementing code,” the answer is 2421 or Excess-3 (not 8421 BCD). Self-complementing codes simplify subtraction in hardware because taking the 9’s complement is just flipping bits!

Gray Code

Only one bit changes between successive values (useful in error-minimized digital communication and K-Maps).

Binary to Gray conversion:

Gray to Binary conversion:

Decimal Binary Gray
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100

Example 1 — Binary to Gray: Convert (1101)₂ to Gray

Rule: $G_i = B_{i+1} \oplus B_i$, MSB stays same.

  • $G_3 = B_3 = 1$
  • $G_2 = B_3 \oplus B_2 = 1 \oplus 1 = 0$
  • $G_1 = B_2 \oplus B_1 = 1 \oplus 0 = 1$
  • $G_0 = B_1 \oplus B_0 = 0 \oplus 1 = 1$

Result: (1101)₂ = (1011) Gray

Example 2 — Binary to Gray: Convert (1010)₂ to Gray

  • $G_3 = 1$
  • $G_2 = 1 \oplus 0 = 1$
  • $G_1 = 0 \oplus 1 = 1$
  • $G_0 = 1 \oplus 0 = 1$

Result: (1010)₂ = (1111) Gray

Example 3 — Gray to Binary: Convert (1011) Gray to Binary

Rule: $B_{MSB} = G_{MSB}$, then $B_i = B_{i+1} \oplus G_i$.

  • $B_3 = G_3 = 1$
  • $B_2 = B_3 \oplus G_2 = 1 \oplus 0 = 1$
  • $B_1 = B_2 \oplus G_1 = 1 \oplus 1 = 0$
  • $B_0 = B_1 \oplus G_0 = 0 \oplus 1 = 1$

Result: (1011) Gray = (1101)₂ — matches Example 1 above!

1.3 Signed Numbers — 1's & 2's Complement

The Problem: How do we represent negative numbers?

Computers only understand 0s and 1s — there’s no “minus sign” key inside a processor. So we need a clever way to tell the computer that a number is negative using only binary digits.

Over the years, engineers developed three approaches: Sign-Magnitude, 1’s Complement, and 2’s Complement. Let’s understand each one as if you’re seeing them for the first time.

Sign-Magnitude Representation

The idea (simplest approach)

Take the leftmost bit (the MSB — Most Significant Bit) and dedicate it as a sign indicator:

The remaining bits represent the magnitude (the actual value, ignoring sign).

8-bit Sign-Magnitude:
┌──────┬───────────────────┐
│ Sign │   Magnitude       │
│ (1 bit)│  (7 bits)       │
└──────┴───────────────────┘

+25 in 8-bit Sign-Magnitude:

  • Sign = 0 (positive)
  • Magnitude of 25 = 0011001
  • Result: 00011001

−25 in 8-bit Sign-Magnitude:

  • Sign = 1 (negative)
  • Magnitude of 25 = 0011001
  • Result: 10011001

Same magnitude, just the sign bit flipped!

Problem with Sign-Magnitude

There are two representations of zero:

This causes headaches when designing hardware for comparison and addition. Also, adding a positive and negative number requires special circuitry — you can’t just use a simple adder. That’s why this method is rarely used in modern computers.

1’s Complement

The idea

To negate a number, simply flip (invert) every bit: change all 0s to 1s and all 1s to 0s.

Mathematically: \(\text{1's complement of } N = (2^n - 1) - N\)

But don’t worry about the formula — just remember: flip every bit.

Find 1’s complement of 25 (8-bit):

  • Binary of 25: 00011001
  • Flip every bit: 11100110
  • So −25 in 1’s complement = 11100110

Verify: Does this make sense?
Original: 00011001
Complement: 11100110
Add them: 11111111 (all 1s) — this always happens in 1’s complement! ✓

Find 1’s complement of 7 (4-bit):

  • Binary of 7: 0111
  • Flip every bit: 1000
  • So −7 in 1’s complement (4-bit) = 1000

How to tell if a 1’s complement number is positive or negative

Same rule as sign-magnitude: look at the MSB.

The same old problem

1’s complement STILL has two zeros:

This two-zero problem complicates hardware design, which led to the invention of…

2’s Complement (Most Widely Used)

The idea

\[\text{2's complement} = \text{1's complement} + 1 = 2^n - N\]

In plain English: flip all bits, then add 1. That’s it!

This small change (adding 1 after flipping) elegantly solves the two-zero problem and makes hardware addition/subtraction work with a single circuit.

Find 2’s complement of (25)₁₀ in 8-bit:

  • Step 1 — Write binary of 25: 00011001
  • Step 2 — Flip every bit (1’s complement): 11100110
  • Step 3 — Add 1: 11100110 + 1 = 11100111

So −25 in 2’s complement = 11100111

Example 2 — Find 2’s complement of (100)₁₀ in 8-bit:

  • Binary of 100: 01100100
  • 1’s complement: 10011011
  • Add 1: 10011100

So -100 in 2’s complement = 10011100

Example 3 — Interpret 2’s complement 11010110 (8-bit): What decimal number is this?

  • MSB = 1 → the number is negative
  • To find its magnitude, take the 2’s complement again: flip → 00101001, add 1 → 00101010
  • 00101010 = 32 + 8 + 2 = 42
  • Value = −42

Why does 2’s complement solve the two-zero problem?

Let’s try to find −0 in 2’s complement (8-bit):

  • Binary of 0: 00000000
  • Flip: 11111111
  • Add 1: 11111111 + 1 = 100000000 (9 bits!)
  • In 8 bits, the carry is discarded → result = 00000000
  • So −0 = +0 = 00000000 — there’s only one zero! ✓

This means 2’s complement has one extra negative number that other systems don’t have. For 8 bits, the range extends to −128 (but only up to +127).

Shortcut for finding 2’s complement: Starting from the rightmost bit (LSB), copy all bits up to and including the first 1, then flip every remaining bit.

Example: 00011001 → scan from right:

  • Copy 1 → _______1
  • Copy 0 → ______01
  • Copy 0 → _____001
  • Now flip the rest: 11100___ → combine: 11100111 ✓

This is faster than “flip + add 1” and avoids any carry computation!

Why is 2’s complement used everywhere?

The killer feature: Addition and subtraction use the exact same circuit!
To subtract B from A, the computer just adds A to the 2’s complement of B.
No special subtractor hardware needed — just one adder + a complement unit.

This is why virtually every modern processor (Intel, ARM, RISC-V) uses 2’s complement.

Range of n-bit Numbers

How many numbers can you represent with $n$ bits? It depends on the representation:

Representation Range # of unique values Two zeros?
Unsigned $0$ to $2^n - 1$ $2^n$ N/A
Sign-Magnitude $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$ $2^n - 1$ Yes (+0 and −0)
1’s Complement $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$ $2^n - 1$ Yes (+0 and −0)
2’s Complement $-2^{n-1}$ to $+(2^{n-1}-1)$ $2^n$ No (only one zero)

For 8 bits (n=8):

Representation Min Max
Unsigned 0 255
Sign-Magnitude −127 +127
1’s Complement −127 +127
2’s Complement −128 +127

Notice 2’s complement gets one extra negative value (−128) because it doesn’t waste a bit pattern on −0.

Exam trap: Students often forget that the positive range of 2’s complement is asymmetric — the negative side goes one further. For 8 bits: −128 to +127 (not −128 to +128).

1.4 Binary Arithmetic

Why learn binary arithmetic?

Everything inside a computer — from 3 + 5 to rendering a 3D game — ultimately comes down to binary arithmetic done by tiny circuits called adders. Understanding how binary addition and subtraction work at the bit level is the foundation for designing these circuits (which we’ll do in Unit II).

Binary Addition

Binary addition works exactly like decimal addition, except you only have two digits (0 and 1). When a column adds up to 2 or more, you carry to the next column — just like carrying in decimal when a column exceeds 9.

The 4 basic rules:

A B Sum Carry
0 + 0   0 0
0 + 1   1 0
1 + 0   1 0
1 + 1   0 1 (carry!)

Think of it this way: $1 + 1 = 2$, but in binary, 2 is written as 10. So the sum digit is 0 and we carry 1 to the next column.

When three bits are added (A + B + Carry from previous column):

Add binary: 1011 + 0110 (decimal: 11 + 6)

  Carry:  1 1 0 0
           1 0 1 1    (11)
         + 0 1 1 0    (6)
         ---------
         1 0 0 0 1    (17)

Step by step (right to left):

  • Column 0: $1 + 0 = 1$, carry 0
  • Column 1: $1 + 1 = 10$ → write 0, carry 1
  • Column 2: $0 + 1 + \text{carry }1 = 10$ → write 0, carry 1
  • Column 3: $1 + 0 + \text{carry }1 = 10$ → write 0, carry 1
  • Final carry: 1

Result: 10001₂ = 17₁₀ ✓

Add binary: 11111 + 00001 (decimal: 31 + 1)

  Carry:  1 1 1 1 0
           1 1 1 1 1    (31)
         + 0 0 0 0 1    (1)
         -----------
         1 0 0 0 0 0    (32)

All the carries cascade from right to left — like a chain reaction. This is called ripple carry and it’s exactly how the ripple carry adder circuit works.

Binary Subtraction using 2’s Complement

Here’s the beautiful part: computers don’t subtract! They convert subtraction into addition using 2’s complement.

To compute $A - B$:

  1. Find the 2’s complement of B (flip bits + add 1)
  2. Add $A$ + (2’s complement of B)
  3. Interpret the result:
    • If there’s a carry out (extra bit on the left) → result is positive. Discard the carry.
    • If no carry out → result is negative. Take the 2’s complement of the result to find the magnitude.

Why does this work? The 2’s complement of B represents −B. So adding A + (−B) is the same as A − B. The carry-out tells you the sign: present = positive, absent = negative.

Compute 13 − 25 in 8-bit 2’s complement:

  • 13 = 00001101
  • 25 = 00011001 → 2’s comp = 11100111
  • Add: 00001101 + 11100111 = 11110100
  • No carry out → result is negative
  • 2’s complement of 11110100 = 00001100 = 12
  • Answer: −12 ✓

Example 2 — Compute 50 − 30 in 8-bit 2’s complement:

  • 50 = 00110010
  • 30 = 00011110 → 2’s comp = 11100010
  • Add: 00110010 + 11100010 = 100010100
  • Carry out = 1 → result is positive, discard carry
  • Result: 00010100 = 20
  • Answer: +20 ✓

Example 3 — Compute −20 − 35 in 8-bit 2’s complement:

  • −20 → 2’s comp of 20 (00010100) = 11101100
  • −35 → 2’s comp of 35 (00100011) = 11011101
  • Add: 11101100 + 11011101 = 111001001
  • Carry out = 1 → discard carry
  • Result: 11001001 → MSB=1 → negative
  • 2’s comp of 11001001: flip → 00110110, +1 → 00110111 = 55
  • Answer: −55 ✓

Overflow Detection

What is overflow?

Overflow happens when the result of an arithmetic operation is too large (or too small) to fit in the available number of bits.

For example, with 8-bit 2’s complement, you can only represent −128 to +127. If you try to compute 100 + 60 = 160, the result exceeds +127 — overflow!

When does overflow occur?

Overflow can ONLY happen when adding two numbers of the same sign:

Adding a positive and negative number NEVER overflows (the result is between the two, so it always fits).

How to detect overflow (two equivalent rules)

  1. Sign rule: If $A$ and $B$ have the same sign, but the result has a different sign → overflow
  2. Carry rule: Overflow if the carry into the MSB ≠ carry out of the MSB (formally: $C_{in,MSB} \oplus C_{out,MSB} = 1$)

Overflow example: 100 + 60 in 8-bit 2’s complement

  • 100 = 01100100
  • 60 = 00111100
  • Add: 01100100 + 00111100 = 10100000
  • Result = 10100000 → MSB = 1 → this is interpreted as a negative number!
  • Both inputs were positive, but the result is negative → OVERFLOW ✓

The “correct” answer (160) exceeds the 8-bit 2’s complement range of −128 to +127.

No overflow: 50 − 30 = 20

  • 50 = 00110010 (positive)
  • −30 = 2’s complement of 30 = 11100010 (negative)
  • We’re adding a positive and negative number → overflow is impossible
  • Indeed: 00110010 + 11100010 = 100010100 → discard carry → 00010100 = 20 ✓

Overflow ≠ Carry out! A carry out of the MSB does NOT necessarily mean overflow. For example, adding −20 and −35 produces a carry out, but the result (−55) is valid. Check the sign rule, not just the carry.

Binary Subtraction — Direct Borrow Method

Before 2’s complement, let’s also understand the classical borrow method — it works just like decimal subtraction but in base 2.

The 4 basic rules:

A B Difference Borrow
0 − 0   0 0
1 − 0   1 0
1 − 1   0 0
0 − 1   1 1 (borrow!)

When you try to do 0 − 1, you borrow 1 from the next higher column (which is worth 2 in that column). So it becomes 2 − 1 = 1, but the next column is reduced by 1.

Subtract binary: 1101 − 0110 (decimal: 13 − 6)

  Borrow:    1 1 0
             1 1 0 1    (13)
           − 0 1 1 0    (6)
           ---------
             0 1 1 1    (7)

Step by step (right to left):

  • Column 0: $1 − 0 = 1$
  • Column 1: $0 − 1$ → can’t do! Borrow from column 2. After borrowing: $10 − 1 = 1$ (that’s $2-1=1$)
  • Column 2: Column 2 was 1, but we lent 1, so it’s now 0. $0 − 1$ → can’t do! Borrow from column 3. After borrowing: $10 − 1 = 1$
  • Column 3: Was 1, lent 1, so $0 − 0 = 0$

Result: 0111₂ = 7₁₀ ✓

Subtract binary: 10000 − 00111 (decimal: 16 − 7)

  Borrow:  1 1 1 1
           1 0 0 0 0    (16)
         − 0 0 1 1 1    (7)
         -----------
           0 1 0 0 1    (9)

Notice how the borrow cascades from column 0 all the way to column 4 (the only column with a 1). This is similar to how borrowing cascades in decimal when you subtract from a number like 10000 − 1.

When to use which method?

  • Borrow method: Good for unsigned numbers and for understanding the concept directly.
  • 2’s complement method: How computers actually do it — no separate subtraction circuit needed! One adder handles both addition and subtraction.
  • Exams: Know both methods. The question will specify which one to use.

1’s Complement Addition (End-Around Carry)

Some older systems use 1’s complement for subtraction. The process is similar to 2’s complement, but with one extra twist.

Method for A − B:

  1. Find the 1’s complement of B (just flip all the bits — no +1 step)
  2. Add A + (1’s complement of B)
  3. If there’s a carry out → add the carry back to the result (end-around carry). Result is positive.
  4. If no carry out → result is negative. Take the 1’s complement of the result.

Compute 13 − 6 using 1’s complement (5-bit numbers):

  • 13 = 01101
  • 6 = 00110 → 1’s complement = 11001
  • Add: 01101 + 11001 = 100110
  • Carry out = 1 → End-around carry: add 1 to result
  • 00110 + 1 = 00111 = 7
  • Answer: +7 ✓

Compute 6 − 13 using 1’s complement (5-bit numbers):

  • 6 = 00110
  • 13 = 01101 → 1’s complement = 10010
  • Add: 00110 + 10010 = 11000
  • No carry out → result is negative
  • 1’s complement of 11000 = 00111 = 7
  • Answer: −7 ✓

1’s complement vs 2’s complement — key difference:

  • 1’s complement: flip bits, end-around carry if carry out
  • 2’s complement: flip bits + add 1, discard carry if carry out
  • 2’s complement is preferred because there’s no end-around carry step, and it has only one representation of zero.

Binary Multiplication — Shift and Add

Binary multiplication is much simpler than decimal multiplication because each multiplier bit is either 0 or 1. There’s no multiplication table to memorize beyond:

\[0 \times n = 0 \qquad 1 \times n = n\]

The method is identical to decimal long multiplication:

  1. Take each bit of the multiplier (bottom number), starting from the LSB
  2. If the bit is 1, write down the multiplicand; if 0, write all zeros
  3. Shift left by one position for each subsequent bit (just like decimal)
  4. Add all the partial products using binary addition

Multiply binary: 1101 × 1010 (decimal: 13 × 10)

              1 1 0 1    (13 = multiplicand)
            × 1 0 1 0    (10 = multiplier)
          -----------
          0 0 0 0 0 0    ← bit 0 of multiplier = 0, so all zeros
        0 1 1 0 1 0      ← bit 1 = 1, so write multiplicand, shifted left by 1
      0 0 0 0 0 0        ← bit 2 = 0, so all zeros
    1 1 0 1 0 0 0        ← bit 3 = 1, so write multiplicand, shifted left by 3
  -----------------
    1 0 0 0 0 0 1 0      (130)

Step-by-step addition of non-zero partial products:

      0 1 1 0 1 0    (13 × 2  = 26)
  + 1 1 0 1 0 0 0    (13 × 8  = 104)
  ---------------
    1 0 0 0 0 0 1 0  (130)

Result: 10000010₂ = 130₁₀ ✓
Verify: 13 × 10 = 130 ✓

Multiply binary: 111 × 101 (decimal: 7 × 5)

          1 1 1    (7)
        × 1 0 1    (5)
        -------
          1 1 1    ← bit 0 = 1 → copy multiplicand
        0 0 0 0    ← bit 1 = 0 → all zeros
      1 1 1 0 0    ← bit 2 = 1 → shifted left by 2
      ---------
      1 0 0 0 1 1  (35)

Addition:

        0 0 1 1 1    (7)
      + 1 1 1 0 0    (28)
      -----------
        1 0 0 0 1 1  (35)

Result: 100011₂ = 35₁₀ ✓

Multiply binary: 1111 × 1111 (decimal: 15 × 15)

              1 1 1 1    (15)
            × 1 1 1 1    (15)
          -----------
              1 1 1 1    ← bit 0 = 1
            1 1 1 1 0    ← bit 1 = 1, shifted left by 1
          1 1 1 1 0 0    ← bit 2 = 1, shifted left by 2
        1 1 1 1 0 0 0    ← bit 3 = 1, shifted left by 3
      -----------------
        1 1 1 0 0 0 0 1  (225)

Adding partial products step by step:

    0 0 0 1 1 1 1    (15)
  + 0 0 1 1 1 1 0    (30)
  ---------------
    0 1 0 1 1 0 1    (45)
  + 0 1 1 1 1 0 0    (60)
  ---------------
    1 1 0 1 0 0 1    (105)
  + 1 1 1 1 0 0 0    (120)
  ---------------
  1 1 1 0 0 0 0 1    (225)

Result: 11100001₂ = 225₁₀ ✓

Key insight: Multiplying two $n$-bit numbers can produce a result up to $2n$ bits long. Here, two 4-bit numbers give an 8-bit result.

Why binary multiplication is easy:

  • No multiplication tables to remember — just 0×n=0 and 1×n=n
  • Each partial product is either the multiplicand or zero
  • The only hard part is the addition of partial products (where carries can cascade)
  • This is exactly how digital multiplier circuits work: shift registers + adders

For signed multiplication: If the numbers are in 2’s complement, you must sign-extend them to double the bit width before multiplying, OR use specialized algorithms like Booth’s algorithm. For this course, most multiplication questions use unsigned numbers.

Binary Division — Long Division Method

Binary division follows the same long division algorithm you learned in school for decimal, but it’s actually easier because at each step, the quotient bit is either 0 or 1 — no guessing needed!

Algorithm:

  1. Compare the divisor with the current partial dividend (the top digits)
  2. If the divisor fits (≤ partial dividend) → quotient bit = 1, subtract the divisor
  3. If the divisor doesn’t fit (> partial dividend) → quotient bit = 0, bring down the next bit
  4. Repeat until all bits are processed
  5. Whatever remains is the remainder

Divide binary: 10110 ÷ 11 (decimal: 22 ÷ 3)

              0 1 1 1    ← Quotient (7)
           --------
     11 │ 1 0 1 1 0
          - 0 0          Step 1: 1 < 11 → quotient = 0, bring down
          -----
            1 0          Step 2: 10 < 11 → quotient = 0, bring down
          - 0 0
          -----
            1 0 1        Step 3: 101 ≥ 11 → quotient = 1
          -   1 1
          -----
              1 0 1      Step 4: 101 ≥ 11 → quotient = 1
            -   1 1
            -----
                1 0 0    Step 5: 100 ≥ 11 → quotient = 1
              -   1 1
              -----
                  0 1    ← Remainder (1)

Result: Quotient = 111₂ (7), Remainder = 01₂ (1) ✓
Verify: 22 ÷ 3 = 7 remainder 1 ✓ (7 × 3 + 1 = 22)

Divide binary: 11010 ÷ 101 (decimal: 26 ÷ 5)

              1 0 1      ← Quotient (5)
           --------
    101 │ 1 1 0 1 0
          - 1 0 1        Step 1: 110 ≥ 101 → quotient = 1, subtract
          -----
              0 1 1      Step 2: 011 < 101 → quotient = 0, bring down
            - 0 0 0
            -----
              0 1 1 0    Step 3: 0110 ≥ 101 → quotient = 1, subtract
            -   1 0 1
            -------
                0 0 1    ← Remainder (1)

Result: Quotient = 101₂ (5), Remainder = 001₂ (1) ✓
Verify: 26 ÷ 5 = 5 remainder 1 ✓ (5 × 5 + 1 = 26)

Divide binary: 110100 ÷ 1000 (decimal: 52 ÷ 8)

              1 1 0      ← Quotient (6)
           ----------
   1000 │ 1 1 0 1 0 0
           - 1 0 0 0      Step 1: 1101 ≥ 1000 → quotient = 1
           -------
             1 0 1 0      Step 2: 1010 ≥ 1000 → quotient = 1
           - 1 0 0 0
           -------
               0 1 0 0    Step 3: 0100 < 1000 → quotient = 0
             - 0 0 0 0
             -------
               0 1 0 0    ← Remainder (4)

Result: Quotient = 110₂ (6), Remainder = 100₂ (4) ✓
Verify: 52 ÷ 8 = 6 remainder 4 ✓ (6 × 8 + 4 = 52)

Why binary division is simpler than decimal:

  • At each step, you only need to decide: does the divisor fit? (Yes/No)
  • In decimal, you’d have to figure out “how many times does 37 go into 258?” — could be any digit 1–9
  • In binary, each quotient bit is simply 1 (fits) or 0 (doesn’t fit)
  • The subtraction at each step is also binary subtraction

Division by zero is undefined in all number systems. In hardware, dividing by zero causes a trap/exception (the CPU halts the operation and signals an error).

Summary — Binary Arithmetic Quick Reference

Operation Method Key Rule Result Size
Addition Column-by-column, carry up $1+1=10$ (sum 0, carry 1) $n$ bits + possible carry
Subtraction (borrow) Column-by-column, borrow from left $0-1$: borrow 1 from next column $n$ bits
Subtraction (2’s comp) A + (2’s comp of B) Carry → positive; no carry → negative $n$ bits
Subtraction (1’s comp) A + (1’s comp of B) End-around carry if carry out $n$ bits
Multiplication Shift and add partial products Each partial product is 0 or multiplicand Up to $2n$ bits
Division Long division (compare, subtract) Quotient bit: 1 if divisor fits, 0 if not Quotient + Remainder
Overflow Check signs or carry in/out of MSB Same-sign inputs + different-sign result Detected by XOR of carries

Common exam mistakes in binary arithmetic:

  1. Forgetting carries in addition — Always track carries column by column.
  2. Wrong 2’s complement — Remember: flip ALL bits, then add 1 to the entire result.
  3. Confusing overflow with carry out — They are NOT the same thing!
  4. In multiplication, not shifting partial products — Each row shifts one position left.
  5. In division, forgetting to bring down — When the divisor doesn’t fit, the quotient bit is 0 and you bring down the next bit.
  6. Applying signed rules to unsigned numbers — Unsigned numbers use full range (0 to $2^n-1$), no overflow in the signed sense.

1.5 Boolean Algebra & Logic Gates

What is Boolean Algebra?

In regular algebra, variables can be any number ($x = 3.7$, $y = -42$, etc.). In Boolean algebra, every variable can only be one of two values: 0 (false) or 1 (true).

Boolean algebra was invented by George Boole in the 1850s — long before computers existed! It became the mathematical foundation of all digital circuits.

Instead of the arithmetic operations you’re used to (add, subtract, multiply), Boolean algebra uses three fundamental operations:

What is a Logic Gate?

A logic gate is a tiny electronic circuit that performs one Boolean operation. It takes 1 or 2 input signals (voltages representing 0 or 1) and produces one output signal.

Just like how words are made from letters, and sentences from words — every digital circuit in existence (from a simple calculator to a billion-transistor CPU) is built by connecting logic gates together.

The 7 Basic Logic Gates

Gate Symbol/Notation Boolean Expression Plain English Description
AND · $Y = A \cdot B$ Output is 1 only when ALL inputs are 1 — like a series circuit: both switches must be ON
OR + $Y = A + B$ Output is 1 when ANY input is 1 — like a parallel circuit: either switch can turn the light ON
NOT ‾ (overbar) $Y = \overline{A}$ Flips (inverts) the input: 0 becomes 1, 1 becomes 0
NAND ↑ $Y = \overline{A \cdot B}$ “NOT-AND” — does AND, then flips the result. Output is 0 only when both inputs are 1
NOR ↓ $Y = \overline{A + B}$ “NOT-OR” — does OR, then flips the result. Output is 1 only when both inputs are 0
XOR ⊕ $Y = A \oplus B$ “Exclusive OR” — output is 1 when inputs are different
XNOR ⊙ $Y = \overline{A \oplus B}$ “Exclusive NOR” — output is 1 when inputs are the same (equality detector!)

Truth Tables — Understanding Each Gate

A truth table lists every possible combination of inputs alongside the output. For 2 inputs, there are $2^2 = 4$ rows.

AND Gate — “Both must be 1”:

A B A·B Why?
0 0 0 Neither is 1
0 1 0 A is not 1
1 0 0 B is not 1
1 1 1 Both are 1 ✓

Real-world analogy: A bank vault requires two keys turned simultaneously. Only when Person A AND Person B both turn their keys (both = 1) does the vault open (output = 1).

OR Gate — “At least one must be 1”:

A B A+B Why?
0 0 0 Neither is 1
0 1 1 B is 1 ✓
1 0 1 A is 1 ✓
1 1 1 Both are 1 ✓

Analogy: An alarm goes off if Door A OR Door B is opened. Any one is enough.

NOT Gate (Inverter) — “Flip it”:

A $\overline{A}$
0 1
1 0

XOR Gate — “Different = 1, Same = 0”:

A B A⊕B Why?
0 0 0 Same → 0
0 1 1 Different → 1 ✓
1 0 1 Different → 1 ✓
1 1 0 Same → 0

Analogy: A hallway light controlled by two switches at opposite ends. Flipping either one (but not both or neither) toggles the light. This is literally how XOR works!

Quick memory trick for XOR: X stands for “eXclusive” — it excludes the case where both are the same. Output is 1 only when the inputs are exclusively different.

NAND Gate — “NOT of AND”:

A B $\overline{A \cdot B}$
0 0 1
0 1 1
1 0 1
1 1 0

Notice: NAND is the exact opposite of AND — every output is flipped.

NOR Gate — “NOT of OR”:

A B $\overline{A + B}$
0 0 1
0 1 0
1 0 0
1 1 0

NOR is the exact opposite of OR.

Universal Gates: NAND and NOR

NAND and NOR are called “universal gates” because you can build any Boolean function using just NAND gates alone, or just NOR gates alone. No other gate type is needed!

This is hugely important in chip manufacturing — factories can be optimized to produce only one type of gate.

How to build every gate from NAND only

Here’s the magic — just using NAND, you can create NOT, AND, and OR:

NOT from NAND: Feed the same input to both pins → $\overline{A \cdot A} = \overline{A}$

AND from NAND: NAND gives $\overline{AB}$, so NAND it with itself to get $\overline{\overline{AB}} = AB$

OR from NAND: First invert each input, then NAND them: $\overline{\overline{A} \cdot \overline{B}} = A + B$ (by De Morgan’s!)

How to build every gate from NOR only

NOT from NOR: $\overline{A + A} = \overline{A}$

OR from NOR: NOR gives $\overline{A+B}$, then NOR with itself: $\overline{\overline{A+B}} = A+B$

AND from NOR: Invert each input, then NOR: $\overline{\overline{A} + \overline{B}} = AB$ (by De Morgan’s!)

1.6 Boolean Laws & Theorems

Why do we need Boolean Laws?

When you design a digital circuit from a truth table, the raw Boolean expression is often big and messy — it might need 20 gates to implement. Using Boolean laws, you can simplify the expression to need only 5 gates. Fewer gates = cheaper, faster, less power.

These laws are the Boolean equivalent of the algebraic rules you already know (like $a + 0 = a$ or $a \times 1 = a$).

Fundamental Laws (The Building Blocks)

Every law has an AND form and an OR form — they come in pairs (this is called duality).

Law AND Form OR Form Intuitive Meaning
Identity $A \cdot 1 = A$ $A + 0 = A$ AND-ing with 1 or OR-ing with 0 changes nothing
Null $A \cdot 0 = 0$ $A + 1 = 1$ AND-ing with 0 kills everything; OR-ing with 1 makes everything 1
Idempotent $A \cdot A = A$ $A + A = A$ Doing the same thing twice is the same as doing it once
Complement $A \cdot \overline{A} = 0$ $A + \overline{A} = 1$ A variable AND its opposite = 0; OR its opposite = 1
Involution $\overline{\overline{A}} = A$ — “Double negative cancels out”
Commutative $A \cdot B = B \cdot A$ $A + B = B + A$ Order doesn’t matter
Associative $(AB)C = A(BC)$ $(A+B)+C = A+(B+C)$ Grouping doesn’t matter
Distributive $A(B+C) = AB+AC$ $A+BC = (A+B)(A+C)$ “Expand brackets” — but notice the OR form is unusual!
Absorption $A(A+B) = A$ $A + AB = A$ The smaller term “absorbs” the bigger one

The Duality Principle: Any Boolean theorem remains valid if you swap AND↔OR and swap 0↔1 throughout. This is why every law has two forms — you get the second one for free!

Let’s see WHY Absorption works: $A + AB = A$

Think about it logically: “A is true, OR (A is true AND B is true).”

  • If A = 0: whole expression = 0 + 0·B = 0
  • If A = 1: whole expression = 1 + 1·B = 1 (regardless of B!)

So the output depends only on A. The $AB$ term is redundant — it’s “absorbed.”

Algebraic proof:
$A + AB = A(1 + B) = A \cdot 1 = A$ ✓ (using Null law: $1+B=1$)

The unusual distributive law: $A + BC = (A+B)(A+C)$

This one doesn’t exist in regular algebra! Let’s verify with truth table:

A B C $BC$ $A+BC$ $A+B$ $A+C$ $(A+B)(A+C)$ Match?
0 0 0 0 0 0 0 0 ✓
0 0 1 0 0 0 1 0 ✓
0 1 0 0 0 1 0 0 ✓
0 1 1 1 1 1 1 1 ✓
1 0 0 0 1 1 1 1 ✓
1 0 1 0 1 1 1 1 ✓
1 1 0 0 1 1 1 1 ✓
1 1 1 1 1 1 1 1 ✓

They’re equal in all 8 rows. ✓

De Morgan’s Theorems

These are arguably the most important theorems in Boolean algebra. They tell you how to “break open” a NOT that covers an entire expression.

\[\overline{A \cdot B} = \overline{A} + \overline{B} \quad \text{(De Morgan's First Theorem)}\] \[\overline{A + B} = \overline{A} \cdot \overline{B} \quad \text{(De Morgan's Second Theorem)}\]

How to remember De Morgan’s: “Break the bar, change the sign.”

When you move a NOT bar from covering an entire expression to individual variables:

  1. “Break the bar” — put a separate NOT over each variable
  2. “Change the sign” — swap AND↔OR

This extends to any number of variables: \(\overline{A \cdot B \cdot C \cdot D} = \overline{A} + \overline{B} + \overline{C} + \overline{D}\) \(\overline{A + B + C + D} = \overline{A} \cdot \overline{B} \cdot \overline{C} \cdot \overline{D}\)

Verify De Morgan’s first theorem with a truth table:

A B $AB$ $\overline{AB}$ $\overline{A}$ $\overline{B}$ $\overline{A}+\overline{B}$ Match?
0 0 0 1 1 1 1 ✓
0 1 0 1 1 0 1 ✓
1 0 0 1 0 1 1 ✓
1 1 1 0 0 0 0 ✓

$\overline{AB}$ and $\overline{A}+\overline{B}$ give the same output for all inputs. ✓

Useful Simplification Identities

These are “power tools” that come up again and again in exam problems:

Identity Why it works
$A + \overline{A}B = A + B$ Think: “If A is true, done. If A is false, then we need B.” So the condition reduces to “A or B.”
$A(\overline{A}+B) = AB$ Expand: $A\overline{A} + AB = 0 + AB = AB$
$AB + A\overline{B} = A$ Factor: $A(B+\overline{B}) = A \cdot 1 = A$ — a variable paired with both forms of another simplifies away
$(A+B)(\overline{A}+B) = B$ Factor out B: same idea as above in POS form
$A \oplus B = A\overline{B} + \overline{A}B$ This is the definition of XOR — exactly one must be 1
$A \oplus B = \overline{A \odot B}$ XOR and XNOR are complements of each other

Simplify: $F = A\overline{B}C + A\overline{B}\overline{C} + AB\overline{C} + ABC$

$= A\overline{B}(C + \overline{C}) + AB(\overline{C} + C)$ $= A\overline{B} \cdot 1 + AB \cdot 1$ $= A\overline{B} + AB$ $= A(\overline{B} + B) = A$

Result: $F = A$

Simplify: $F = \overline{A}\overline{B}C + \overline{A}BC + A\overline{B}C + ABC$

$= \overline{A}C(\overline{B} + B) + AC(\overline{B} + B)$ $= \overline{A}C + AC$ $= C(\overline{A} + A) = C$

Result: $F = C$

Simplify using De Morgan’s: $F = \overline{\overline{A}B + A\overline{B}}$

Apply De Morgan’s: $F = \overline{\overline{A}B} \cdot \overline{A\overline{B}}$

Apply De Morgan’s again to each term: $= (A + \overline{B})(\overline{A} + B)$

Expand: $= A\overline{A} + AB + \overline{A}\overline{B} + \overline{B}B$ $= 0 + AB + \overline{A}\overline{B} + 0$ $= AB + \overline{A}\overline{B}$

Result: $F = AB + \overline{A}\overline{B} = \overline{A \oplus B}$ (XNOR)

1.7 Canonical Forms — SOP & POS

The Big Picture: From Truth Table to Expression

Every Boolean function can be defined by a truth table. But a truth table isn’t a formula you can simplify or build a circuit from. We need to convert it into a Boolean expression. There are two standard ways to do this:

  1. SOP (Sum of Products) — look at the rows where output = 1, write AND terms for each, then OR them together
  2. POS (Product of Sums) — look at the rows where output = 0, write OR terms for each, then AND them together

The “canonical” form means every variable appears in every term — nothing is simplified yet.

Minterms & Maxterms — The Building Blocks

What is a Minterm?

A minterm is an AND term where every variable appears exactly once (either normal or complemented). Each minterm equals 1 for exactly one row of the truth table.

Think of it as a “fingerprint” for one specific input combination.

What is a Maxterm?

A maxterm is an OR term where every variable appears exactly once. Each maxterm equals 0 for exactly one row of the truth table.

A maxterm is the complement (opposite) of the corresponding minterm.

Naming convention

Complete table for 3 variables (A, B, C)

Row A B C Minterm ($m_i$) How to build it Maxterm ($M_i$) How to build it
0 0 0 0 $\overline{A}\overline{B}\overline{C}$ All 0 → all complemented, AND $A+B+C$ All 0 → all normal, OR
1 0 0 1 $\overline{A}\overline{B}C$ C=1 → C normal; A,B=0 → complemented $A+B+\overline{C}$ C=1 → C complemented
2 0 1 0 $\overline{A}B\overline{C}$   $A+\overline{B}+C$  
3 0 1 1 $\overline{A}BC$   $A+\overline{B}+\overline{C}$  
4 1 0 0 $A\overline{B}\overline{C}$   $\overline{A}+B+C$  
5 1 0 1 $A\overline{B}C$   $\overline{A}+B+\overline{C}$  
6 1 1 0 $AB\overline{C}$   $\overline{A}+\overline{B}+C$  
7 1 1 1 $ABC$ All 1 → all normal, AND $\overline{A}+\overline{B}+\overline{C}$ All 1 → all complemented, OR

How to write a minterm: Look at the binary values. Where the variable is 1, write it normally. Where it’s 0, write it complemented (with a bar). Then AND them all together.

How to write a maxterm: The opposite rule! Where the variable is 1, write it complemented. Where it’s 0, write it normally. Then OR them all together.

In other words: minterms and maxterms are built with opposite complementation rules.

Sum of Products (SOP) — Canonical Form

To build the canonical SOP:

  1. Look at each row where output F = 1
  2. Write the minterm for that row
  3. OR (add) all the minterms together

This is called “sum of products” because it’s a sum (OR) of product (AND) terms.

\[F(A,B,C) = \sum m(1, 3, 5, 7) = m_1 + m_3 + m_5 + m_7\]

Build SOP for this truth table:

A B C F
0 0 0 0
0 0 1 1 ← $m_1$
0 1 0 0
0 1 1 1 ← $m_3$
1 0 0 0
1 0 1 1 ← $m_5$
1 1 0 0
1 1 1 1 ← $m_7$

F = 1 at rows 1, 3, 5, 7, so:

\[F = \overline{A}\overline{B}C + \overline{A}BC + A\overline{B}C + ABC = \sum m(1,3,5,7)\]

(If you look carefully, F = 1 whenever C = 1, so this simplifies to just $F = C$. But the canonical form lists all minterms.)

Product of Sums (POS) — Canonical Form

To build the canonical POS:

  1. Look at each row where output F = 0
  2. Write the maxterm for that row
  3. AND (multiply) all the maxterms together

This is called “product of sums” because it’s a product (AND) of sum (OR) terms.

\[F(A,B,C) = \prod M(0, 2, 4, 6)\]

SOP ↔ POS conversion: The minterm numbers in SOP are the ones missing from POS, and vice versa. They’re complements!

If $F = \sum m(1,3,5,7)$ then $F = \prod M(0,2,4,6)$
(The minterms where F=1 become the “not listed” maxterms, and the rows where F=0 become the maxterms.)

Converting Between Forms

Express $F = AB + \overline{A}C$ in canonical SOP (3 variables A, B, C):

$AB = AB(C + \overline{C}) = ABC + AB\overline{C}$ → minterms 7, 6

$\overline{A}C = \overline{A}C(B + \overline{B}) = \overline{A}BC + \overline{A}\overline{B}C$ → minterms 3, 1

\[F = \sum m(1, 3, 6, 7)\]

Express $F = \overline{A}B + BC$ in canonical SOP (3 variables A, B, C):

$\overline{A}B = \overline{A}B(C + \overline{C}) = \overline{A}BC + \overline{A}B\overline{C}$ → minterms 3, 2

$BC = BC(A + \overline{A}) = ABC + \overline{A}BC$ → minterms 7, 3

Combine (remove duplicate $m_3$): \(F = \sum m(2, 3, 7)\)

Canonical POS: Missing minterms are 0, 1, 4, 5, 6 → \(F = \prod M(0, 1, 4, 5, 6)\)

Express $F(A,B,C) = \sum m(0, 3, 5, 6)$ as a POS expression:

Minterms where F=1: 0, 3, 5, 6
Minterms where F=0: 1, 2, 4, 7

\[F = \prod M(1, 2, 4, 7)\]

Expanded POS: \(F = (A+B+\overline{C})(A+\overline{B}+C)(\overline{A}+B+C)(\overline{A}+\overline{B}+\overline{C})\)

1.8 Karnaugh Maps (K-Maps)

What is a K-Map and why do we need it?

You’ve learned Boolean algebra laws to simplify expressions. But algebraic simplification requires insight — you need to “see” which law to apply, and there’s no guarantee you’ll find the minimal expression.

A Karnaugh Map (K-Map) is a visual, systematic method that guarantees you’ll find the simplest possible SOP or POS expression. It was invented by Maurice Karnaugh in 1953 and is one of the most important tools in digital logic design.

The core idea

A K-Map is a special grid where:

Think of it as a visual tool that automatically finds which variables can be removed.

K-Maps provide a visual method for simplifying Boolean expressions. Adjacent cells differ by only one variable (Gray code ordering).

2-Variable K-Map

The simplest K-Map. 2 variables = $2^2 = 4$ cells.

\[\begin{array}{c|c|c} & B=0 & B=1 \\ \hline A=0 & m_0 & m_1 \\ \hline A=1 & m_2 & m_3 \end{array}\]

Each cell is one minterm. Adjacent cells differ by exactly one variable.

3-Variable K-Map

3 variables = $2^3 = 8$ cells, arranged in 2 rows × 4 columns.

Important: The column ordering is NOT 00, 01, 10, 11. It’s Gray code: 00, 01, 11, 10 — so adjacent columns differ by only one bit!

\[\begin{array}{c|c|c|c|c} & \overline{B}\overline{C} & \overline{B}C & BC & B\overline{C} \\ \hline A=0 & m_0 & m_1 & m_3 & m_2 \\ \hline A=1 & m_4 & m_5 & m_7 & m_6 \end{array}\]

Notice: $m_2$ and $m_3$ are swapped compared to normal order. This is the Gray code trick that makes adjacent cells differ by one variable.

4-Variable K-Map

4 variables = $2^4 = 16$ cells, arranged in 4 rows × 4 columns. Both rows and columns use Gray code ordering.

\[\begin{array}{c|c|c|c|c} & \overline{C}\overline{D} & \overline{C}D & CD & C\overline{D} \\ \hline \overline{A}\overline{B} & m_0 & m_1 & m_3 & m_2 \\ \hline \overline{A}B & m_4 & m_5 & m_7 & m_6 \\ \hline AB & m_{12} & m_{13} & m_{15} & m_{14} \\ \hline A\overline{B} & m_8 & m_9 & m_{11} & m_{10} \end{array}\]

Common mistake: Students often write the rows as 00, 01, 10, 11. But the correct Gray code order is 00, 01, 11, 10. Row 3 ($AB$) comes BEFORE row 2 ($A\overline{B}$)! Getting this wrong will produce incorrect simplifications.

Grouping Rules — How to Simplify

After filling in the 1s and 0s from your truth table, follow these rules to group the 1s (for SOP simplification):

  1. Groups must contain $2^k$ cells — only 1, 2, 4, 8, or 16 cells. Never 3, 5, 6, etc.
  2. Groups must be rectangular — rows and/or columns only, no diagonals or L-shapes
  3. Each group should be as large as possible — bigger groups = simpler terms
  4. Every 1-cell must be in at least one group — you can’t leave any 1 ungrouped
  5. Groups can overlap — a 1-cell can belong to multiple groups
  6. The map wraps around! The leftmost column is adjacent to the rightmost column. The top row is adjacent to the bottom row. (Think of the K-Map as a torus/donut shape)
  7. Don’t-care conditions (X) can be treated as 0 or 1 — include them in groups if they make the group bigger, ignore them otherwise
  8. For SOP: group the 1s. For POS: group the 0s.

Reading Groups — How a Group Becomes a Term

The magic: when you make a group, the variables that stay constant within the group become the simplified term. Variables that change (both 0 and 1 appear) are eliminated.

Why does grouping work? Let’s see with a 2-cell group.

Suppose $m_4$ and $m_5$ are both 1 in a 3-variable map.

  • $m_4$ = $A\overline{B}\overline{C}$ (A=1, B=0, C=0)
  • $m_5$ = $A\overline{B}C$ (A=1, B=0, C=1)

Notice: A and B are the same in both (A=1, B=0), but C changes (0→1).
So C doesn’t matter — the group simplifies to $A\overline{B}$ (just the constant variables).

Algebraically: $A\overline{B}\overline{C} + A\overline{B}C = A\overline{B}(\overline{C}+C) = A\overline{B} \cdot 1 = A\overline{B}$ ✓

Simplify $F(A,B,C,D) = \sum m(0, 1, 2, 5, 8, 9, 10)$ using K-Map:

Map:

  $\overline{C}\overline{D}$ $\overline{C}D$ $CD$ $C\overline{D}$
$\overline{A}\overline{B}$ 1 1 0 1
$\overline{A}B$ 0 1 0 0
$AB$ 0 0 0 0
$A\overline{B}$ 1 1 0 1

Groups:

  • Group 1: $m_0, m_1, m_8, m_9$ (4 cells, wrap top-bottom) → $\overline{B}\overline{C}$
  • Group 2: $m_0, m_2, m_8, m_{10}$ (4 cells, wrap top-bottom) → $\overline{B}\overline{D}$
  • Group 3: $m_1, m_5$ (2 cells) → $\overline{A}\overline{C}D$
\[\boxed{F = \overline{B}\overline{C} + \overline{B}\overline{D} + \overline{A}\overline{C}D}\]

Simplify $F(A,B,C) = \sum m(0, 2, 4, 5, 6)$ using a 3-variable K-Map:

  $\overline{B}\overline{C}$ $\overline{B}C$ $BC$ $B\overline{C}$
$A=0$ 1 0 0 1
$A=1$ 1 1 0 1

Groups:

  • Group 1: $m_0, m_2, m_4, m_6$ (4 cells, column 1 & column 4 wrap) → $\overline{C}$
  • Group 2: $m_4, m_5$ (2 cells) → $A\overline{B}$
\[\boxed{F = \overline{C} + A\overline{B}}\]

Simplify $F(A,B,C,D) = \sum m(1,3,7,11,15) + d(0,2,5)$ using K-Map with Don’t-Cares:

Column order (Gray code): $\overline{C}\overline{D}$, $\overline{C}D$, $CD$, $C\overline{D}$

  $\overline{C}\overline{D}$ $\overline{C}D$ $CD$ $C\overline{D}$
$\overline{A}\overline{B}$ X(m₀) 1(m₁) 1(m₃) X(m₂)
$\overline{A}B$ 0(m₄) X(m₅) 1(m₇) 0(m₆)
$AB$ 0(m₁₂) 0(m₁₃) 1(m₁₅) 0(m₁₄)
$A\overline{B}$ 0(m₈) 0(m₉) 1(m₁₁) 0(m₁₀)

Groups (using don’t-cares as 1 where beneficial):

  • Group 1: $m_0, m_1, m_2, m_3$ (use don’t-cares $m_0, m_2$ as 1; top row, all 4 cells) → $\overline{A}\overline{B}$
  • Group 2: $m_3, m_7, m_{15}, m_{11}$ (entire $CD$ column) → $CD$
\[\boxed{F = \overline{A}\overline{B} + CD}\]

Note: Don’t-cares $m_0, m_2$ were used as 1 to make Group 1 larger (4 cells instead of 2). Don’t-care $m_5$ was left as 0 since it didn’t help form a larger group.

POS Simplification with K-Map

Everything above was for SOP (grouping 1s to get AND terms, then OR-ing them). For POS, you do the mirror image:

  1. Group the 0s instead of the 1s
  2. Read the complement of each group variable (where the variable is 0, write it normal; where it’s 1, write it complemented — the opposite of SOP!)
  3. Write each group as an OR (sum) term
  4. AND (multiply) all the sum terms together

When to use POS vs SOP: Choose whichever has fewer groups (fewer terms in the final expression). If there are fewer 0s than 1s in the K-Map, POS might be simpler. If there are fewer 1s, SOP is simpler.

Don’t-Care Conditions

What are don’t-cares?

Sometimes certain input combinations cannot occur in practice, or we don’t care what the output is for those inputs. These are marked X (or d) in the truth table.

The most common example: in BCD (0–9), the 4-bit combinations 1010 through 1111 (decimal 10–15) are invalid — they never appear. So the output for these inputs can be either 0 or 1 — we get to choose whatever makes our circuit simpler.

How to use don’t-cares in K-Maps

In BCD, inputs 1010–1111 are invalid. These 6 combinations are don’t-cares. When designing BCD-based circuits (like a BCD-to-7-segment decoder), using these don’t-cares can dramatically simplify the logic.

Exam trap: Some students treat ALL don’t-cares as 1 or ALL as 0. That’s wrong! You should treat each don’t-care individually — include it as 1 only if it makes a specific group larger. Leave it as 0 if it doesn’t help.

Unit I — Practice Questions & PYQs

Q1. Convert the following: (IIIT-type)

  • $(247.5)_8$ to hexadecimal
  • $(1AC.8)_{16}$ to octal
  • $(0.6875)_{10}$ to binary

Q2. Perform using 2’s complement arithmetic (8-bit): (Standard Exam)

  • $45 - 78$
  • $-32 - 48$
  • Detect overflow for $+100 + 60$

Q3. Simplify using Boolean algebra: (IIIT PYQ-type)

  • $F = \overline{A}B + A\overline{B}C + AB\overline{C} + ABC$
  • $F = (A+B)(\overline{A}+C)(B+\overline{C})$

Q4. Prove using Boolean algebra: (Frequently asked)

  • $AB + A\overline{B} = A$
  • $A + \overline{A}B = A + B$
  • De Morgan’s theorem for 3 variables

Q5. Express $F(A,B,C) = A + B\overline{C}$ in: (IIIT PYQ-type)

  • (a) Canonical SOP (list minterms)
  • (b) Canonical POS (list maxterms)

Q6. Simplify using K-Maps and draw the logic circuit: (Frequent exam question)

  • $F(A,B,C) = \sum m(0, 2, 4, 5, 6)$
  • $F(A,B,C,D) = \sum m(0, 1, 3, 5, 7, 8, 9, 11, 15)$
  • $F(A,B,C,D) = \sum m(1, 3, 7, 11, 15) + d(0, 2, 5)$ (with don’t cares)

Q7. Get the POS form using K-Map: (Important)

  • $F(A,B,C,D) = \prod M(0, 1, 2, 4, 5, 9, 12)$

Q8. Realize $F = ABC + \overline{A}B\overline{C}$ using: (Lab / Theory)

  • (a) NAND gates only
  • (b) NOR gates only

Q9. Convert 4-bit Binary to Gray code and vice versa for all values 0–15. (Table-based)

Q10. What is the 2’s complement representation of −1 in 8-bit? Why does it have all 1s? Explain with the mathematical definition.

Back to Digital Logic & Design