Unit 3: Introduction to number system and logic gates

1. Number Systems

A number system is a systematic way to represent numbers with symbolic characters. The base or radix of a number system is the total number of unique digits used to represent numbers.

1.1. Types of Number Systems

1.2. Number System Conversions

1.2.1. Decimal to Other Bases

Method (Integer Part): Use the Repeated Division Method.

1. Divide the decimal number by the new base.
2. Record the remainder.
3. Replace the number with the quotient and repeat steps 1 & 2 until the quotient is 0.
4. Write the remainders in reverse order of calculation to get the equivalent number.

Method (Fractional Part): Use the Repeated Multiplication Method.

1. Multiply the decimal fraction by the new base.
2. Record the integer part of the result.
3. Replace the fraction with the fractional part of the result and repeat steps 1 & 2 until the fractional part is 0 or sufficient precision is reached.
4. Write the recorded integers in the order of calculation.

Example: Convert (42.625)₁₀ to Binary

• Integer Part (42):
  • 42 / 2 = 21, Remainder = 0
  • 21 / 2 = 10, Remainder = 1
  • 10 / 2 = 5, Remainder = 0
  • 5 / 2 = 2, Remainder = 1
  • 2 / 2 = 1, Remainder = 0
  • 1 / 2 = 0, Remainder = 1
  • Result (reverse order): (101010)₂
• Fractional Part (0.625):
  • 0.625 * 2 = 1.25
  • 0.25 * 2 = 0.5
  • 0.5 * 2 = 1.0
  • Result (forward order): (.101)₂
• Final Answer: (101010.101)₂

1.2.2. Other Bases to Decimal

Method: Use the Positional Weight Method.

1. Multiply each digit by its positional weight (base raised to the power of the position).
2. The position of the first digit to the left of the radix point is 0, the next is 1, and so on. The position of the first digit to the right is -1, the next is -2, etc.
3. Sum up all the products.

Example: Convert (1A.4)₁₆ to Decimal

• (1A.4)₁₆ = (1 × 16¹) + (A × 16⁰) + (4 × 16⁻¹)
• = (1 × 16) + (10 × 1) + (4 × 0.0625)
• = 16 + 10 + 0.25
• Final Answer: (26.25)₁₀

Example: Convert (10110.11)₂ to Decimal

• (10110.11)₂ = (1×2⁴) + (0×2³) + (1×2²) + (1×2¹) + (0×2⁰) + (1×2⁻¹) + (1×2⁻²)
• = (16) + (0) + (4) + (2) + (0) + (0.5) + (0.25)
• Final Answer: (22.75)₁₀

1.2.3. Binary to Octal & Hexadecimal (and vice-versa)

This is a shortcut method based on grouping bits.

• Binary to Octal: Group binary digits into sets of 3 bits, starting from the radix point. Add leading/trailing zeros if needed. Convert each group to its octal equivalent.
• Octal to Binary: Convert each octal digit into its 3-bit binary equivalent.
• Binary to Hexadecimal: Group binary digits into sets of 4 bits, starting from the radix point. Add leading/trailing zeros if needed. Convert each group to its hexadecimal equivalent.
• Hexadecimal to Binary: Convert each hexadecimal digit into its 4-bit binary equivalent.

Conversion Table:

Example: Convert (101101110.0101)₂ to Octal and Hexadecimal

• To Octal:
  • Group: (101)(101)(110) . (010)(100) (added trailing zeros)
  • Convert: ( 5 )( 5 )( 6 ) . ( 2 )( 4 )
  • Result: (556.24)₈
• To Hexadecimal:
  • Group: (0001)(0110)(1110) . (0101)
  • Convert: ( 1 )( 6 )( E ) . ( 5 )
  • Result: (16E.5)₁₆

2. Digital Codes

Digital codes are used to represent decimal digits, letters, and symbols.

2.1. BCD (Binary Coded Decimal)

• Each decimal digit (0-9) is represented by its 4-bit binary equivalent.
• It is a weighted code. The weights are 8, 4, 2, 1.
• The binary combinations 1010 through 1111 are invalid in BCD.

Example: Convert (189)₁₀ to BCD

• 1 → 0001
• 8 → 1000
• 9 → 1001
• BCD: 0001 1000 1001

2.2. Excess-3 Code

• An unweighted, self-complementing code.
• Derived from BCD by adding 3 (0011) to each BCD value.
• Self-complementing: The 9's complement of a decimal digit can be found by inverting the bits of its Excess-3 code.

Example: Convert (5)₁₀ to Excess-3

1. Decimal: 5
2. BCD: 0101
3. Add 3 (0011): 0101 + 0011 = 1000
4. Excess-3: 1000

2.3. Gray Code

• An unweighted, non-arithmetic code.
• Its primary feature is that successive code words differ by only one bit. This property is important for reducing errors in electromechanical systems.

