C

Unit 1: Digital Systems, Number Systems, and Conversion (EENG 2710)

Digital Systems and Switching Circuits

  • Digital vs. analog systems
    • Digital: physical quantities/signals are discrete values; higher accuracy and reliability in computation, data processing, control, communications, and measurement.
    • Analog: quantities vary continuously over a range; outputs can have errors from a fraction of a percent to several percent.
    • Digital systems enable robust interfacing with two-valued signals and binary numbers.
  • Two major types of circuits
    • Combinational circuits: outputs depend only on current inputs.
    • Sequential circuits: outputs depend on past and present inputs (memory).
  • Design perspective for digital systems
    • System design: partition into subsystems and define each subsystem's characteristics.
    • Logic design: interconnect basic logic blocks to perform a function.
    • Circuit design: interconnect hardware components (diodes, transistors, etc.) to form logic gates, flip-flops; mostly implemented in ICs using CAD tools.
  • Building blocks of switching circuits
    • Combinational blocks: logic gates (AND, OR, NOT, etc.).
    • Sequential blocks: flip-flops (memory elements).
    • Switching devices: typically two-state devices (relays, diodes, transistors).
    • Internal binary numbers: natural to use binary representations due to two-state outputs of devices.

Number Systems and Conversion

  • Base and positional notation
    • Any base R > 1 uses digits 0, 1, …, R-1.
    • A number in base R can be expanded as a power series: N = an R^n + a{n-1} R^{n-1} + \cdots + a1 R^1 + a0 R^0, where 0 ≤ a_i ≤ R−1.
    • Decimal point separates positive and negative powers of the base.
  • Examples (positional notation)
    • Decimal example: 953.78 = 9\cdot 10^2 + 5\cdot 10^1 + 3\cdot 10^0 + 7\cdot 10^{-1} + 8\cdot 10^{-2}.
    • Binary example: (1011.11)2 = 1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 + 1\cdot 2^{-1} + 1\cdot 2^{-2} = 11.75{10}.
  • Power-series expansion in base R
    • Any positive integer N can be written in base R as N=(an a{n-1} \dots a1 a0)R = an R^n + a{n-1} R^{n-1} + \cdots + a1 R + a0, with 0 ≤ ai ≤ R−1.
    • If R > 10, digits beyond 9 use letters (e.g., A=10, B=11, … in hex).
  • Examples with base 8 and base 16
    • Example: (147.3)8 = 1\cdot 8^2 + 4\cdot 8^1 + 7\cdot 8^0 + 3\cdot 8^{-1} = 64 + 32 + 7 + \frac{3}{8} = 103.375{10}.
    • Example: (A2F){16} = 10\cdot 16^2 + 2\cdot 16^1 + 15\cdot 16^0 = 2560 + 32 + 15 = 2607{10}.
  • Base conversion: decimal integers to base R using division method
    • Representation: N = (an a{n-1} \dots a1 a0)R = an R^n + a{n-1} R^{n-1} + \cdots + a1 R + a_0.
    • Division steps: divide N by R to get quotient Q1 and remainder a0; then divide Q1 by R to get Q2 and remainder a1; continuing until the quotient is 0. The digits in reverse order are a0, a1, …, an.
    • Note: the remainder at each step is the next digit (least significant first).
  • Decimal fraction to base R using successive multiplication
    • A decimal fraction F in base 10 can be written as F = (0.a{-1} a{-2} a{-3} \dots a{-m})R = a{-1}R^{-1} + a{-2}R^{-2} + \cdots + a{-m}R^{-m}.
    • Multiply by R: FR = a{-1} + F1, where a{-1} = \lfloor FR \rfloor \in {0,1,\dots,R-1} and F1 = FR - a_{-1}.
    • Continue: multiply F1 by R to get F1R = a{-2} + F2, etc. Digits a_{-k} are obtained in order from most significant to least.
    • Examples: binary/Octal/Hex fractional conversions (0.625){10} → (0.101){2}, (0.1285){10} → (0.1224…){8}, (0.479){10} → (0.7…){16} (illustrative).
  • Converting between binary, octal, and hexadecimal
    • Binary to hex: group bits in sets of 4 from right to left; each group maps to a hex digit.
    • Binary to octal: group bits in sets of 3 from right to left; each group maps to an octal digit.
    • Example: (100101101011010)2 = (45532)8.
  • Conversion tables and common codes
    • Decimal ↔ Binary ↔ Octal ↔ Hex usually tabulated; example mappings for single digits in common codes listed below.
  • Binary Codes for decimal digits (Table excerpts)
    • BCD (8-4-2-1) coding: replace each decimal digit by its 4-bit binary equivalent.
    • 0 → 0000, 1 → 0001, 2 → 0010, 3 → 0011, 4 → 0100, 5 → 0101, 6 → 0110, 7 → 0111, 8 → 1000, 9 → 1001.
    • Excess-3 code: BCD digit + 3 (0000 becomes 0011, etc.).
    • 2-out-of-5 code: for every valid decimal digit, exactly 2 of 5 bits are 1.
    • Gray code: digits differ by exactly one bit between successive decimal values.
  • ASCII and other character encodings
    • ASCII: 7-bit code; supports letters, digits, and symbols.
    • Example encodings (7-bit): for the word “Start” the bits are shown as
    • S: 01010011, t: 01110100, a: 01100001, r: 01110010, t: 01110100.
    • ASCII tables map decimal/hex values to characters; e.g., 0x53 is 'S', 0x74 is 't', 0x61 is 'a', 0x72 is 'r'.
  • Other common binary codes
    • 8-4-2-1 code and 6-3-1-1 code are weighted codes: N = w3 a3 + w2 a2 + w1 a1 + w0 a0, with weights (8-4-2-1) or (6-3-1-1).
    • Examples: In 6-3-1-1, digit 8 is encoded as 1010, etc.; Excess-3 adds 3 to the 8-4-2-1 representation to yield the code for the digit.
  • Practical note on codes
    • Binary codes are used because digital circuits operate on discrete signals; I/O equipment often uses decimal, hence the need for binary-coded representations (BCD, gray, etc.).

