JP2000181733A - Method and device for data inspection based upon crc and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To obtain the CRC-based data inspecting method which eliminates the need for loop calculation and residue table storage, has small calculation load, and performs a fast process by finding a residue through a bit-shift process and logical operations. SOLUTION: The inspecting device 1 has an input part 2 for inputting information data to be inspected, a ROM 3 which stores the program for the inspecting method, a logical operation part 4 which performs logical operations such as an EX-OR process and an AND process, a RAM 5 which stores a calculation intermediate value, etc., a shift register 6 which performs a shift process for an arbitrary number of bits, and a CPU 7 which controls the respective parts. This device 1 is able to find a new residue for new data through a combination of bit shift operation and logical operation for EX-OR and AND. Namely, the residue for bits can easily be found only by performing the bit shift process and logical operations.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data inspection method and apparatus for inspecting the presence or absence of data errors based on a CRC and a recording medium on which a program for executing the inspection method is recorded.

[0002]

2. Description of the Related Art As a method for checking whether there is an error in data recorded on a recording medium and data transmitted through a transmission line, a parity check (to match an odd number or an even number in a byte unit) is performed. A method of adding 1-bit parity to each byte) and a sum check (a method of adding 2 bytes which are the addition result of each byte over the entire medium) are used. These methods are simple error checking methods that require less computational load and test storage capacity. However, these methods do not have high inspection accuracy and often fail to perform accurate error inspection.

As an error checking method having a higher checking accuracy than such checking methods, a CRC (Cyclic Redundancy Ch.
eck: cyclic redundancy check) is known. The CRC is often used for inspection when data reliability is insufficient, and is mainly used for applications such as serial communication and access to a hard disk.

Hereinafter, the concept of the CRC will be briefly described. CRC uses a cyclic code (a code in which a vector obtained by cyclically shifting an arbitrary code word of a certain code by an arbitrary bit is also a code word) that is a code effective for error checking, and uses a predetermined code as a code. Divide by the number and use the remainder for inspection. This cyclic code data block is composed of k information bits and (nk) check bits.

[0005] Then, consider the data as a polynomial of a variable x,
Treat mathematically. For example, for data "101011",
1 of leftmost x ^5, 1 second from the left end x ^3, likewise the third 1 x ^1, when one of the right-most were considered constant term, expressed the data polynomial x ⁵ + x ³ + x + 1.

For such a polynomial expression, the following modulo 2 addition of a polynomial is defined and an operation based on this is performed. In general, mod N addition indicates addition within a range of a number N, and portions exceeding N are discarded. Therefore, in mod 2 addition, 0 + 1 = 1, 1 + 1 = 0, which means “binary addition without carry”, which is an exclusive OR operation of both bits in addition of binary values. (EX-O
R). Specifically, it is as follows. 1x ⁿ + a ^{1x n = 0x n 1x n +} 0x n = 0x n + 1x n = 1x n 0x n + 0x n = 0x n -1x n = 1x n above, in the mod 2 adder, associativity, distributivity, exchange It can be seen that the rule holds. Further, the mod 2 adder, because it is -1x ⁿ = 1x ^n, subtraction is the same as additive.

A cyclic code can be uniquely defined by a (n−k) -th order residue generating polynomial G (x) that determines a check bit of data. This residue generating polynomial G
Generation of a cyclic code by (x) is performed as follows.

Message polynomial M indicating information bits
In order to encode (x), x ( ^nk ) is multiplied by M (x) to obtain x ( ^nk ) M (x), and the multiplication formula is divided by the remainder generator polynomial G (x). The quotient and remainder of this division are Q
Assuming that (x) and R (x), the following equation (1) holds. x ^nk · M (x) = Q (x) · G (x) + R (x) (1)

For example, transmission data U (x) in communication
Is generated by dividing the remainder R (x) by x ^nk・ Addition to M (x)
Calculate. Addition and subtraction are the same in mod 2 addition
Then, U (x) is expressed by the following equation (2). U (x) = x^nkM (x) + R (x) = Q (x) G (x) (2) Therefore, in the transmission data, the information bits of the upper k bits are
x^nk-Inspection of lower (nk) bits, representing M (x)
The bits represent R (x). From the above equation (2),
Expression (3) is derived. U (x) ÷ G (x) = (x^nkM (x) + R (x)) ÷ G (x) = Q (x) (3) As can be seen from equation (3), the data including the check bits
Dividing the entire data U (x) by the remainder generator polynomial G (x)
The remainder is 0. Therefore, the remainder of this division is 0 on the receiving side.
Whether the transmission data is correct or not.
I can get out. Here, the division is mod 2 addition, that is, 2
EX so that carry and borrow do not occur.
-OR. Therefore, in this case, the remainder is always
One bit less than the divisor, so that the remainder is
And the divisor is a remainder generator polynomial.

As a typical example of such a CRC,
A 16-bit CRC with nk = 16 is often used. The remainder generating polynomial in this 16-bit CRC is G
(X) = x ¹⁶ + x ¹⁵ + x ² +1 and the coefficient x ^nk is x ¹⁶ because ^nk = 16. In 16-bit CRC, burst error detection can be performed up to a maximum length of 16 bits, and when an error burst is larger than 16 bits, 99 bits can be detected.
It has also been proven that errors can be detected with a% probability.

A specific example of a 16-bit CRC will be described. An example
For example, the remainder generator polynomial G (x) = x ¹⁶+ X¹⁵+ X^Two+1
Consider cyclic code of n = 24, k = 8, nk = 16 using
You. Message polynomial M (x) = x⁶+ X^FourCorresponds to +1
X to encode the message "01010001"
¹⁶Dividing M (x) by G (x) to correspond to the remainder R (x)
Data "1000000111100101" is obtained.

Therefore, x ¹⁶ · M (x) is expressed by the following equation (4), and transmission data U (x) is expressed by x ¹⁶ · M (x)
And the remainder R (x) = x ¹⁵ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ²
Since it is made by adding +1, it becomes like the following equation (5). ^{x 16 · M (x) =} x 22 + x 20 + x 16 = (x 16 + x 15 + x 2 +1) × (x 6 + x 5 +1) + (x 15 + x 8 + x 7 + x 6 + x 5 + x 2 +1) ... ( 4) U (x) = (x ²² + x ²⁰ + x ¹⁶ ) + (x ¹⁵ + x ⁸ + x ⁷ + x ⁶ + x ⁵ + x ² +1) (5)

[0013]

As a general method for obtaining a remainder in a 16-bit CRC, the following two methods have been conventionally used. In the first conventional method, division is performed sequentially from the upper digit while shifting by one bit. In the first conventional method, although the calculation is simple,
There is a problem that many loops are required and the execution speed is slow. On the other hand, the second conventional method is a method of increasing the execution speed by using a remainder table, in which the remainders of all 8-bit dividends (256) are stored in advance as a table, and when the division is performed, The necessary remainder is obtained by referring to the table. The second conventional method has a high execution speed, but has a problem that a table representing a remainder needs to be prepared.

The present invention has been made in view of such circumstances, and does not require any of the loop calculation and the storage of the remainder table. It is an object of the present invention to provide a data inspection method and apparatus based on a computer and a recording medium on which a program for executing the inspection method is recorded.

[0015]

According to a first aspect of the present invention, there is provided a data inspection method based on CRC, wherein a polynomial of x indicating a certain M-bit data including an N-bit remainder with respect to an earlier data string is determined. In the method for sequentially checking the remainder when divided by the remainder generation polynomial of x, and checking for a data error based on CRC, the remainder is obtained by a bit shift process and a logical operation.

According to a second aspect of the present invention, there is provided a data inspection method based on a CRC according to the first aspect, wherein N = 2M, the N-bit remainder of the previous data string is replaced by the upper M-bit remainder data and the lower M-bit remainder data. The remainder is obtained by performing a bit shift process and a logical operation on the M-bit data, the upper M-bit remainder data, and the lower M-bit remainder data.

