JP3239866B2 - Data inspection method and apparatus based on CRC and recording medium - Google Patents

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^Fifteen+ 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 a CRC, wherein M (M is an arbitrary integer)
Each of the (numerical) bits of data is defined as one inspection unit, and M bits of inspection data as a certain inspection unit are added to the preceding M data.
By sequentially calculating the remainder when dividing a polynomial of x indicating a sum of N bits (N is an arbitrary integer) bits with respect to a check unit of a bit by a predetermined remainder generation polynomial of x,
In a method for checking a data error based on a CRC, without using a known remainder obtained when a predetermined x polynomial is divided by the remainder generating polynomial, the previous M bits are used.
N bits of surplus data for the inspection unit of
The remainder is obtained by a bit shift process and a logical operation using the inspection data of the data .

The data checking method based on CRC according to claim 2, in claim 1, a N = 2M, the previous
The N-bit remainder for the M-bit inspection unit is divided into upper M-bit remainder data and lower M-bit remainder data, and the M-bit inspection data, the upper M-bit remainder data, and the lower M-bit The remainder is obtained by a bit shift process and a logic operation on the remainder data.

According to a third aspect of the present invention, there is provided a data inspection method based on CRC according to the second aspect, wherein M = 8, and the upper 8 bits of the remainder data and the 8 bits of the inspection data are subjected to an EX-OR process. Obtaining a first processing result;
Shifting the first processing result to the right by one bit to obtain a second processing result; EX-ORing the first processing result and the second processing result 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; The fifth processing result is shifted to the left by 4 bits to obtain a sixth processing result.
Obtaining a processing result; the fifth processing result and the sixth processing result;
EX-ORing the processing result to obtain a seventh processing result; shifting the seventh processing result to the right by 6 bits to obtain an eighth processing result; 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 the ninth processing result Characterized by a step of the lower 8 bits of the new 16-bit remainder.

According to a fourth aspect of the present invention, there is provided a data inspection apparatus based on CRC, in which each successive M-bit (M is an arbitrary integer) data is regarded as one inspection unit, and M-bit inspection data as a certain inspection unit is used as one inspection unit. The CRC is obtained by sequentially calculating the remainder when an x polynomial, which is obtained by adding an N (N is an arbitrary integer) bit remainder to the preceding M-bit inspection unit, by a predetermined x remainder generation polynomial, An apparatus for checking a data error based on a data unit includes a shift register and a logical operation unit, and checks for a previous M-bit check unit.
N-bit remainder data and M-bit inspection data
By using a bit shift process by the shift register and a logical operation by the logical operation unit using a data, a memory for storing a known remainder when a predetermined x polynomial is divided by the remainder generation polynomial can be used. , The remainder is obtained.

The data checking apparatus based on the CRC according to claim 5, in claim 4, a N = 2M, the previous
The N-bit remainder for the M-bit inspection unit is divided into upper M-bit remainder data and lower M-bit remainder data, and the M-bit inspection data, the upper M-bit remainder data, and the lower M-bit The remainder is obtained by a bit shift process on the remainder data by the shift register and a logical operation by the logical operation unit.

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, the shift register and the logical operation unit inspect the upper 8 bits of surplus data and the 8 bits. A first logical operation unit for performing an EX-OR operation on the data 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 that performs an EX-OR operation on the processing result and the second processing result to obtain a third processing result; and a second logical operation unit that shifts the third processing result to the left by 2 bits to obtain a fourth processing result. A shift register; a third logical operation unit for performing an EX-OR operation on the third processing result and the fourth processing result to obtain a fifth processing result; (6) a third shift register for obtaining a processing result; Processing results and a sixth processing result EX
A fourth logical operation unit for performing an OR operation 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, A fifth logical operator that performs an EX-OR operation on the fourth processing result to obtain a ninth processing result, a fifth shift register that shifts the seventh processing result left by one bit 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 second logical operator. The physical result is the upper 8 bits of the new 16-bit remainder, the ninth processing result a new
It is characterized in that the lower 8 bits of the 16-bit remainder are used.

According to a seventh aspect of the present invention, the recording medium has eight continuous
Each set of data is considered as one inspection unit and a certain inspection unit.
8 bits before this for all 8 bits of inspection data
To check the data error based on the 16-bit CRC by sequentially obtaining the remainder when the polynomial of x indicating the addition of the 16-bit remainder to the check unit is divided by the predetermined remainder generation polynomial of x In a computer-readable recording medium that has recorded the program of
Program code means for causing the computer to divide the 16-bit remainder with respect to the immediately preceding 8-bit test unit into upper 8 bits of remainder data and lower 8 bits of remainder data; and the upper 8 bits of remainder data. Program code means for causing the computer to obtain the first processing result by performing an EX-OR operation on the data and the 8-bit data, and shift the first processing result right by one bit to obtain a second processing result Program code means for causing the computer to: EX-OR the first processing result and the second processing result to obtain a third processing result; and Program code means for causing the computer to shift the processing result to the left by 2 bits to obtain a fourth processing result; Program code means for causing the computer to perform an EX-OR operation on the third processing result and the fourth processing result to obtain a fifth processing result; and shift the fourth processing result to the left by 4 bits to perform a sixth processing. Program code means for causing the computer to obtain a result, and EX-ORing the fifth processing result and the sixth processing result with each other.
Program code means for causing the computer to process and 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 processing result and the fourth processing result are subjected to an EX-OR processing to obtain a ninth processing result.
Program code means for causing the computer to obtain a processing result, program code means for causing the computer to shift the seventh processing result left by one bit to obtain a tenth processing result, and the tenth processing result Program code means for causing the computer to AND-process the data and "10000000" to obtain an eleventh processing result; and
(12) program code means for causing the computer to obtain a processing result, and program code means for causing the computer to perform an EX-OR process on the eleventh processing result and the twelfth processing result to obtain a thirteenth processing result And the 13th processing result and the lower 8 bits of the remainder data
Program code means for causing the computer to perform an OR operation and to set the processing result to the upper 8 bits of a new 16-bit remainder; and to set the ninth processing result to the lower 8 bits of a new 16-bit remainder. Program code means for causing the computer to operate.

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 ^Fifteen+ 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)
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). The ninth processing result is the lower 8 bits of the new 16-bit remainder, and the data of each of these 8 bits is the processing result in step S15.
8 bits are set as upper bits, and the ninth processing result of 8 bits
Then, a new 16-bit remainder with the lower bit as the lower bit is obtained (step S16).

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)

(57) [Claims] 1. Each data of consecutive M bits (M is an arbitrary integer) is defined as one inspection unit, and M
When a polynomial in x indicating a result of adding N bits (where N is an arbitrary integer) bits to a check unit of M bits immediately before this to the check data of 1 bit is divided by a predetermined remainder generation polynomial of x In a method of checking a data error based on a CRC by sequentially calculating the remainder, without using a known remainder obtained when a predetermined x polynomial is divided by the remainder generation polynomial, the previous M bits are used. Inspection units
N bits of surplus data and the M bits of inspection data
A data inspection method based on CRC, characterized in that the remainder is obtained by a bit shift process and a logical operation using 2. The method according to claim 2, wherein N = 2M, and the N-bit remainder for the immediately preceding M-bit inspection unit is divided into upper M-bit remainder data and lower M-bit remainder data, and the M-bit inspection is performed. 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 data, the upper M-bit remainder data, and the lower M-bit remainder data. 3. A step of EX-ORing the upper 8 bits of surplus data and the 8 bits of test data to obtain a first processing result, wherein M = 8, Obtaining a second processing result by shifting by one bit to EX-O
R processing to obtain a third processing result; shifting the third processing result to the left by 2 bits to obtain a fourth processing result; EX processing the third processing result and the fourth processing result
-OR processing to obtain a fifth processing result; shifting the fifth processing result to the left by 4 bits to obtain a sixth processing result; and exchanging the fifth processing result and the sixth processing result with EX -Performing an OR operation to obtain a seventh processing result;
Shifting the seventh processing result to the right by 6 bits to obtain an eighth processing result; EX-ORing the eighth processing result and the fourth processing result to obtain a ninth processing result; Shifting the seventh processing result left by one bit to obtain a tenth processing result;
000000 "to obtain an eleventh processing result, and shifting the third processing result rightward by 6 bits.
Obtaining a 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. Each successive M (M is an arbitrary integer) bit data is defined as one inspection unit, and M
When a polynomial in x indicating a result of adding N bits (where N is an arbitrary integer) bits to a check unit of M bits immediately before this to the check data of 1 bit is divided by a predetermined remainder generation polynomial of x An apparatus for checking a data error based on a CRC by sequentially obtaining a remainder is provided with a shift register and a logical operation unit, and a check unit of the previous M bits is used.
The N bits of surplus data for the
Using a memory for storing a known remainder when a predetermined x polynomial is divided by the remainder generating polynomial by a bit shift process by the shift register using the check data and a logical operation by the logical operation unit. A data inspection device based on CRC, wherein the remainder is obtained. 5. The method according to claim 5, wherein N = 2M, the N-bit remainder for the immediately preceding M-bit inspection unit is divided into upper M-bit remainder data and lower M-bit remainder data, and the M-bit inspection is performed. 5. The CRC according to claim 4, wherein the remainder is obtained by performing a bit shift process on the data, the upper M-bit remainder data and the lower M-bit remainder data by the shift register and a logical operation by the logical operation unit. Data inspection device. 6. When M = 8, the shift register and the logical operation unit perform an EX-OR process on the upper 8 bits of the surplus data and the 8 bits of the check data to obtain a first processing result. 1 logical operation unit, a first shift register that shifts the first processing result right by one bit to obtain a second processing result, and outputs the first processing result and the second processing result as EX-
A second logical operator for performing an OR operation to obtain a third processing result;
A second shift register that shifts the third processing result to the left by two bits to obtain a fourth processing result, and performs an EX-OR operation on the third processing result and the fourth processing result to obtain a fifth processing result A third logical operation unit, a third shift register for shifting the fifth processing result to the left by 4 bits to obtain a sixth processing result, and performing an EX-OR operation on the fifth processing result and the sixth processing result A fourth logical operation unit for obtaining a seventh processing result, and a fourth logical operation unit for shifting the seventh processing result to the right by 6 bits to obtain an eighth processing result.
A shift register; a fifth logical operator that performs an EX-OR operation on the eighth processing result and the fourth processing result to obtain a ninth processing result; A fifth shift register for obtaining a tenth 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 converting the third processing result to the right by 6 bits A sixth shift register that shifts to obtain a twelfth processing result, and outputs the eleventh processing result and the twelfth processing result by EX.
A seventh logical operator for performing an OR operation to obtain a thirteenth processing result, and an eighth logical operator for performing an EX-OR operation on the thirteenth processing result and the lower 8-bit remainder data. 8
6. The CR according to claim 5, wherein the processing result in the logical operation unit is the upper 8 bits of the new 16-bit remainder, and the ninth processing result is the lower 8 bits of the new 16-bit remainder.
Data inspection device based on C. 7. Each piece of continuous 8-bit data is defined as one inspection unit, and the 8-bit inspection data as a certain inspection unit is obtained by adding a 16-bit remainder to the immediately preceding 8-bit inspection unit. By sequentially calculating the remainder when the polynomial of x shown is divided by a predetermined remainder generating polynomial of x, a computer capable of reading a program for checking data errors based on a 16-bit CRC can be read by a computer. Program code means for causing the computer to divide the 16-bit remainder with respect to the immediately preceding 8-bit inspection unit into upper 8-bit remainder data and lower 8-bit remainder data on the recording medium; A program that causes the computer to perform an EX-OR operation on the 8-bit remainder data and the 8-bit data to obtain a first processing result. Gram code means, program code means for causing the computer to shift the first processing result to the right by one bit to obtain a second processing result, and EX-convert the first processing result and the second processing result. OR
Program code means for causing the computer to process and obtain a third processing result; 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; The third
EX-OR processing the processing result and the fourth processing result to obtain a fifth processing result
Program code means for causing the computer to obtain a 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 the fifth processing result Program code means for causing the computer to EX-OR-process the sixth processing result with the sixth processing result to obtain a seventh processing result;
Program code means for causing the computer to obtain a processing result, and program code means for causing the computer to perform an EX-OR operation on the eighth processing result and the fourth processing result to obtain a ninth processing result; Program code means for causing the computer to shift the seventh processing result left by one bit to obtain a tenth processing result, and to perform an AND operation on the tenth processing result and data "10000000"
Program code means for causing the computer to perform D 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
EX-OR processing with the bit remainder data, and program code means for causing the computer to set the processing result to the upper 8 bits of the new 16-bit remainder, and converting the ninth processing result to a new 16-bit remainder And a program code means for causing the computer to set the lower 8 bits.