Data Representation Fundamentals and Numeral Systems

Introduction to Digital Data Representation

• Background of Digital Techniques: Digital methods have permeated numerous technological sectors, with automatic digital computers representing the most extensive application.

• Definition of a Computer: A computer is defined as a hardware system designed to perform arithmetic operations, manipulate data, and make logical decisions.

• Nature of Quantities: In science, business, and technology, physical quantities are constantly measured, recorded, and utilized. In digital systems, these quantities are represented using symbols known as digits.

• Common Number Systems: Digital technology utilizes various number systems to represent digits, specifically:

  • Decimal system.

  • Binary system.

  • Octal system.

  • Hexadecimal system.

Numeral Systems Architecture

• Definition: Numeral or numbering systems provide a mechanism for representing numbers through a finite set of distinct graphic symbols or signs.

• Interchangeability: The same numerical value can be represented differently across various systems. For example, the decimal value $42_{10}$ is equivalent to $52_8$ in the octal system and $2A_{16}$ in the hexadecimal system.

• Major Categories of Number Systems:

  • Non-positional Number Systems: Historically based on additive approaches using fingers, stones, or sticks. A symbol carries a constant value regardless of its position within a sequence.

  • Positional Number Systems: Also known as place-value systems, where the placement of a digit relative to other symbols determines its actual weight or weight-value.

Non-Positional Numeral Systems

Roman Numeral System

• Symbols and Decimal Values:

  • $I$ = $1$

  • $V$ = $5$

  • $X$ = $10$

  • $L$ = $50$

  • $C$ = $100$

  • $D$ = $500$

  • $M$ = $1000$

• Operational Rules:

  • Additive Rule: If two consecutive digits are ordered such that the first is greater than or equal to the second, their values are added (e.g., $III = 1+1+1=3$; $MD = 1000+500=1500$; note: transcript says $MD=2500$ as typo for $MMD$).

  • Subtractive Rule: If digits are in increasing order of value, the smaller value is subtracted from the larger (e.g., $IX = 10 - 1 = 9$; $MXL = 1000 + (50 - 10) = 1040$; $CM = 1000 - 100 = 900$).

Greek Numeral System

• Symbols and Decimal Values:

  • $|$ = $1$

  • $\Gamma$ = $5$

  • $\Delta$ = $10$

  • $H$ = $100$

  • $X$ = $1,000$

  • $M$ = $10,000$

• Methodology: Grouping is often centered around fives. Powers of 10 are represented by the first letter of the corresponding Greek word.

• Examples:

  • $\Gamma \Delta = 5 \times 10 = 50$

  • $\Gamma H = 5 \times 100 = 500$

  • $\Gamma X = 5 \times 1,000 = 5,000$

  • $\Gamma M = 5 \times 10,000 = 50,000$

Positional Numeral Systems and Base (Radix)

• Nature of Weighted Values: The value of a digit is its intrinsic value multiplied by a weight determined by its position.

  • Example using digit '5': In 135, it represents $5 \times 1 = 5$. In 153, it represents $5 \times 10 = 50$. In 531, it represents $5 \times 100 = 500$.

• Definition of Base or Radix: The base (or radix) indicates the total number of distinct symbols used in that system.

  • Decimal: Base 10 (Symbols: ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$).

  • Binary: Base 2 (Symbols: ${0, 1}$).

  • Octal: Base 8 (Symbols: ${0, 1, 2, 3, 4, 5, 6, 7}$).

  • Hexadecimal: Base 16 (Symbols: ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}$).

• Mathematical Representation of Positional Values:

  • For a number like $437.591$:

  • $4 \times 10^2 + 3 \times 10^1 + 7 \times 10^0 + 5 \times 10^{-1} + 9 \times 10^{-2} + 1 \times 10^{-3}$.

• Fixed-Radix vs. Mixed-Radix: Digital systems typically stick to fixed-radix systems where the base is constant for all positions.

Digital Number Systems Characteristics

Decimal Number System (Base-10)

• Evolution: Likely derived from humans having 10 fingers.

• Nomenclature:

  • Most Significant Digit (MSD): The leftmost digit carrying the most weight.

  • Least Significant Digit (LSD): The rightmost digit carrying the least weight.

• Example: $2512.1971$ is decomposed as $2 \times 10^3 + 5 \times 10^2 + 1 \times 10^1 + 2 \times 10^0 + 1 \times 10^{-1} + 9 \times 10^{-2} + 7 \times 10^{-3} + 1 \times 10^{-4}$.

Binary Number System (Base-2)