According to a third aspect of the present invention, in the data inspection method according to the second aspect of the present invention, M = 8 and the upper 8 bits of the remainder data and the 8 bits of the data are EX.
-ORing to obtain a first processing result, shifting the first processing result to the right by one bit to obtain a second processing result, and performing EX processing on the first processing result and the second processing result. -ORing to obtain a third processing result;
Shifting the third processing result to the left by 2 bits to obtain a fourth processing result; EX-ORing the third processing result and the fourth processing result to obtain a fifth processing result; Shifting the fifth processing result to the left by 4 bits to obtain a sixth processing result; EX-ORing the fifth processing result and the sixth processing result to obtain a seventh processing result; The seventh processing result is shifted 6 bits to the right to
Obtaining a processing result, the eighth processing result and the fourth
EX-OR processing the processing result to obtain a ninth processing result; shifting the seventh processing result left by one bit to obtain a tenth processing result; and calculating the tenth processing result and data "10000000". And AND processing to obtain an eleventh processing result; shifting the third processing result to the right by 6 bits to obtain a twelfth processing result; and calculating the eleventh processing result and the twelfth processing result. EX-OR processing to obtain a thirteenth processing result; EX-OR processing the thirteenth processing result and the lower 8-bit remainder data to obtain a higher 16 bits of the new 16-bit remainder And converting the ninth processing result to the lower 8 bits of the new 16-bit remainder.
Bit setting step.

According to a fourth aspect of the present invention, there is provided a data inspection apparatus based on a CRC, wherein a polynomial of x indicating a certain M-bit data including an N-bit remainder with respect to a data sequence earlier than the predetermined M-bit data is converted into a predetermined x-residue generation polynomial. A device for checking a data error based on a CRC by sequentially calculating the remainder when divided by a shift register and a logical operation unit, wherein a bit shift process by the shift register and a logical operation by the logical operation unit Thus, the remainder is obtained by the following.

According to a fifth aspect of the present invention, there is provided a data inspection apparatus based on a CRC according to the fourth aspect, wherein N = 2M, the N-bit remainder of the previous data string is replaced by upper M-bit remainder data and lower M-bit remainder data. And dividing the M bits of data, the upper M bits of surplus data, and the lower M bits of surplus data by a bit shift process by the shift register and a logical operation by the logical operation unit. It is characterized by having done.

According to a sixth aspect of the present invention, in the data inspecting apparatus based on CRC according to the fifth aspect, wherein M = 8, and the shift register and the logical operation unit include the upper 8 bits of surplus data and the 8 bits of data. A first logical operation unit for performing an EX-OR operation on the first processing result to obtain a first processing result, a first shift register for shifting the first processing result to the right by one bit to obtain a second processing result, A second logical operation unit for performing an EX-OR operation on the result and the second processing result to obtain a third processing result;
A second shift register that obtains a processing result, a third logical operation unit that performs an EX-OR operation on the third processing result and the fourth processing result to obtain a fifth processing result, and shifts the fifth processing result to the left 4
A third shift register for performing a bit shift to obtain a sixth processing result, and EX-O converting the fifth processing result and the sixth processing result with each other.
A fourth logical operation unit for performing R processing to obtain a seventh processing result, a fourth shift register for shifting the seventh processing result to the right by 6 bits to obtain an eighth processing result, 4
A fifth logical operation unit that performs an EX-OR operation on the processing result to obtain a ninth processing result, a fifth shift register that shifts the seventh processing result one bit to the left to obtain a tenth processing result, A sixth logical operation unit for performing an AND operation on the tenth processing result and the data “10000000” to obtain an eleventh processing result, and a sixth logical operation unit for shifting the third processing result rightward by 6 bits to obtain a twelfth processing result
A shift register; a seventh logical operation unit for performing an EX-OR operation on the eleventh processing result and the twelfth processing result to obtain a thirteenth processing result; And an eighth logical operator for performing an EX-OR operation on
The processing result of the eighth logical operation unit is set to the upper 8 bits of the new 16-bit remainder, and the ninth processing result is set to the lower 8 bits of the new 16-bit remainder.