2.3.1. Binary to Gray Code Conversion (B-G)

1. The Most Significant Bit (MSB) of the Gray code is the same as the MSB of the binary number.
2. Moving from left to right, add the current binary bit to the previous binary bit (without carry) to get the next Gray code bit. This is equivalent to an XOR operation.
   • Gᵢ = Bᵢ ⊕ Bᵢ₊₁ (where Bᵢ₊₁ is the bit to the left of Bᵢ)

Example: Convert (1011)₂ to Gray Code

  Binary:  1   0   1   1
           |  / \ / \ / \
           | XoR XoR XoR
           V   V   V   V
Gray Code: 1   1   1   0

1. MSB: G₃ = B₃ = 1
2. G₂ = B₃ ⊕ B₂ = 1 ⊕ 0 = 1
3. G₁ = B₂ ⊕ B₁ = 0 ⊕ 1 = 1
4. G₀ = B₁ ⊕ B₀ = 1 ⊕ 1 = 0
   • Result: 1110

2.3.2. Gray to Binary Code Conversion (G-B)

1. The MSB of the binary number is the same as the MSB of the Gray code.
2. Moving from left to right, add the current binary bit to the next Gray code bit (without carry) to get the next binary bit.
   • Bᵢ = Bᵢ₊₁ ⊕ Gᵢ

Example: Convert 1110 (Gray) to Binary

Gray Code: 1   1   1   0
           | \ / \ / \ /
           | XoR XoR XoR
           V   V   V   V
  Binary:  1   0   1   1

1. MSB: B₃ = G₃ = 1
2. B₂ = B₃ ⊕ G₂ = 1 ⊕ 1 = 0
3. B₁ = B₂ ⊕ G₁ = 0 ⊕ 1 = 1
4. B₀ = B₁ ⊕ G₀ = 1 ⊕ 0 = 1
   • Result: (1011)₂

3. Boolean Algebra

Boolean algebra is the algebra of logic, operating on variables that can have only two values: TRUE (1) or FALSE (0). It's the mathematical foundation for digital circuits.

Basic Operations:

• AND (.): Logical Multiplication (A AND B is written as A.B or AB)
• OR (+): Logical Addition (A OR B is written as A+B)
• NOT ('): Logical Inversion/Complement (NOT A is written as A' or Ā)

3.1. Postulates and Laws

3.2. De Morgan's Theorems

These are crucial for simplifying expressions and converting between logic forms.

1. (A + B)' = A' . B'
   • The complement of a sum is the product of the complements.
2. (A . B)' = A' + B'
   • The complement of a product is the sum of the complements.

Example: Simplify F = (A'B' + C)'

