CN103297196B - A kind of cyclic redundancy check method of non-whole byte data - Google Patents

Abstract

The invention discloses the cyclic redundancy check method of a kind of non-whole byte data, it comprises the following steps: table look at Crc16_Table [S₀] obtain the first byte S₀CRC16 value；By the high n position C of the CRC16 value of a upper byte_HAnd B_nPhase XOR, XOR result is tabled look-up as subscript and is obtained Crc16_Table [(C_H+B_n)]；By behind low (16 n) lt n position of the CRC16 of a upper byte with table look-up value Crc16_Table [(C_H+B_n)] phase XOR, wherein the value relation of n is: the n=8 when calculating whole byte CRC16, the bit number on n treating excess syndrome border when calculating not enough byte CRC16.The present invention can be to use under the conditions of non-integer byte is unsatisfactory for the use calculated by byte mode in transmission information, substantially increase computational efficiency, shorten the calculating time, release substantial amounts of cpu resource, reduce cpu performance and the requirement of operation clock, reduce CPU power consumption.

Description

A kind of cyclic redundancy check method of non-whole byte data

Technical field

The present invention relates to the cyclic redundancy check (CRC) algorithm of a kind of non-whole byte data.

Background technology

In various data communication, being the most all transmitted after packet, after grouped data, additional data Frame Check Sequence (Frame Check Sequence is called for short FCS) carries out Error Control, to ensure the correctness of the transmission of data.In the realization of Frame Check Sequence, CRC (Cyclic Redundancy Code, it is called for short CRC) obtain a wide range of applications with its high efficiency, high-performance, it is a kind of method improving data communication reliability commonly used in current data transmission procedure.

Data are during sending, and transmitting terminal will need the data transmitted to carry out CRC check yardage calculation, and send together after being attached to check code transmit data.Receiving terminal needs to carry out check code calculating by the same computational methods data to receiving, and is then compared with the CRC code received by calculated CRC code, if unanimously the transmission of explanation data is errorless, if the transmission of inconsistent explanation data is wrong.

The computational efficiency of CRC and time delay are the most all the keys of CRC coding techniques, directly determine whether it can apply in reality.At present, the computational methods of CRC, there is step-by-step calculate and calculate two kinds of distinct modes by byte, computational efficiency is calculated high by byte mode, during calculating, cycle-index is 1/8 that a mode calculates, and calculate the shortest and controlled, byte mode is by calculating of having tabled look-up, the shortest and fixing, calculate more than position mode and be more suitable for real-time embedded system by conditional judgment executive mode, although byte mode superiority is obvious, but its actual application has stringent condition requirement: transmission information is necessary for integer byte, transmission information is the CRC transmitting information sequence with regard to only using position mode to calculate that non-integer byte is unsatisfactory for the use condition of byte mode, extremely inefficient, the real-time response performance of serious limit product.

Summary of the invention

It is an object of the invention to overcome the deficiencies in the prior art, thering is provided a kind of can be to use under the conditions of non-integer byte is unsatisfactory for the use calculated by byte mode in transmission information, substantially increase computational efficiency, shorten the calculating time, release substantial amounts of cpu resource, reduce cpu performance and the requirement of operation clock, reduce the cyclic redundancy check (CRC) algorithm of a kind of non-whole byte data of CPU power consumption.

It is an object of the invention to be achieved through the following technical solutions: the cyclic redundancy check (CRC) algorithm of a kind of non-whole byte data, CRC mathematics essence is to be to CRC generator polynomial complementation, the generator polynomial of CRC16 to transmission message polynomial:

G(x)=x¹⁶+x¹²+x⁵+ 1, its computational methods are: add to after S (x) by 16 0, namely

S(x)=r¹⁶× S (x), wherein r=2 is the base of binary polynomial operation, and then generator polynomial G (x) is done division arithmetic by S (x), i.e. carries out logic xor operation, finally obtains the complementing part of division, be CRC16, referred to as C_reg, and business's part is called for short M (x), it comprises the following steps:

S1: assume S_mCorresponding CRC16 value is C_reg, by defining, then:

${\mathrm{CRC}}_{S_m}=(R^2*S_m)\mathrm{Mod}\left(G\left(x\right)\right)=G_{\mathrm{reg}}=\mathrm{Crc}16\_\mathrm{Table}\left[S_m\right]$ (formula 1)

R²*S_m=M(x)*G(x)+C_reg(formula 2)

S2: at S_mRear increase n position, less than a byte information position, forms a new binary polynomial S'_m, calculate S'_mCRC16, it comprises the following steps:

S201: at S_mRear increase n position, less than a byte information position, forms a new binary polynomial S'_m,

S'_m=rⁿ*S_m+B_n(formula 3)

B_nRepresenting n position binary polynomial, wherein high-order front, low level is rear.

S202: to S'_mCarry out increasing by 16 0 operations and ensure that remainder is exactly directly the CRC16 result of data stream:

R²*S'_m=R²*(rⁿ*S_m+B_n)=rⁿ*(R²*S_m)+R²*B_n(formula 4)

Formula 2 is substituted and obtains into formula 4:

R²*S'_m=rn*(M(x)*G(x)+C_reg)+R²*B_n

=(rⁿ*M(x)*G(x))+rⁿ*C_reg+R²*B_n(formula 5)

Make C_HRepresent C_regHigh n position, C_LRepresent C_regLow (16-n) position,

C_reg=r^(16-n)*C_H+C_L(formula 6)

Formula 6 substitutes into formula 5 obtain:

R²*S'_m=(rⁿ*M(x)*G(x))+R²*C_H+rⁿ*C_L+R²*B_n(formula 7)

=(rⁿ*M(x)*G(x))+R²*(C_H+B_n)+rⁿ*C_L

Defined by CRC and know: (rⁿ* M (x) * G (x)) Mod (G (x)) ≡ 0 (formula 8)

$(R^2*(C_H+B_n))\mathrm{Mod}\left(G\left(x\right)\right)={\mathrm{CRC}}_{C_H+B_n}=\mathrm{Crc}16\_\mathrm{Table}[C_H+B_n]$

$(r^n*C_L)\mathrm{Mod}\left(G\left(x\right)\right)=r^n*C_L$

Obtained by logic or the associativity of operation, formula 7 and formula 8:

(R²*S'_m)Mod(G(x))=Crc16_Table[C_H+B_n]+rⁿ*C_L(formula 9)

That is:

${\mathrm{CRC}}_{S_m^{\′}}=\mathrm{Crc}16\_\mathrm{Table}\left[(C_H+B_n)\right]+r^n*C_L.$ (formula 10)

S3: from formula 10, the CRC16 calculating current data completes in two steps, comprises the following steps that；

S301: by the high n position C of the CRC16 value of a upper byte_HAnd B_nPhase XOR, XOR result is tabled look-up as subscript and is obtained Crc16_Table [(C_H+B_n)]；

S302: by behind low (16-n) lt n position of the CRC16 of a upper byte with table look-up value Crc16_Table [(C_H+B_n)] phase XOR.

S4: calculate the CRC16 of random length byte, it comprises the following steps:

S401: the first byte S of the stream that fetches data₀Table look-up Crc16_Table [S as subscript₀] obtain S₀Current CRC16 value；

S402: CRC16 calculating can be completed by the part that byte processes according to byte by all in order；

S403: take the actual bit number that n is remaining data and substitute into formula 10, completes to remain the calculating of not enough byte sections CRC16；

S404: combine the current CRC16 value that S401, S402 and S403 obtain, the CRC result calculated according to byte and not enough byte sections CRC result and obtain the CRC16 result of whole data.

The invention has the beneficial effects as follows:

The present invention can be to use under the conditions of non-integer byte is unsatisfactory for the use calculated by byte mode in transmission information, not only CRC result is correct, and substantially increase computational efficiency, shorten the calculating time, actual test shows: the calculating time brings up to 9us from 70us, improves real-time response performance, releases substantial amounts of cpu resource, reduce cpu performance and the requirement of operation clock, reduce CPU power consumption.

Detailed description of the invention

Technical scheme being detailed further below: the cyclic redundancy check (CRC) algorithm of a kind of non-whole byte data, CRC mathematics essence is to be to CRC generator polynomial complementation, the generator polynomial of CRC16 to transmission message polynomial:

G(x)=x¹⁶+x¹²+x⁵+ 1, its computational methods are: add to after S (x) by 16 0, namely

S(x)=r¹⁶× S (x), wherein r=2 is the base of binary polynomial operation, and then generator polynomial G (x) is done division arithmetic by S (x), i.e. carries out logic xor operation, finally obtains the complementing part of division, be CRC16, referred to as C_reg, and business's part is called for short M (x), it comprises the following steps:

S1: assume S_mCorresponding CRC16 value is C_reg, by defining, then:

${\mathrm{CRC}}_{S_m}=(R^2*S_m)\mathrm{Mod}\left(G\left(x\right)\right)=G_{\mathrm{reg}}=\mathrm{Crc}16\_\mathrm{Table}\left[S_m\right]$ (formula 1)

R²*S_m=M(x)*G(x)+C_reg(formula 2)

S2: at S_mRear increase n position, less than a byte information position, forms a new binary polynomial S'_m, calculate S'_mCRC16, it comprises the following steps:

S201: at S_mRear increase n position, less than a byte information position, forms a new binary polynomial S'_m,

S'_m=rⁿ*S_m+B_n(formula 3)

B_nRepresenting n position binary polynomial, wherein high-order front, low level is rear.

S202: to S'_mCarry out increasing by 16 0 operations and ensure that remainder is exactly directly the CRC16 result of data stream:

R²*S'_m=R²*(rⁿ*S_m+B_n)=rⁿ*(R²*S_m)+R²*B_n(formula 4)

Formula 2 is substituted and obtains into formula 4:

R²*S'_m=rn*(M(x)*G(x)+C_reg)+R²*B_n

=(rⁿ*M(x)*G(x))+rⁿ*C_reg+R²*B_n(formula 5)

Make C_HRepresent C_regHigh n position, C_LRepresent C_regLow (16-n) position,

C_reg=r^(16-n)*C_H+C_L(formula 6)

Formula 6 substitutes into formula 5 obtain:

R²*S'_m=(rⁿ*M(x)*G(x))+R²*C_H+rⁿ*C_L+R²*B_n(formula 7)

=(rⁿ*M(x)*G(x))+R²*(C_H+B_n)+rⁿ*C_L

Defined by CRC and know: (rⁿ* M (x) * G (x)) Mod (G (x)) ≡ 0 (formula 8)

$(R^2*(C_H+B_n))\mathrm{Mod}\left(G\left(x\right)\right)={\mathrm{CRC}}_{C_H+B_n}=\mathrm{Crc}16\_\mathrm{Table}[C_H+B_n]$

$(r^n*C_L)\mathrm{Mod}\left(G\left(x\right)\right)=r^n*C_L$

Obtained by logic or the associativity of operation, formula 7 and formula 8:

(R²*S'_m)Mod(G(x))=Crc16_Table[C_H+B_n]+rⁿ*C_L(formula 9)

That is:

${\mathrm{CRC}}_{S_m^{\′}}=\mathrm{Crc}16\_\mathrm{Table}\left[(C_H+B_n)\right]+r^n*C_L.$ (formula 10)

S3: from formula 10, the CRC16 calculating current data completes in two steps, concretely comprises the following steps；

S301: by the high n position C of the CRC16 value of a upper byte_HAnd B_nPhase XOR, XOR result is tabled look-up as subscript and is obtained Crc16_Table [(C_H+B_n)]；

S302: by behind low (16-n) lt n position of the CRC16 of a upper byte with table look-up value Crc16_Table [(C_H+B_n)] phase XOR.

S4: calculate the CRC16 of random length byte, it comprises the following steps:

S401: the first byte S of the stream that fetches data₀Table look-up Crc16_Table [S as subscript₀] obtain S₀Current CRC16 value；

S402: CRC16 calculating can be completed by the part that byte processes according to byte by all in order；

S403: take the actual bit number that n is remaining data and substitute into formula 10, completes to remain the calculating of not enough byte sections CRC16；

S404: combine the current CRC16 value that S401, S402 and S403 obtain, the CRC result calculated according to byte and not enough byte sections CRC result and obtain the CRC16 result of whole data.

Claims (1)

1. the cyclic redundancy check method of a non-whole byte data, it is characterised in that: CRC mathematics essence is many to transmission information CRC generator polynomial complementation, the generator polynomial of CRC16 are by item formula: G (x)=x¹⁶+x¹²+x⁵+ 1, its computational methods are: 16 0 are added to after S (x), namely S (x)=r¹⁶× S (x), wherein r=2 is the base of binary polynomial operation, Then generator polynomial G (x) is done division arithmetic by S (x), i.e. carries out logic xor operation, finally obtains the complementing part of division, It is CRC16, referred to as C_reg, and business's part is called for short M (x), said method comprising the steps of:

S401: the first byte S of the stream that fetches data₀Table look-up Crc16_Table [S as subscript₀] obtain S₀Current CRC16 value；

S402: in order by all calculating that can complete CRC16 by the part that byte processes according to byte；

S403: take actual bit number that n is remaining data and substitute into formula 10: Complete to remain the calculating of not enough byte sections CRC16；

S404: combine current CRC16 value, the CRC result calculated according to byte and deficiency that S401, S402 and S403 obtain Byte sections CRC result obtains the CRC16 result of whole data；

Wherein, the calculating of CRC16 described in step S402 and step S403 completes in two steps, comprises the following steps that；

S301: by the high n position C of the CRC16 value of a upper byte_HAnd B_nPhase XOR, XOR result is tabled look-up as subscript and is obtained Crc16_Table[(C_H+B_n)]；

S302: by behind low (16-n) lt n position of the CRC16 of a upper byte with table look-up value Crc16_Table [(C_H+B_n)] phase XOR；

Wherein the concrete derivation of step S301 and step S302 is as follows:

S1: assume S_mCorresponding CRC16 value is C_reg, by defining, then:

R²*S_m=M (x) * G (x)+C_regFormula 2

S2: at S_mRear increase n position, less than a byte information position, forms a new binary polynomial S'_m, calculate S'_m's CRC16, it comprises the following steps:

S201: at S_mRear increase n position, less than a byte information position, forms a new binary polynomial S'_m,

S'_m=rⁿ*S_m+B_nFormula 3

B_nRepresenting n position binary polynomial, wherein high-order front, low level is rear；

S202: to S'_mCarry out increasing by 16 0 operations and ensure that remainder is exactly directly the CRC16 result of data stream:

R²*S'_m=R²*(rⁿ*S_m+B_n)=rⁿ*(R²*S_m)+R²*B_nFormula 4

Formula 2 is substituted and obtains into formula 4:

R²*S'_m=rⁿ*(M(x)*G(x)+C_reg)+R²*B_n=(rⁿ*M(x)*G(x))+rⁿ*C_reg+R²*B_n Formula 5

Make C_HRepresent C_regHigh n position, C_LRepresent C_regLow (16-n) position,

C_reg=r^(16-n)*C_H+C_LFormula 6

Formula 6 substitutes into formula 5 obtain:

R²*S'_m=(rⁿ*M(x)*G(x))+R²*C_H+rⁿ*C_L+R²*B_nFormula 7

=(rⁿ*M(x)*G(x))+R²*(C_H+B_n)+rⁿ*C_L；

Defined by CRC and know: (rⁿ* M (x) * G (x)) Mod (G (x)) ≡ 0 formula 8

$(R^2*(C_H+B_n\left)\right)Mod\left(G\right(x\left)\right)={\mathrm{CRC}}_{C_H+B_n}=Crc16\_Table\[C_H+B_n\]$

(rⁿ*C_L) Mod (G (x))=rⁿ*C_L

Obtained by the associativity of logic xor operation, formula 7 and formula 8:

(R²*S'_m) Mod (G (x))=Crc16_Table [C_H+B_n]+rⁿ*C_LFormula 9

That is: