KR19980044216A - How to check for data errors - Google Patents

Abstract

The present invention relates to a data error check method. In the conventional data error check method, a cyclic redundancy check method has a problem that a transmission rate is slow because only one bit of CRC calculation is performed at a time. The present invention is such a message data in order to solve the conventional problems for receiving one byte it CRC register value of the previous state and the equation ^{S '= X 32 U' (} X) = R g (X) [X 32 (b ( X) + X ⁸ U (X))]; A second step of storing the calculated value in the CRC register; A third step of repeating the first step and the second step until all the message data are input; And a fourth step of transmitting the message data together with the message data when all of the message data is processed as a result of the third step. In this way, the present invention creates 8 bits of message data, The CRC register value and the CRC register value are calculated using a predetermined formula, so that the CRC code can be processed in an 8-bit format to generate a CRC code.

Description

How to check for data errors

FIG. 1 is a circuit diagram of a conventional circulating redundancy system.

2 is a table showing the relationship between i and R _{g (X)} [X ⁱ ] in the formula (1).

Table 3 shows the relationship between hexadecimal and binary numbers.

4 is a table showing the value of the CRC register after 8-bit shift.

FIG. 5 is a circuit diagram for calculating a CRC value in the present invention. FIG.

FIG. 6 is a flow chart of a VeriLog high level data link control of the present invention. FIG.

