Number Systems

In the realm of computers, information is processed and stored using binary digits, or bits, which can be either 0 or 1. This fundamental concept leads us to the study of number systems. A number system is a mathematical way of representing numbers of a given set, which consists of a set of symbols and a radix or base. The base determines the value of the numbers. Different number systems are used in computing for various purposes, from representing data internally to facilitating human interaction with digital devices. Understanding these systems is crucial for comprehending how computers function at their core.

Introduction to Number Systems

A number system requires two main components: a set of distinct symbols (digits) and a rule for assigning value to these symbols based on their position. The most common number systems encountered in computer science are:

• Decimal Number System (Base-10)
• Binary Number System (Base-2)
• Octal Number System (Base-8)
• Hexadecimal Number System (Base-16)

Decimal Number System (Base-10)

This is the number system we use in our daily lives. It uses ten digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. Each digit's position represents a power of 10. For example, the number 257 can be expressed as:

257 = (2 * 10²) + (5 * 10¹) + (7 * 10⁰) = 200 + 50 + 7

Binary Number System (Base-2)

This is the language of computers. It uses only two digits: 0 and 1. Each position represents a power of 2. For example, the binary number 1101 can be expressed in decimal as:

1101₂ = (1 * 2³) + (1 * 2²) + (0 * 2¹) + (1 * 2⁰) = (1 * 8) + (1 * 4) + (0 * 2) + (1 * 1) = 8 + 4 + 0 + 1 = 13₁₀

Each digit in a binary number is called a bit.

Octal Number System (Base-8)

The octal system uses eight digits: 0, 1, 2, 3, 4, 5, 6, and 7. Each position represents a power of 8. It is often used as a shorthand for binary numbers because each octal digit can represent exactly three binary digits (bits). For example, the octal number 315 can be expressed in decimal as:

315₈ = (3 * 8²) + (1 * 8¹) + (5 * 8⁰) = (3 * 64) + (1 * 8) + (5 * 1) = 192 + 8 + 5 = 205₁₀

Hexadecimal Number System (Base-16)

The hexadecimal system uses sixteen symbols: 0-9 and A-F, where A represents 10, B represents 11, C represents 12, D represents 13, E represents 14, and F represents 15. Each position represents a power of 16. Hexadecimal is widely used in computing because each hexadecimal digit can represent exactly four binary digits (bits), making it an even more compact shorthand for binary than octal. For example, the hexadecimal number 1A5 can be expressed in decimal as:

1A5₁₆ = (1 * 16²) + (A * 16¹) + (5 * 16⁰) = (1 * 256) + (10 * 16) + (5 * 1) = 256 + 160 + 5 = 421₁₀

Conversion Between Number Systems

Converting numbers between different bases is a fundamental skill in computer science. The most common conversions involve changing numbers from binary, octal, or hexadecimal to decimal, and vice versa. We also frequently convert between binary, octal, and hexadecimal, which can be simplified by using decimal as an intermediate step or by grouping bits directly.

Decimal to Other Bases

To convert a decimal number to another base (e.g., binary, octal, hexadecimal), we use the method of successive division by the target base. The remainders, read from bottom to top, form the number in the new base.

Example: Convert decimal 42 to binary.

1. Divide 42 by 2: 42 / 2 = 21 remainder 0
2. Divide 21 by 2: 21 / 2 = 10 remainder 1
3. Divide 10 by 2: 10 / 2 = 5 remainder 0
4. Divide 5 by 2: 5 / 2 = 2 remainder 1
5. Divide 2 by 2: 2 / 2 = 1 remainder 0
6. Divide 1 by 2: 1 / 2 = 0 remainder 1

Reading the remainders from bottom to top: 101010₂. So, 42₁₀ = 101010₂.

Example: Convert decimal 150 to hexadecimal.

1. Divide 150 by 16: 150 / 16 = 9 remainder 6
2. Divide 9 by 16: 9 / 16 = 0 remainder 9

Reading the remainders from bottom to top: 96₁₆. So, 150₁₀ = 96₁₆.

Other Bases to Decimal