1. Apply De Morgan's first theorem: F = (A'B')' . C'
2. Apply De Morgan's second theorem to (A'B')': F = ((A')' + (B')') . C'
3. Apply Involution Law: F = (A + B) . C'
4. Apply Distributive Law: F = A.C' + B.C'
   • Simplified Expression: F = AC' + BC'

4. Canonical and Standard Forms

4.1. Minterms and Maxterms

For a function with 'n' variables, there are 2ⁿ possible combinations.

• Minterm (m): A product term (AND) that contains all 'n' variables, either in true or complemented form. A minterm is 1 for only one specific combination of inputs.
• Maxterm (M): A sum term (OR) that contains all 'n' variables, either in true or complemented form. A maxterm is 0 for only one specific combination of inputs.

4.2. Sum of Products (SOP)

• An SOP expression is a logical ORing of two or more AND terms (minterms).
• Derived from a truth table by summing the minterms for which the function output is 1.
• Also called "Disjunctive Normal Form" (DNF).
• Shorthand notation: Σm(...)

Example: A function F is 1 for combinations ABC = 001, 100, 111.

• F = A'B'C + AB'C' + ABC
• F = m₁ + m₄ + m₇
• F(A,B,C) = Σm(1, 4, 7)

4.3. Product of Sums (POS)

• A POS expression is a logical ANDing of two or more OR terms (maxterms).
• Derived from a truth table by multiplying the maxterms for which the function output is 0.
• Also called "Conjunctive Normal Form" (CNF).
• Shorthand notation: ΠM(...)

Example: A function F is 0 for combinations ABC = 000, 010, 101.

• F = (A+B+C) . (A+B'+C) . (A'+B+C')
• F = M₀ . M₂ . M₅
• F(A,B,C) = ΠM(0, 2, 5)

5. Logic Gates

Logic gates are the basic building blocks of digital circuits. Each gate performs a specific Boolean function.

Gate	Symbol	Boolean Expression	Truth Table	Description
AND		Y = A . B	A B | Y --- | - 0 0 | 0 0 1 | 0 1 0 | 0 1 1 | 1	Output is HIGH (1) only when all inputs are HIGH.
OR		Y = A + B	A B | Y --- | - 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 1	Output is HIGH (1) when any input is HIGH.
NOT (Inverter)		Y = A'	A | Y - | - 0 | 1 1 | 0	Output is the complement (inverse) of the input.
NAND (Universal)		Y = (A . B)'	A B | Y --- | - 0 0 | 1 0 1 | 1 1 0 | 1 1 1 | 0	Output is LOW (0) only when all inputs are HIGH. (NOT-AND)
NOR (Universal)		Y = (A + B)'	A B | Y --- | - 0 0 | 1 0 1 | 0 1 0 | 0 1 1 | 0	Output is HIGH (1) only when all inputs are LOW. (NOT-OR)
XOR (Exclusive OR)		Y = A ⊕ B = A'B + AB'	A B | Y --- | - 0 0 | 0 0 1 | 1 1 0 | 1 1 1 | 0	Output is HIGH (1) when an odd number of inputs are HIGH.
XNOR (Exclusive NOR)		Y = (A ⊕ B)' = A'B' + AB	A B | Y --- | - 0 0 | 1 0 1 | 0 1 0 | 0 1 1 | 1	Output is HIGH (1) when inputs are the same (both HIGH or both LOW).

NAND and NOR gates are called Universal Gates because any other logic gate (AND, OR, NOT) can be constructed using only NAND gates or only NOR gates.

6. Karnaugh Map (K-Map)

The K-map is a graphical method used to simplify Boolean expressions. It's a visual representation of a truth table.

Key Features:

• Cell arrangement follows Gray code, meaning adjacent cells (including wrap-around) differ by only one variable.
• This adjacency property allows for easy identification of terms that can be simplified.

6.1. K-Map Structures

2-Variable K-Map (for F(A,B))

      B=0 B=1
    +---+---+
A=0 | 0 | 1 |
    +---+---+
A=1 | 2 | 3 |
    +---+---+
(Cell numbers are minterm indices)

3-Variable K-Map (for F(A,B,C))

       BC
      00  01  11  10
    +---+---+---+---+
A=0 | 0 | 1 | 3 | 2 |
    +---+---+---+---+
A=1 | 4 | 5 | 7 | 6 |
    +---+---+---+---+

4-Variable K-Map (for F(A,B,C,D))

       CD
      00  01  11  10
    +---+---+---+---+
AB=00 | 0 | 1 | 3 | 2 |
    +---+---+---+---+
AB=01 | 4 | 5 | 7 | 6 |
    +---+---+---+---+
AB=11 | 12| 13| 15| 14|
    +---+---+---+---+
AB=10 | 8 | 9 | 11| 10|
    +---+---+---+---+

6.2. Rules for K-Map Simplification (SOP)

1. Plot the 1s: Place a '1' in each cell corresponding to a minterm of the function.
2. Group Adjacent 1s:
   • Groups must contain a number of 1s that is a power of 2 (e.g., 1, 2, 4, 8, 16).
   • Groups must be in the shape of a rectangle or a square.
   • Groups can wrap around the edges of the map.
3. Create Largest Possible Groups: Make each group as large as you can to achieve maximum simplification.
4. Cover all 1s: Ensure every '1' on the map is included in at least one group. Groups can overlap.
5. Write the Simplified Expression:
   • For each group, determine which variables remain constant (do not change value within the group).
   • Write a product term for these constant variables. If a variable is constant at 0, use its complement; if it's constant at 1, use its true form.
   • The final simplified expression is the sum (OR) of all the product terms derived from the groups.

6.3. Example: 4-Variable K-Map Simplification

Simplify the function: F(A,B,C,D) = Σm(0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14)

1. Plot the K-Map:
   

   TEXT

              CD
             00  01  11  10
           +---+---+---+---+
       AB=00 | 1 | 1 | 0 | 1 |
           +---+---+---+---+
       AB=01 | 1 | 1 | 0 | 1 |
           +---+---+---+---+
       AB=11 | 1 | 1 | 0 | 1 |
           +---+---+---+---+
       AB=10 | 1 | 1 | 0 | 0 |
           +---+---+---+---+
       

2. Group the 1s:

   • Group 1 (Red): An octet (group of 8) formed by the cells in columns CD=00 and CD=01. This is a wrap-around group of columns.

     • m(0,1,4,5,8,9,12,13)

   • Group 2 (Blue): A quad (group of 4) formed by cells m(4,6,12,14). This group wraps around horizontally.

     • Wait, let's re-plot more clearly. The provided minterms are: 0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14.

   Correct Plot:
   

   TEXT

              CD
             00  01  11  10
           +---+---+---+---+
       AB=00 | 1 | 1 | 0 | 1 |  (m0, m1, m2)
           +---+---+---+---+
       AB=01 | 1 | 1 | 0 | 1 |  (m4, m5, m6)
           +---+---+---+---+
       AB=11 | 1 | 1 | 0 | 1 |  (m12, m13, m14)
           +---+---+---+---+
       AB=10 | 1 | 1 | 0 | 0 |  (m8, m9)
           +---+---+---+---+
       

   Correct Grouping:

   • Group 1 (Octet): The largest group is an octet covering the first two columns (CD=00 and CD=01).

     • Cells: m(0,1,4,5,8,9,12,13)
     • A changes, B changes, D changes.
     • The only variable that stays constant is C=0.
     • Term: C'

   • Group 2 (Quad): A group of four covering m(0,2,4,6). This is not possible. Let's look for another group.

   • Let's re-examine the map. We have uncovered 1s at m2, m6, m14.

   • Group 2 (Quad): A group of four covering m(4, 5, 6, 7) is not right.

   • Let's check the corners. No.

   • Let's form a quad with m(0,2,8,10). No, m10 is not in the function.

   • Let's form a quad with m(4,6,12,14). These are m(4), m(6), m(12), m(14). Let's see...

     • m4: AB=01, CD=00
     • m6: AB=01, CD=10
     • m12: AB=11, CD=00
     • m14: AB=11, CD=10
     • This forms a valid 2x2 group.
     • In this group: A changes, C changes.
     • Variable B is constant at 1 (B).
     • Variable D is constant at 0 (D').
     • Term: BD'

   • Group 3 (Quad): Now, let's look at remaining 1s.

     • The octet (Group 1) covered m(0,1,4,5,8,9,12,13).
     • The quad (Group 2) covered m(4,6,12,14).
     • Remaining uncovered 1s: m(2).
     • We need to cover m(2). We can do this with a pair m(0,2) or m(2,6). Let's take the pair m(2,6).
     • m2: AB=00, CD=10
     • m6: AB=01, CD=10
     • A changes, B is not constant.
     • C is constant at 1 (C). D is constant at 0 (D').
     • Wait, let's rethink the whole grouping to be optimal.

   Optimal Grouping Strategy:

   1. Start with the largest possible groups.
   2. Cover any remaining 1s with the largest possible groups.

   Let's restart the grouping on the correctly plotted map:
   

   TEXT

              CD
             00  01  11  10
           +---+---+---+---+
       AB=00 | 1 | 1 | 0 | 1 |
           +---+---+---+---+
       AB=01 | 1 | 1 | 0 | 1 |
           +---+---+---+---+
       AB=11 | 1 | 1 | 0 | 1 |
           +---+---+---+---+
       AB=10 | 1 | 1 | 0 | 0 |
           +---+---+---+---+
       

   • Group 1 (Octet): Covers all 1s in columns CD=00 and CD=01.

     • Variables changing: A, B, D.
     • Variable constant: C=0.
     • Term: C'

   • Group 2 (Quad): Covers the 1s at m(4, 6, 12, 14).

     • Variables changing: A, C.
     • Variables constant: B=1, D=0.
     • Term: BD'

   • Group 3 (Quad): Covers the 1s at m(0, 2, 4, 6). No, m(0), m(2), m(8), m(10) is a valid quad but m10 is 0.

   • Let's try m(0,2) with m(4,6) forming a quad.

     • m0, m2, m4, m6
     • A changes (0 -> 1)
     • B is constant at 0 for m0,m2. Constant at 1 for m4,m6. Not a valid group.

   • Let's check the remaining 1s after Group 1 and Group 2:

     • Group 1 (C') covers: 0, 1, 4, 5, 8, 9, 12, 13.
     • Group 2 (BD') covers: 4, 6, 12, 14.
     • All 1s are now covered except for m(2).
     • We must cover m(2). We can group it with m(6) to form a pair.

   • Group 3 (Pair): Covers m(2) and m(6).

     • m2(0010), m6(0110)
     • A changes.
     • B is constant at 0 in AB=00 and 1 in AB=01. Not right. Let's look at the map variables.
     • For m(2) and m(6):
       • A is constant: 0 for m2, 0 for m6. Wait, A is the first var of AB. A=0 for both.
       • B changes (0 -> 1).
       • C is constant: 1.
       • D is constant: 0.
     • Term: A'CD'

3. Final Expression:

   • Sum the terms from the groups.
   • F = C' + BD' + A'CD'

   Let's check for a more optimal solution. What if we grouped m(2) with m(0)?

   • Alternative Group 3 (Pair): m(0) and m(2)
     • A=0, B=0, D=0.
     • Term: A'B'D'
   • This gives: F = C' + BD' + A'B'D'. This is also a valid simplified solution. Both solutions have the same number of terms and literals, so they are equally simple. The first is typically preferred. Let's stick with F = C' + BD' + A'CD'.