Binary Arithmetic

  • Binary addition
    • Arithmetic in digital systems is performed in binary (base 2).
    • Truth table for addition:
    • 0 + 0 = 0
    • 0 + 1 = 1
    • 1 + 0 = 1
    • 1 + 1 = 0 with carry 1 to the next column.
  • Binary subtraction
    • Subtraction table (borrow concept):
    • 0 − 0 = 0
    • 0 − 1 = 1 with borrow 1 from the next column
    • 1 − 0 = 1
    • 1 − 1 = 0
  • Binary multiplication
    • Like decimal multiplication, but with bits 0/1; four basic bit products:
    • 0 × 0 = 0, 0 × 1 = 0, 1 × 0 = 0, 1 × 1 = 1.
    • A common method to manage carries is to add partial products one at a time.
    • Example (1111) × (1101): final product is 11000011 (195 in decimal).
  • Binary division
    • Long division with quotient bits 0 or 1 only.
    • Algorithm: compare divisor with the upper bits of dividend, subtract when possible, record 1 in quotient, append next dividend bit, repeat until bits run out.

Representation of Negative Numbers

  • Three common methods
    • Sign and magnitude (sign bit indicates sign)
    • 1’s complement
    • 2’s complement
  • Sign & magnitude
    • Leftmost bit is sign: 0 for positive, 1 for negative.
    • Example: +5 in 4 bits: 0101; −5 in 4 bits: 1101.
  • 1’s complement
    • Positive number N: 0 followed by magnitude; Negative −N is the 1’s complement of N: N* = 2^n − 1 − N, equivalently bitwise NOT of N.
    • Example (4-bit): +5 = 0101; −5 = 1010 (since 1111 − 0101 = 1010).
  • 2’s complement
    • Positive numbers have a leading 0; negative numbers −N are N* = 2^n − N.
    • Obtain by bitwise NOT of N and adding 1: N* = (NOT N) + 1.
    • Range: −2^{n-1} ≤ M ≤ 2^{n-1} − 1 for n-bit representation.
    • Example (4-bit): +5 = 0101; −5 = 1011 (since 0101 → NOT 1010 → add 1 → 1011).
  • Overflow
    • Occurs when the result of an operation is outside the representable range.

Binary Codes (Binary Coding Schemes)

  • Why binary codes
    • Computers operate on binary signals internally, while I/O often uses decimal.
  • Common code families
    • BCD (8-4-2-1) Code
    • Each decimal digit is encoded by a 4-bit binary code.
    • Valid BCD digits for 0–9 map to 0000–1001; codes 1010–1111 are invalid for BCD.
    • Excess-3 Code
    • Each decimal digit is represented by its 4-bit BCD code plus 3 (i.e., add 0011).
    • 2-out-of-5 Code
    • Each decimal digit is represented by 5 bits with exactly two 1s.
    • Gray Code
    • A binary encoding where successive decimal digits differ in exactly one bit.
  • ASCII (7-bit) Code
    • 7-bit encoding for characters; 2^7 = 128 distinct codes.
    • Example encodings used to spell a word: S t a r t
    • S = 01010011, t = 01110100, a = 01100001, r = 01110010, t = 01110100.
  • Additional notes
    • Gray code table (0–15):
    • Decimal: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    • Binary: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
    • Gray: 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
  • Examples for cross-checking conversions
    • Binary to hexadecimal grouping example: (100101101011010)2 → (45532)8
    • Decimal digits to digit-weights (Weights example): For 6-3-1-1 code, a digit N = 6a3 + 3a2 + 1a1 + 1a0.
  • ASCII table concept
    • ASCII maps decimal/hex values to characters; the excerpt shows the start of the ASCII table with common control characters and letters.

