Catalog

CRC（ Cyclic redundancy check ）

CRC Check code generation

CRC Sender and receiver of

The sender

The receiving party

Schematic diagram of division XOR operation

---

CRC（ Cyclic redundancy check ）

CRC（Cyclic Redundancy Check） Cyclic redundancy test , Is a technology used to detect digital data errors . As a checksum type ,CRC Generate fixed length data sets based on the construction of files or larger data sets . As far as its purpose is concerned ,CRC It's a hash function , Used to detect unexpected changes in raw computer data commonly used in storage devices such as digital telecommunications networks and hard drives .

In cyclic redundancy check , A fixed number of check bits are appended to the message to be transmitted . The data receiver receives data , And check the check bit for any errors . In Mathematics , The data receiver evaluates the additional check value by looking for the rest of the polynomial division of the transmitted content . If something seems to have gone wrong , A negative confirmation will be sent , Request retransmission of data .

Cyclic redundancy check is also applicable to storage devices such as hard disks . under these circumstances , The check bit will be assigned to each block in the hard disk . When the computer reads a corrupted or incomplete file , A cyclic redundancy error will be triggered .CRC It can come from other storage devices or CD/DVD. Common causes of errors include system crashes , The document is incomplete or damaged , Or there are many wrong files .

CRC The polynomial design depends on the length of the block that should be protected . The error protection function can also determine CRC Design . Can be used for CRC The resources implemented may have an impact on performance . understand CRC Another way is to look at a specific word in its name . Experts point out that ,CRC go by the name of “ redundancy ”, Because it increases the size of the dataset without adding new information , and “ periodic ” Because it is suitable for periodic implementation systems .

As mentioned earlier , Pointed out that CRC Is a specific type of checksum, which is also helpful , Where a data set of any size is mapped to a fixed size string , It can be called a hash function . by comparison , The checksum itself can be very simple , for example , The primitive checksum can be just the sum of the relevant byte values . Using its periodic setting CRC It is generally considered a very good strategy for checking errors and verifying data integrity . It is part of an evolving toolkit for checksum usage and hashing, as well as general file checking .

CRC Check code generation

CRC The generation of check code mainly includes the following processes ：

1. Find the length of the divisor , This divisor is defined by ourselves .
2. The number of digits of the divisor is reduced by one to CRC The number of digits of the check code , Suppose the number of digits of the divisor is 5, Then the number of digits of the check code is 4, The number of digits of the check code is added to the divisor, that is, the number of information to be transmitted 0, If the number of digits of the check code is 4, Then add... Directly after the divisor 4 individual 0
3. Perform a division operation , Add 4 individual 0 As the new divisor , Divided by the divisor we define , After the division operation is completed , You will get two results ： One is business , The other is the remainder .（ Be careful ： The division operation adopts XOR operation ）
4. The remainder we get, even if we want CRC Check code

CRC Sender and receiver of

The sender

The sender gives the data to be transmitted （Data）, And define polynomials （polynomial）, Get... As a polynomial （n+1） Bit divisor （divisor）, Add... At the end of the data n position 0, As divisor , Divide the divisor by the divisor , The remainder is what you need to calculate n position CRC Check code , What will be obtained CRC The check code is spliced to the end of the original data to generate new data , Send this data to the receiver .

The receiving party

What the receiver needs to do is simpler , Take the whole block of data as the divisor , Use the divisor obtained at the sender to remove the divisor , If the remainder of the result is 0 Words , Represents that there is no error in the transmission of data , The data obtained is correct and effective .

The receiver has another way , Even if the sender sends data and CRC data , The end party gets the data, and the end is filled with n individual 0 As divisor , Divide the divisor by a polynomial , If the remainder is the receiver's CRC Check code , How the recipient gets CRC Data and from the sender CRC In agreement , It can also be proved that there is no problem with data transmission .

Schematic diagram of division XOR operation

You can see , The message we want to convey is 100100, That is, the divisor , Our custom divisor is 1101, Its digits are 4, So add... After the divisor 3 individual 0, Then divide and XOR , The final quotient is 111101, The remainder is 001, According to the previous definition , This remainder 001 That's what we want CRC Check code .

And then what will be generated CRC The check code is added after the original divisor , That is to say 100100 Fill in the back 001 have to 100100001, This is the new data we want to send. The information contains CRC Check code , The receiver can perform corresponding analysis .

  More specific CRC The calculation method of check code can refer to one digit B standing up Main teaching video

[CRC check ] Manual calculation and visual demonstration

Show the customized polynomial in the form of circuit , The original data plus the corresponding number of digits 0, Enter the circuit in turn , The final generation is what we need CRC Check code . More detailed calculation methods can be learned in the video .