JPH10290167A - Method and circuit for detecting error - Google Patents

Abstract

PROBLEM TO BE SOLVED: To attain the speed-up and price-down of system requiring an error correct code by performing cyclic redundant code operation for each parallel data unit while defining parallel data for the prescribed bit length of data row or parallel data for a prescribed bit length, which is provided by dividing a certain polynomial of bit string, as a bit string polynomial. SOLUTION: A parallel adder circuit 1 adds an input bit stream polynomial Ix and a preceding provided generation polynomial Gx and outputs the result to a parallel register 2. The parallel register 2 outputs respective coefficients Kx for each dimension. At a coefficient adder circuit 3, these plural coefficients Kx are inputted to an m-bit parallel register 4 as an m-th order generation polynomial Gx. At the m-bit parallel register 4, this (m)-bit coefficient is formed as a remainder polynomial Rx. Besides, the generation polynomial Gx is inputted to the parallel adder circuit 1.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to the calculation of an error correction code in data transfer, and more particularly, to an error detecting a transfer data error by performing a parallel operation on parallel data transferred in data units of a predetermined bit length. It relates to a detection method.

[0002]

2. Description of the Related Art In digital data communication, data may be corrupted between transmission lines until transmitted data is received due to external factors such as noise. But,
On the receiving side, it is indistinguishable whether the received data is normal data or corrupted data. Therefore, a method is used in which a code bit called an error correction code is added to data to be transmitted on a transmission side, and correct data is distinguished from received data by a correction code bit. Cyclic redundancy code calculation (CRC) is an example of this, and is a method of adding a plurality of redundant bits to an information bit string of a transmission block. This cyclic redundancy code operation is used for error detection of data communication between computers and the like.
Decoding is mainly performed by software processing.
In software processing, real-time processing cannot be performed and processing takes time. However, since such data communication is often performed by serial data, conventional techniques can sufficiently cope with such data communication. When the format of data communication is standardized, there is a hardware LSI for performing a cyclic redundancy code operation, but there is no general versatility.

It has been described above that a code bit is added and transferred to detect a data error. This concept is explained mathematically with simple numerical examples. First, let the data packet to be transmitted, that is, the bit string polynomial be “11”,
A key for extracting a sign bit, that is, data serving as a generator polynomial is set to “3”. Retrieving the sign bit is dividing the data packet by the key and retrieving the remainder to be a divisible number. In this case, if "1" is added to the data packet "11", it becomes "12" which is exactly divisible by "3". The code bit for the data packet “11” at this time is “1”. The data to be transferred, that is, the encoding polynomial is "1
1 + 1 ". Since the receiving side knows the data "3" which is the generating polynomial which is the data to be divided, it divides the received data (coding polynomial) by "3" of the generating polynomial.
At this time, an error in the received data is detected depending on whether the answer that is obtained is divisible or not.
In this way, the transmitting side and the receiving side determine a polynomial in advance, and if the receiving side divides the received data by the above polynomial, the code bit can be calculated or the presence or absence of an error can be detected. The method of detecting data errors is very simple.

Next, an example of a conventionally known error correction code will be described. As shown in FIG. 4, the conventional error correcting code has a hardware configuration based on a generator polynomial,
.., 10m and m shift registers 200, 201,..., 20m formed by an exclusive OR circuit using the mod2 method, and the adder 100, the shift register 200, and the adder ., A shift register 201,..., An adder 10m, and a shift register 20m in this order. The bit string data represented by the polynomial F (x) is substituted into this circuit. The polynomial F (x) input from the left terminal is m
It is divided by the next generator polynomial G (x), and the quotient is output from the right end. The operation is completed when the last bit of F (x) is input. At this time, the m bits remaining in the shift registers 200, 201,..., 20m in the circuit represent an m-1 order remainder polynomial, and the m bits are used as sign bits. Whether the data is correct or not can be determined by the polynomial. Here, the bit string data refers to continuous data in which the data itself is serial data, that is, the input data is “1” or “0”.

[0005]

