Digital Logic Design - Data Representation and Number Systems

Data Representation

• Data can be represented in various forms, including text, numbers, images, audio, and video.
• Text is represented using character encoding standards like ASCII, where each character is assigned a unique bit pattern.
  • Example: The word \"BYTE\" is represented in ASCII code as \"1000010 1011001 1010100 1000101\".
• Images can be represented as bitmap or vector graphics.
  • Bitmap graphics represent images as a matrix of pixels.
    • Example: A black-and-white image can be represented using a matrix representation or a linear representation of bit patterns.
• Color pixels are represented using color models like RGB (Red, Green, Blue).
  • Each color component is assigned an intensity value.
    • Example:
      • Red (100% intensity): \"11111111 00000000 00000000\"
      • Green (100% intensity): \"00000000 11111111 00000000\"
      • Blue (100% intensity): \"00000000 00000000 11111111\"
      • White (100% intensity): \"11111111 11111111 11111111\"
• Audio is represented through sampling, quantization, and coding.

Number Systems

• Common Number Systems:
  • Decimal (Base 10): Uses digits 0-9. Used by humans. Not used directly in computers.
  • Binary (Base 2): Uses digits 0 and 1. Not used by humans. Used in computers.
  • Octal (Base 8): Uses digits 0-7. Not used by humans. Not used directly in computers.
  • Hexadecimal (Base 16): Uses digits 0-9 and letters A-F. Not used by humans. Not used directly in computers.

Quantities/Counting in Different Number Systems

Conversion Among Bases

• It's possible to convert between Decimal, Octal, Binary, and Hexadecimal number systems.

Quick Example of Base Conversion

• $25<em>{10} = 11001</em>2 = 31<em>8 = 19</em>{16}$

Binary to Decimal Conversion

• Technique:
  • Multiply each bit by $2^n$, where n is the weight (position) of the bit, starting from 0 on the right.
  • Add the results.
• Example:
  • $101011_2$
    • $1 \times 2^0 = 1$
    • $1 \times 2^1 = 2$
    • $0 \times 2^2 = 0$
    • $1 \times 2^3 = 8$
    • $0 \times 2^4 = 0$
    • $1 \times 2^5 = 32$
    • $1 + 2 + 0 + 8 + 0 + 32 = 43_{10}$

Hexadecimal to Decimal Conversion

• Technique:
  • Multiply each digit by $16^n$, where n is the weight (position) of the digit, starting from 0 on the right.
  • Add the results.
• Example:
  • $ABC_{16}$
    • $C \times 16^0 = 12 \times 1 = 12$
    • $B \times 16^1 = 11 \times 16 = 176$
    • $A \times 16^2 = 10 \times 256 = 2560$
    • $12 + 176 + 2560 = 2748_{10}$

Decimal to Binary Conversion

• Binary Conversion Algorithm:

  1. Divide the value by two and record the remainder.
  2. As long as the quotient obtained is not zero, continue to divide the newest quotient by two and record the remainder.
  3. Once a quotient of zero has been obtained, the binary representation of the original value consists of the remainders listed from right to left in the order they were recorded.

• Technique:

  • Divide by two, keep track of the remainder.
  • The first remainder is bit 0 (LSB - least-significant bit).
  • The second remainder is bit 1, and so on.

• Binary Conversion Example:

  • $21_{10}$
    • $21 \div 2 = 10$, remainder 1
    • $10 \div 2 = 5$, remainder 0
    • $5 \div 2 = 2$, remainder 1
    • $2 \div 2 = 1$, remainder 0
    • $1 \div 2 = 0$, remainder 1
    • Binary representation: $10101_2$

• Example: Converting decimal 123 to binary.

  • $123 \div 2 = 61$, remainder 1
  • $61 \div 2 = 30$, remainder 1
  • $30 \div 2 = 15$, remainder 0
  • $15 \div 2 = 7$, remainder 1
  • $7 \div 2 = 3$, remainder 1
  • $3 \div 2 = 1$, remainder 1
  • $1 \div 2 = 0$, remainder 1
  • Result: $1111011_2$

Hexadecimal to Binary Conversion

• Technique:
  • Convert each hexadecimal digit to a 4-bit equivalent binary representation.
• Example:
  • $10AF<em>{16} = ?</em>2$
    • 1 = 0001
    • 0 = 0000
    • A = 1010
    • F = 1111
    • $10AF<em>{16} = 0001000010101111</em>2$

Decimal to Hexadecimal Conversion

• Technique:
  • Divide by 16 and keep track of the remainder.
• Example:
  • $1234<em>{10} = ?</em>{16}$
    • $1234 \div 16 = 77$, remainder 2
    • $77 \div 16 = 4$, remainder 13 (D)
    • $4 \div 16 = 0$, remainder 4
    • Result: $4D2_{16}$

Binary to Hexadecimal Conversion

• Technique:
  • Group bits in fours, starting from the right.
  • Convert each group of four bits to its equivalent hexadecimal digit.
• Example:
  • $1010111011<em>2 = ?</em>{16}$
    • 10 1011 1011
    • 2 B B
    • $1010111011<em>2 = 2BB</em>{16}$

Octal to Hexadecimal Conversion

• Technique:
  • Use binary as an intermediary.

Common Powers

• Base 10:

• Base 2:

In computing, particularly with memory, the base-2 interpretation generally applies.

Review – Multiplying Powers

• For common bases, add powers:
  • $2^6 \times 2^{10} = 2^{16} = 65,536$
  • $2^6 \times 2^{10} = 64 \times 2^{10} = 64k$
  • $a^b \times a^c = a^{b+c}$

Binary Addition

• Two 1-bit values:

| A | B | A + B |
| :-: | :-: | :---: |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 10 |

