Lecture Notes: Number System and Computer Arithmetic

1. Information Representation

Computers use number systems to represent information accurately so it can be processed.

• Examples:
  • Yes/No: 0/1
  • Seasons: Fall(0), Winter(1), Spring(2), Summer(3)
  • Identification Numbers: IC numbers, Matrix numbers.

Positional vs. Non-Positional Systems

1. Non-Positional (Sign-Value) Notation: The position of a symbol does not determine its magnitude.
   • Example: Roman Numerals (I, V, X, L, C, D, M). Calculation is difficult (e.g., IV = 4, VI = 6).
2. Weighted Positional Notation: The value of a digit depends on its position.
   • Example: Decimal system (Base 10).

2. Number Systems and Conversions

Common Number Systems

• Decimal (Base 10): Weights are powers of 10. Digits: 0-9.
• Binary (Base 2): Weights are powers of 2. Digits: 0, 1.
• Octal (Base 8): Weights are powers of 8. Digits: 0-7.
• Hexadecimal (Base 16): Weights are powers of 16. Digits: 0-9, A-F (where A=10...F=15).

Base to Decimal Conversion

To convert any Base number to Decimal, sum the products of each digit and its positional weight ().

Examples:

• Binary:
• Octal:
• Hexadecimal:

Decimal to Base Conversion

1. Integers (Repeating Division): Repeatedly divide the decimal number by and record the remainders (read from bottom to top).
2. Fractions (Repeating Multiplication): Repeatedly multiply the fraction by , recording the integer part (read from top to bottom) until the fraction is 0 or sufficient precision is reached.

Binary Octal/Hexadecimal Shortcuts

• Binary Octal: Group bits into 3s starting from the radix point.
• Octal Binary: Convert each octal digit to 3 bits.
• Binary Hexadecimal: Group bits into 4s starting from the radix point.
• Hexadecimal Binary: Convert each hex digit to 4 bits.

3. Binary Arithmetic

Basic Operations

• Addition: Similar to decimal.
  • (0 carry 1)
• Subtraction: Uses borrowing.
• Multiplication: Partial products shifted and added.

4. Negative Number Representation

In computers, the sign is represented by a bit (usually the MSB: Most Significant Bit):

• 0 for Positive (+)
• 1 for Negative (-)

Three Representation Methods:

1. Sign & Magnitude

• Format: [Sign Bit] [Magnitude Bits]
• Range (for n-bits): to .
• Issues: Two representations for zero (+0 and -0).
• Example: , .

2. 1's Complement

• Method: Invert all bits of the positive number (0 1, 1 0).
• Range: Same as Sign & Magnitude.
• Issues: Two representations for zero.
• Example: If , then .

3. 2's Complement

• Method: 1's Complement + 1 (or ).
• Range: to .
• Advantages: Single representation for zero; arithmetic is simpler.
• Example: If , 1's Comp = , 2's Comp = .

5. Arithmetic with Complements (Subtraction)

Subtraction ( ) is performed as Addition ( ).

Using 1's Complement (r-1 Complement)

1. Add to the 1's complement of .
2. If carry occurs (End-Around Carry): Add 1 to the result (LSB). The result is positive.
3. If no carry: The result is negative. Take the 1's complement of the sum and add a negative sign.

Using 2's Complement (r Complement)

1. Add to the 2's complement of .
2. If carry occurs: Discard the carry. The result is positive and correct.
3. If no carry: The result is negative. Take the 2's complement of the sum and add a negative sign.

6. Overflow

Overflow occurs when the result of an arithmetic operation exceeds the fixed bit range of the system (e.g., range to for signed numbers).

Overflow Detection Rules:

• Positive + Positive = Negative: Overflow occurred.
• Negative + Negative = Positive: Overflow occurred.
• Note: Carry out of the sign bit is not necessarily an overflow in 2's complement arithmetic; the sign change is the indicator.

7. Coding Schemes

Binary Coded Decimal (BCD)

• 8421 Code: Each decimal digit (0-9) is represented by a 4-bit binary group.
• Invalid Codes: 1010 to 1111 (10 to 15) are errors in BCD.
• Useful for interfaces like keypads.

Gray Code

• Property: Only one bit changes between consecutive numbers.
• Usage: Error detection, position encoders.
• Conversion: XOR-based methods between Binary and Gray code.

Alphanumeric Codes

• ASCII: 7-bit code (often with a parity bit) for letters, numbers, and symbols.
• EBCDIC: 8-bit code extended from BCD.

8. Error Detection and Correction

Parity Bit

• Used to detect errors during transmission.
• Even Parity: Total number of 1s (including parity) is even.
• Odd Parity: Total number of 1s (including parity) is odd.
• Limitation: Can only detect single-bit (or odd number of) errors; cannot detect even number of errors.

Hamming Code

• A technique for Single Bit Error Correction.
• Adds parity bits to data bits.
• Parity bits are placed at power-of-2 positions (1, 2, 4, 8...).
• Each parity bit checks a specific set of bits in the sequence.