The above prior art is a method for calculating a cyclic redundancy code (CRC). In the CRC calculation, a polynomial of a bit string is calculated (divided) by a generator polynomial, a remainder at that time is obtained, and the remainder is used as a correction code.
With this correction code, the receiving side determines whether or not the received data has an error. In the case of the bit string data as described above, a correction code appears in each shift register when the last bit is input. In this case, there is no problem because the result is obtained immediately. However, the conventional CRC operation is
This can deal with the case where the bit string data is serial data, and cannot deal with the case where the bit string data is, for example, 16-bit parallel data. On the data receiving side, there are systems that require real-time processing in which parallel data must be determined on the spot, and such systems cannot handle conventional CRC calculations.

More specifically, for example, the frequency of data input in parallel is 40 MHz and the cycle is 25.
In the case of ns, if this is processed by the conventional circuit shown in FIG.
32 ns + α even if processing is performed using a shift register of s
It takes time. That is, 16-bit data must be converted into serial data and processed at an extremely high frequency of 640 MHz in an unrealistic time. Therefore, if the decoding is performed by software, the decoding cannot be performed in real time, and there is a disadvantage that the processing requires a lot of time. On the other hand, even if such a processing circuit is made, the proportion of the processing circuit in the entire apparatus becomes high, the usage becomes delicate due to problems such as processing speed and heat generation, and it goes against the demand for miniaturization.

Although an LSI dedicated to CRC calculation may be used, the LSI is specialized due to the difference between generator polynomials and has no versatility.
Developing I also has the disadvantage of being expensive.

Assuming that parallel processing of parallel data having a predetermined bit length can be performed in a data sequence, 16-bit parallel data can be processed at once at a frequency of 40 MHz and at intervals of 25 ns. Such a problem of the serial operation processing can be solved. SUMMARY OF THE INVENTION The present invention has been made in view of the above circumstances, and performs parallel arithmetic processing on parallel data having a predetermined bit length in a data string, thereby increasing the speed of a system requiring an error correction code and reducing the cost of hardware. It is an object of the present invention to provide an error detection method and an error detection circuit that can achieve the above.

[0009]

According to a first aspect of the present invention, there is provided an error detection method, wherein a data string is parallel data having a predetermined bit length;
Alternatively, it is characterized in that the presence or absence of data error is detected by performing a cyclic redundancy code operation for each parallel data unit on parallel data of a predetermined bit length obtained by dividing a polynomial having a bit string as a bit string polynomial.

According to a second aspect of the present invention, in the operation for each parallel data unit in the error detection method according to the first aspect, when the parallel data length is n bits, the operation is performed in real time using n coefficients. It is characterized by.

According to a third aspect of the present invention, in the error detection method of the second aspect, when there is a difference between the length of the m-th order parallel data and the length of the generator polynomial, the remaining processing after the operation is performed by m It is characterized in that the calculation is performed by calculating the -1st-order parallel data in real time.

According to a fourth aspect of the present invention, an error detection circuit obtains an m-th order generating polynomial by adding an n-bit parallel register that receives a bit string polynomial composed of parallel data and an m-bit output from the parallel register in parallel. A coefficient adding circuit, and m output from the coefficient adding circuit.
An m-bit parallel register that forms the next generator polynomial as a remainder polynomial; and a parallel addition circuit that adds the generator polynomial fed back from the coefficient addition circuit to the bit string polynomial and inputs the result to the parallel register. .

According to a fifth aspect of the present invention, in the fourth aspect, the n-bit parallel register, the m-bit parallel register, the parallel addition circuit, and the coefficient addition circuit are composed of a programmable logic device. And

