
## Concepts

The computer system's fault always be caused by instruments' and components' aging and inefficient. We trait their lifespan and present statistics information, conclude that every component in system have three stages: starting stage, normal working stage and aging stage.

At first starting stage, the component's working status may not stable, and has higher failure rate. At second stage it works normally and enters into stable, also has lower failure rate. But if it enters the third stage, system reliability will decrease due to aging factors. Its failure rate will re-increase again. This is also known as the _bathtub curve_. So the component should be kept in the second stage as much as possible.

The definition of reliability in computer systems refers to the probability of it operating normally from its initiation at time $t = 0$ to a specified time $t$. This probability can be represented by $R(t)$. The failure rate of a computer system refers to the proportion of components failing per unit time compared to the total number of components. It is denoted by $\lambda$. When $\lambda$ is constant, the relationship between reliability and failure rate can be expressed as

$$
R(t) = e^{-\lambda t}
$$

In computer systems, the time during which the system operates normally between two failure occurrences is termed the system's uptime. The average of all such uptime durations is referred to as the Mean Time Between Failures (MTBF). Its relationship with the failure rate is expressed as:

$$
MTBF = \frac{1}{\lambda}
$$

To express the maintainability of a computer, we commonly use the Mean Time to Repair (MTTR), which represents the efficiency of maintenance. It is the average duration from the occurrence of a failure to the restoration of operation. In computer systems, we also use "availability" to denote the system's operational efficiency, which refers to the probability of the computer system functioning normally at any given time. It can be expressed as:

$$
A = \frac{MTBF}{MTBF + MTTR}
$$

The reliability measurement of a computer typically relies on the aforementioned concepts.

## Reliability of series components

In a series system composed of $N$ components connected sequentially end-to-end, the entire system operates normally only when all components function properly. If the reliability of these components is $R_{1}, R_{2}, R_{3}, ..., R_{N}$, and their failure rates are $\lambda_{1}, \lambda_{2}, \lambda_{3}, ..., \lambda_{N}$, then:

The overall reliability of the system is:

$$
R = R_{1} \times R_{2} \times ... \times R_{N}
$$

The overall failure rate of the system is:

$$
\lambda = \lambda_{1} + \lambda_{2} + \lambda_{3} + ... + \lambda_{N}
$$

## Reliability of parallel components

In a parallel system composed of $N$ components connected in parallel, the entire system operates normally as long as at least one component functions properly. In a parallel system, only one component is essential, while the remaining $N-1$ components are redundant. The more redundant components there are, the higher the system reliability. Assuming the reliability of these components is $R_{1}, R_{2}, R_{3}, ..., R_{N}$:

The overall reliability of the system is calculated as:

$$
R = 1 - (1-R_{1})(1-R_{2})...(1-R_{N})
$$

Assuming the failure rate of all components in the system is $\lambda$, the overall failure rate of the system is:

$$
\mu = \frac{1}{\frac{1}{\lambda}\sum_{j=1}^{N}\frac{1}{j}}
$$

## N-modular redundancy system

An N-modular redundancy system consists of N (where $N = 2n + 1$) identical subsystems and one voting unit. When the system is operational, all subsystems simultaneously compute results, and the voting unit outputs the result that is in the majority, thus serving as the final outcome. This setup helps to mitigate failures caused by random factors, ensuring the reliability of the system. If at least $n+1$ components function properly, then the entire system operates normally.

When a module in the system fails, the remaining modules continue to provide service, ensuring the system's availability. The level of redundancy in an N-modular redundancy system is determined by the value of N, with a higher N value indicating greater redundancy and reliability.

Assuming the voter is entirely reliable and each subsystem has a reliability of $R_{0}$ , the reliability of an N-modular redundancy system is calculated as:

$$
R = \sum_{i=n+1}^{N}\binom{i}{N}R_{0}^{i}(1-R_{0})^{N-i}
$$

In the United States' lunar exploration satellites, N-modular redundancy systems are utilized to construct the computer systems onboard the satellite to mitigate failures in the space environment.


Outlines computer system reliability, including series, parallel components, and N-modular redundancy.

System Reliability Model


## Coding Methods

There are four ways to represent binary data in computers: sign-magnitude, one's complement, two's complement, and excess-n notation. These methods are used to represent and process signed numbers in computers, each solving the problems encountered when using binary to represent signed numbers.

1. **Sign-Magnitude**:

   Sign-magnitude was the earliest method used for representation. The highest bit represents the sign, while the remaining bits represent the magnitude. However, sign-magnitude has a problem: there are two representations for zero, positive zero and negative zero. Moreover, special processing is required to compare the results of addition and subtraction, which adds complexity to operations and comparisons.

   The main advantage of sign-magnitude is its simplicity, but the problem of representing zero makes it inconvenient for practical applications.

