Code 1

1. About the code

During the repetition of electricity flowing (1) and not flowing (0) on the computer, there are cases where the state is not perfect and the complete value cannot be known. Therefore, by adding or modifying binary numbers, it is checked whether they match the original number, which is collectively called a code.
  Although there is no separate standard, it can be divided into two main categories: codes for reducing or checking errors in computer devices, and codes for comfortable writing of numbers and characters. There are more types of codes than the ones below, but let's look at only a few codes for error reduction.

 

2. Parity code

It has the advantage that it is the simplest structure by adding one digit to check whether an error occurs during the transfer of binary numbers. The parity digit is divided into even parity, which attempts to match the number of 1s in a binary number to an even number, and odd parity, which attempts to match the number of 1s to an odd number. The example below is for even parity.

 

Binary								Parity
		0	0	1	1	0	1	1
	0	1	1	0	0	1	0	1
1	1	1	1	0	0	1	1	0
0	0	0	0	0	0	0	1	1

 

The first binary number has 6 digits and the number of '1's is odd (3), so the parity becomes 1 and the total number of '1's becomes even. The second binary number has 7 digits, but the parity is also 1 because the number of '1's is also odd (3). The third binary number has 8 digits and the number of '1's is even (6), so the parity becomes 0 and keeps the even number. The fourth binary number has 8 digits and the number of '1's is odd (1), so parity becomes 1, making it an even number. In the case of odd parity, you can think of it as the opposite of this result.
  Although the structure is simple, there is a disadvantage that only errors can be checked and cannot be corrected. Moreover, if the error occurs in multiple digits at once (such as 2 or 4 digits), the error is not even checked. Finally, even if an error is found, there is a problem that the number of digits that occurred is unknown. This is only a problem with single parity, and there is a way to solve it by extending it to parallel parity (add parity for the entire binary number separately for each digit), but it is not used well.
  Even with these shortcomings, it is often used because it is very simple.

 

3. Hamming code

A code that can detect and correct errors by mixing parity with binary numbers, named after Richard Wesley Hamming. A plurality of parity digits are inserted to create a Hamming code, and the formula to calculate the number is as follows.

 

2P≥D+P+1 (D=number of data (binary), P=number of parity)

 

If there are 5 binary numbers (D = 5), the expression is 2P≥P+6, and the inequality is established at P≥3. In this case, even if the number of parities is increased, error detection is possible, but there is a loss in that only the calculation time increases, so the minimum value is applied. And the position of this parity is inserted at a position of a power of 2, such as digit numbers 1, 2, 4, 8, 16. Combining these points, applying the Hamming code (D=8, P=4) to the binary number 10101101₂ with even parity is as follows.

 

Number	12	11	10	9	8	7	6	5	4	3	2	1
Category	D	D	D	D	P8	D	D	D	P4	D	P2	P1
Before Calc	1	0	1	0	-	1	1	0	-	1	-	-
P1 range		V		V		V		V		V		V
P2 range		V	V			V	V			V	V
P4 range	V					V	V	V	V
P8 range	V	V	V	V	V
After Calc	1	0	1	0	0	1	1	0	1	1	0	0

 

As shown in the table, the calculation target is different for each parity digit, repeatedly spaced apart from its own position as many as the parity number. That is, the parity calculation range is (1)·(3)·(5)·(7)·(9)·(11) for P1, (2·3)·(6·7)·(10·11) for P2, (4·5·6·7)·(12) for P4 and P8 is calculated only (8·9·10·11·12), and set the value so that the number of '1's is even. P8＝0, P4＝1, P2＝0, and P1＝0 determined in this way are inserted into the parity position to complete the code.
  When the 7th digit becomes '0' due to a problem after transmitting the 12-digit number, the receiving part knows that D＋P＝12 from 2^P≥D＋P＋1, obtains P＝4 from the calculated 2^P≥13, and understands that D＝8. After that, it is calculated for each parity digit and P8＝0, P4＝1, P2＝1, P1＝1. These four digits are treated as binary numbers, and as a result of 0111₂(7₁₀), it is confirmed that there is an error in the 7th digit. Binary number is 0 or 1, correction is completed by inverting the 7th digit. If all '0's are returned during parity calculation at the receiving end, it can be said that there is no error.
  Although it has a weakness that it cannot even check an error when multiple occurrences occur at the same time, it is used as an advantage that an error can be detected and corrected at the same time even for a single digit.

 

4. Gray code

Gray code has been modified without adding a separate number of digits from the original binary number, and is a code that differs only by one digit between consecutive numbers. In the case of a basic binary number, it changes repeatedly from 0₁₀ to 7₁₀, and the number of digits changes in the order of 000₂→001₂→010₂→011₂→100₂→101₂→110₂→111₂→000₂, keeps changing 1→2→1→3→1→2→1→3. When two or more of these changes, it is not guaranteed that they occur exactly at the same time, but if the computer's performance is good and the error is recognized, there is a possibility that it can be recognized that there was a different value for a moment.
  To eliminate this problem, change the number sequence in the order of 000_2G→001_2G→011_2G→010_2G→110_2G→111_2G→101_2G→100_2G→000_2G so that the change in digit is always one digit. The change is always only one digit has the advantage in that errors are reduced because the range of change is reduced when representing continuously changing numerical values (counters, etc.) or quantities (analog environment).

 

< This is the 3-digit gray code notation of the encoder (rotation angle measuring device). If you rotate it quickly, it may appear gray... >

 

The method to convert the 8-digit binary number 10011101₂ to gray code is as follows.

 

Number		8		7		6		5		4		3		2		1
Binary		1	→	0	→	0	→	1	→	1	→	1	→	0	→	1
↓		↓		↓		↓		↓		↓		↓		↓		↓
Gray code		1		1		0		1		0		0		1		1

 

First, the highest digit (8th) number (1) is taken as it is. For the next digit (7th), even parity operation is performed on the upper digit of the binary number (8th) and the current digit of the binary number (7th). That is, the number of '1's is odd (1), so it becomes 1. The next digit (the 6th) is also equal to the even parity operation for the upper (7th) binary number and the current (6th) digit of the binary number. Since the number of '1's is even (0), it becomes 0. Repeat this to the lowest digit (1st).
  Conversely, the method of changing the gray code 01100100_2G to binary is as follows.

 

Number		8		7		6		5		4		3		2		1
Gray code		0		1		1		0		0		1		0		0
↓		↓	↗	↓	↗	↓	↗	↓	↗	↓	↗	↓	↗	↓	↗	↓
Binary		0		1		0		0		0		1		1		1

 

First, the highest digit (8th) number (0) is taken as it is. For the next digit (7th), even parity operation is performed on the upper digit of the binary number (8th) and the current digit of the gray code (7th). That is, the number of '1's is odd (1), so it becomes 1. The next digit (6th) is also equal to the higher (7th) binary number and the current (6th) digit of the gray code for even parity operation, and the number of '1's is even (2), so it becomes 0. Repeat this to the lowest digit (1st).
  Even if the maximum number of digits is changed, the change method is the same, and if the number is changed, the highest digit is always the same, so the binary number and the highest digit of the gray code match.
  Finally, remember that even though the reduction of errors can be expected by converting to gray code, it is necessary to reconvert to binary number because calculations such as arithmetic operations are not established.

 

5. Conclusion

Know only the type of code, and if necessary, find a calculator on the Internet and use it.