DETAILED DESCRIPTION OF THE INVENTION [

More particularly, the present invention relates to a CRC error check method, and more particularly, to a CRC error check method, And a method for checking a data error.

A cyclic redundancy check (CRC) is a method of detecting a data error, in which transmission data is modified by a certain rule, a CRC code is generated for the modified data, a CRC code is added to the modified data, , And the receiving side checks the received data to detect an error.

The feature of this method is that multiplication of the special logical operation is performed on the transformation of the data, and similar division is performed on the reception data. Whether or not the data is erroneous is determined by the presence or absence of the remainder in this division.

At this time, a polynomial G (X) for generating a CRC code is predetermined, and in the case of CRC-32, it is defined by the following equation.

^{G (X) = X 32 +} X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 7 + X 5 + X 4 + X 2 + X + 1

At this time, the polynomial G (X) is called a generator polynomial.

The CRC error check method will be briefly described as follows.

Assuming that the generated polynomial G (X) is G (X) = X ⁶ + X ⁴ + X ² +1 and there is transmission data D displayed as the following equation

^{D = X 7 + X 4 +} X 2 + X

First, the transmission data D is multiplied by multiplying the maximum difference of the generator polynomial G (X) by the transmission data D to transform the transmission data. If this is D,

D '= D x X ⁶

= (X ⁷ + X ⁴ + X ² + X) x X ⁶

= X¹³+ X¹⁰+ X⁸+ X⁷

to be.

When the transformed data D 'is created, the transformed data D' is divided by the generator polynomial G (X).

^{(X 13 + X 10 + X} 8 + X 7) / If ^{(X 6 + X 4 + X} 2 +1), shares ^{X 7 + X 5 + X 4} + X + 1, the remainder X ³ + X ² + X + 1

At this time, the remaining X ³ + X ² + X + 1 is set as a CRC code.

When the CRC code (X ³ + X ² + X + 1) and the modified data D 'are added, the data S to be finally transmitted is obtained. That is, S

S = (X ¹³ + X ¹⁰ + X ⁸ + X ⁷ ) + (X ³ + X ² + X + 1)

= X ¹³ + X ¹⁰ + X ⁸ + X ⁷ + X ³ + X ² + X + 1

to be.

At this time, the receiving side receives the data S as shown in the following equation, divides it by the generating polynomial G (X), and judges that there is no data error if the remainder is zero.

S / G (X) = ( X 13 + X 10 + X 8 + X 7) + (X 3 + X 2 + X + 1) / (X 6 + X 4 + X 2 +1)

= X ⁷ + X ⁵ + X ⁴ + X + 1 (the rest = 0)

At this time, among the CRC error checking methods, a shift register (Sn) and exclusive OR gates (XOR) can be configured as shown in FIG. 1, which shows the calculation method of CRC-32 in a circuit.

The operating process is calculated one bit at a time by storing one bit of the input message either exclusively according to the generator polynomial of CRC-32 or shifted to the next CRC register (Sn) and stored in the CRC register.

As described above, the conventional cyclic redundancy check method has a problem that the transmission rate is slow because only one bit of CRC calculation is performed at a time.

SUMMARY OF THE INVENTION An object of the present invention is to provide a data error check method capable of improving the transmission speed by configuring an algorithm for processing data in 8-bit parallel in order to solve such conventional problems.

According to another aspect of the present invention, there is provided a data error checking method comprising: a first step of receiving message data by one byte and calculating the CRC register value by a CRC register value of a previous state and the following equation; A second step of storing the calculated value in the CRC register; A third step of repeating the first step and the second step until all the message data are input; In the third step, when all the message data are processed and the CRC code is generated, the message data is transmitted together with the message data.

S '= X ³² U' (X)

_{= R g (X) [X} 32 (b (X) + X 8 U (X))]

However, U '(X) = (b (X) + X ⁸ U (X)

X ⁸ X ³² U (X) is an 8-bit shifted CRC register value in all states.

b (X) is the newly entered 8-bit message data.

X ³² is the highest order of the generator polynomial.

S 'is the remainder of dividing the CRC code: [X ³² (b (X) + X ⁸ U (X))] by the generator polynomial [g (X)].

Hereinafter, the functions and effects of the present invention will be described with reference to the accompanying drawings.

First, if the message data is U (X) and the generator polynomial for generating the CRC code is g (X), the general formula of the transmission data U (X) and the generator polynomial g (X) is as follows.

U (X) = U ₀ + U ₁ X + U ₂ X ² + U ₇ X ⁷

g (X) = 1 + X + X 2 + X 4 + X 5 + X 7 + X 8 + X 10 + X 11 + X 12 + X 16 + X 22 + X 23 + X 26 + X 32

The CRC code is defined as the remainder S (X) obtained by multiplying the polynomial U (X) of the transmission data by the highest order of the generator polynomial g (X) and dividing it by the generator polynomial g (X) .

R _{g (x)} [X ³² U (X)] where R _{g (x)}

In this case, the X ³² U (X) can be expressed as X ³² U (X) = a (X) g (X) + S (X)

Where a (X) is the quotient of X ³² U (X) divided by g (X). And the remainder of S (X)

S (X) = S ₀ + S ₁ X + S ₂ X ² + + S ₃₁ X ³¹

to be.

When 8-bit data is processed as described above, it is shifted to the right by 8 bits, and 8-bit new data is input to the vacant positions.

B (X) = b ₀ + b ₁ X + b ₂ X ² + b ₇ x ⁷ , the new data to be processed U '(X) is the sum of the value of the CRC register processed in the previous state, that is, U (X) and the newly inputted 8-bit message data b (X). This can be expressed as follows.

U '(X) = b (X) + X ⁸ U (X) where X ⁸ indicates 8-bit shift.

In order to obtain the CRC code for U '(X), first multiply X ³² , which is the highest derivative of the generator polynomial, to obtain X ³² U' (X). At this time, X ³² U '(X) is developed as follows.

X ³² U '(X) = X ³² [b (X) + X ⁸ U (X)]

= X ³² b (X) + X ⁸ [X ³² U (X)]

= X ³² b (X) + X ⁸ [a (X) g (X) + S (X)

= X ³² b (X) + X ⁸ [a (X) g (X)] + X ⁸ S (X)

Now, using X ³² U '(X) to find the remainder S' (X)

_{S '(X) = R g} (x) [X 32 U' (X)]

Substituting the equation U '(X) = b (X) + X ⁸ U (X) into the formula S' (X) = R _{g (x)} [X ³² U '(X)]

S '(X) = R _{g (x)} [X ³² b (X) + X ⁸ U (X)]

= R _{g (x)} [X ³² b (X) + X ⁸ X ³² U (X)]

to be.

At this time, since X ³² U (X) = a (X) g (X) + S (X)

R _{g (x)} [X ³² b (X) + X ⁸ X ³² U (X)]

= R _{g (x)} [X ³² b (X) + X ⁸ a (X) g (X) + X ⁸ S (X)]

_{= R g (x) [X} 32 b (X)] + R g (x) [X 8 a (X) g (X)] + R g (x) [X 8 S (X)]

.

In addition, by dividing the X ⁸ a (X) g (X) by g (X) that shares X ⁸ a (X) the remainder _{0 R g (x) [X} 8 a (X)] wherein because it is zero .

therefore

_{S '(X) = R g} (x) [X 32 b (X)] + R g (x) [X 8 S (X)]

.

When the above equations are developed using the general formulas b (X) and S (X)

_{S '(X) = R g} (x) [X 32 (b 0 + b 1 X 1 + b 2 X 2 + b 3 X 3 + b 4 X 4 + b 5 X 5 + b 6 X 6 + b 7 X ⁷ ) + X ⁸ (S ₀ + S ₁ X ¹ + ... + S ₃₁ X ³¹ )

_{= ((b 0 + S 24} ) X 32 + (b 1 + S 25) X 32 + ... + (b 7 + S 31) X 39 + S 0 X 8 + S 1 X 9 + ... S 23 X 31

Can be used as.

Also, when generalizing the above equation

, Where (b _i + S _{24 + i} ) is set to ti for convenience of explanation,

.

And S ₀ X ⁸ + S ₁ X ⁹ + ... + S ₂₃ X ³¹ divided by g (X) is 0 and the remainder is S ₀ X ⁸ + S ₁ X ⁹ + ... + S ₂₃ X ³¹ , (S ₀ X ⁸ + S1 ^X9 + ... S ₂₃ X ³¹ ) can be subtracted from Rg (X). therefore

.

Here, with reference to FIG. 3 showing the relationship between the second, hexadecimal and binary numbers showing the relationship between i and R _{g (x)} [X ⁱ ] in the above equation (1), the CRC register Is calculated as shown in FIG. 4.

The value of the CRC register after 8-bit shift is written as follows.

S0 = t0 + t1 + b0 + b6 + s24 + s30

S'1 = t0 + t1 + t6 + t7

S'2 = t0 + t1 + t2 + t6 + t7

S'3 = t1 + t2 + t3 + t7

S'4 = t0 + t2 + t3 + t4 + t6

S'5 = t0 + t1 + t3 + t4 + t5 + t6 + t7

S'6 = t1 + t2 + t4 + t5 + t6 + t7

S'7 = t0 + t2 + t3 + t5 + t7

S'8 = S0 + t0 + t1 + t3 + t4

S'9 = S1 + t1 + t2 + t4 + t5

S'10 = S2 + t0 + t2 + t3 + t5

S'11 = S3 + t0 + t1 + t3 + t5

S'12 = S4 + t0 + t1 + t2 + t4 + t5 + t6

S'13 = S5 + t1 + t2 + t3 + t5 + t6 + t7

S'14 = S6 + t2 + t3 + t4 + t6 + t7

S'15 = S1 + t3 + t4 + t5 + t7

S'16 = S8 + t0 + t4 + t5

S'17 = S9 + t1 + t5 + t6

S'18 = S10 + t2 + t6 + t7

S'19 = S11 + t3 + t7

S'20 = S12 + t4

S'21 = S13 + t5

S'22 = S14 + t0

S'23 = S15 + t0 + t1 + t6

S'24 = S16 + t1 + t2 + t7

S'25 = S17 + t2 + t3

S'26 = S18 + t0 + t3 + t4 + t6

S'27 = S19 + t1 + t4 + t5 + t7

S'28 = S20 + t2 + t5 + t6

S'29 = S21 + t3 + t6 + t7

S'30 = S22 + t4 + t7

S'31 = S23 + t5

The circuit configuration of the present invention is shown in FIG.

Reference is made to FIG. 6 for a VeriLog High Level Data Link Control Order (HDL) of the present invention.

As described in detail above, according to the present invention, the CRC code is generated through the calculation of the CRC register value and the pre-calculated formula just before the message data, so that the CRC code can be processed 8 bits at a time, have.

Claims (1)

A first step of receiving the message data one byte at a time and calculating the CRC register value by a CRC register value of the previous state and the following equation; A second step of storing the calculated value in the CRC register; A third step of repeating the first step and the second step until all the message data are input; And a fourth step of transmitting the combined message data when the CRC code is generated by processing all the message data as a result of performing the third step. S '= X ³² U' (X) _{= R g (X) [X} 32 (b (X) + X 8 U (X))] However, U '(X) = (b (X) + X ⁸ U (X) X ⁸ X ³² U (X) is an 8-bit shifted CRC register value in all states. b (X) is the newly entered 8-bit message data. X ³² is the highest order of the generator polynomial. S 'is the remainder of dividing the CRC code: [X ³² (b (X) + X ⁸ U (X))] by the generator polynomial [g (X)].