cos

Chapter 2 Arithmetic Methods and Arithmetic Units#

2.1 Number Systems and Encoding#

1. Carry Counting System and Its Conversion#

Conversion between decimal and R-base
From R-base to decimal:

$\sum_{i = n}^{-m} k_i × r^i$
eg: Converting binary to decimal

// Binary to Decimal
int bToD(char str[]) {
    int sum = 0;
    for(int i = 0; str[i] != '\0'; i++) {
        sum = sum*2 + (str[i] - '0');
    }
    return sum;
}

From decimal to R-base:

• Integer part: Divide by r and take the remainder, where r is the base
• Fractional part: Multiply by r and take the integer part, code as follows

// Convert decimal number n to k-base integer
void dToK(int n, int k, char str[]) {
    int i = 0;
    if (n == 0) {
        str[0] = '0';
        return;
    }
    while(n) {
        str[i++] =n % k + '0';
        n = (n-n % k) / k;
    }
    i--;
    //reverse
    for (int j = 0; j < i; j++,i--) {
        char t = str[j];
        str[j] = str[i];
        str[i] = t;
    }
}

2. True Value and Machine Number#

• True Value: The number generally written
• Machine Code: The number represented in the machine, addressing the issues of positive and negative signs and decimal point operations in the computer.

3. BCD Code#

Each bit of the binary code representing a decimal digit has a definite weight. Generally, 8421 code is used, where the weights of the four binary codes from high to low are 8, 4, 2, and 1. The values 0000, 0001, ..., 1001 represent 0, 1, ..., 9 respectively, with each digit satisfying binary rules internally, while the digits between satisfy decimal rules, hence this encoding is called "Binary Coded Decimal (BCD)".

Note!
The value range of BCD code is from 0000 to 1001 (i.e., decimal 0 to 9)
Sometimes, performing addition or subtraction on BCD code may yield values outside this range, requiring manual adjustment to obtain correct results.

To implement BCD arithmetic operations in the computer, the operation results need to be corrected, and the correction rule for addition is:

• If the sum of two one-digit BCD codes is less than or equal to (1001)~2~, i.e., (9)~10~, no correction is needed;

Example 1 ① 1+8 = 9
  0 0 0 1
+ 1 0 0 0 
——————————
  1 0 0 1 
No correction needed

• If the sum is greater than or equal to (10)~10~, a correction of +6 must be performed, and a carry is generated, which can occur during the first addition (Example 1 ③) or during correction (Example 1 ②).

Example 1 ② 4+9 = 13
  0 1 0 0
+ 1 0 0 1 
——————————
  1 1 0 1 
+ 0 1 1 0  Correction
——————————
1 0 0 1 1
0001 0011 is 13~
③ 9+7 = 16
  1 0 0 1
+ 0 1 1 1
——————————
1 0 0 0 0
+ 0 1 1 0 Correction
——————————
1 0 1 1 0 
0001 0110 is 16~

4. Characters and Strings#

1. Representation Methods for Characters and Strings#

Symbol data: Character information is represented by data, such as ASCII.
Character representation method ASCII: Uses one byte for representation, with the lower 7 bits for encoding (128), and the highest bit as a parity bit, as shown in the image

Storage method for strings: Occupies multiple contiguous bytes in main memory, each byte stores one character.

2. Representation Method for Chinese Characters#

There are 3755 first-level Chinese characters and 3008 second-level Chinese characters.
Internal code for Chinese characters: The internal code for storing, exchanging, and retrieving Chinese character information, composed of two bytes, with the highest bit of each byte being 1 (distinguishing from English characters).
Chinese character glyph code: The dot matrix of Chinese character shapes.

5. Checksum (Key Point)#

Recommended videos 3Blue1Brown's Hamming Code part1, 3Blue1Brown's Hamming Code part2, very interesting! Although mainly about Hamming codes, it also describes parity codes in detail.
Checksum (only introducing parity codes)

Introduction#

During information transmission and processing, interference and faults can easily lead to errors.

Solution#

Add some redundant information (parity bits) to the effective information.

Definition#

Let x=(x~0~ x~1~.x~n-1~) be an n-bit word, then the even parity bit C is defined as: C=x~0~ ^ x~1~ ^ x~2~ ^ ... ^x~n-1~, where ^ represents bitwise addition, indicating that C=0 only when x contains an even number of 1s, otherwise C=1. It can only detect errors but cannot correct them. Similarly, odd parity can be defined.
Odd parity: C=0 only when there is an odd number of 1s, otherwise C=1.

2.2 Representation and Operations of Fixed-Point Numbers (Key Point)#

1. Representation of Fixed-Point Numbers#

1. Sign-Magnitude Representation#

Fixed-point decimal x~n~.x~n-1~x~n-2~…..x~0~, x is the true value