According to a seventh aspect of the present invention, when a polynomial of x indicating a certain 8-bit data including a 16-bit remainder with respect to an earlier data sequence is divided by a predetermined remainder generating polynomial of x. By sequentially calculating the remainder of
On a computer-readable recording medium on which a program for checking a data error based on a bit CRC is recorded, a 16-bit remainder with respect to a previous data string is replaced with upper 8-bit remainder data and lower 8-bit remainder data. Program code means for causing the computer to divide the data into surplus data; and EX-OR processing of the upper 8 bits of the surplus data and the 8-bit data to obtain a first data.
Program code means for causing the computer to obtain a processing result, program code means for causing the computer to shift the first processing result right by one bit to obtain a second processing result, and the first processing result Program code means for causing the computer to EX-OR-process the second processing result with the second processing result to obtain a third processing result; and
Program code means for causing the computer to obtain a processing result; and program code means for causing the computer to obtain a fifth processing result by performing an EX-OR operation on the third processing result and the fourth processing result. Program code means for causing the computer to shift the fifth processing result to the left by 4 bits to obtain a sixth processing result; and EX-O processing the fifth processing result and the sixth processing result.
Program code means for causing the computer to perform R processing to obtain a seventh processing result; and program code means for causing the computer to shift the seventh processing result to the right by 6 bits to obtain an eighth processing result. , The eighth
Program code means for causing the computer to perform an EX-OR operation on the processing result and the fourth processing result to obtain a ninth processing result; and shifting the seventh processing result left by one bit to the tenth processing result. Program code means for causing the computer to obtain the first processing result, program code means for causing the computer to perform an AND operation on the tenth processing result and data "10000000" to obtain an eleventh processing result, and the third processing Program code means for causing the computer to shift the result to the right by 6 bits to obtain a twelfth processing result; and EX-OR processing the eleventh processing result and the twelfth processing result to obtain a thirteenth processing result Program code means for causing the computer to determine
The 13th processing result and the lower 8 bits of surplus data are
X-OR processing, program code means for causing the computer to make the processing result the upper 8 bits of a new 16-bit remainder, and
Program code means for causing the computer to set the lower 8 bits of the bit remainder to the lower 8 bits.

According to the present invention, a new remainder is obtained only by performing a bit shift process and a logical operation in this manner. Therefore, a table representing the remainder is unnecessary, and a loop calculation is not performed. A new remainder can be obtained, and the calculation load is extremely small and the processing speed is faster than in the past.

[0023]

FIG. 1 is a functional block diagram of an inspection apparatus 1 for inspecting a data error based on a CRC. The inspection apparatus 1 includes an input unit 2 for inputting information data to be inspected.
And RO storing program of inspection method according to the present invention
M3, a logical operation unit 4 that performs a logical operation such as an EX-OR process and an AND process in a CRC check, a RAM 5 that stores an intermediate value calculated in a CRC check, and a shift register that can perform a shift process of an arbitrary number of bits 6 and a CPU 7 for controlling these components.

As described above, in the case of a 16-bit CRC,
Residue generating polynomial G (x) = x¹⁶+ X ¹⁵+ X^Two+1
And the coefficient x^nkIs nk = 16, so x¹⁶Becomes

Data string M in arbitrary 8-bit data units
(X) is generally represented by the following equation (6). _{M (x) = k 7 ·} x 7 + k 6 · x 6 + k 5 · x 5 + k 4 · x 4 + k 3 · x 3 + k 2 · x 2 + k 1 · x 1 + k 0 · x 0 ... (6) ( However, k _i = 0 or 1)

Therefore, the polynomial which is the dividend corresponding to this data string is as shown in the following equation (7). ^{x 16 · M (x) =} x 16 · (k 7 · x 7 + k 6 · x 6 + k 5 · x 5 + k 4 · x 4 + k 3 · x 3 + k 2 · x 2 + k 1 · x 1 + k 0 · _{^{x 0) = k 7 · x}} 16 · x 7 + k 6 · x 16 · x 6 + k 5 · x 16 · x 5 + k 4 · x 16 · x 4 + k 3 · x 16 · x 3 + k 2 · x 16 · x ² + k ₁ · x ¹⁶ · x ¹ + k ₀ · x ¹⁶ · x ⁰ (7)