Worked Examples and Key Takeaways

  • Example conversions and rules from the notes
    • Convert decimal 53 to binary using division-by-2 method:</n- Step-by-step divisions yield binary 110101.
    • Convert decimal 234 to octal using division-by-8 method: 234{10} → (344){8} (illustrative).
    • Convert decimal 315 to hexadecimal: 0x13B (illustrative).
    • Convert (1011.11)2 to decimal: (1011.11)2 = 1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 + 1\cdot 2^{-1} + 1\cdot 2^{-2} = 11.75_{10}.
    • Convert octal 147.38 to decimal: 1\cdot 8^2 + 4\cdot 8^1 + 7\cdot 8^0 + 3\cdot 8^{-1} = 64+32+7+0.375 = 103.375{10}.
    • Convert hex A2F{16} to decimal: 10\cdot 16^2 + 2\cdot 16^1 + 15\cdot 16^0 = 2560+32+15 = 2607{10}.
    • Convert (45532)_8 back to binary/decimal as needed by grouping and weights.
  • Real-world relevance
    • Understanding number systems is foundational for digital logic design, computer architecture, data encoding, error detection/correction, and embedded systems.
  • Ethical/philosophical/practical implications
    • Accurate representation and conversion of numbers underlies security, financial calculations, and reliable communication systems.

Notes on equations used in this unit

  • General base representation
    • N = an R^n + a{n-1} R^{n-1} + \cdots + a1 R^1 + a0 R^0.
  • Fractional part in a base
    • F = a{-1}R^{-1} + a{-2}R^{-2} + \cdots + a_{-m}R^{-m}.
  • Decimal to base R (division method)
    • If N = a{n}R^{n} + \cdots + a1R + a_0, division produces remainders a0, a1, …, an.
  • Fractional multiplication (successive multiplication method)
    • FR = a{-1} + F1, \ F1 = FR - a{-1},
    • and recursively Fk R = a{-(k+1)} + F_{k+1}.
  • 2’s complement
    • N^* = 2^n - N \, (for n\text{-bit representation}) and perform bitwise NOT followed by +1 to obtain the negative representation.
  • Weighted codes (example)
    • For 8-4-2-1: N = 8a3 + 4a2 + 2a1 + a0.
    • For 6-3-1-1: N = 6a3 + 3a2 + 1a1 + 1a0.$n

Digital Systems and Switching Circuits

  • Digital vs. analog systems
    • Digital: physical quantities/signals are discrete values; higher accuracy and reliability in computation, data processing, control, communications, and measurement.
    • Analog: quantities vary continuously over a range; outputs can have errors from a fraction of a percent to several percent.
  • Digital systems enable robust interfacing with two-valued signals and binary numbers.
  • Two major types of circuits
    • Combinational circuits: outputs depend only on current inputs.
    • Sequential circuits: outputs depend on past and present inputs (memory).
  • Design perspective for digital systems
    • System design: partition into subsystems and define each subsystem's characteristics.
    • Logic design: interconnect basic logic blocks to perform a function.
    • Circuit design: interconnect hardware components (diodes, transistors, etc.) to form logic gates, flip-flops; mostly implemented in ICs using CAD tools.
  • Building blocks of switching circuits
    • Combinational blocks: logic gates (AND, OR, NOT, etc.).
    • Sequential blocks: flip-flops (memory elements).
    • Switching devices: typically two-state devices (relays, diodes, transistors).
  • Internal binary numbers: natural to use binary representations due to two-state outputs of devices.

