Part 2: Introduction to Logic Design

Source: Part-2-Logic+Design.pdf

1. Analog vs Digital Signals
💡 Simple Explanation: Analog signals are like a dimmer switch — they can be any brightness. Digital signals are like a regular switch — only ON or OFF. Computers use digital because it's easier to work with just two states.

Formal Definition: An analog signal is a continuous signal that varies over time. A digital signal is a discrete signal with a finite number of values, typically two (0 and 1).

In the real world, most signals are analog — they vary smoothly and continuously (e.g., temperature, sound waves, voltage). Digital signals only have distinct levels — in binary digital systems, these are 0 (LOW) and 1 (HIGH). Digital systems are preferred in computing because they're more noise-resistant, easier to store and process, and can be manufactured reliably.

Key Points

  • Analog = continuous values, Digital = discrete values
  • Binary digital: only 2 values — 0 and 1
  • Digital is more noise-immune than analog
  • A/D converter: converts analog → digital, D/A converter: digital → analog
  • Computers process digital signals internally even if inputs/outputs are analog

⚠️ Common Traps

Don't confuse 'digital' with 'binary' — digital can have more than 2 levels, but binary digital (used in computers) specifically has 2.
The real world is analog — computers need converters (ADC/DAC) to interact with it.

🧪 Quick Self-Test

A digital signal can take any value between 0 and 5 volts.
A digital signal can only take discrete values (e.g., 0V or 5V), not any value in between. That would be analog.
Which of the following is an advantage of digital signals over analog?
Digital signals are more noise-immune because small distortions don't change the interpreted value (still reads as 0 or 1).
2. Number Systems (Binary, Octal, Decimal, Hexadecimal)
💡 Simple Explanation: We count in base-10 (0-9) because we have 10 fingers. Computers count in base-2 (0-1) because they have switches. Octal (base-8) and hex (base-16) are shortcuts to write long binary numbers more compactly.

Formal Definition: A number system with base/radix $r$ uses $r$ distinct digits. The value of a number $d_n d_{n-1} ... d_1 d_0$ in base $r$ is $\\sum_{i=0}^{n} d_i \\times r^i$.

Every number system has a base (radix). The base tells you how many unique digits the system uses.

Decimal (base 10): digits 0–9. What we use daily.
Binary (base 2): digits 0, 1. What computers use.
Octal (base 8): digits 0–7. Compact way to write binary (3 bits = 1 octal digit).
Hexadecimal (base 16): digits 0–9, A–F. Even more compact (4 bits = 1 hex digit).

Key Points

  • Binary (base 2): 0, 1 — used in digital circuits
  • Octal (base 8): 0-7 — each octal digit = 3 binary digits
  • Decimal (base 10): 0-9 — human-readable
  • Hex (base 16): 0-9, A(10), B(11), C(12), D(13), E(14), F(15) — each hex digit = 4 binary digits
  • The subscript notation: $(1010)_2$ means binary, $(FF)_{16}$ means hex
  • MSB = Most Significant Bit (leftmost), LSB = Least Significant Bit (rightmost)

Formulas

$$V = \sum_{i=0}^{n} d_i \times r^i$$
Positional value formula: each digit $d_i$ is multiplied by $r^i$ where $r$ is the base and $i$ is the position (starting from 0 at the right).

Worked Examples

Example 1

Problem: What is the decimal value of the binary number $(1011)_2$?

  1. $1 \\times 2^3 = 8$
  2. $0 \\times 2^2 = 0$
  3. $1 \\times 2^1 = 2$
  4. $1 \\times 2^0 = 1$
  5. Sum: $8 + 0 + 2 + 1 = 11$

Answer: $(1011)_2 = (11)_{10}$

Example 2

Problem: What is the decimal value of $(2A)_{16}$?

  1. $A = 10$ in decimal
  2. $2 \\times 16^1 = 32$
  3. $10 \\times 16^0 = 10$
  4. Sum: $32 + 10 = 42$

Answer: $(2A)_{16} = (42)_{10}$

⚠️ Common Traps

Remember: positions count from RIGHT to LEFT, starting at 0!
In hex, A=10, B=11, C=12, D=13, E=14, F=15 — don't mix them up.
$(10)_2 = 2_{10}$, NOT $10_{10}$ — always note the base!

🧪 Quick Self-Test

How many unique digits does the octal number system use?
Octal is base-8, so it uses digits 0 through 7 — that's 8 unique digits.
Convert $(1100)_2$ to decimal.
$1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 = 8 + 4 + 0 + 0 = 12$
What decimal value does the hex digit 'F' represent?
In hexadecimal: A=10, B=11, C=12, D=13, E=14, F=15.
3. Base Conversion Methods
💡 Simple Explanation: Converting between bases is like translating between languages. To go from any base to decimal, multiply each digit by its place value and add. To go from decimal to any base, keep dividing by the base and collect remainders.
There are several conversion methods:

Any base → Decimal: Use the positional value formula (multiply each digit by base^position, sum up).

Decimal → Any base: Repeated division by the target base. The remainders (read bottom to top) give the answer.

Binary ↔ Octal: Group binary digits in 3s (from right). Each group = 1 octal digit.

Binary ↔ Hex: Group binary digits in 4s (from right). Each group = 1 hex digit.

Octal ↔ Hex: Convert through binary as an intermediate step.

Key Points

  • To decimal: multiply each digit by base^position, add all up
  • From decimal: repeated division, remainders read bottom-to-top
  • Binary → Octal: group by 3 bits (pad with leading zeros if needed)
  • Binary → Hex: group by 4 bits (pad with leading zeros if needed)
  • For fractional parts: multiply by base repeatedly, take integer parts
  • Octal ↔ Hex: go through binary (Octal → Binary → Hex or reverse)

Formulas

$$\text{Decimal} = d_n \times r^n + d_{n-1} \times r^{n-1} + \cdots + d_0 \times r^0$$
Any base to decimal conversion using positional notation

Worked Examples

Example 1

Problem: Convert $(25)_{10}$ to binary.

  1. $25 \div 2 = 12$ remainder $1$
  2. $12 \div 2 = 6$ remainder $0$
  3. $6 \div 2 = 3$ remainder $0$
  4. $3 \div 2 = 1$ remainder $1$
  5. $1 \div 2 = 0$ remainder $1$
  6. Read remainders bottom to top: $11001$

Answer: $(25)_{10} = (11001)_2$

Example 2

Problem: Convert $(10110110)_2$ to hexadecimal.

  1. Group into 4 bits from right: $1011 \ 0110$
  2. $0110_2 = 6_{16}$
  3. $1011_2 = B_{16}$ (since $8+0+2+1 = 11 = B$)
  4. Result: $B6$

Answer: $(10110110)_2 = (B6)_{16}$

Example 3

Problem: Convert $(10110110)_2$ to octal.

  1. Group into 3 bits from right: $10 \ 110 \ 110$
  2. Pad leftmost group: $010 \ 110 \ 110$
  3. $010_2 = 2_8$
  4. $110_2 = 6_8$
  5. $110_2 = 6_8$
  6. Result: $266$

Answer: $(10110110)_2 = (266)_8$

⚠️ Common Traps

When grouping binary for octal/hex, always group from the RIGHT side, not the left!
Pad with LEADING zeros on the leftmost group if needed (e.g., 10 → 010 for octal grouping).
When converting decimal to binary, read remainders BOTTOM to TOP, not top to bottom.
Don't forget: for fractional conversions, you MULTIPLY by the base (not divide).

🧪 Quick Self-Test

Convert $(13)_{10}$ to binary.
$13÷2=6$ R$1$, $6÷2=3$ R$0$, $3÷2=1$ R$1$, $1÷2=0$ R$1$. Read bottom-up: $1101$.
Convert binary $11011011$ to hexadecimal.
Group by 4: $1101 \ 1011$. $1101=D$ (13), $1011=B$ (11). Answer: $DB$.
When converting binary to octal, you group bits in groups of:
Octal is base-8 = $2^3$, so each octal digit represents exactly 3 binary bits.
4. Complements (1's and 2's Complement)
💡 Simple Explanation: Complements are a clever trick to do subtraction using addition. Instead of subtracting B from A, you add A to the 'complement' of B. It's like saying 'instead of going 3 steps back, go 7 steps forward on a 10-step track' — you end up at the same place.

Formal Definition: For a number $N$ with $n$ digits in base $r$: the $r$'s complement is $r^n - N$, and the $(r-1)$'s complement is $r^n - 1 - N$.

In binary systems:

1's Complement: Flip all bits (0→1, 1→0). That's it!

2's Complement: Flip all bits, then add 1. OR: find the rightmost 1, keep it and everything to the right, flip everything to the left.

2's complement is used to represent negative numbers in computers. It allows subtraction to be done using addition hardware.

Key Points

  • 1's complement: flip all bits (0↔1)
  • 2's complement: flip all bits + add 1 (OR: 1's complement + 1)
  • 2's complement shortcut: from right, keep bits until first 1 (inclusive), then flip the rest
  • 2's complement is used for signed number representation in computers
  • In n-bit 2's complement: range is $-2^{n-1}$ to $2^{n-1}-1$
  • MSB = sign bit: 0 = positive, 1 = negative (in signed representation)
  • For decimal: 9's complement (flip each digit from 9), 10's complement = 9's + 1

Formulas

