Unit 3: Introduction to Number System and Logic Gates

I. Foundations of Digital Representation

Digital electronics represents information using discrete states, usually the binary digits (0) and (1). Number systems encode quantities, while Boolean algebra and logic gates describe how binary information is processed.

• Radix or base: A positional number system with base (r) uses digits from (0) to (r-1).
• Positional value: For digits (d_i), the value of a number is determined by powers of its base:
  
  TEXT

    N = Σ(d_i × r^i)

  
  Here, (N) is the number, (d_i) is the digit at position (i), and (r) is the radix.
• Common systems:
  • Binary: base (2), digits (0,1)
  • Octal: base (8), digits (0) through (7)
  • Decimal: base (10), digits (0) through (9)
  • Hexadecimal: base (16), digits (0) through (9) and (A) through (F)
• Binary conventions: The rightmost digit is the least significant bit (LSB); the leftmost is the most significant bit (MSB).
• Logic convention: Binary (0) usually represents LOW or false, while binary (1) represents HIGH or true.
• Bit groupings: Four bits form a nibble; eight bits form a byte.

II. Number Systems and Digital Codes — Representing Quantities

Number-system conversions preserve numerical value while changing its representation. Digital codes may instead encode decimal digits or arrange binary values to provide useful properties.

A. Number system conversion

Number-system conversion changes the radix in which a value is expressed without changing the quantity itself.

• Any base to decimal: Multiply each digit by its positional weight and add:
  
  TEXT

    (d_n...d_1d_0.d_-1...)_r = Σ(d_i × r^i)

  
  For example, ((101101.01)2 = 32+8+4+1+0.25=45.25{10}).
• Decimal integer to another base: Repeatedly divide by the new base; read the remainders from last to first.
• Decimal fraction to another base: Repeatedly multiply the fraction by the new base; read integer parts from first to last.
• Binary-octal conversion: Replace each octal digit with three binary bits, grouping binary digits in threes from the radix point.
• Binary-hexadecimal conversion: Replace each hexadecimal digit with four binary bits. Thus:
  
  TEXT

    (1101 0110)₂ = (D6)₁₆

• Required padding: Add zeros only at the outer ends of groups; padding does not alter value.

B. Binary to Gray and Gray to binary code conversion

Gray code orders values so that adjacent code words differ in exactly one bit, reducing transition errors in encoders and measurement systems.

1. Binary to Gray:

   • MSB rule: Copy the binary MSB directly.
   • Remaining bits: XOR each binary bit with the bit immediately to its left:
     
     TEXT

          G_n = B_n
          G_i = B_(i+1) ⊕ B_i

     
     Here, (B_i) and (G_i) are binary and Gray bits, and (\oplus) denotes XOR.

2. Gray to binary:

   • MSB rule: Copy the Gray MSB directly.
   • Remaining bits: XOR each Gray bit with the previously obtained binary bit:
     
     TEXT

          B_n = G_n
          B_i = B_(i+1) ⊕ G_i

   • Worked conversion: For binary (1011), the Gray bits are (1,\ 1\oplus0,\ 0\oplus1,\ 1\oplus1), giving (1110).

C. Excess-3

Excess-3 is a non-weighted decimal code obtained by adding (3) to each decimal digit and encoding the result in four-bit binary.

• Encoding rule:
  
  TEXT

    Excess-3 code of digit d = binary representation of (d + 3)

  
  Here, (d) is one decimal digit from (0) to (9).
• Example: Decimal (25) is encoded digit by digit: (2+3=5=0101_2) and (5+3=8=1000_2), so (25) becomes 0101 1000.
• Self-complementing property: Complementing all four bits produces the Excess-3 representation of the 9’s complement digit.
• Invalid combinations: 0000, 0001, 0010, 1101, 1110, and 1111 do not represent decimal digits.

D. BCD

Binary-coded decimal (BCD), commonly the 8421 code, represents each decimal digit independently using four weighted bits.

• Weights: The four positions have weights (8,4,2,1).
• Valid codes: 0000 through 1001 represent decimal (0) through (9); 1010 through 1111 are invalid.
• Example: Decimal (59) becomes 0101 1001, not binary 111011.
• BCD addition correction: If a four-bit digit sum exceeds 1001 or produces a carry, add 0110 to obtain a valid BCD digit and carry.
• Use: BCD is convenient in calculators and digital displays because decimal digits can be decoded separately.

III. Binary Operations — Complements and Arithmetic

Binary arithmetic follows positional rules like decimal arithmetic, but every operation uses only bits (0) and (1). Complements allow subtraction to be implemented through addition.

A. Compliments

Complements are alternative representations used for signed numbers and subtraction; the standard term in arithmetic is complements.

1. 1’s complement:

   • Rule: Replace every (0) with (1) and every (1) with (0).
   • Example: The 1’s complement of 001011 is 110100.
   • Range: An (n)-bit system represents (-(2^{n-1}-1)) to (+(2^{n-1}-1)), with separate positive and negative zeros.

2. 2’s complement:

   • Rule: Add (1) to the 1’s complement:
     
     TEXT

          2's complement of N = 2^n - N

     
     Here, (n) is the bit width and (N) is the unsigned magnitude.
   • Range: An (n)-bit system represents (-2^{n-1}) to (2^{n-1}-1).
   • Advantage: It has one representation for zero and supports addition and subtraction with the same hardware.

B. Binary arithmetic