• Implementation: Hard to design circuits with 10 voltage levels; very easy to design circuits with two (ON/OFF, high/low voltage).

• Terms:

  • Bit: Abbreviation for Binary Digit.

  • Most Significant Bit (MSB): Leftmost bit.

  • Least Significant Bit (LSB): Rightmost bit.

• Positional Weights: Powers of 2 (e.g., $2^3, 2^2, 2^1, 2^0$ for integers; $2^{-1}, 2^{-2}$ etc. for fractions).

• Counting Pattern:

  • Units bit (LSB) alternates every count ($0, 1, 0, 1...$).

  • Second bit ($2^1$) alternates every 2 counts ($0, 0, 1, 1...$).

  • Third bit ($2^2$) alternates every 4 counts.

  • General rule: Alternates in groups of $2^{N-1}$.

Octal Number System (Base-8)

• Weights: Based on powers of 8.

• Example: $3721.2406_8$ converted to decimal is $2001.313964_{10}$.

Hexadecimal Number System (Base-16)

• Symbols: $0-9$ and letters $A-F$.

  • $A = 10$, $B = 11$, $C = 12$, $D = 13$, $E = 14$, $F = 15$.

• Utility: Serves as a shorthand for representing large binary strings; every hex digit represents exactly 4 binary bits.

Number System Conversions

Decimal-to-Binary

• Method 1: Powers of 2 Table: Subtract the largest possible power of 2 from the decimal number, record the bit, and repeat with the remainder.

  • Example: $43_{10} \rightarrow 32 (2^5)$, remainder $11 \rightarrow 8 (2^3)$, remainder $3 \rightarrow 2 (2^1)$, remainder $1 \rightarrow 1 (2^0)$. Result: $101011_2$.

• Method 2: Repeated Division: Successively divide the integer by 2; remainders recorded from bottom to top form the binary string.

• Decimal Fractions to Binary: Successively multiply the fractional part by 2. Collect integers to the left of the decimal point from top to bottom.

  • Example: $0.375_{10} \times 2 = 0.75 (0)$, $0.75 \times 2 = 1.50 (1)$, $0.50 \times 2 = 1.00 (1)$. Result: $0.011_2$.

Binary-to-Decimal

• Method 1: Positional Weights: Sum the values of $2^n$ for every bit position containing a 1.

• Method 2: Dibble-Dobble Method: Start with the leftmost bit, multiply by 2, add the next bit, and repeat until the binary point is reached.

Decimal-to-Octal / Hex

• Integer: Use repeated division by the target radix (8 or 16).

• Fractions: Use repeated multiplication by the target radix (8 or 16).

Octal/Hex Conversions

• Octal to Binary: Replace each octal digit with its 3-bit binary equivalent ($7_8 \rightarrow 111_2$).

• Binary to Octal: Group binary bits in threes starting from the binary point. Add leading or trailing zeros to complete groups.

• Hex to Binary: Replace each hex digit with its 4-bit binary equivalent ($F_{16} \rightarrow 1111_2$).

• Binary to Hex: Group binary bits in fours starting from the binary point.

Binary Representation of Integers

• Storage standard: Integers are stored using a fixed number of bits (8, 16, 32, or 64).

• Unsigned Integers: Represent 0 and positive values. Range for $n$ bits is $0$ to $2^n - 1$.

  • 8-bit range: $0$ to $255$.

  • 16-bit range: $0$ to $65,535$.

• Signed Integers: Represent negative, zero, and positive values. Three main schemes:

Sign-Magnitude Representation

• MSB: Used as sign bit ($0$ for positive, $1$ for negative).

• Magnitude: The remaining $n-1$ bits represent the absolute value.

• Drawbacks:

  1. Two representations of zero ($+0$ as $00000000$ and $-0$ as $10000000$).

  2. Difficulty in processing arithmetic; positive and negative logic must be handled separately.

One's Complement Representation

• Method: Positive numbers are standard binary. Negative numbers are found by inverting all bits of the positive equivalent ($0 \rightarrow 1, 1 \rightarrow 0$).

• Drawbacks: Still contains two versions of zero ($0000$ and $1111$).

Two's Complement Representation

• Method: Add 1 to the 1's complement of the number.

• Alternative Method: Copy bits from right to left up to and including the first 1; then invert all remaining bits.

• Advantages:

  1. Only one unique representation for zero ($0000$\dots$0000$).

  2. Addition and subtraction use the same unified logic circuitry.

• Storage: Modern computers use 2's complement for signed integers.

Floating-Point Representation (Real Numbers)

Fixed-Point Representation