$$\text{1's complement of } N = (2^n - 1) - N$$
Also: just flip every bit in the binary number
$$\text{2's complement of } N = 2^n - N = \text{1's complement} + 1$$
Used for subtraction: $A - B = A + (\text{2's complement of } B)$

Worked Examples

Example 1

Problem: Find the 1's and 2's complement of $(1010)_2$.

  1. 1's complement: flip all bits → $0101$
  2. 2's complement: 1's complement + 1 → $0101 + 1 = 0110$

Answer: 1's complement = $0101$, 2's complement = $0110$

Example 2

Problem: Subtract $(0111)_2$ from $(1010)_2$ using 2's complement.

  1. Find 2's complement of $0111$: flip → $1000$, add 1 → $1001$
  2. Add: $1010 + 1001 = 10011$
  3. There is a carry out (5th bit) — discard it
  4. Result: $0011 = 3_{10}$
  5. Verify: $10 - 7 = 3$ ✓

Answer: $(1010)_2 - (0111)_2 = (0011)_2 = 3_{10}$

⚠️ Common Traps

2's complement ≠ 1's complement! Don't forget to add 1.
When subtracting with 2's complement: if there's a carry out, DISCARD it — the result is positive. If there's NO carry out, the result is negative and is in 2's complement form.
The 2's complement of 0 is 0 (not a special case — it works: flip 0000 → 1111, add 1 → 10000, discard carry → 0000).

🧪 Quick Self-Test

What is the 2's complement of $(1100)_2$?
1's complement: $0011$. Add 1: $0011 + 1 = 0100$.
In 2's complement representation, the MSB (leftmost bit) indicates the sign of the number.
Yes — MSB = 0 means positive, MSB = 1 means negative in signed 2's complement.
5. Binary Codes (BCD, Gray, Excess-3)
💡 Simple Explanation: Binary codes are different 'languages' for writing numbers in binary. BCD uses 4 bits per decimal digit (like writing each digit separately). Gray code changes only 1 bit at a time (useful for preventing errors). Excess-3 is BCD shifted by 3.
BCD (Binary Coded Decimal): Each decimal digit is represented by its 4-bit binary equivalent, separately. So $25_{10}$ = $0010 \ 0101_{BCD}$ (not the same as binary $11001$!).

Gray Code: A binary code where consecutive numbers differ by only 1 bit. Used in Karnaugh maps and rotary encoders to prevent glitches.

Excess-3: Add 3 to each decimal digit, then convert to 4-bit binary. Self-complementing code (9's complement = 1's complement of the code).

Key Points

  • BCD: each decimal digit → 4 bits independently (0→0000, 9→1001)
  • BCD only uses codes 0000–1001; codes 1010–1111 are INVALID in BCD
  • Gray code: adjacent values differ by exactly 1 bit
  • Binary to Gray: MSB stays same, each next bit = XOR of adjacent binary bits
  • Gray to Binary: MSB stays same, each next bit = XOR of previous result with current Gray bit
  • Excess-3: add 3 to decimal digit, then convert to 4-bit binary
  • Excess-3 is self-complementing: 9's complement of decimal digit = 1's complement of Excess-3 code

Formulas

$$G_i = B_i \oplus B_{i+1}, \quad G_{MSB} = B_{MSB}$$
Binary to Gray code conversion (XOR adjacent bits)
$$\text{Excess-3} = \text{BCD} + 0011$$
Excess-3 code = BCD representation + 3

Worked Examples

Example 1

Problem: Convert decimal 47 to BCD.

  1. Digit 4 → $0100$
  2. Digit 7 → $0111$
  3. Concatenate: $0100 \ 0111$

Answer: $(47)_{10} = (0100 \ 0111)_{BCD}$

Example 2

Problem: Convert binary $1011$ to Gray code.

  1. MSB stays: $G_3 = B_3 = 1$
  2. $G_2 = B_3 \oplus B_2 = 1 \oplus 0 = 1$
  3. $G_1 = B_2 \oplus B_1 = 0 \oplus 1 = 1$
  4. $G_0 = B_1 \oplus B_0 = 1 \oplus 1 = 0$

Answer: $(1011)_2 = (1110)_{Gray}$

⚠️ Common Traps

BCD is NOT the same as regular binary! $(12)_{10}$ in BCD = $0001\ 0010$ (8 bits), but in binary = $1100$ (4 bits).
BCD codes 1010 through 1111 are INVALID — this is a common exam trap!
Gray code conversion uses XOR (⊕) — don't confuse with AND or OR.

🧪 Quick Self-Test

What is the BCD representation of decimal 93?
9 → $1001$, 3 → $0011$. So $93_{10} = 1001 \ 0011_{BCD}$.
The BCD code 1011 is a valid BCD digit.
BCD only uses codes 0000 (0) through 1001 (9). 1011 = 11, which is not a single decimal digit.
In Gray code, how many bits change between consecutive numbers?
The defining property of Gray code is that exactly 1 bit changes between any two consecutive values.