To convert a number from any base to decimal, we use the positional value of each digit. Multiply each digit by its corresponding power of the base and sum the results.

Example: Convert binary 11011₂ to decimal.

11011₂ = (1 * 2⁴) + (1 * 2³) + (0 * 2²) + (1 * 2¹) + (1 * 2⁰) = (1 * 16) + (1 * 8) + (0 * 4) + (1 * 2) + (1 * 1) = 16 + 8 + 0 + 2 + 1 = 27₁₀

Example: Convert octal 723₈ to decimal.

723₈ = (7 * 8²) + (2 * 8¹) + (3 * 8⁰) = (7 * 64) + (2 * 8) + (3 * 1) = 448 + 16 + 3 = 467₁₀

Binary to Octal and Hexadecimal

These conversions are straightforward due to the relationship between bases 2, 8 (2³), and 16 (2⁴).

Binary to Octal: Group the binary digits into sets of three, starting from the rightmost digit (the least significant bit). If the leftmost group doesn't have three digits, pad it with leading zeros. Convert each group of three bits into its corresponding octal digit.

Example: Convert binary 11010110₂ to octal.

Group into threes from the right: 11 010 110 Pad the leftmost group: 011 010 110 Convert each group: 011₂ = 3₈ 010₂ = 2₈ 110₂ = 6₈

So, 11010110₂ = 326₈.

Binary to Hexadecimal: Group the binary digits into sets of four, starting from the rightmost digit. If the leftmost group doesn't have four digits, pad it with leading zeros. Convert each group of four bits into its corresponding hexadecimal digit.

Example: Convert binary 11101101₂ to hexadecimal.

Group into fours from the right: 1110 1101 Convert each group: 1110₂ = E₁₆ (14 in decimal) 1101₂ = D₁₆ (13 in decimal)

So, 11101101₂ = ED₁₆.

Octal and Hexadecimal to Binary

These conversions are the reverse of the above.

Octal to Binary: Convert each octal digit into its 3-bit binary equivalent.

Example: Convert octal 572₈ to binary.

5₈ = 101₂ 7₈ = 111₂ 2₈ = 010₂

Concatenate the binary groups: 101111010₂. So, 572₈ = 101111010₂.

Hexadecimal to Binary: Convert each hexadecimal digit into its 4-bit binary equivalent.

Example: Convert hexadecimal 9F3₁₆ to binary.

9₁₆ = 1001₂ F₁₆ = 1111₂ 3₁₆ = 0011₂

Concatenate the binary groups: 100111110011₂. So, 9F3₁₆ = 100111110011₂.

Octal to Hexadecimal and Vice Versa

The easiest way to convert between octal and hexadecimal is to use binary as an intermediate step.

Octal to Hexadecimal: Convert the octal number to binary, then convert the binary number to hexadecimal.

Hexadecimal to Octal: Convert the hexadecimal number to binary, then convert the binary number to octal.

Example: Convert octal 275₈ to hexadecimal.

1. Octal to Binary:
2₈ = 010₂ 7₈ = 111₂ 5₈ = 101₂ Binary: 010111101₂
2. Binary to Hexadecimal:
Group into fours from the right: 0101 1110 1 Pad the leftmost group: 0101 1110 1001 Convert each group: 0101₂ = 5₁₆ 1110₂ = E₁₆ 1001₂ = 9₁₆ Hexadecimal: 5E9₁₆

So, 275₈ = 5E9₁₆.

Digital Codes

Digital codes are a system of symbols used to represent data in a digital format. These codes are essential for storing, transmitting, and processing information within computers and other digital devices. They can range from simple representations of numbers to complex schemes for text and error handling.

Weighted Binary Code

In a weighted binary code, each binary digit (bit) is assigned a specific weight. The decimal value of the number is the sum of the products of each bit and its corresponding weight.

Binary-Coded Decimal (BCD): This is the most common example of a weighted binary code. In BCD, each decimal digit is represented by its own 4-bit binary equivalent. The weights are typically 8, 4, 2, 1.

Example: Represent decimal 47 in BCD.

Decimal 4: Binary 0100 (weights 8-4-2-1) Decimal 7: Binary 0111 (weights 8-4-2-1)

So, 47₁₀ in BCD is 0100 0111.

Other Weighted Codes: While 8-4-2-1 is standard, other weighted codes exist, such as 2-4-2-1, 5-2-1-1, etc. The key is that each position has a fixed weight.

Non-Weighted Binary Code

In a non-weighted code, the position of a bit does not correspond to a specific power of a base. The value of the code is determined by the pattern of bits rather than a positional weight.

Excess-3 Code: This is a non-weighted code derived from BCD. Each decimal digit is represented by its 4-bit BCD equivalent plus 3 (0011).

Example: Represent decimal 47 in Excess-3 code.

Decimal 4: BCD is 0100. Add 0011: 0100 + 0011 = 0111. Decimal 7: BCD is 0111. Add 0011: 0111 + 0011 = 1010.

So, 47₁₀ in Excess-3 code is 0111 1010.

Gray Code: This is another important non-weighted code where successive values differ by only one bit. This property is useful in preventing errors in systems where outputs change state.

Example: Gray code for decimal numbers.

Decimal | Binary | Gray Code ------- | ------ | --------- 0 | 0000 | 0000 1 | 0001 | 0001 2 | 0010 | 0011 3 | 0011 | 0010 4 | 0100 | 0110

Notice how each Gray code value differs from the previous one by only a single bit.

Alphanumeric Code