1. **One's Complement**:

   To address the issue of the sign bit in sign-magnitude representation, one's complement was introduced. In one's complement, the representation of negative numbers is obtained by taking the complement of each bit of the corresponding positive number. Therefore, addition and subtraction operations for two one's complement numbers can be unified as addition operations, with the sign bit participating in the operation, and the sign bit of the result being determined by the operation.

   One's complement solves the problem of the sign bit in sign-magnitude representation. However, when performing addition and subtraction operations, the issue of positive zero and negative zero still needs to be considered.

1. **Two's Complement**:

   To address the issue of positive and negative zero in one's complement representation, two's complement was introduced. In two's complement, all bits are complemented based on one's complement representation, and then $1$ is added.

   Since there is only one representation for zero in two's complement, the problem of positive and negative zero is avoided during operations.

1. **Excess-N Notation (Bias)**:
   Excess-N notation is commonly used to represent the exponent part of floating-point numbers. Excess-N notation is introduced to enable direct comparison of floating-point numbers with integers without the need for additional operations.

   Excess-N notation sets a bias value to represent unsigned integers as signed integers, enabling direct comparison with integers and simplifying the comparison process.

These different representation methods exist to more effectively represent and process signed numbers within a limited number of bits, while keeping operations and comparisons simple and efficient. The choice of representation method depends on specific application requirements and hardware design considerations.

Below, we will introduce their specific representation methods and calculation methods, assuming the binary number is $X_{(2)}$, and the machine's word length is $n$.

### Sign-Magnitude Representation

- If $X$ is a pure integer
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, the highest bit is $1$, and the remaining $n-1$ bits are $X_{(2)}$.
- If $X$ is a pure fraction
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, the highest bit is $1$, and the remaining $n-1$ bits are $X_{(2)}$.
- If $X$ is $0$, there are two representations: $+0$ and $-0$.
- Addition rule: First, determine the sign bit. If the signs are the same, add the absolute values, and the sign of the result remains unchanged; if the signs are different, perform subtraction, and the sign of the result is the same as the sign of the absolute value of the larger number.
- Subtraction rule: Subtracting two numbers represented by sign-magnitude, first negate the sign of the subtrahend, then perform sign-magnitude addition on the minuend and the negated subtrahend. (Subtract numbers with the same sign; add numbers with different signs)

### One's Complement Representation

- If $X$ is a pure integer
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, take the complement of each bit of $X_{(2)}$.
- If $X$ is a pure fraction
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, take the complement of each bit of $X_{(2)}$.
- If $X$ is $0$, there are two representations: $+0$ and $-0$.
- Addition and subtraction: $[X+Y] = [X] + [Y],[X-Y] = [X] + [-Y]$. The sign bit is considered as part of the number, and any carry generated by the sign bit is discarded.

### Two's Complement Representation

- If $X$ is a pure integer
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, the highest bit is $1$, and the remaining $n-1$ bits are $X + 1_{(2)}$.
- If $X$ is a pure fraction
  - When it is positive, the highest bit is $0$, and the remaining $n-1$ bits are $X_{(2)}$.
  - When it is negative, the highest bit is $1$, and the remaining $n-1$ bits are $X + 1_{(2)}$.
- If $X$ is $0$, there is only one representation, for example, when $n=8$, it is $00000000$.
- Addition and subtraction: $[X+Y] = [X] + [Y],[X-Y] = [X] + [-Y]$. The sign bit is considered as part of the number, and any carry generated by the sign bit is discarded.

### Excess-N Notation (Bias)

A bias value of $(2^{n-1})_{(2)}$ is set.

- If $X$ is a pure integer, it is $X_{(2)} + (2^{n-1})_{(2)}$.
- If $X$ is a pure fraction, it is $X_{(2)} + 1_{(2)}$.
- If $X$ is $0$, there is only one representation, for example, when $n=8$, it is $10000000$.
- In fact, when the bias value is $(2^{n-1})_{(2)}$, **only the complement of the highest bit of the two's complement needs to be taken, to obtain the corresponding excess-n notation representation**. In other words, the highest bits of the two's complement and excess-n notation are each other's complements.
- Addition and subtraction operations are the same as two's complement.

### Fixed-Point Numbers

For fixed-point numbers, the decimal point is after the lowest bit. For fixed-point fractions, if there is a

sign bit, the decimal point is after the sign bit; if there is no sign bit, the decimal point is before the highest bit.

Among the above representation methods, for fixed-point integers,

- The representation range of sign-magnitude and two's complement is $[-(2^{n-1}-1),2^{n-1}-1]$.
- The representation range of two's complement and excess-n notation is $[-2^{n-1},2^{n-1}-1]$.
- They can both represent $2^{n}$ numbers.

For fixed-point fractions,

- The representation range of sign-magnitude and two's complement is $[-(1-2^{-(n-1)}),1-2^{-(n-1)}]$.
- The representation range of two's complement and excess-n notation is $[-(1-2^{-(n-1)}),1-2^{-(n-1)}]$.
- They can both represent $2^{n-1}$ numbers.

### Floating-Point Numbers

Floating-point numbers are represented by exponent $E$ and mantissa $F$, where the exponent is represented by $R$ bits of excess-n notation, and the mantissa is represented by $M$ bits of two's complement. The binary number $2^{E} * F$ can be expressed.

The range that can be expressed is $[-2^{(2^R-1)},(1-2^{-M+1})*(2^{(2^R-1)})]$.

## Error Checking Codes

### Parity Check

Parity check refers to adding $1$ to the check bit so that the number of $1$s in the binary number is odd. The same applies to even parity. However, odd parity can only detect coding errors in odd-numbered bits, and cannot detect coding errors in even-numbered bits. Even parity is the same.

### Hamming Code

Hamming codes insert $k$ check bits into $n$ bits of binary data. And satisfy $2^{k}-1≥ n+k$.

Taking the checked data $1100$ as an example, first determine the position of the check bits, and use the above formula to determine that $k=3$. Calculate the positions of the check bits using $2^{i},i =0,1,2,3$. These are the subscripts of the Hamming code check bits. Write down the binary representations of these subscripts.

| 1     | 2     | 4     |
| ----- | ----- | ----- |
| $001$ | $010$ | $100$ |

Then use $*$ to replace $0$ in the above table to use as a wildcard.

| 1     | 2     | 4     |
| ----- | ----- | ----- |
| $**1$ | $*1*$ | $1**$ |

Write down the binary sequence from $1$ to $n+k$, which is from $1$ to $4+3=7$.

| Decimal | Binary |
| ------- | ------ |
| $1$     | $001$  |
| $2$     | $010$  |
| $3$     | $011$  |
| $4$     | $100$  |
| $5$     | $101$  |
| $6$     | $110$  |
| $7$     | $111$  |

Then use the wildcard table to match the numbers.

| 1        | 2        | 4        |
| -------- | -------- | -------- |
| $**1$    | $*1*$    | $1**$    |
| $001(1)$ | $010(2)$ | $100(4)$ |
| $011(3)$ | $011(3)$ | $101(5)$ |
| $101(5)$ | $110(6)$ | $110(6)$ |
| $111(7)$ | $111(7)$ | $111(7)$ |

Then, the Hamming code table to be determined is obtained.

| $H_{7}$ | $H_{6}$ | $H_{5}$ | $H_{4}$ | $H_{3}$ | $H_{2}$ | $H_{1}$ |
| ------- | ------- | ------- | ------- | ------- | ------- | ------- |
| $1$     | $1$     | $0$     |         | $0$     |         |         |

Therefore, we can determine that

- $H_{1}$ is responsible for the parity check of bits $1,3,5,7$.
- $H_{2}$ is responsible for the parity check of bits $2,3,6,7$.
- $H_{4}$ is responsible for the parity check of bits $4,5,6,7$.

Now, let's determine the values of $H_{1},H_{2},H_{4}$. If it is even parity:

- $H_{3},H_{5},H_{7}$, the number of $1$s is odd, so $H_{1}=1$.
- $H_{3},H_{6},H_{7}$, the number of $1$s is even, so $H_{2}=0$.
- $H_{5},H_{6},H_{7}$, the number of $1$s is even, so $H_{4}=0$.

If it is odd parity, simply take the complement of the above check bits.

Finally, the complete Hamming code is obtained.

| $H_{7}$ | $H_{6}$ | $H_{5}$ | $H_{4}$ | $H_{3}$ | $H_{2}$ | $H_{1}$ |
| ------- | ------- | ------- | ------- | ------- | ------- | ------- |
| $1$     | $1$     | $0$     | $0$     | $0$     | $0$     | $1$     |

To check for errors, simply perform XOR operations on the check bits and the bits to be checked:

$$
G_{1}=H_{1} \oplus (H_{1} \oplus H_{3} \oplus H_{5} \oplus H_{7}) \\
G_{2}=H_{2} \oplus (H_{2} \oplus H_{3} \oplus H_{6} \oplus H_{7}) \\
G_{3}=H_{4} \oplus (H_{4} \oplus H_{5} \oplus H_{6} \oplus H_{7})
$$

If even parity is used, $G_{3}G_{2}G_{1}$ should be $000$, and for odd parity, it should be $111$. If it is not all $0$ or $1$, an error has occurred, and the data bit corresponding to the error should be flipped.


Concepts of Sign-Magnitude, One's Complement, Two's Complement, and Excess-n Notation, along with Parity Check and Hamming Code Error Detection Methods for Binary Data

NOTE & BLOG

Posts of CS-BASIC

System Reliability Model

Coding and Error Checking of Binary Data