[Computer System] Check Code
- Check code
-
- parity code
- Hamming code
-
- Number of check digits
- Check digit position
- Determine the check value
- Check error detection
- cyclic redundancy check code
Check code
When the computer system is running, in order to ensure that the data is correct during transmission, one is to improve the reliability of the hardware circuit, and the other is to improve the verification capability of the code. The check code method is usually used to detect whether the transmitted data has errors.
The basic idea of the check code is to improve the integrity and reliability of the data by introducing redundant information and using a check algorithm to detect and correct data errors. details as follows.
Parity check code
e
.
g
.
e.g.
e.g. A simple example
Assume that the data to be transmitted is 01010011, which is an 8-bit binary number.
Odd parity: In odd parity, you need to ensure that there is an odd number of ones in total. First, count the number of 1’s in the data. There are 4 1’s here. In order to ensure that there is an odd number of 1’s in total, a 1 needs to be added to the end of the data so that it becomes 010100111. This extra 1 at the end is the odd parity digit.
Even parity: In even parity, you need to ensure that there is an even number of ones in total. Calculate the number of 1’s in the data. There are 4 1’s here. In order to ensure that there is an even number of 1’s in total, you need to add a 0 at the end of the data to make it become 010100110. This extra 0 at the end is the even parity bit.
Hamming code
Hamming codes are inserted at specific positions between data bits
k
k
K check bits are used to detect and correct errors through the XOR method of combining check bits with data bits.
Number of check digits
Let the data bit be
n
n
n bits, the check digit is
k
k
k bits, then
n
n
n and
k
k
k must satisfy the following relationship:
2
k
?
1
≥
n
+
k
2^k-1 ≥ n + k
2k?1≥n + k
Assume that for 8-bit data bits, 4 check digits are needed to perform Hamming check:
2
3
?
1
< 8 + 3 , 2 4 ? 1 ≥ 8 + 4 2^3-1 < 8 + 3, 2^4-1 ≥ 8 + 4 23?1<8+3, 24?1≥8+4
Position of check digit
The position of the Hamming code check digit is also called the encoding rule of Hamming code.
set up:
-
k
k
The k check digits are
P
k
,
P
k
?
1
,
.
.
.
,
P
1
P_k, P_{k-1}, … , P_{1}
Pk?,Pk?1?,…,P1?;
-
n
n
n data bits are
D
n
?
1
,
D
n
?
2
,
.
.
.
,
D
0
D_{n-1}, D_{n-2}, … , D_{0}
Dn?1?,Dn?2?,…,D0?;
- The corresponding Hamming code is
H
n
+
k
,
H
n
+
k
?
1
,
.
.
.
,
H
1
H_{n + k}, H_{n + k-1}, … , H_{1}
Hn + k?,Hn + k?1?,…,H1?;
So:
-
P
i
P_i
Pi? in the Hamming code
2
i
?
1
2^{i-1}
2i?1 position, that is
H
j
=
P
i
H_j = P_i
Hj?=Pi?,
j
=
2
i
?
1
j=2^{i-1}
j=2i?1, the data bits occupy the remaining positions in the Hamming code from low to high:
- 8 data bits
D
7
,
D
6
,
D
5
,
D
4
,
D
3
,
D
2
,
D
1
,
D
0
D_7, D_6, D_5, D_4, D_3, D_2, D_1, D_0
D7?,D6?,D5?,D4?,D3?,D2?,D1?,D0?, 4 check digits
P
4
,
P
3
,
P
2
,
P
1
P_4, P_3, P_2, P_1
P4?,P3?,P2?,P1?, the formed Hamming code
H
12
,
H
11
,
.
.
.
,
H
3
,
H
2
,
H
1
H_{12}, H_{11}, … , H_3, H_2, H_1
H12?,H11?,…,H3?,H2?,H1?;
- Determine the location of data bits and check bits:
- The location of the check code is
2
0
,
2
1
,
2
2
,
2
3
2^0, 2^1, 2^2, 2^3
20,21,22,23 positions;
- The location of the check code is
- 8 data bits
Determine the verification value
- Odd and even parity:
- In odd parity, the parity bit value is set to ensure that the relevant data bit contains an odd number of ones. If the data bits contain an even number of 1’s, the parity bit is 1 to ensure the sum is odd.
- In even parity, the parity bit value is set to ensure that the relevant data bits contain an even number of ones. If the data bits contain an odd number of 1’s, the check bit is 1 to ensure the sum is even.
- Check digit check position:
- Check Digit
P
1
P_1
P1? Verification position
1
,
3
,
5
,
7
,
9
,
.
.
.
1, 3, 5, 7, 9, …
1,3,5,7,9,…(take 1 and separate 1)
- Check Digit
P
2
P_2
P2? Verification position
2
,
3
,
6
,
7
,
10
,
11
,
.
.
.
2, 3, 6, 7, 10, 11, …
2,3,6,7,10,11,…(take 2 and separate 2)
- Check Digit
P
3
P_3
P3? Verification position
4
,
5
,
6
,
7
,
12
4, 5, 6, 7, 12
4,5,6,7,12 (take 4 and separate 4)
- Check Digit
P
4
P_4
P4? Verification position
8
,
9
,
10
,
11
,
12
8, 9, 10, 11, 12
8,9,10,11,12 (take 5 and divide 5)
- Check Digit
- Check value (even parity):
-
P
1
=
D
0
?
D
1
?
D
3
?
D
4
?
D
6
P_1 = D_0 \bigoplus D_1 \bigoplus D_3 \bigoplus D_4 \bigoplus D_6
P1?=D0D1D3D4D6?
-
P
2
=
D
0
?
D
2
?
D
3
?
D
5
?
D
6
P_2 = D_0 \bigoplus D_2 \bigoplus D_3 \bigoplus D_5 \bigoplus D_6
P2?=D0D2D3D5D6?
-
P
3
=
D
1
?
D
2
?
D
3
?
D
7
P_3 = D_1 \bigoplus D_2 \bigoplus D_3 \bigoplus D_7
P3?=D1D2D3D7?
-
P
4
=
D
4
?
D
5
?
D
6
?
D
7
P_4 = D_4 \bigoplus D_5 \bigoplus D_6 \bigoplus D_7
P4?=D4D5D6D7?
- in
?
\bigoplus
? XOR, different is 1, same is 0;
-
Validation error detection
The verification test plan is as follows:
-
G
1
=
P
1
?
D
0
?
D
1
?
D
3
?
D
4
?
D
6
G_1 = P_1 \bigoplus D_0 \bigoplus D_1 \bigoplus D_3 \bigoplus D_4 \bigoplus D_6
G1?=P1D0D1D3D4D6?
-
G
2
=
P
2
?
D
0
?
D
2
?
D
3
?
D
5
?
D
6
G_2 = P_2 \bigoplus D_0 \bigoplus D_2 \bigoplus D_3 \bigoplus D_5 \bigoplus D_6
G2?=P2D0D2D3D5D6?
-
G
3
=
P
1
?
D
1
?
D
2
?
D
3
?
D
7
G_3 = P_1 \bigoplus D_1 \bigoplus D_2 \bigoplus D_3 \bigoplus D_7
G3?=P1D1D2D3D7?
-
G
4
=
P
1
?
D
4
?
D
5
?
D
6
?
D
7
G_4 = P_1 \bigoplus D_4 \bigoplus D_5 \bigoplus D_6 \bigoplus D_7
G4?=P1D4D5D6D7?
- If even parity is adopted, then when
G
4
G
3
G
2
G
1
G_4G_3G_2G_1
When G4?G3?G2?G1? are all 0, the received data has no errors. (Odd parity is all 1);
e
.
g
.
e.g.
e.g. If even parity is adopted,
G
4
G
3
G
2
G
1
=
1010
G_4G_3G_2G_1=1010
G4?G3?G2?G1?=1010, description
H
10
(
D
5
)
H_{10}(D_5)
H10?(D5?) is wrong. Invert it to correct the error.
Cyclic redundancy check code
Cyclic Redundancy Check (CRC) is an algorithm used to check whether errors occur during data transmission or storage.
The basic principle is to add some redundant data to the original data to be sent, so that the CRC value of the entire data is 0. The receiver recalculates the CRC after receiving the data. If the value is not 0, it means that there is something wrong with the data during transmission. mistake.
e
.
g
.
e.g.
e.g. A simple example is as follows, where the polynomial used in CRC is CRC-4:
x
4
+
x
+
1
x^4 + x + 1
x4 + x + 1
Original data: 1101
Add 0: 11010000
Generating polynomial: 10011 (because
x
4
+
x
+
1
x^4 + x + 1
x4 + x + 1 converted to binary is 10011)
Start modulo 2 division:
11010000 10011 <-- first XOR ---------- 01001000 <-- result, move to the next bit, repeat the XOR operation 10011 ---------- 00000100 10011 ---------- 00100010 10011 ---------- 00110001 From the above result, we can see that the remainder is `0001`, so the CRC value is `0001`.
In this way, the CRC value we get is 0001, so the data sent should be 11010001. After the receiving end receives this data, it can use the same method to calculate the CRC again. If the calculated CRC is 0000, it means that there is no error in the data.
Above, there are three check codes, namely parity check code, Hamming code and cyclic redundancy check code.