Binary arithmetic applies base-2 addition, subtraction, multiplication, and division rules.

• Addition rules:
  
  TEXT

    0 + 0 = 0
    0 + 1 = 1
    1 + 0 = 1
    1 + 1 = 10
    1 + 1 + 1 = 11

• Subtraction rules: (1-0=1), (1-1=0), and (0-1) requires borrowing (10_2) from the next position.
• Multiplication: Partial products are either zero or the multiplicand; each new position shifts left by one bit.
• Division: Binary long division repeatedly compares, subtracts, and shifts, following the decimal method.
• Overflow: Signed overflow occurs when two operands with the same sign produce a result with the opposite sign.

C. Addition and subtraction using 2's complement

Two’s-complement arithmetic performs subtraction by adding the two’s complement of the subtrahend.

• Addition procedure: Sign-extend operands to equal width, add all bits, and discard any carry beyond the fixed width.
• Subtraction formula:
  
  TEXT

    A - B = A + (2's complement of B)

  
  Here, (A) is the minuend and (B) is the subtrahend.
• Worked example: Using five bits, calculate (13-7):
  
  TEXT

     01101       13
    +11001       2's complement of 00111
    ------
    100110

  
  Discarding the end carry gives 00110, or (6_{10}).
• Negative result: If no final carry appears, the result is negative; take its two’s complement to find its magnitude.
• Sign interpretation: In an (n)-bit signed number, MSB (0) indicates non-negative and MSB (1) indicates negative.

IV. Digital Logic — Gates and Boolean Operations

Digital logic maps binary inputs to binary outputs. Logic gates implement Boolean functions physically using electronic switching circuits.

A. Logic gates

A logic gate produces an output according to a defined truth function.

• NOT: Produces the complement, (Y=\overline{A}).
• AND: Produces (1) only when every input is (1), (Y=A\cdot B).
• OR: Produces (1) when at least one input is (1), (Y=A+B).
• NAND and NOR: Complement AND and OR respectively; each is a universal gate capable of implementing any Boolean function.
• XOR: Produces (1) when inputs differ, (Y=A\oplus B).
• XNOR: Produces (1) when inputs are equal, (Y=\overline{A\oplus B}).
• Two-input truth table:
  
  TEXT

    A B | AND OR NAND NOR XOR XNOR
    0 0 |  0   0   1    1   0    1
    0 1 |  0   1   1    0   1    0
    1 0 |  0   1   1    0   1    0
    1 1 |  1   1   0    0   0    1

B. Boolean algebra

Boolean algebra manipulates variables whose only values are (0) and (1), enabling logical expressions to be simplified.

• Identity laws: (A+0=A) and (A\cdot1=A).
• Null laws: (A+1=1) and (A\cdot0=0).
• Idempotent laws: (A+A=A) and (A\cdot A=A).
• Complement laws: (A+\overline A=1) and (A\overline A=0).
• Absorption laws: (A+AB=A) and (A(A+B)=A).
• Distributive laws: (A(B+C)=AB+AC) and (A+BC=(A+B)(A+C)).
• De Morgan’s theorems:
  
  TEXT

    overline(A + B) = overline(A) · overline(B)
    overline(A · B) = overline(A) + overline(B)

• Duality: Interchanging (+) with (\cdot), and (0) with (1), converts a valid identity into its dual.

V. Standard Forms and Minimization — SOP, POS, and K-Maps

Boolean functions can be written in standard algebraic forms and minimized to reduce gate count, input count, propagation delay, and circuit cost.

A. SOP and POS

Sum of products and product of sums express Boolean functions through combinations of literals, terms, and standard truth-table rows.

1. SOP:

   • Form: OR of product terms, such as (F=\overline AB+AC).
   • Canonical SOP: A sum of minterms; every minterm contains each variable once.
   • Minterm rule: For a row where (F=1), write a variable uncomplemented for input (1) and complemented for input (0).
   • Notation: (F(A,B,C)=\Sigma m(1,3,6)).

2. POS:

   • Form: AND of sum terms, such as (F=(A+B)(\overline A+C)).
   • Canonical POS: A product of maxterms; every maxterm contains each variable once.
   • Maxterm rule: For a row where (F=0), write a variable complemented for input (1) and uncomplemented for input (0).
   • Notation: (F(A,B,C)=\Pi M(0,2,4,5,7)).

B. K-Map (up to 4 variables)

A Karnaugh map graphically minimizes Boolean expressions by grouping adjacent cells whose coordinates differ in one variable.

• Map sizes: Two, three, and four variables require (4), (8), and (16) cells respectively.
• Gray-code order: Rows and columns follow 00, 01, 11, 10, ensuring one-bit adjacency.
• Grouping rule: Form rectangular groups containing (1,2,4,8,) or (16) cells; use the largest possible groups.
• Adjacency: Opposite edges are adjacent, and four corner cells may form one group; diagonal cells are not adjacent.
• SOP minimization: Group (1)s. Retain only variables that remain constant within each group.
• POS minimization: Group (0)s. A constant (0) gives an uncomplemented sum literal, while a constant (1) gives a complemented literal.
• Overlap and coverage: Groups may overlap when this produces simpler terms, but every required cell must be covered.
• Don’t-care conditions: Marked (X), they may be treated as (0) or (1) when doing so creates larger groups.
• Limitation: K-maps are practical up to four variables; larger functions are usually minimized algorithmically.