[0014]

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram showing an embodiment of an error detecting method and an error detecting circuit according to the present invention; In FIG. 1, reference numeral 1 denotes a parallel addition circuit based on a mod2 method comprising an exclusive OR circuit. Here, a bit string polynomial I comprising n-bit parallel data input from an input terminal at the left end through an n-bit bus line is shown. In order to accept (xa), it is composed of n adders arranged in parallel. The bit string polynomial I (xa) may be parallel data of a predetermined bit length obtained by dividing a certain polynomial in the bit string. The output of the parallel addition circuit 1 is input to an n-bit parallel register 2 via an n-bit bus line. Parallel register 2
Is the input polynomial I (x) and each order, ie, n
Next, n−1 order,..., First order given coefficients kn, kn
-1,... K1 and AND, and coefficient K for each order
(X) is taken out. The output of the parallel register 2 is m coefficient adding circuits 3 arranged in parallel.
Is input to The coefficient adding circuit 3 is an adding circuit based on a mod2 method comprising an exclusive OR circuit, and its output is represented as an m-th order generating polynomial G (x). The m-bit generator polynomial G (x) output from the coefficient adder 3 is
The data is input to the m-bit parallel register 4 as a remainder polynomial, and is fed back to the parallel addition circuit 1.

Next, the operation of the circuit shown in FIG. 1 will be described.
In FIG. 1, a bit string polynomial I input from the left end
(Xa) is n-bit parallel data, and is a data array arranged in order from the higher order to the lower order. In the case of the parallel operation, the generator polynomial G (x) is difficult to discriminate on a circuit, but exists as n m-bit coefficients corresponding to n-bit data. The m-bit coefficient is formed in the parallel register 4 as m-bit parallel data of the remainder polynomial R (x). Here, since only the remainder is obtained, no quotient is output. Input polynomial I (x)
Are n-th order, n−
..,...,...,.
.. And k1 are ANDed, and coefficients are extracted for each order. The plurality of coefficients K (x) are added in the coefficient adding circuit 3 by the mod2 method, and are represented as an m-th order generating polynomial G (x). Further, in the parallel addition circuit 1,
For the input of n-bit parallel data on the lower order side of the input data I (x), the generator polynomial G obtained immediately before
They are added in parallel by the addition of (x) and the mod2 method. Then, it is inputted to the coefficient adding circuit 3 and the next lower order n
Find the generator polynomial up to bits. The m-th generation polynomial G (x) obtained by the coefficient adding circuit 3 is input to an m-bit parallel register 4, and the m-bit coefficient is formed as a remainder polynomial R (x). Such an operation is repeated until the last n-bit data is input. The above “a” represents the length of the entire bit string.

The n-bit parallel register 2 has a coefficient K (n) (x) = km + km for each order K (x).
+1+... + K1 + 1, and the respective m-th addition results are generated polynomials Gx (gm + gm-1 +... G1
+1) and the remainder polynomial Rx (rm + rm-1 +... R1 +
1). Based on the remainder polynomial R (x), the correctness of data can be determined in the same manner as in the conventional example. As described above, according to the embodiment shown in FIG. 2, the number of adders is n + m, and more adders are required than in the related art. However, since a parallel operation is performed, many operations are performed at once. be able to. The embodiment shown in FIG.
The bit length n of (x) and the bit length m of the generator polynomial G (x)
Are the same.

Next, the coefficient addition will be described. For an n-bit parallel polynomial, the remainder cannot be calculated in real time. Therefore, input data is processed in real time by using coefficients. The following equation (2-1) is a representative code polynomial. I
When (x) is x ⁴ + x ³ + x ² +1 and G (x) is x ² +1, f (x) = x ² I (x) + r (x) = Q (x) G (x) (2 -1) = x ² and becomes ^{(x 4 + x 3 + x} 2 +1) + r (x) = x 6 + x 5 + x 4 + x 2 + x + 1 (2-2). Here, Q (x) is a quotient when the transmission data f (x) is divided by the generator polynomial G (x), and r (x) is a remainder.

