Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-06-15
2002-04-09
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S781000
Reexamination Certificate
active
06370667
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a code error detecting apparatus for detecting the occurrence or non-occurrence of a code error by performing the communication or data processing of the digital data. More specifically, the present invention relates to a CRC operational calculating method and a CRC operational calculation circuit for generating a CRC (Cyclic Redundancy Check) to perform error detection and correction for received data in a digital communication system.
2. Discussion of the Background Art
In a CRC calculating method and CRC calculation circuit, LSI is typically utilized. The method and circuit have an operational calculating function for calculating a cyclic redundancy check code for detecting the occurrence or non-occurrence of a code error by performing the communication or data processing of the digital data.
High-speed performance of CRC calculation in connection with error detection has been strictly (strongly) required in accordance with the high-speed performance requirements of data communication.
One such background-art CRC calculation circuit aimed at responding to the requirement of high-speed CRC calculation, for instance, is disclosed in the published specification of Japanese Laid-open Patent Publication No. 6-37,737/1994. Hereinafter, the technology relating to the calculation circuit described in this publication will be referred to as “the first background-art technology”.
FIG. 3
is a circuit diagram for explaining the CRC calculation circuit of the first background-art technology.
The first background-art CRC calculation circuit includes: n-stage storing circuits
11
connected to each other through the respective corresponding first through (n−1)-th exclusive logical sum circuits
14
and for storing the result of the CRC calculation by the n-order creating multinomial equation. A recurrence symbol selecting circuit
12
selects one of the recurrence code signals from among the first through n-th storing circuit outputs of the n-th hereby certify that this paper is being deposited this date with the storing circuits
11
in accordance with the first through n-th coefficient input signal of the CRC creating multinomial equation. An n-th exclusive logical sum circuit
14
performs an exclusive logical sum of the input binary signal and the recurrence code signal output both for calculating the CRC, and for inputting the output signal thereof to the first storing circuit
11
of the n-stage storing circuits. The first through (n−1)-th logical sum circuits
15
respectively take the logical sum of the output signal of the n-th exclusive logical sum circuit and the first through (n−1)-th coefficient input signals, and respectively input the output signals thereof to the corresponding first through (n−1)-th exclusive logical sum circuits.
In the CRC calculation circuit of such structure, by enabling the coefficient of the CRC creating multinomial equation to be optionally set, when changing-over of the CRC creating multinomial equation is required, it is not necessary to prepare the CRC calculation circuits corresponding to the number (sort) of the required CRC creating multinomial equations.
Furthermore, it is described in the background-art document that only one CRC calculating circuit is sufficient and therefore the size of the circuit can be made small. In addition, even when the coefficient of the required CRC creating multinomial equation has to be changed, it is sufficient to only change the setting thereof. Therefore, it is possible to easily change the setting of the coefficient.
Another type of background-art CRC calculation circuit, for instance, is described in the published specification of Japanese Laid-open Patent Publication No. 9-69,836/1997. Hereinafter, the technology concerning the type of calculation circuit described in this publication is referred to as “the second background-art technology”.
FIG. 4
is a circuit diagram for explaining the CRC calculation circuit of the second background-art technology.
In
FIG. 4
, the second background-art CRC calculation circuit performs division of the information data input in parallel with the previously determined paralleling rate by use of a predetermined CRC creating multinomial equation. By obtaining the surplus (residue) of the division, the CRC code can be created as the error detecting (cyclic) redundancy code for the information data.
The surplus can be obtained by dividing the number of bits of the information data by the paralleling rate. The information data attached with “O” of the same number as that of the value obtained by subtracting the surplus from the parallel rate is multiplied by the monomial equation including the order number of the value obtained as the result of performing the modulo calculation with the period of the CRC creating multinomial equation in connection with the value obtained by subtracting the number of “O” attached to the information data from the number of bits of the CRC code. Thereafter the division is performed by use of the CRC creating multinomial equation, by use of an operational calculation medium. The CRC code generating circuit includes the operational calculation medium for performing such division and the outputting medium for outputting the surplus obtained by the division performed by the above-mentioned operational calculation medium as the CRC code for the information data.
The above background-art document (second background art) describes that, in such structure of the CRC calculation circuit, even though the bit number of the information data can be indivisible (cannot be divided) by the paralleling rate of the CRC calculation, the CRC code creating circuit can be effectively realized.
The document further describes that the paralleling rate of the information input to the calculation circuit need not be changed and nevertheless it is possible to form the structure the same as that of the background-art CRC creating method with very small time delay, and the CRC code can be created without increasing the scale of the circuit (size, number of parts, etc.) and with the time delay as small as possible compared with the background-art circuit structure in which the number of bits of the information data is a multiple of the paralleling rate.
Another type of CRC calculation circuit, for instance, is described in the published specification of Japanese Laid-open Patent Publication No. 6-224,783/1994. The technology concerning this type of circuit is called hereinafter “the third background-art technology”.
FIG. 5
is a circuit diagram for explaining the CRC calculation circuit of the third background-art technology.
In
FIG. 5
, a CRC calculation circuit performs a cyclic coding process and a cyclic redundant code check (CRC) process both for data of a number predetermined by the m-order creating multinomial equation G(X) (m is an integer satisfying m≦n/2) by use of a computer provided with a n-bit commonly used register. The CRC calculation circuit according to the third background-art technology is composed of CPU
100
a
, a table ROM
200
, a data memory
300
and a bus
400
. Table ROM
200
stores a surplus table for storing
2
n
surplus tables created by surplus data obtained by dividing the respective
2
n
data by the CRC creating multinomial equation. A reference address creating medium generates a reference address of the surplus table. A surplus table reading-out medium reads out the surplus table corresponding to the reference address. A repetition medium repeats a predetermined number of times the reference address creating medium and the surplus table reading-out medium.
Here, when the surplus table satisfies n/2−m=0 for the respective
2
n
data {D
n
} [{D
n
}={d
0
, d
1
, d
2
, . . . , d
n−1
}, d
i
(i is an integer, on the condition of 0≦i≦n−1) is 0 or 1, K is an integer on the condition of 0≦K≦2
n
], one of the data created by the modulo-2 division
Cooper & Dunham LLP
De'cady Albert
Ricoh & Company, Ltd.
Torres Joseph D.
LandOfFree
CRC operating calculating method and CRC operational... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with CRC operating calculating method and CRC operational..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and CRC operating calculating method and CRC operational... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2886523