• Two n-bit values:
  • Add individual bits.
  • Propagate carries.
  • Example:
    • 10101 (21)
    • 11001 (25)
    • 101110 (46)

Multiplication

• Binary, two 1-bit values:

| A | B | A × B |
| :-: | :-: | :---: |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

• Binary, two n-bit values:
  • As with decimal values.
  • Example:
    • 1110 x 1011 = 10011010

Unsigned Binary Integers

• Y = \"abc\" = a \cdot 2^2 + b \cdot 2^1 + c \cdot 2^0
  • Where the digits a, b, c can each take on the values of 0 or 1 only.
• N = number of bits
• Range is: $0 \le i \le 2^N - 1$

Signed Magnitude

• Leading bit is the sign bit
• Y = \"abc\" = (-1)^a(b \cdot 2^1 + c \cdot 2^0)
• Range is: -2^{N-1} + 1 < i < 2^{N-1} - 1
• Problems:
  • How do we do addition/subtraction?
  • We have two numbers for zero (+/-)!
    • Not good!

One's Complement

• Invert all bits
• If MSB (most significant bit) is 1, then the number is negative (same as signed magnitude)
• Range is: -2^{N-1} + 1 < i < 2^{N-1} - 1
• Problems:
  • Same as for signed magnitude
    • Not good!

Two's Complement

• Transformation: To transform a into -a, invert all bits in a and add 1 to the result
• Range is: -2^{N-1} < i < 2^{N-1} - 1
• Advantages:
  • Operations need not check the sign
  • Only one representation for zero
  • Efficient use of all the bits

Two’s Complement Calculation

1. Calculate One's Complement
2. Add 1

• Example -94:
  • Get Binary Representation of 94: 01011110
  • Produce One's Complement: 10100001
  • Add 1: 10100010

Two's Complement Examples

• a. Using patterns of length three:

• b. Using patterns of length four:

Fractions

• Binary to decimal:

  • $10.1011_2$
    • $1 \times 2^{-4} = 0.0625$
    • $1 \times 2^{-3} = 0.125$
    • $0 \times 2^{-2} = 0.0$
    • $1 \times 2^{-1} = 0.5$
    • $0 \times 2^{0} = 0.0$
    • $1 \times 2^{1} = 2.0$
    • $2.6875$

• Decimal to binary:

  • $3.14579$
    • $.14579 \times 2 = 0.29158$
    • $.29158 \times 2 = 0.58316$
    • $.58316 \times 2 = 1.16632$
    • $.16632 \times 2 = 0.33264$
    • $.33264 \times 2 = 0.66528$
    • $.66528 \times 2 = 1.33056$
    • $11.001001…$

Logic Gates

• Logic gates are the building blocks used to create digital circuits.
• There are three elementary logic gates: AND, OR, and NOT, as well as other simple gates like NAND, NOR, XOR, and XNOR.
• Each gate has its own logic symbol, which allows complex functions to be represented by a logic diagram.
• The function of each gate can be represented by a truth table or using Boolean notation.

Elementary Logic Gates

• AND:

  • Output is 1 only if both inputs are 1.
  • Truth Table:

  | A | B | C (A AND B) |
  | :-: | :-: | :-----------: |
  | 0 | 0 | 0 |
  | 0 | 1 | 0 |
  | 1 | 0 | 0 |
  | 1 | 1 | 1 |

  • Boolean expression: $C = A \cdot B$

• OR:

  • Output is 1 if at least one input is 1.
  • Truth Table:

  | A | B | C (A OR B) |
  | :-: | :-: | :----------: |
  | 0 | 0 | 0 |
  | 0 | 1 | 1 |
  | 1 | 0 | 1 |
  | 1 | 1 | 1 |

  • Boolean expression: $C = A + B$

• NOT:

  • Output is the inverse of the input.
  • Truth Table:

  | A | B (NOT A) |
  | :-: | :-------: |
  | 0 | 1 |
  | 1 | 0 |

  • Boolean expression: $B = \overline{A}$

Other Logic Gates

• NAND:

  • Output is 0 only if both inputs are 1.
  • Truth Table:

  | A | B | C (A NAND B) |
  | :-: | :-: | :------------: |
  | 0 | 0 | 1 |
  | 0 | 1 | 1 |
  | 1 | 0 | 1 |
  | 1 | 1 | 0 |

  • Boolean expression: $C = \overline{A \cdot B}$

• NOR:

  • Output is 1 only if both inputs are 0.
  • Truth Table:

  | A | B | C (A NOR B) |
  | :-: | :-: | :-----------: |
  | 0 | 0 | 1 |
  | 0 | 1 | 0 |
  | 1 | 0 | 0 |
  | 1 | 1 | 0 |

  • Boolean expression: $C = \overline{A + B}$

• XOR:

  • Output is 1 if the inputs are different.
  • Truth Table:

  | A | B | C (A XOR B) |
  | :-: | :-: | :----------: |
  | 0 | 0 | 0 |
  | 0 | 1 | 1 |
  | 1 | 0 | 1 |
  | 1 | 1 | 0 |

  • Boolean expression: $C = A \oplus B$

Logic Gate Integrated Circuits (ICs)

• Examples of common logic gate ICs:
  • 5400/7400: Quad NAND gate
  • 5402/7402: Quad NOR gate
  • 5408/7408: Quad AND gate
  • 5432/7432: Quad OR gate
  • 5486/7486: Quad XOR gate
  • 5404/7404: Hex inverter

Flip-Flops

• Flip-flop = a circuit built from gates that can store one bit of data.
  • Has an input line which sets its stored value to 1 (Set).
  • Has an input line which sets its stored value to 0 (Reset).
  • While both input lines are 0, the most recently stored value is preserved.
  • 1s are not applied to both input lines simultaneously.