Someone asked me in the Wukong Q&A: What is modulo-2 operation? Here, I will use simple language to talk about this interesting modulo-2 operation.
First of all, this problem involves ancient 20,000 years ago and has been widely used; secondly, this problem spans philosophy, mathematics, modern computer technology, communication technology and many other disciplines, covering a wide range of topics, as a popular science topic, it is very meaningful.
"Modulo-2 operations" are involved in the base conversion of applied mathematics in college, and also in the basic disciplines of learning computer science and related majors.
First, what is a mold? What is "Modulo 2 Operation"
So what is a "modulo"? "Modulo" is a transliteration of the English "modulo", also abbreviated as "mod", as a noun is "modulo; modulus; Coefficient; modulus" means ; as a preposition is "to... Take the meaning of "modulo"; as a verb is the meaning of "calculated by modulo". Confused? So speaking of Chinese, the modulo is the operation of finding the remainder of an integer, also known as the "modulo operation" or "the remainder operation", these two operations are not the same, when the integer of the "modulo" is a positive number, the two operations are the same, when the integer of the "modulo" is negative, the two operations are not the same, and I will not discuss it here. For the sake of understanding, we can understand that a "modulo" is the divisor that takes the remainder of an integer. When this divisor is "2", we are called "modulo 2 operations". For example: 5 MOD 2 remains 1, where 2 is the modulus.
Second, what is the principle of "modulo 2 operation"?
In fact, the principle of "modulo 2 operation" is very simple, that is, the four operations of binary in mathematics, including "addition", "subtraction", "multiplication", "division", its rules are the same as our decimal addition, subtraction, multiplication and division of four operation rules, and the difference is not to consider the problem of debit or carry (when there is a carry, retain the calculation of the local number of digits, not the forward one; subtraction is not enough to subtract, equivalent to borrowing 1 from the previous bit when 2, and the previous bit does not decrease) In this way, after the "modu 2 operation", the result has only valid for the base, but for the previous bit , the next bit does not affect the characteristics.
Modulo 2 addition:
0+0 =0，1+0 = 0+1 =1，1+1=0
Modulo 2 addition is the addition of the vertical column aligned with the last bit, according to the modulo 2 algorithm, it can be simply summarized as: odd 1s add up to 1, even numbers of 1s add up to 0
Subtraction of modulo 2:
0-0 = 0，1-1 = 0，1-0=1，0-1=1
The fourth form represents the characteristics of the subtraction of modulo 2, from which it is also possible to draw conclusions of +1 = -1
Modulo 2 multiplication:
The multiplication of a single digit of modulo 2 is defined as follows: 0×0=0, 0×1=0, 1×0=0, 1×1=1
Multi-digit modulo 2 multiplication is calculated like ordinary multiplication, the only difference being that the partial products are added by modulo 2, i.e. the odd number of 1s is added to 1, and the even number of 1s is added to 0.
Modulus 2 division:
Division of modulo 2 is the inverse operation of multiplication of modulo 2. The modulo 2 division has the following three properties:
1. When the number of digits of the last remainder is less than the number of divisors, the division stops.
2. When the number of digits of the divisor is less than the number of divisors, the quotient is 0, and the divisor is the remainder.
3. As long as the number of digits of the divisor or part of the remainder is as many as the divisor, and the highest bit is 1, no matter what other digits are, it can be quoted 1.
Third, why was the "modulo 2 operation" invented?
"Modulo 2 operations" were invented for machine computing.
It was the German genius master Gottfried Wilhelm Leibniz (1646 - 1716), influenced and inspired by the Chinese Zhou Yi, who invented the complete binary algorithm in order to solve the method of machine operation. While recording his binary system on 15 March 1679, Leibniz designed a machine that could perform mechanical calculations. This also laid the foundation for the invention of the electronic computer more than 200 years later.
Leibniz
Fourth, now "modulo 2 operation" is mainly used
"Mode 2 operation" is widely used, mainly used in data storage and data transmission, data communication on the verification of data correctness. The famous communication protocol X.25 FCS (Frame Error Detection Sequence) uses CRC-CCITT, WinRAR, NERO, ARJ, LHA and other compression tool software uses CRC32, disk drive read and write using CRC16, common image storage formats GIF, TIFF, etc. also use CRC as a means of error detection.
Since our modern communication technology is the use of digital technology, in the transmission, there are analog-to-digital, digital-to-analog multiple conversions. In digital transmission, various information is converted to binary for transmission. The transmission may be wired or wireless. Affected by the means of transmission or the transmission distance, interference is inevitable, and the quality of transmission must be affected. Therefore, people invented a "check data" at the same time as transferring data. Now digital communication uses the CRC (Cyclic Redundancy Check) check method, also known as the cyclic redundancy check method.
It is characterized by strong error detection ability, low overhead, and easy to implement with encoders and detection circuits. Judging from its ability to detect errors, the probability of errors it cannot find is only less than 0.0047%. In terms of performance and cost, they are far superior to parity and arithmetic and checksum.
Due to the limited space, I will not explain them one by one, and I will carry out science popularization in the form of articles in the future.
[Changchun Yashixuan] is a popular science creation number, vernacular science series, which is to use easy-to-understand language to popularize science for everyone. It can also be used as an extracurricular book for teenagers to understand high-tech, and I hope you can like it.
More please pay attention to 【Changchun Yashixuan】