Number Systems and Conversion

  • Base and positional notation

    • Any base R > 1 uses digits 0, 1, …, R-1.
    • A number in base R can be expanded as a power series: N = an R^n + a{n-1} R^{n-1} + \cdots + a1 R^1 + a0 R^0, where 0 \le a_i \le R-1.
    • Decimal point separates positive and negative powers of the base.

  • Examples (positional notation)

    • Decimal example: 953.78 = 9\cdot 10^2 + 5\cdot 10^1 + 3\cdot 10^0 + 7\cdot 10^{-1} + 8\cdot 10^{-2}.
    • Binary example: (1011.11)2 = 1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 1\cdot 2^0 + 1\cdot 2^{-1} + 1\cdot 2^{-2} = 11.75{10}.

  • Power-series expansion in base R

    • Any positive integer N can be written in base R as \quad N=(an a{n-1} \dots a1 a0)R = an R^n + a{n-1} R^{n-1} + \cdots + a1 R + a0, with 0 \le ai \le R-1.
    • If R > 10, digits beyond 9 use letters (e.g., A=10, B=11,
      …).

  • Examples with base 8 and base 16

    • Example: (147.3)8 = 1\cdot 8^2 + 4\cdot 8^1 + 7\cdot 8^0 + 3\cdot 8^{-1} = 64 + 32 + 7 + \frac{3}{8} = 103.375{10}.
    • Example: (A2F){16} = 10\cdot 16^2 + 2\cdot 16^1 + 15\cdot 16^0 = 2560 + 32 + 15 = 2607{10}.

  • Base conversion: decimal integers to base R using division method

    • Representation: N = (an a{n-1} \dots a1 a0)R = an R^n + a{n-1} R^{n-1} + \cdots + a1 R + a_0.
    • Division steps: divide N by R to get quotient Q1 and remainder a0; then divide Q1 by R to get Q2 and remainder a1; continuing until the quotient is 0. The digits in reverse order are a0, a1, …, an.
    • Note: the remainder at each step is the next digit (least significant first).
    • Example: Convert decimal 53_{10} to binary (R=2).

    53 \div 2 = 26 \text{ R } 1 \quad (a_0)

    26 \div 2 = 13 \text{ R } 0 \quad (a_1)

    13 \div 2 = 6 \text{ R } 1 \quad (a_2)

    6 \div 2 = 3 \text{ R } 0 \quad (a_3)

    3 \div 2 = 1 \text{ R } 1 \quad (a_4)

    1 \div 2 = 0 \text{ R } 1 \quad (a5) Reading the remainders from bottom up: (53){10} = (110101)_2.

  • Decimal fraction to base R using successive multiplication

    • A decimal fraction F in base 10 can be written as F = (0.a{-1} a{-2} a{-3} \dots a{-m})R = a{-1}R^{-1} + a{-2}R^{-2} + \cdots + a{-m}R^{-m}.
    • Multiply by R: FR = a{-1} + F1, where a{-1} = \lfloor FR \rfloor \in {0,1,\dots,R-1} and F1 = FR - a_{-1}.
    • Continue: multiply F1 by R to get F1R = a{-2} + F2, etc. Digits a_{-k} are obtained in order from most significant to least.
    • Example: Convert decimal (0.625)_{10} to binary (R=2).

    0.625 \times 2 = 1.25 \implies a_{-1} = 1 \text{ (Integer part)}

    0.25 \times 2 = 0.50 \implies a_{-2} = 0 \text{ (Integer part)}

    0.50 \times 2 = 1.00 \implies a{-3} = 1 \text{ (Integer part)} The process terminates when the fractional part is 0. So, (0.625){10} = (0.101)_2.

  • Converting between binary, octal, and hexadecimal

    • Binary to hex: group bits in sets of 4 from right to left; each group maps to a hex digit.
    • Binary to octal: group bits in sets of 3 from right to left; each group maps to an octal digit.
    • Example: (100101101011010)2 = (45532)8.
    • Example: Convert (1101011)_2 to hexadecimal.

    Group in 4s from right: \quad 0110 \quad 1011
    Convert each group: \quad 01102 = 6{16}, \quad 10112 = B{16}

    So, (1101011)2 = (6B){16}.

  • Conversion tables and common codes

    • Decimal \

Binary Arithmetic

  • Binary addition

    • Arithmetic in digital systems is performed in binary (base 2).
    • Truth table for addition:
    • 0 + 0 = 0
    • 0 + 1 = 1
    • 1 + 0 = 1
    • 1 + 1 = 0 with carry 1 to the next column.
    • Example: Add (1011)2 + (0110)2
      1011  (11 decimal)
+ 0110   (6 decimal)
------
 10001  (17 decimal)

  • Binary subtraction

    • Subtraction table (borrow concept):
    • 0 - 0 = 0
    • 0 - 1 = 1 with borrow 1 from the next column
    • 1 - 0 = 1
    • 1 - 1 = 0
    • Example: Subtract (1011)2 - (0110)2
      1011  (11 decimal)
