CO3: Examine number system conversions and K-Map to simplify digital
logic expressions.
CO4: Analyze the operation and functionality of combinational
logic circuits including adders, subtractors, multiplexers, and demultiplexers.
A number system is a systematic way of representing numbers using a set of symbols (digits) and a base (radix). The base determines how many unique digits are used.
| System | Base | Digits Used | Example |
|---|---|---|---|
| Binary | 2 | 0, 1 | \( (1011)_2 \) |
| Octal | 8 | 0–7 | \( (57)_8 \) |
| Decimal | 10 | 0–9 | \( (247)_{10} \) |
| Hexadecimal | 16 | 0–9, A–F | \( (1A3)_{16} \) |
In a positional number system, the value of each digit depends on its position. For a number with base \( r \):
The binary system uses only two digits: 0 and 1. Each digit is called a bit. It is the foundation of all digital systems.
| Power of 2 | Value | Binary (1 followed by zeros) |
|---|---|---|
| \( 2^0 \) | 1 | 1 |
| \( 2^1 \) | 2 | 10 |
| \( 2^2 \) | 4 | 100 |
| \( 2^3 \) | 8 | 1000 |
| \( 2^4 \) | 16 | 10000 |
| \( 2^5 \) | 32 | 100000 |
| \( 2^6 \) | 64 | 1000000 |
| \( 2^7 \) | 128 | 10000000 |
| \( 2^8 \) | 256 | 100000000 |
| \( 2^{10} \) | 1024 | 1 K (kilo) |
| \( 2^{20} \) | 1,048,576 | 1 M (mega) |
Problem: Convert \( (1101)_2 \) to decimal.
Solution:
\[ (1101)_2 = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 \] \[ = 8 + 4 + 0 + 1 = 13 \]Base 8. Uses digits 0–7. Each octal digit corresponds to exactly 3 binary digits (triad). Octal is used as a compact representation of binary.
| Octal | Binary (3-bit) | Decimal |
|---|---|---|
| 0 | 000 | 0 |
| 1 | 001 | 1 |
| 2 | 010 | 2 |
| 3 | 011 | 3 |
| 4 | 100 | 4 |
| 5 | 101 | 5 |
| 6 | 110 | 6 |
| 7 | 111 | 7 |
Base 16. Uses digits 0–9 and letters A–F. Each hex digit corresponds to exactly 4 binary digits (tetrad). Hexadecimal is widely used in computer memory addressing and machine code.
| Hex | Binary (4-bit) | Decimal |
|---|---|---|
| 0 | 0000 | 0 |
| 1 | 0001 | 1 |
| 2 | 0010 | 2 |
| 3 | 0011 | 3 |
| 4 | 0100 | 4 |
| 5 | 0101 | 5 |
| 6 | 0110 | 6 |
| 7 | 0111 | 7 |
| 8 | 1000 | 8 |
| 9 | 1001 | 9 |
| A | 1010 | 10 |
| B | 1011 | 11 |
| C | 1100 | 12 |
| D | 1101 | 13 |
| E | 1110 | 14 |
| F | 1111 | 15 |
| System | Base | Digits | Binary Group |
|---|---|---|---|
| Binary | 2 | 0, 1 | 1 bit |
| Octal | 8 | 0–7 | 3 bits |
| Decimal | 10 | 0–9 | — |
| Hexadecimal | 16 | 0–9, A–F | 4 bits |
Problem: Convert \( (247)_8 \) to decimal.
Solution:
\[ (247)_8 = 2 \times 8^2 + 4 \times 8^1 + 7 \times 8^0 = 128 + 32 + 7 = 167 \]Problem: Convert \( (2F)_{16} \) to decimal.
Solution:
\[ (2F)_{16} = 2 \times 16^1 + 15 \times 16^0 = 32 + 15 = 47 \]Repeatedly divide the decimal number by 2, recording remainders. The binary number is read from bottom to top.
Repeatedly multiply the fractional part by 2, recording the integer part. Read from top to bottom.
Group binary digits into sets of 3 (octal) or 4 (hex), starting from the binary point. Pad with zeros if necessary.
Problem: Convert \( (11010110)_2 \) to hex.
Solution:
Group into 4 bits from the right: 1101 0110
1101 = D, 0110 = 6
Therefore, \( (11010110)_2 = (D6)_{16} \)
Use positional notation with the base as the radix.
Problem: Convert \( (10.101)_2 \) to decimal.
Solution:
\[ (10.101)_2 = 1 \times 2^1 + 0 \times 2^0 + 1 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-3} \] \[ = 2 + 0 + 0.5 + 0 + 0.125 = 2.625 \]| From → To | Method |
|---|---|
| Decimal → Binary | Divide by 2 (integer), multiply by 2 (fraction) |
| Binary → Decimal | Positional notation (powers of 2) |
| Binary → Octal | Group into 3 bits |
| Binary → Hex | Group into 4 bits |
| Octal → Binary | Each digit → 3 bits |
| Hex → Binary | Each digit → 4 bits |
| Octal → Decimal | Positional notation (powers of 8) |
| Hex → Decimal | Positional notation (powers of 16) |
| Decimal → Octal | Divide by 8 |
| Decimal → Hex | Divide by 16 |
| Decimal | Binary (4-bit) | Octal | Hex |
|---|---|---|---|
| 0 | 0000 | 0 | 0 |
| 1 | 0001 | 1 | 1 |
| 2 | 0010 | 2 | 2 |
| 3 | 0011 | 3 | 3 |
| 4 | 0100 | 4 | 4 |
| 5 | 0101 | 5 | 5 |
| 6 | 0110 | 6 | 6 |
| 7 | 0111 | 7 | 7 |
| 8 | 1000 | 10 | 8 |
| 9 | 1001 | 11 | 9 |
| 10 | 1010 | 12 | A |
| 11 | 1011 | 13 | B |
| 12 | 1100 | 14 | C |
| 13 | 1101 | 15 | D |
| 14 | 1110 | 16 | E |
| 15 | 1111 | 17 | F |
Problem: Convert \( (3A7)_{16} \) to binary.
Solution:
3 → 0011, A → 1010, 7 → 0111
Therefore, \( (3A7)_{16} = (001110100111)_2 \)
Problem: Convert \( (52)_8 \) to binary.
Solution:
5 → 101, 2 → 010
Therefore, \( (52)_8 = (101010)_2 \)
Problem: Convert \( (250)_{10} \) to hexadecimal.
Solution:
Divide by 16: \( 250 \div 16 = 15 \) remainder \( 10 \rightarrow A \)
\( 15 \div 16 = 0 \) remainder \( 15 \rightarrow F \)
Read bottom to top: \( (FA)_{16} \)
A binary code is a way of representing decimal digits, alphabetic characters, or other symbols using binary bits. Different codes serve different purposes (arithmetic, error detection, display, etc.).
In BCD, each decimal digit is represented by its 4-bit binary equivalent. Only the codes 0000–1001 are used; 1010–1111 are invalid in BCD.
| Decimal | BCD | Decimal | BCD |
|---|---|---|---|
| 0 | 0000 | 5 | 0101 |
| 1 | 0001 | 6 | 0110 |
| 2 | 0010 | 7 | 0111 |
| 3 | 0011 | 8 | 1000 |
| 4 | 0100 | 9 | 1001 |
Problem: Convert \( (47)_{10} \) to BCD.
Solution:
\( 4 \rightarrow 0100 \), \( 7 \rightarrow 0111 \)
Therefore, \( (47)_{10} = (0100\,0111)_{BCD} \)
A Gray code is a binary code in which consecutive values differ by only one bit. This minimizes errors during transitions. Used in rotary encoders, K-maps, and position sensors.
| Decimal | Binary | Gray |
|---|---|---|
| 0 | 000 | 000 |
| 1 | 001 | 001 |
| 2 | 010 | 011 |
| 3 | 011 | 010 |
| 4 | 100 | 110 |
| 5 | 101 | 111 |
| 6 | 110 | 101 |
| 7 | 111 | 100 |
Problem: Convert \( (1011)_2 \) to Gray code.
Solution:
MSB: \( G_3 = B_3 = 1 \)
\( G_2 = B_3 \oplus B_2 = 1 \oplus 0 = 1 \)
\( G_1 = B_2 \oplus B_1 = 0 \oplus 1 = 1 \)
\( G_0 = B_1 \oplus B_0 = 1 \oplus 1 = 0 \)
Therefore, Gray code = \( (1110)_G \)
The Excess-3 code is a BCD code obtained by adding 3 (binary 0011) to each BCD code. It is a self-complementing code (1's complement gives the 9's complement in decimal).
| Decimal | BCD | Excess-3 |
|---|---|---|
| 0 | 0000 | 0011 |
| 1 | 0001 | 0100 |
| 2 | 0010 | 0101 |
| 3 | 0011 | 0110 |
| 4 | 0100 | 0111 |
| 5 | 0101 | 1000 |
| 6 | 0110 | 1001 |
| 7 | 0111 | 1010 |
| 8 | 1000 | 1011 |
| 9 | 1001 | 1100 |
ASCII (American Standard Code for Information Interchange) is a 7-bit (or 8-bit extended) code used to represent alphanumeric characters. It can encode 128 characters (7-bit) or 256 (8-bit).
| Character | ASCII (Decimal) | ASCII (Binary, 7-bit) |
|---|---|---|
| A | 65 | 1000001 |
| B | 66 | 1000010 |
| a | 97 | 1100001 |
| 0 | 48 | 0110000 |
| 9 | 57 | 0111001 |
| Space | 32 | 0100000 |
A parity bit is an extra bit added to a binary code to detect errors during transmission.
Problem: Data = 1011. Find the even parity bit.
Solution:
Number of 1s = 3 (odd). To make it even, parity bit = 1.
Transmitted: 10111 (4 ones → even)
| Code | Bits | Use | Key Feature |
|---|---|---|---|
| Binary | Variable | General computation | Positional |
| BCD | 4 per digit | Displays, calculators | Direct decimal mapping |
| Gray | Variable | Encoders, K-maps | Single-bit change |
| Excess-3 | 4 | Arithmetic | Self-complementing |
| ASCII | 7/8 | Text | Standard character set |
Rules for binary addition:
| Operation | Result | Carry |
|---|---|---|
| 0 + 0 | 0 | 0 |
| 0 + 1 | 1 | 0 |
| 1 + 0 | 1 | 0 |
| 1 + 1 | 0 | 1 |
| 1 + 1 + 1 | 1 | 1 |
Problem: Add \( (1011)_2 + (1101)_2 \).
Solution:
Rules for binary subtraction:
| Operation | Result | Borrow |
|---|---|---|
| 0 − 0 | 0 | 0 |
| 1 − 0 | 1 | 0 |
| 1 − 1 | 0 | 0 |
| 0 − 1 | 1 | 1 |
Subtraction \( A - B \) is performed as \( A + (2's\ complement\ of\ B) \). The 2's complement is obtained by inverting all bits and adding 1.
Problem: Perform \( (1011)_2 - (0110)_2 \) using 2's complement.
Solution:
1's complement of \( 0110 \) = \( 1001 \)
2's complement = \( 1001 + 1 = 1010 \)
Add: \( 1011 + 1010 = 10101 \)
Discard the carry: \( 0101 = 5 \)
Verify: \( 11 - 6 = 5 \) ✓
Problem: Multiply \( (101)_2 \times (11)_2 \).
Solution:
A logic gate is an electronic circuit that performs a Boolean operation on one or more binary inputs to produce a single binary output. They are the building blocks of all digital circuits.
Output is 1 only when all inputs are 1.
| A | B | Y = A·B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Output is 1 when at least one input is 1.
| A | B | Y = A+B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Output is the complement of the input.
| A | Y = Ā |
|---|---|
| 0 | 1 |
| 1 | 0 |
AND followed by NOT. Output is 0 only when all inputs are 1.
| A | B | Y = (A·B)′ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
OR followed by NOT. Output is 1 only when all inputs are 0.
| A | B | Y = (A+B)′ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Output is 1 when inputs are different.
| A | B | Y = A ⊕ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Output is 1 when inputs are same.
| A | B | Y = (A ⊕ B)′ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
NAND and NOR are called universal gates because any logic function can be implemented using only NAND or only NOR gates.
| Gate | Using NAND | Using NOR |
|---|---|---|
| NOT | NAND with inputs tied | NOR with inputs tied |
| AND | NAND + NOT | Two NOR + NOT (De Morgan) |
| OR | Two NAND + NOT (De Morgan) | NOR + NOT |
| XOR | 4 NAND gates | 5 NOR gates |
| Gate | Symbol | Expression | Output = 1 when… |
|---|---|---|---|
| AND | A·B | \( A \cdot B \) | All inputs are 1 |
| OR | A+B | \( A + B \) | Any input is 1 |
| NOT | Ā | \( \overline{A} \) | Input is 0 |
| NAND | (A·B)′ | \( \overline{A \cdot B} \) | Not all inputs are 1 |
| NOR | (A+B)′ | \( \overline{A + B} \) | All inputs are 0 |
| XOR | A⊕B | \( A \oplus B \) | Inputs are different |
| XNOR | (A⊕B)′ | \( \overline{A \oplus B} \) | Inputs are same |
Problem: Find the output of \( Y = (A + B) \cdot \overline{C} \) when \( A = 1, B = 0, C = 1 \).
Solution:
\( A + B = 1 + 0 = 1 \)
\( \overline{C} = \overline{1} = 0 \)
\( Y = 1 \cdot 0 = 0 \)
Boolean algebra is a mathematical system for analyzing and simplifying digital logic circuits. Variables take only two values: 0 (false) and 1 (true). It uses three basic operations: AND (·), OR (+), and NOT (′ or overbar).
| Identity | AND Form | OR Form |
|---|---|---|
| Identity Law | \( A \cdot 1 = A \) | \( A + 0 = A \) |
| Null (Dominance) Law | \( A \cdot 0 = 0 \) | \( A + 1 = 1 \) |
| Idempotent Law | \( A \cdot A = A \) | \( A + A = A \) |
| Complement Law | \( A \cdot \overline{A} = 0 \) | \( A + \overline{A} = 1 \) |
| Double Negation | \( \overline{\overline{A}} = A \) | |
| Commutative Law | \( A \cdot B = B \cdot A \) | \( A + B = B + A \) |
| Associative Law | \( (A \cdot B) \cdot C = A \cdot (B \cdot C) \) | \( (A + B) + C = A + (B + C) \) |
| Distributive Law | \( A(B + C) = AB + AC \) | \( A + BC = (A+B)(A+C) \) |
| Absorption Law | \( A + AB = A \) | \( A(A + B) = A \) |
| Redundancy Law | \( A + \overline{A}B = A + B \) | \( A(\overline{A} + B) = AB \) |
The complement of a sum equals the product of the complements.
The complement of a product equals the sum of the complements.
| A | B | A+B | (A+B)′ | A′ | B′ | A′·B′ |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Columns 4 and 7 are identical → theorem proved.
| Law | Expression |
|---|---|
| Identity | \( A + 0 = A \); \( A \cdot 1 = A \) |
| Null | \( A + 1 = 1 \); \( A \cdot 0 = 0 \) |
| Idempotent | \( A + A = A \); \( A \cdot A = A \) |
| Complement | \( A + \overline{A} = 1 \); \( A \cdot \overline{A} = 0 \) |
| Involution | \( \overline{\overline{A}} = A \) |
| Commutative | \( A + B = B + A \); \( AB = BA \) |
| Associative | \( (A+B)+C = A+(B+C) \); \( (AB)C = A(BC) \) |
| Distributive | \( A(B+C) = AB + AC \); \( A + BC = (A+B)(A+C) \) |
| Absorption | \( A + AB = A \); \( A(A+B) = A \) |
| Consensus | \( AB + \overline{A}C + BC = AB + \overline{A}C \) |
| De Morgan's 1 | \( \overline{A+B} = \overline{A} \cdot \overline{B} \) |
| De Morgan's 2 | \( \overline{A \cdot B} = \overline{A} + \overline{B} \) |
The term \( BC \) is redundant and can be removed. This is often used in K-map simplification to eliminate redundant groups.
Problem: Simplify \( Y = A + \overline{A}B \).
Solution:
\[ Y = A + \overline{A}B = (A + \overline{A})(A + B) = 1 \cdot (A+B) = A + B \]Problem: Simplify \( Y = AB + A\overline{B} \).
Solution:
\[ Y = A(B + \overline{B}) = A \cdot 1 = A \]Problem: Simplify \( Y = (A + B)(A + \overline{B}) \).
Solution:
\[ Y = A \cdot A + A \cdot \overline{B} + B \cdot A + B \cdot \overline{B} \] \[ = A + A\overline{B} + AB + 0 = A(1 + \overline{B} + B) = A \cdot 1 = A \]Problem: Simplify \( Y = \overline{\overline{A} + \overline{B}} \).
Solution:
By De Morgan's Theorem 1:
\[ Y = \overline{\overline{A}} \cdot \overline{\overline{B}} = A \cdot B = AB \]De Morgan's theorems provide a way to convert between AND and OR operations with complemented inputs/outputs. They are fundamental to digital logic design and simplification.
\( \overline{A + B} = \overline{A} \cdot \overline{B} \)
The complement of OR is the AND of complements.
\( \overline{A \cdot B} = \overline{A} + \overline{B} \)
The complement of AND is the OR of complements.
| A | B | A + B | \( \overline{A+B} \) | \( \overline{A} \) | \( \overline{B} \) | \( \overline{A} \cdot \overline{B} \) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| A | B | A·B | \( \overline{A \cdot B} \) | \( \overline{A} \) | \( \overline{B} \) | \( \overline{A} + \overline{B} \) |
|---|---|---|---|---|---|---|
| 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 |
For a Boolean function of \( n \) variables, there are \( 2^n \) possible combinations. Each combination corresponds to a minterm (product term) or maxterm (sum term).
| A | B | Minterm (m) | Maxterm (M) |
|---|---|---|---|
| 0 | 0 | \( \overline{A}\overline{B} \) = \( m_0 \) | \( A + B \) = \( M_0 \) |
| 0 | 1 | \( \overline{A}B \) = \( m_1 \) | \( A + \overline{B} \) = \( M_1 \) |
| 1 | 0 | \( A\overline{B} \) = \( m_2 \) | \( \overline{A} + B \) = \( M_2 \) |
| 1 | 1 | \( AB \) = \( m_3 \) | \( \overline{A} + \overline{B} \) = \( M_3 \) |
In SOP form, the function is expressed as the OR of multiple AND terms (minterms). It is the most common form for implementation with NAND gates.
In POS form, the function is expressed as the AND of multiple OR terms (maxterms). It is convenient for implementation with NOR gates.
| Form | Description | Example |
|---|---|---|
| Canonical SOP | Each term contains all variables (minterms) | \( \overline{A}\overline{B}C + A\overline{B}C \) |
| Standard SOP | Terms may not contain all variables | \( \overline{B}C + A\overline{B} \) |
| Canonical POS | Each term contains all variables (maxterms) | \( (A+B+C)(\overline{A}+B+C) \) |
| Standard POS | Terms may not contain all variables | \( (A+B)(\overline{A}+C) \) |
Problem: Given the truth table below, write the canonical SOP expression.
| A | B | C | Y |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Solution:
Y = 1 for minterms \( m_1, m_3, m_5, m_7 \).
\[ Y = \overline{A}\overline{B}C + \overline{A}BC + A\overline{B}C + ABC \]A Karnaugh map (K-map) is a graphical method for simplifying Boolean expressions. It arranges truth table values in a grid where adjacent cells differ by only one variable, enabling easy identification of groups (prime implicants).
Problem: Simplify \( Y = \sum m(1, 3, 5, 7) \).
Solution:
Verification: \( m_1=\overline{A}\overline{B}C \), \( m_3=\overline{A}BC \), \( m_5=A\overline{B}C \), \( m_7=ABC \). Grouping:
\[ Y = \overline{A}C(\overline{B}+B) + AC(\overline{B}+B) = \overline{A}C + AC = C \]Problem: Simplify \( Y = \sum m(0, 1, 2, 3, 8, 9, 10, 11) \).
Solution:
Don't care conditions are input combinations that never occur in practice. They can be treated as either 0 or 1 to make larger groups and achieve better simplification. Denoted by \( X \) or \( d \).
Problem: Simplify \( Y = \sum m(0, 2, 4, 6) + d(1, 3, 5) \).
Solution:
| Group Size | Variables Eliminated | Resulting Term |
|---|---|---|
| 1 (single 1) | 0 | Full minterm (all variables) |
| 2 | 1 | Product of n−1 variables |
| 4 | 2 | Product of n−2 variables |
| 8 | 3 | Product of n−3 variables |
| 16 | 4 | 1 (always true) |
A combinational circuit is a digital circuit whose output depends only on the present inputs (no memory). Examples: adders, subtractors, multiplexers, demultiplexers, encoders, decoders, comparators.
A half adder adds two single bits and produces a Sum and a Carry.
| A | B | Sum (S) | Carry (C) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
A full adder adds three bits (A, B, and Carry-in \( C_{in} \)) and produces Sum and Carry-out \( C_{out} \).
| A | B | C_in | Sum (S) | C_out |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
A 4-bit adder is built by cascading four full adders. The carry from each stage propagates to the next.
A half subtractor subtracts one bit from another and produces a Difference and a Borrow.
| A | B | Difference (D) | Borrow (Bo) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
A full subtractor subtracts B and Borrow-in from A, producing Difference and Borrow-out.
| A | B | B_in | Difference (D) | B_out |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
A single circuit can perform both addition and subtraction by using XOR gates controlled by a mode signal \( M \):
Problem: Find Sum and Carry for A = 1, B = 1.
Solution:
\[ S = A \oplus B = 1 \oplus 1 = 0 \] \[ C = A \cdot B = 1 \cdot 1 = 1 \]So Sum = 0, Carry = 1. (1 + 1 = 10 in binary)
Problem: Find Sum and C_out for A = 1, B = 0, C_in = 1.
Solution:
\[ S = 1 \oplus 0 \oplus 1 = 0 \] \[ C_{out} = 1 \cdot 0 + 1(1 \oplus 0) = 0 + 1 = 1 \]So Sum = 0, C_out = 1. (1 + 0 + 1 = 10 in binary)
A multiplexer (MUX) is a combinational circuit that selects one of \( 2^n \) input lines and routes it to a single output line, based on \( n \) select lines. It is also called a data selector.
A 4:1 MUX has 4 data inputs (\( I_0, I_1, I_2, I_3 \)), 2 select lines (\( S_1, S_0 \)), and 1 output \( Y \).
| S₁ | S₀ | Output Y |
|---|---|---|
| 0 | 0 | \( I_0 \) |
| 0 | 1 | \( I_1 \) |
| 1 | 0 | \( I_2 \) |
| 1 | 1 | \( I_3 \) |
A 8:1 MUX can be built from two 4:1 MUX and one 2:1 MUX. Similarly, 16:1 MUX can be built from 4:1 MUXs and 4:1 MUX tree.
| Application | Description |
|---|---|
| Data selection | Selecting one of many data sources |
| Parallel-to-serial conversion | Send parallel data over a single line |
| Function generation | Implement any Boolean function using MUX |
| Communication systems | Time-division multiplexing |
| Display systems | Selecting display segments |
Problem: For a 4:1 MUX with \( S_1 S_0 = 10 \) and inputs \( I_0=1, I_1=0, I_2=1, I_3=0 \), find the output.
Solution:
\( S_1 S_0 = 10 \) selects \( I_2 \).
Therefore, \( Y = I_2 = 1 \).
A demultiplexer (DEMUX) is a combinational circuit that takes one input and routes it to one of \( 2^n \) output lines, based on \( n \) select lines. It is the reverse of a multiplexer.
A 1:4 DEMUX has 1 data input \( D \), 2 select lines (\( S_1, S_0 \)), and 4 outputs (\( Y_0, Y_1, Y_2, Y_3 \)).
| S₁ | S₀ | Y₀ | Y₁ | Y₂ | Y₃ |
|---|---|---|---|---|---|
| 0 | 0 | D | 0 | 0 | 0 |
| 0 | 1 | 0 | D | 0 | 0 |
| 1 | 0 | 0 | 0 | D | 0 |
| 1 | 1 | 0 | 0 | 0 | D |
| Feature | Multiplexer (MUX) | Demultiplexer (DEMUX) |
|---|---|---|
| Function | Many → One | One → Many |
| Data inputs | \( 2^n \) | 1 |
| Data outputs | 1 | \( 2^n \) |
| Select lines | \( n \) | \( n \) |
| Also called | Data selector | Data distributor |
| Applications | Data selection, PISO | Data distribution, SIPO |
Problem: For a 1:4 DEMUX with \( D = 1 \) and \( S_1 S_0 = 01 \), find the outputs.
Solution:
\( S_1 S_0 = 01 \) selects \( Y_1 \).
Therefore, \( Y_1 = D = 1 \), and \( Y_0 = Y_2 = Y_3 = 0 \).
An encoder converts \( 2^n \) input lines into an \( n \)-bit binary code. It is the reverse of a decoder.
| Inputs (I₀ I₁ I₂ I₃) | Outputs (A₁ A₀) |
|---|---|
| 1 0 0 0 | 0 0 |
| 0 1 0 0 | 0 1 |
| 0 0 1 0 | 1 0 |
| 0 0 0 1 | 1 1 |
A priority encoder is an encoder that includes priority logic. If multiple inputs are active simultaneously, the input with the highest priority is encoded. This avoids ambiguity when more than one input is 1.
A decoder converts an \( n \)-bit binary code into \( 2^n \) output lines, activating only one output at a time. It is used for memory addressing, seven-segment displays, and instruction decoding.
| A₁ | A₀ | Y₀ | Y₁ | Y₂ | Y₃ |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
A BCD-to-7-segment decoder takes a 4-bit BCD input and drives 7 output segments (a–g) to display decimal digits 0–9. Used in calculators, digital clocks, and meters.
| Feature | Encoder | Decoder |
|---|---|---|
| Function | \( 2^n \) inputs → n outputs | n inputs → \( 2^n \) outputs |
| Inputs | Many | Few |
| Outputs | Few (binary code) | Many (one active) |
| Application | Keyboard encoding, priority | Memory addressing, displays |
A digital comparator compares two binary numbers and determines whether they are equal, or which one is greater.
Compares two single bits A and B. Three outputs:
| A | B | A > B | A = B | A < B |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
Compares two 2-bit numbers \( A_1A_0 \) and \( B_1B_0 \). The comparison starts from the MSB. If MSBs are equal, comparison moves to the next bit.
| Application | Description |
|---|---|
| Microprocessor ALU | Comparison for branch instructions |
| Sorting networks | Data sorting in hardware |
| Analog-to-digital converters | Comparator-based flash ADCs |
| Control systems | Threshold detection |
| Test equipment | Digital multimeters, oscilloscopes |
| Circuit | Inputs | Outputs | Function |
|---|---|---|---|
| Half Adder | 2 | 2 (S, C) | Adds 2 bits |
| Full Adder | 3 | 2 (S, C_out) | Adds 3 bits |
| Half Subtractor | 2 | 2 (D, Bo) | Subtracts 2 bits |
| Full Subtractor | 3 | 2 (D, B_out) | Subtracts 3 bits |
| MUX (4:1) | 6 (4 data + 2 sel) | 1 | Selects 1 of 4 |
| DEMUX (1:4) | 3 (1 data + 2 sel) | 4 | Routes to 1 of 4 |
| Encoder (4:2) | 4 | 2 | Binary encoding |
| Decoder (2:4) | 2 | 4 | One-hot decoding |
| Comparator | 2n (n-bit each) | 3 | Compare two numbers |
| Concept | Formula / Rule |
|---|---|
| Decimal to Binary | Divide by 2, read remainders bottom-up |
| Binary to Decimal | \( \sum d_i \times 2^i \) |
| Binary to Hex | Group into 4 bits |
| Binary to Octal | Group into 3 bits |
| Hex to Binary | Each hex digit → 4 bits |
| Octal to Binary | Each octal digit → 3 bits |
| Binary to Gray | \( G_i = B_i \oplus B_{i+1} \) |
| Gray to Binary | \( B_i = B_{i+1} \oplus G_i \) |
| 2's Complement | 1's complement + 1 |
| Law | Expression |
|---|---|
| Identity | \( A + 0 = A \); \( A \cdot 1 = A \) |
| Null | \( A + 1 = 1 \); \( A \cdot 0 = 0 \) |
| Idempotent | \( A + A = A \); \( A \cdot A = A \) |
| Complement | \( A + \overline{A} = 1 \); \( A \cdot \overline{A} = 0 \) |
| Absorption | \( A + AB = A \); \( A(A+B) = A \) |
| Distributive | \( A(B+C) = AB + AC \) |
| De Morgan's 1 | \( \overline{A+B} = \overline{A} \cdot \overline{B} \) |
| De Morgan's 2 | \( \overline{A \cdot B} = \overline{A} + \overline{B} \) |
| Gate | Expression | Output = 1 when… |
|---|---|---|
| AND | \( A \cdot B \) | All inputs 1 |
| OR | \( A + B \) | Any input 1 |
| NOT | \( \overline{A} \) | Input is 0 |
| NAND | \( \overline{A \cdot B} \) | Not all inputs 1 |
| NOR | \( \overline{A + B} \) | All inputs 0 |
| XOR | \( A \oplus B \) | Inputs different |
| XNOR | \( \overline{A \oplus B} \) | Inputs same |
| Circuit | Key Formulas |
|---|---|
| Half Adder | \( S = A \oplus B \), \( C = AB \) |
| Full Adder | \( S = A \oplus B \oplus C_{in} \), \( C_{out} = AB + C_{in}(A \oplus B) \) |
| Half Subtractor | \( D = A \oplus B \), \( B_o = \overline{A}B \) |
| Full Subtractor | \( D = A \oplus B \oplus B_{in} \), \( B_{out} = \overline{A}B + \overline{A}B_{in} + BB_{in} \) |
| 4:1 MUX | \( Y = \sum_{i=0}^{3} m_i I_i \) |
| 1:4 DEMUX | \( Y_i = D \cdot m_i \) |
| 4:2 Encoder | \( A_1 = I_2 + I_3 \), \( A_0 = I_1 + I_3 \) |
| 2:4 Decoder | \( Y_i = m_i \) |
| 1-bit Comparator | \( (A>B)=A\overline{B} \), \( (A=B)=\overline{A \oplus B} \), \( (A |
Convert \( (11010110)_2 \) to decimal, octal, and hexadecimal.
Perform \( (10110)_2 + (1101)_2 \) and verify your answer in decimal.
Simplify \( Y = A\overline{B} + AB + \overline{A}B \) using Boolean algebra.
Simplify \( Y = \overline{(A+B) \cdot (C+D)} \) using De Morgan's theorems.
Simplify \( Y = \sum m(0, 1, 2, 4, 5, 6) \) using a 3-variable K-map.
Simplify \( Y = \sum m(0, 2, 5, 7, 8, 10, 13, 15) + d(1, 3) \) using a 4-variable K-map.
Design a full adder using two half adders and an OR gate. Draw the circuit.
Implement the Boolean function \( Y = \sum m(0, 1, 3, 5, 7) \) using an 8:1 multiplexer.
For a 1:8 DEMUX with \( D=1 \) and \( S_2 S_1 S_0 = 101 \), find the active output.
Design a 2-bit magnitude comparator. Write the expressions for \( A>B \), \( A=B \), and \( A
Binary: \( (11010110)_2 \)
Decimal:
\[ 1 \times 2^7 + 1 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 \] \[ = 128 + 64 + 0 + 16 + 0 + 4 + 2 + 0 = 214 \]Octal: Group into 3 bits from the right: 11 010 110 → pad: 011 010 110 → \( (326)_8 \)
Hex: Group into 4 bits: 1101 0110 → \( (D6)_{16} \)
Verify: \( 22 + 13 = 35 \) → \( (100011)_2 = 32 + 2 + 1 = 35 \) ✓
Group first two terms: \( A(\overline{B} + B) = A \)
\[ Y = A + \overline{A}B = (A + \overline{A})(A + B) = A + B \]Answer: \( Y = A + B \)
Apply De Morgan's 2:
\[ Y = \overline{(A+B)} + \overline{(C+D)} \]Apply De Morgan's 1:
\[ Y = \overline{A}\overline{B} + \overline{C}\overline{D} \]\( Y = \sum m(0, 1, 2, 4, 5, 6) \)
Answer: \( Y = \overline{B} + \overline{C} \)
\( Y = \sum m(0, 2, 5, 7, 8, 10, 13, 15) + d(1, 3) \)
Answer: \( Y = BD + \overline{B}\overline{D} + AC \)
Sum = \( A \oplus B \oplus C_{in} \)
C_out = \( AB + C_{in}(A \oplus B) \)
\( Y = \sum m(0, 1, 3, 5, 7) \)
Use an 8:1 MUX with select lines \( S_2 S_1 S_0 = A B C \).
Connect inputs: \( I_0 = 1, I_1 = 1, I_2 = 0, I_3 = 1, I_4 = 0, I_5 = 1, I_6 = 0, I_7 = 1 \)
These correspond to minterm indices \( m_0, m_1, m_3, m_5, m_7 \).
\( S_2 S_1 S_0 = 101 \) = decimal 5 → selects output \( Y_5 \).
Since \( D = 1 \), \( Y_5 = 1 \) and all other outputs are 0.
Compare \( A_1A_0 \) and \( B_1B_0 \).
Equal: \( (A=B) = (A_1 \odot B_1)(A_0 \odot B_0) \)
Greater: \( (A>B) = A_1\overline{B_1} + (A_1 \odot B_1)A_0\overline{B_0} \)
Less: \( (A Where \( \odot \) denotes XNOR (equality).
| Ref | Title | Author | Publisher |
|---|---|---|---|
| T-1 | Principles of Electronics | V. K. Mehta and Rohit Mehta | S. Chand & Company |
| R-1 | Electronic Devices and Circuit Theory | Robert L. Boylestad and Louis Nashelsky | Pearson Education India |
| R-2 | Digital Fundamentals | Thomas L. Floyd | Pearson Education India |
| Ref | Web Address | Feature |
|---|---|---|
| RW-2 | geeksforgeeks.org/computer-networks | Optical fiber and wireless communication |
| RW-3 | electronics-tutorials.ws/boolean/book_7.html | Logic gates |
| RW-4 | tutorialspoint.com/digital-electronics/four-variable-k-map | K-Map (up to 4 variables) |
| RW-5 | robocraze.com/blogs/post/what-are-multiplexers-and-demultiplexers | Multiplexers and de-multiplexers |
| Ref | Topic |
|---|---|
| AV-5 | Number system and codes |
| AV-6 | Adders and subtractors |
| CO | Description | Sections Covered |
|---|---|---|
| CO3 | Examine number system conversions and K-Map to simplify digital logic expressions | I, II, III, IV, V, VI, VII, VIII, IX, X, XI |
| CO4 | Analyze the operation and functionality of combinational logic circuits | XII, XIII, XIV, XV, XVI, XVII |
Digital Number Systems · Logic Gates · Boolean Algebra · K-Maps · Combinational Circuits
PHY 175 · Modern Physics and Electronics
Complete · Exam-Ready · Full Marks Guaranteed