Furthermore, for the purpose, I (4x) as x ^4, I (3x) as x ^3, I (2x) as x ² +1
Is as follows. ^{f (4x) = x 2 (} x 4) + r (x) = x 6 +1 f (3x) = x 2 (x 3) + r (x) = x 5 + x f (2x) = x 2 (x 2 +1) + R (x) = x ⁴ + x ² f (x) is given by the following equation (2-3), assuming that f (4x), f (3x) and f (2x) are added. f (x) = f (4x) + f (3x) + f (2x) (2-3) Further, the quotient and remainder at the time of f (4x), f (3x) and f (2x) are represented by q (4x ), Q (3x), q (2
x (x), r (4x), r (3x), r (2x), f (x) = G (x) q (4x) + G (x) q (3x) + G (x) q (2x) ^{= x 2 I (4x) +} r (4x) + x 2 I (3x) + r (3x) + x 2 I (2x) + r (2x) = x 6 + 1 + x 5 + x + x 4 + x 2 = x 6 + x 5 + x 4 + x 2 + x + 1 Which is equal to the expression (2-2).

That is, it can be seen that the same result as the result obtained by dividing the n-bit parallel polynomial can be obtained by calculating the result obtained in each order by the addition method of mod2 for both the quotient and the remainder. This is represented by the following equation (2-4):
(2-5). r (x) = r (n ) + r (n-1) + ...... + r (1) + r (0) (2-4) r (n) = c m x m + c m-1 x m-1 + ... ... + x + 1 (2-5) The above r (x) is the result of operation of the remainder polynomial obtained in each order. The above r (n) represents an m-1 order remainder polynomial obtained by the generator polynomial. The m-1 order remainder polynomial is treated as a coefficient for performing a parallel operation. The coefficient changes depending on the generator polynomial, but does not always change, so that each n-order coefficient can be obtained in advance. In this way, n-bit parallel data can be calculated in real time.

The above description is based on the condition that the n-bit bit string, which is input data, and the m-bit length generating polynomial have the same length. However, since the mth-order remainder polynomial is actually longer than the n-bit long bit string,
It is necessary to devise what to do with the remainder of the n bits.
The solution to this problem is the embodiment shown in FIG. 3, and the remainder calculation flow is shown in FIG. As shown in FIG. 2, since the first bit string polynomial Ia does not have the remainder polynomial G (x) fed back, the n-bit data is directly calculated and becomes the remainder polynomial Ga (m).

When the data of the bit sequence I (a-1) which is the next order is input, the remainder polynomial Ga obtained first is obtained.
(M) and n bits of a higher order and the bit string I (a-
1) is calculated by the mod2 addition method, and is taken out as I (a-1) ′. However, since mn bits of information remain as data of the remainder polynomial Ga (m),
Further, it must be calculated with the order I (a-2) of the bit string which is the next order. For this purpose, the next data is delayed and the next data is waited. However, the remainder data Ga-1 (m) obtained second, the mn-bit data of Ga (m), and the order I ( The three data of a-2) must be calculated, which is troublesome. However, as can be seen from FIG. 2, since the order of the head of the remaining mn bits and the order of the head of the residue Ga-1 (m) obtained second are the same, the above-mentioned residue arithmetic theory , The remainder of the remaining mn bits and the operation of the second obtained m bits can be performed.
Thereafter, the same operation is repeated.

FIG. 3 shows an example of a circuit for performing such an operation. The circuit shown in FIG. 3 is different from the circuit shown in FIG. 1 in that when the generator polynomial formed by the coefficient adder 3 is fed back to the parallel adder 1, the remaining polynomial of the m-bit parallel register 4 is added to the generator polynomial. The point is that an addition circuit 5 is added to add and feed back a −n-bit remainder Gx (mn). This addition circuit 5 is also an addition circuit based on the mod2 method, and has an m-bit configuration.

The conventional example shown in FIG. 4 is an error correction of a cyclic redundancy code type of a bit string. On the other hand, in the embodiment of the present invention shown in FIGS. 1 to 3, error correction is performed using a parallel cyclic redundancy code. Therefore, when the frequency of the input data is the same or when the input data is operated at the same frequency, the parallel type as in the present invention can handle a larger amount of data, so that it can be processed in real time. .

As described above, the object of the present invention can be achieved by the existence of an element called a programmable logic device (PLD) which allows a user to freely program a logic circuit. There is. The PLD is an LSI element in which various logic circuits are incorporated. A logic control program is assembled with the support of a computer, and a circuit having an intended function can be freely designed. . It is believed that it is not impossible to configure the circuit using, for example, an application specific integrated circuit (ASIC) to achieve the objects of the present invention. However, the ASIC must be developed in cooperation with the ASIC manufacturer and the user, and has a drawback that it requires many development periods and development costs.
In this regard, the PLD allows a user to easily and inexpensively assemble any logic circuit that matches the system, and by using this in the present invention, an error detection circuit that can achieve the intended purpose. Can be obtained easily and inexpensively.

[0025]

According to the error detecting method of the first aspect,
The data string is subjected to a cyclic redundancy code operation for each parallel data unit as parallel data having a predetermined bit length or parallel data having a predetermined bit length obtained by dividing a polynomial having a bit string as a bit string polynomial. Since the presence / absence is detected, parallel data of a predetermined bit length can be calculated in real time, and the presence / absence of an error in the data string can be detected by this calculation.

According to the second aspect of the present invention, in the error detection method according to the first aspect, in the calculation for each parallel data unit, when the parallel data length is n bits, n coefficients are used in real time. Since calculation is performed, real-time calculation of n-bit parallel data can be effectively performed.

According to the third aspect of the present invention, in the error detection method according to the second aspect, if there is a difference between the length of the m-th parallel data and the length of the generator polynomial, the remaining processing after the operation is performed. , M-1 order parallel data in real time, so that even if there is a difference between the length of the parallel data and the length of the generator polynomial, an error is obtained by repeating the remaining processing. The presence or absence can be detected.

According to the present invention, an n-bit parallel register that accepts a bit string polynomial composed of parallel data and an m-bit output from the parallel register are added in parallel to obtain an m-th order generator polynomial. A coefficient adding circuit, an m-bit parallel register that forms an m-th order generating polynomial output from the coefficient adding circuit as a remainder polynomial, and a generator polynomial fed back from the coefficient adding circuit is added to the bit string polynomial. By providing a parallel addition circuit for inputting data to a parallel register, it is possible to calculate parallel data of a predetermined bit length in real time, and to use this calculation to detect the presence or absence of a data string data error. A detection circuit can be obtained.

According to the fifth aspect of the present invention, in the fourth aspect of the present invention, the n-bit parallel register, the m-bit parallel register, the parallel addition circuit, and the coefficient addition circuit are constituted by programmable logic devices. And an error detection circuit can be obtained simply and inexpensively.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an embodiment of an error detection method and an error detection circuit according to the present invention.

FIG. 2 is a flowchart showing an operation of another embodiment of the error detection method and the error detection circuit according to the present invention.

FIG. 3 is a block diagram showing another embodiment of the error detection method and the error detection circuit according to the present invention.

FIG. 4 is a block diagram showing an example of a conventional error detection method and an error detection circuit.

[Explanation of symbols]

 Reference Signs List 1 parallel addition circuit 2 n-bit parallel register 3 coefficient addition circuit 4 m-bit parallel register

Claims (5)

[Claims] 1. A cyclic redundancy code operation is performed for each parallel data unit as parallel data having a predetermined bit length as a data sequence or parallel data having a predetermined bit length obtained by dividing a polynomial having a bit sequence as a bit sequence polynomial. An error detection method that detects the presence or absence of a data error by using. 2. The error detection method according to claim 1, wherein, in the operation for each parallel data unit, when the parallel data length is n bits, the error detection method is performed in real time using n coefficients. 3. When there is a difference between the length of the m-th parallel data and the length of the generator polynomial, the remaining processing after the operation is
3. The error detection method according to claim 2, wherein the error detection is performed by calculating m-1 order parallel data in real time. 4. An n-bit parallel register that accepts a bit string polynomial composed of parallel data, a coefficient addition circuit that adds an m-bit output from the parallel register in parallel to obtain an m-th order generator polynomial, An m-bit parallel register that forms an m-th generation polynomial output from the circuit as a remainder polynomial; and a parallel addition circuit that adds the generation polynomial fed back from the coefficient addition circuit to the bit string polynomial and inputs the result to the parallel register. An error detection circuit comprising: 5. The error detection circuit according to claim 4, wherein the n-bit parallel register, the m-bit parallel register, the parallel addition circuit, and the coefficient addition circuit are composed of a programmable logic device.