Here, x ¹⁶ · x ⁷ = Q ₇ (x) · G
(X) + R ₇ (x), x ¹⁶ · x ⁶ = Q ₆ (x) · G
(X) + R ₆ (x),..., X ¹⁶ × x ⁰ = Q ₀ (x)
When G (x) + R ₀ (x) is set, the above equation (7) can be transformed into the following equation (8). ^{x 16 · M (x) =} k 7 · {Q 7 (x) · G (x) + R 7 (x)} + k 6 · {Q 6 (x) · G (x) + R 6 (x)} + · _{·· + k 0 · {Q 0} (x) · G (x) + R 0 (x)} = {k 7 · Q 7 (x) + k 6 · Q 6 (x) + ··· + k 0 · Q 0 ( x)｝ · G (x) + {k ₇ · R ₇ (x) + k ₆ · R ₆ (x) +... + k ₀ · R ₀ (x)} (8)

Therefore, the arbitrary 8 shown in the above equation (6)
The remainder when the polynomial corresponding to the data sequence M (x) in bit data units is divided by the remainder generating polynomial G (x) is expressed by the following equation (9). k ₇ · R ₇ (x) + k ₆ · R ₆ (x) + k ₅ · R ₅ (x) + k ₄ · R ₄ (x) + k ₃ · R ₃ (x) + k ₂ · R ₂ (x) + k _{1 · R 1 (x) + k} 0 · R 0 (x) ... (9)

In the equation (9), R₇(X), R
₆(X), R_Five(X), R_Four(X), R _Three(X), R_Two
(X), R₁(X), R₀(X) is x⁷,
x⁶, X ^Five, X^Four, X^Three, X^Two, X¹, X⁰Corresponding to
This is the remainder obtained by dividing the polynomial by the remainder generating polynomial G (x).
Therefore, one unit of data is composed of a constant 8 bits.
Data, “10000000”, “01000000”, “0010
0000 "," 00010000 "," 00001000 "," 00000100 ",
Polynomials corresponding to “00000010” and “00000001” are surplus
Divide by the polynomial G (x) and calculate the remainder by R₇
(X), R₆(X), R_Five(X), R_Four(X), R
_Three(X), R_Two(X), R₁(X), R₀(X)
In some cases, the combination of these eight types of remainders
The remainder (check) in any unit of 8-bit data
Bit).

An 8-bit code, which is a remainder generating polynomial G
Table 1 below shows specific values of R _i (x) (i = 7,..., 0) when (x) is a 16-bit CRC in which x ¹⁶ + x ¹⁵ + x ² +1.

[0031]

[Table 1]

In general, when considering a certain 8-bit data in a 16-bit CRC, a remainder (ie, 16-bit check bits) for a data string before this data is added to form data to be checked. Therefore, the sum including the remainder must be divided as the dividend.

Assuming that the preceding data string, quotient, and remainder are M '(x), Q' (x), and R '(x), the following equation (10) holds. x ¹⁶ · M ′ (x) = Q ′ (x) · G (x) + R ′ (x) (10)