Alphanumeric codes are used to represent not only numbers but also letters (uppercase and lowercase) and special characters (like !, @, #, $, etc.). These codes are essential for representing text data.

American Standard Code for Information Interchange (ASCII): ASCII is a widely used 7-bit or 8-bit alphanumeric code. A 7-bit ASCII code can represent 128 characters (0-9, A-Z, a-z, punctuation, control characters). An 8-bit ASCII code (often called Extended ASCII) can represent 256 characters.

Example: ASCII representation.

The letter 'A' in 7-bit ASCII is 1000001. The digit '5' in 7-bit ASCII is 0110101. The symbol '$' in 7-bit ASCII is 0100100.

Extended Binary Coded Decimal Interchange Code (EBCDIC): Developed by IBM, EBCDIC is another alphanumeric code, typically an 8-bit code, used on IBM mainframe and midrange systems. It is not as widely used as ASCII in modern computing.

Unicode: For international character representation, Unicode is the standard. It assigns a unique number to every character, symbol, and emoji in all writing systems. It can be encoded in various ways, such as UTF-8, UTF-16, and UTF-32. UTF-8 is particularly popular as it is backward compatible with ASCII.

Error Detection and Error Correction Codes

In digital systems, data can be corrupted during transmission or storage due to noise or hardware malfunctions. Error detection and correction codes are techniques used to identify and, in some cases, fix these errors.

Error Detection Codes

These codes allow the receiver to detect if an error has occurred, but they cannot correct the error.

Parity Check: This is the simplest form of error detection. An extra bit, called the parity bit, is added to a binary string.

• Even Parity: The parity bit is set so that the total number of '1's in the data plus the parity bit is even.
• Odd Parity: The parity bit is set so that the total number of '1's in the data plus the parity bit is odd.

Example: Using Even Parity.

Data: 1011001 Number of 1s: 4 (even) To maintain even parity, the parity bit is 0. Transmitted data: 10110010.

Data: 1101001 Number of 1s: 4 (even) To maintain even parity, the parity bit is 0. Transmitted data: 11010010.

Data: 1001001 Number of 1s: 3 (odd) To maintain even parity, the parity bit is 1. Transmitted data: 10010011.

If the receiver gets 10110011, it counts 5 ones (odd), which contradicts the even parity scheme, indicating an error. However, if two bits flip (e.g., 10110010 becomes 11100010), the parity remains even, and the error goes undetected. Parity check can detect single-bit errors but not double-bit errors.

Checksum: This method involves dividing the data into blocks and calculating a sum. The sum is transmitted along with the data. The receiver recalculates the sum and compares it.

Cyclic Redundancy Check (CRC): CRC is a more robust error detection technique, commonly used in networking and storage devices. It treats the data as a polynomial and divides it by a predefined generator polynomial. The remainder of this division is the CRC code, which is transmitted with the data. The receiver performs the same division.

Error Correction Codes

These codes not only detect errors but also have the capability to correct them, usually up to a certain number of bit errors.

Hamming Code: Developed by Richard Hamming, this is a well-known error correction code. It adds redundant bits to the data in specific positions. These redundant bits are calculated based on different subsets of the data bits. If an error occurs, the pattern of these redundant bits (called the syndrome) can pinpoint the exact location of the erroneous bit, allowing it to be flipped and corrected.

Example: Hamming Code (7,4)

This code takes 4 data bits (D) and adds 3 parity bits (P) to form a 7-bit codeword. Positions: P1 P2 D1 P3 D2 D3 D4 Parity bit P1 checks positions 1, 3, 5, 7 (P1, D1, D2, D4) Parity bit P2 checks positions 2, 3, 6, 7 (P2, D1, D3, D4) Parity bit P3 checks positions 4, 5, 6, 7 (P3, D2, D3, D4)

If data bits are 1011 (D1=1, D2=0, D3=1, D4=1): P1: Checks 1, 3, 5, 7. Bits are D1, D2, D4. (1, 0, 1). To make even parity, P1=0. P2: Checks 2, 3, 6, 7. Bits are D1, D3, D4. (1, 1, 1). To make even parity, P2=1. P3: Checks 4, 5, 6, 7. Bits are D2, D3, D4. (0, 1, 1). To make even parity, P3=0. Codeword: P1 P2 D1 P3 D2 D3 D4 = 0 1 1 0 0 1 1

If the codeword is received as 0110111 (error in D3): Check P1 (1, 3, 5, 7): 0, 1, 0, 1. Number of 1s is 2 (even). Parity OK. Check P2 (2, 3, 6, 7): 1, 1, 1, 1. Number of 1s is 4 (even). Parity OK. Check P3 (4, 5, 6, 7): 0, 0, 1, 1. Number of 1s is 2 (even). Parity OK. Wait, this example needs careful calculation. Let's re-evaluate the syndrome calculation.

Let's assume even parity for all. Data: D4 D3 D2 D1 = 1011 Positions: 7 6 5 4 3 2 1 Codeword: P1 P2 D1 P3 D2 D3 D4 Let D1=1, D2=0, D3=1, D4=1 Codeword bits: P1 P2 1 P3 0 1 1 P1 checks positions 1, 3, 5, 7: P1, D1, D2, D4. (P1, 1, 0, 1). For even parity, P1 must be 0. P2 checks positions 2, 3, 6, 7: P2, D1, D3, D4. (P2, 1, 1, 1). For even parity, P2 must be 1. P3 checks positions 4, 5, 6, 7: P3, D2, D3, D4. (P3, 0, 1, 1). For even parity, P3 must be 0. So, the codeword is 0110011. Now, let's say an error occurs and the received codeword is 0110111 (error in D3, which is at position 5). Receiver checks: Syndrome S1 (checks 1, 3, 5, 7): Received bits are 0, 1, 1, 1. Number of 1s is 3 (odd). S1 = 1. Syndrome S2 (checks 2, 3, 6, 7): Received bits are 1, 1, 1, 1. Number of 1s is 4 (even). S2 = 0. Syndrome S3 (checks 4, 5, 6, 7): Received bits are 0, 1, 1, 1. Number of 1s is 3 (odd). S3 = 1. The syndrome is S3 S2 S1 = 101. Convert this binary syndrome to decimal: 101₂ = 5₁₀. This indicates that the error is in the 5th position of the received codeword. The 5th bit is indeed D2, which was received as 1, but should be 0. So, the receiver flips the 5th bit from 1 to 0. Received: 0110111 Corrected: 0110011.

Other error correction codes, like Reed-Solomon codes, are used in applications requiring higher levels of error resilience, such as CDs, DVDs, and satellite communications.