- 0110   (6 decimal)
------
  0101   (5 decimal)

  • Binary multiplication

    • Like decimal multiplication, but with bits 0/1; four basic bit products:
    • 0 \times 0 = 0, 0 \times 1 = 0, 1 \times 0 = 0, 1 \times 1 = 1.
    • A common method to manage carries is to add partial products one at a time.
    • Example (1111)2 \times (1101)2:
        1111
  x 1101
  ------
    1111  (1111 x 1)
   0000   (1111 x 0, shifted)
  1111    (1111 x 1, shifted twice)
 1111     (1111 x 1, shifted thrice)
 ---------
 11000011

    Final product is (11000011)_2 (195 in decimal).

  • Binary division

    • Long division with quotient bits 0 or 1 only.
    • Algorithm: compare divisor with the upper bits of dividend, subtract when possible, record 1 in quotient, append next dividend bit, repeat until bits run out.
    • Example: Divide (1100)2 \div (10)2
        110   (Quotient)
  ------
10|1100
   -10
   ---
    10
   -10
   ---
     00

    So, (1100)2 \div (10)2 = (110)_2 (12 \div 2 = 6 in decimal).

Representation of Negative Numbers

  • Three common methods
    • Sign and magnitude (sign bit indicates sign)
    • 1’s complement
    • 2’s complement
  • Sign & magnitude
    • Leftmost bit is sign: 0 for positive, 1 for negative.
    • Example: +5 in 4 bits: 0101; -5 in 4 bits: 1101.
  • 1’s complement
    • Positive number N: 0 followed by magnitude; Negative -N is the 1’s complement of N: N^* = 2^n - 1 - N, equivalently bitwise NOT of N.
    • Example (4-bit): +5 = 0101; -5 = 1010 (since 11112 - 01012 = 1010_2).
  • 2’s complement
    • Positive numbers have a leading 0; negative numbers -N are N^* = 2^n - N.
    • Obtain by bitwise NOT of N and adding 1: N^* = (\text{NOT } N) + 1.
    • Range: -2^{n-1} \le M \le 2^{n-1} - 1 for n-bit representation.
    • Example (4-bit): +5 = 0101; -5 = 1011 (since 0101 \text{ -> } \text{NOT } 1010 \text{ -> } \text{add } 1 \text{ -> } 1011).
  • Overflow
    • Occurs when the result of an operation is outside the representable range.

Binary Codes (Binary Coding Schemes)

  • Why binary codes

    • Computers operate on binary signals internally, while I/O often uses decimal.

  • Common code families

    • BCD (8-4-2-1) Code
    • Each decimal digit is encoded by a 4-bit binary code.
    • Valid BCD digits for 0–9 map to 0000–1001; codes 1010–1111 are invalid for BCD.
    • Example: Decimal 25_{10} in BCD is 0010 \quad 0101.
    • Excess-3 Code
    • Each decimal digit is represented by its 4-bit BCD code plus 3 (i.e., add 0011).
    • Example: Decimal 4_{10}
      BCD of 4 is 0100
      Excess-3 is 0100 + 0011 = 0111.
    • 2-out-of-5 Code
    • Each decimal digit is represented by 5 bits with exactly two 1s.
    • Example: Decimal 3_{10} is encoded as 00011.
    • Gray Code
    • A binary encoding where successive decimal digits differ in exactly one bit.

  • ASCII (7-bit) Code

    • 7-bit encoding for characters; 2^7 = 128 distinct codes.
    • Example encodings used to spell a word: S t a r t
    • S: 01010011, t: 01110100, a: 01100001, r: 01110010, t: 01110100.

  • Additional notes

    • Gray code table (0–15):
    DecimalBinaryGray
    000000000
    100010001
    200100011
    300110010
    401000110
    501010111
    601100101
    701110100
    810001100
    910011101
    1010101111
    1110111110
    1211001010
    1311011011
    1411101001
    1511111000
    • Examples for cross-checking conversions: (100101101011010)2 \rightarrow (45532)8.
    • Decimal digits to digit-weights (Weights example): For 6-3-1-1 code, a digit N = w3 a3 + w2 a2 + w1 a1 + w0 a0.
    • Example: To encode decimal 8{10} using 6-3-1-1: 6\cdot 1 + 3\cdot 0 + 1\cdot 1 + 1\cdot 1 = 6+0+1+1=8. So, 8{10} in 6-3-1-1 code is 1011. (This example assumes a3=1, a2=0, a1=1, a0=1$$ as one possible valid encoding).
    • ASCII table concept: ASCII maps decimal/hex