• Real numbers are split by a fixed number of bits for the integer part and the fractional part.

• Example: A 32-bit system might use 24 bits for the integer and 8 for the fraction.

• Limitation: Cannot represent very large or very small numbers efficiently.

Scientific (Exponential) Notation

• Form: $F \times r^E$ ($F$ = Mantissa/Fraction, $r$ = Radix, $E$ = Exponent).

• Normalization: A number is normalized when there is exactly one non-zero digit before the radix point. In binary, this digit is always 1.

IEEE 754 Standard

• Single Precision (32-bit):

  • 1 sign bit.

  • 8 exponent bits.

  • 23 mantissa bits.

• Double Precision (64-bit):

  • 1 sign bit.

  • 11 exponent bits.

  • 52 mantissa bits.

• Implicit Leading Bit: In the normalized mantissa, the leading '1' before the binary point is not stored to save space.

• Excess/Biased Notation: Computers store exponents in biased form (e.g., Excess-127 for single precision) to allow easy sorting of floating-point numbers.

• Trade-off: Increasing bits for the mantissa improves precision (accuracy), while increasing bits for the exponent increases the range of numbers.

Binary Arithmetic Operations

Binary Addition Rules

• $0 + 0 = 0$

• $0 + 1 = 1$

• $1 + 0 = 1$

• $1 + 1 = 10$ ($0$ with carry $1$)

• $1 + 1 + 1 = 11$ ($1$ with carry $1$)

Binary Subtraction Rules

• $0 - 0 = 0$

• $1 - 0 = 1$

• $1 - 1 = 0$

• $10 - 1 = 1$ ($0 - 1 = 1$ with a borrow of $1$)

Multiplication and Division

• Multiplication: Rules follow standard logic: $0 \times 0 = 0$, $0 \times 1 = 0$, $1 \times 1 = 1$. Partial products are shifted and added.

• Division: Follows same long-division format as decimal: $0 \div 1 = 0$, $1 \div 1 = 1$.

Complement Arithmetic

• 1's Complement Addition: If a carry is generated out of the sign bit, it must be added to the LSB (End-Around Carry).

• 2's Complement Addition: Standard addition including the sign bit. Any final carry generated out of the sign bit position is ignored.

• Overflow Detection: In 2's complement, an overflow occurs if adding two numbers of the same sign produces a result with the opposite sign.

Alphanumeric Codes and Character Representation

ASCII

• Full Name: American Standard Code for Information Interchange.

• Detail: 7-bit code providing $128$ code groups. Used for standard keyboard characters and control functions like $(RETURN)$ and $(LINEFEED)$.

EBCDIC

• Full Name: Extended Binary Coded Decimal Interchange Code.

• Detail: 8-bit code (256 symbols). Primarily used in IBM mainframe systems.

ISCII

• Full Name: Indian Standard Code for Information Interchange.

• Detail: Adopted in 1991 by the Bureau of Indian Standards. 8-bit code ($256$ characters) that retains ASCII and adds support for Devanagari, Bengali, Gujarati, Gurmukhi, Oriya, Telugu, Kannada, Malayalam, and Tamil.

• Similar script structure allows for easy transliteration between Indian languages.

Unicode

• Purpose: A universal standard providing a unique number for every character regardless of platform, program, or language.

• Capacity:

  • Version 3.0: Represented $49,194$ characters.

  • Version 3.1: Represented $94,140$ characters.

• Architecture: Usually 16-bit, representing up to $65,536$ characters in its basic plane. Based on ISCII-1988 for the Indian language block.

Questions & Discussion

• Q: Convert $43_{10}$ to binary using repeated division.

  • A: $43 \div 2 = 21$ R $1$ (LSB); $21 \div 2 = 10$ R $1$; $10 \div 2 = 5$ R $0$; $5 \div 2 = 2$ R $1$; $2 \div 2 = 1$ R $0$; $1 \div 2 = 0$ R $1$ (MSB). Result: $101011_2$.

• Q: Decode ASCII hex values 48, 45, 4C, 50.

  • A: Using Table 1.10: $48 \rightarrow H$, $45 \rightarrow E$, $4C \rightarrow L$, $50 \rightarrow P$. The word is "HELP".

• Q: What is the benefit of Excess-notation?

  • A: It maintains the sorted order of bit patterns for both positive and negative numbers, which assists in computational sorting processes.

• Q: Determine the 8-bit sign-magnitude for $-23$.

  • A: Binary $23$ is $10111$. For an 8-bit sign-magnitude, MSB is $1$ (for negative) followed by zeros for padding and the magnitude: $10010111$.