Therefore, the following equation (11) holds for a data string M (x) obtained by adding new data D (x) to the data string M (x). ^{x 16 · M (x) =} x 16 · {x 8 · M '(x) + D (x)} = x 8 · x 16 · M' (x) + x 16 · D (x) = x 8 · Q ' (X) · G (x) + x ⁸ · R ′ (x) + x ¹⁶ · D (x) (11)

Here, R '(x) is replaced with R' of the upper 8 bits.
_Up (x) and lower 8 bits R ' _lo (x)
R ′ (x) is represented by the following equation (12), and using this to rewrite equation (11) gives the following equation (13). ^{R '(x) = x 8} · R' up (x) + R 'lo (x) ... (12) x 16 · M (x) = x 8 · Q' (x) · G (x) + x 16 · R ^{_{'up (x) + x 8}} · R' lo (x) + x 16 · D (x) = x 8 · Q '(x) · G (x) + x 16 · {R' up (x) + D (x)} + X ⁸ · R ' _lo (x) ... (13)

In the equation (13), x ¹⁶ · ｛R ' _up (x)
Since + term D (x)} is greater than x ¹⁶ degree can be divided by the remainder generator polynomial G (x). Assuming that the quotient and the remainder at this time are Q ″ (x) and R ″ (x), the following equation (14) holds. x ¹⁶ · {R ′ _up (x) + D (x)} = Q ″ (x) · G (x) + R ″ (x) (14)

By rewriting equation (13) using the relationship of equation (14), the following equation (15) is obtained. ^{x 16 · M (x) =} x 8 · Q '(x) · G (x) + Q "(x) · G (x) + R" (x) + x 8 · R' lo (x) = {x 8 · Q ′ (x) + Q ″ (x)｝ · G (x) + R ″ (x) + x ⁸ · R ′ _lo (x) (15) The first term {x ⁸ · Q ′ (x) in equation (15) ) + Q ″
Since (x)｝ · G (x) is divisible by G (x), x ¹⁶
The remainder when M (x) is divided by G (x) is R ″ (x)
+ X ⁸ · R ' _lo (x).

Therefore, to summarize the above, by performing the following steps, new data D (x)
To obtain a new remainder. (Step 1): mod 2 is added to the new data D (x) and the upper 8 bits R ′ _up (x) of the previous residue. (Step 2): A residue R ″ (x) in a 16-bit CRC using the addition result as a dividend is calculated. (Step 3): The calculated R ″ (x) and the lower 8 bits R of the immediately preceding residue. ' _Lo (x) by x ⁸ and mod 2 addition, and the addition result (R ″ (x) + x ⁸ · R ′ _lo (x))
Is the new remainder.

In the present invention, utilizing the characteristics of the remainder of the 16-bit CRC as shown in Table 1 and the characteristics of the remainder calculation of the 16-bit CRC as shown in steps 1 to 3,
By bit shift processing and logical operation, a new remainder is obtained without using any remainder table.

Hereinafter, the present invention will be described in detail. 2 and 3 are flowcharts showing the procedure of the present invention.
FIG. 6 to FIG. 6 are diagrams showing the flow of data in the present invention.

First, the 16-bit remainder (check bit) of the immediately preceding data string is divided into upper 8 bits and lower 8 bits (step S1). EX-OR processing (mod 2 addition) is performed on the upper 8 bits and the new 8-bit data to obtain a first processing result (step S2). The second processing result is obtained by shifting the first processing result to the right by one bit (step S3). EX-OR processing of the first processing result and the second processing result to obtain a third processing result (step S
4). The third processing result is shifted to the left by two bits to obtain a fourth processing result (step S5). EX-OR processing is performed on the third processing result and the fourth processing result to obtain a fifth processing result (step S6).

The fifth processing result is shifted to the left by 4 bits to obtain a sixth processing result (step S7). The fifth processing result and the sixth processing result are subjected to EX-OR processing to obtain a seventh processing result (step S8). The seventh processing result is shifted rightward by 6 bits to obtain an eighth processing result (step S9). The ninth processing result is obtained by performing the EX-OR processing on the eighth processing result and the fourth processing result (step S10).

The tenth processing result is obtained by shifting the seventh processing result leftward by one bit (step S11). An AND process is performed on the tenth processing result and the data "10000000" to obtain an eleventh processing result (step S12). The twelfth processing result is obtained by shifting the third processing result rightward by 6 bits (step S1).
3). EX-OR processing is performed on the eleventh processing result and the twelfth processing result to obtain a thirteenth processing result (step S14).

The thirteenth processing result and the 16
EX-OR processing is performed on the lower 8 bits of the bit remainder and the processing result is set as the upper 8 bits of the new 16-bit remainder (step S15). In addition, the ninth processing result is set as the lower 8 bits of the new 16-bit remainder, and a new remainder is obtained from each of these 8-bit data (Step S
16).

As described above, according to the CRC of the present invention, a new remainder for new data can be obtained only by a combination of a bit shift operation and a logical operation of EX-OR and AND. In the processing described above, 16
Although there is no such thing as a calculation formula in the bit CRC, the bit shift operation and the logical operation are performed based on the characteristics of the remainder of the 16-bit CRC shown in Table 1 and the characteristics of the residue calculation of the 16-bit CRC in steps 1 to 3. Obviously, a new remainder can be obtained in combination with the operation.

FIG. 7 is a block diagram showing the configuration of an embodiment of the recording medium of the present invention. The program exemplified here includes steps S1 to S16 shown in FIGS. 2 and 3, and is recorded on a recording medium described below.

In FIG. 7, a recording medium 11 that is connected online to the computer 10 is, for example, a WWW (World Wide Web) server computer that is installed separately from a place where the computer 10 is installed. The program 11a is recorded as follows. By controlling the computer 10 by the program 11a read from the recording medium 11, the computer 10 calculates the remainder in the 16-bit CRC.

The recording medium 12 provided inside the computer 10 uses a built-in hard disk drive or a ROM, for example, and the recording medium 12 stores the program 12a as described above. The program 12a read from the recording medium 12 controls the computer 10 so that the computer 10 calculates the remainder in the 16-bit CRC.

The recording medium 13 used by being loaded into the disk drive 10a provided in the computer 10 is a transportable medium such as a magneto-optical disk, a CD-ROM or a flexible disk. The program 13a is recorded as follows. By controlling the computer 10 by the program 13a read from the recording medium 13, the computer 10 calculates the remainder in the 16-bit CRC.

In the above example, a certain 8 bits (M =
The data to be inspected is formed by adding a 16-bit (N = 16) remainder to the data sequence 8) to the data of 8), but this is an example. In the case where a data error is checked based on the result of one remainder calculation, the values of M and N may be completely arbitrary numbers.
In the case where a data error is checked based on the result of a plurality of remainder calculations, any value of M and N that satisfies the condition of N = 2M may be used.

[0051]

As described above, according to the present invention, the remainder of a bit can be easily obtained only by performing a bit shift process and a logical operation, and both the conventional loop calculation and table storage can be performed. This is unnecessary, and the calculation load is smaller than in the past, and high-speed processing can be performed.

As described above, according to the present invention, the calculation load on the CRC can be reduced, so that the application of the CRC to a recording medium, such as a memory card or a flash memory, to which the CRC has not been applied due to a large calculation load, is promoted. It is possible to do.

[Brief description of the drawings]

FIG. 1 is a functional block diagram of an inspection device for inspecting a data error.

FIG. 2 is a flowchart showing the procedure of the inspection method of the present invention.

FIG. 3 is a flowchart showing the procedure of the inspection method of the present invention.

FIG. 4 is a diagram showing a data flow in the inspection method of the present invention.

FIG. 5 is a diagram showing a data flow in the inspection method of the present invention.

FIG. 6 is a diagram showing a data flow in the inspection method of the present invention.

FIG. 7 is a block diagram illustrating a configuration of an embodiment of a recording medium.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Inspection apparatus 4 Logical operation part 6 Shift register 7 CPU 10 Computer 11, 12, 13 Recording medium

Claims (7)

[Claims] 1. x indicating a certain M-bit data including an N-bit remainder with respect to an earlier data string
In a method for checking data errors based on CRC by sequentially calculating the remainder when the polynomial in (1) is divided by a predetermined remainder generating polynomial in x, wherein the remainder is obtained by a bit shift process and a logical operation. A data inspection method based on CRC. 2. N = 2M, and the N-bit remainder of the previous data sequence is divided into upper M-bit remainder data and lower M-bit remainder data, and the M-bit data and the upper M-bit 2. The CRC-based data inspection method according to claim 1, wherein the remainder is obtained by performing a bit shift process and a logical operation on the remainder data and the lower M-bit remainder data. 3. A step of EX-ORing the upper 8 bits of the surplus data and the 8 bits of data to obtain a first processing result, wherein M = 8, and shifting the first processing result to the right. Obtaining a second processing result by shifting by one bit, and EX-ORing the first processing result and the second processing result
Processing to obtain a third processing result, shifting the third processing result to the left by 2 bits to obtain a fourth processing result, and converting the third processing result and the fourth processing result to EX-
OR processing to obtain a fifth processing result;
Shifting the processing result to the left by 4 bits to obtain a sixth processing result; and converting the fifth processing result and the sixth processing result to E
X-OR processing to obtain a seventh processing result, shifting the seventh processing result to the right by 6 bits to obtain an eighth processing result, and calculating the eighth processing result and the fourth processing result. EX-OR processing to obtain a ninth processing result; shifting the seventh processing result by one bit to the left to obtain a tenth processing result;
000000 "to obtain an eleventh processing result; and shifting the third processing result to the right by 6 bits.
Obtaining the 12th processing result, the 11th processing result and the
EX-ORing the 12th processing result to obtain a 13th processing result; EX-ORing the 13th processing result and the lower 8-bit remainder data;
3. The CRC-based data inspection method according to claim 2, further comprising the steps of: setting upper 8 bits of a 16-bit remainder; and setting the ninth processing result to lower 8 bits of a new 16-bit remainder. 4. An x indicating a certain M-bit data including an N-bit remainder with respect to an earlier data string.
A device for checking data errors based on CRC by sequentially calculating the remainder when dividing the polynomial of a given x by a residue generation polynomial of x, comprising a shift register and a logical operation unit, A CRC-based data inspection device wherein the remainder is obtained by a shift process and a logical operation by the logical operation unit. 5. N = 2M, the N-bit remainder of the previous data string is divided into upper M-bit remainder data and lower M-bit remainder data, and the M-bit data and the upper M-bit 5. The CRC-based data inspection device according to claim 4, wherein the remainder is obtained by performing bit shift processing on the remainder data and the remainder data of the lower M bits by the shift register and a logical operation by the logical operation unit. 6. M = 8, wherein the shift register and the logical operation unit perform an EX-OR process on the upper 8 bits of the remainder data and the 8 bits of data to obtain a first processing result. A logical operation unit, a first shift register that shifts the first processing result right by one bit to obtain a second processing result, and performs an EX-OR operation on the first processing result and the second processing result.
A second logical operation unit for processing to obtain a third processing result; a second shift register for shifting the third processing result to the left by 2 bits to obtain a fourth processing result; A third logical operation unit that performs an EX-OR operation on the processing result to obtain a fifth processing result, a third shift register that shifts the fifth processing result to the left by 4 bits to obtain a sixth processing result, A fourth logical operation unit that performs an EX-OR operation on the fifth processing result and the sixth processing result to obtain a seventh processing result; and a fourth logical operation unit that shifts the seventh processing result rightward by 6 bits to obtain an eighth processing result. A fourth shift register, a fifth logical operation unit for performing an EX-OR operation on the eighth processing result and the fourth processing result to obtain a ninth processing result, and shifting the seventh processing result left by one bit. Tenth
A fifth shift register for obtaining a processing result, a sixth logical operator for performing an AND operation on the tenth processing result and data "10000000" to obtain an eleventh processing result, and
A sixth shift register for performing a bit shift to obtain a twelfth processing result, and EX-O
R processing to obtain a thirteenth processing result, a seventh logical operation unit, and EX processing the thirteenth processing result and the lower 8 bits of the remainder data
An eighth logical operation unit for performing an OR operation, wherein the processing result of the eighth logical operation unit is set as the upper 8 bits of the new 16-bit remainder, and the ninth processing result is set as the lower 8 bits of the new 16-bit residue. 6. A data inspection device based on a CRC according to claim 5, wherein the data inspection device is configured to use bits. 7. An x indicating a certain 8-bit data including a 16-bit remainder with respect to an earlier data string.
Is sequentially obtained by dividing the polynomial of the above by a predetermined remainder generating polynomial of x, and thereby a computer-readable recording medium storing a program for checking a data error based on a 16-bit CRC. A program code means for causing the computer to divide the 16-bit remainder with respect to the previous data string into upper 8 bits of remainder data and lower 8 bits of remainder data;
Program code means for causing the computer to EX-OR the upper 8 bits of the remainder data and the 8 bits of data to obtain a first processing result; and shift the first processing result to the right by one bit. Program code means for causing the computer to obtain a second processing result by using an EX-O
Program code means for causing the computer to perform R processing to obtain a third processing result; and program code means for causing the computer to shift the third processing result to the left by two bits to obtain a fourth processing result. Program code means for causing the computer to EX-OR the third processing result and the fourth processing result to obtain a fifth processing result; and shifting the fifth processing result to the left by 4 bits. Program code means for causing the computer to obtain a sixth processing result, and program code for causing the computer to perform an EX-OR operation on the fifth processing result and the sixth processing result to obtain a seventh processing result Means and program code means for causing the computer to shift the seventh processing result right by 6 bits to obtain an eighth processing result Program code means for causing the computer to EX-OR the eighth processing result and the fourth processing result to obtain a ninth processing result; and shifting the seventh processing result left by one bit. Program code means for causing the computer to obtain a tenth processing result; and storing the tenth processing result and data "10000000" in A
Program code means for causing the computer to perform ND processing to obtain an eleventh processing result; and program code means for causing the computer to shift the third processing result to the right by 6 bits to obtain a twelfth processing result. Program code means for causing the computer to perform an EX-OR operation on the eleventh processing result and the twelfth processing result to obtain a thirteenth processing result; and the thirteenth processing result and the lower 8-bit remainder data. And EX-OR processing of the above and program code means for causing the computer to make the processing result the upper 8 bits of a new 16-bit remainder;
A recording medium comprising program code means for causing the computer to make the ninth processing result the lower 8 bits of a new 16-bit remainder.