Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-08-25
2003-05-06
Moise, Emmanuel L. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S757000, C714S758000
Reexamination Certificate
active
06560746
ABSTRACT:
FIELD OF THE INVENTION
This application claims priority under 35 U.S.C. §§119 and/or 365 to 198 38 865.9 filed in Federal Republic of Germany on Aug. 26, 1998; the entire content of which is hereby incorporated by reference.
The invention generally relates to the generation of a CRC (cyclic redundancy check) which is used for checking errors when transmitting digital data from a transmitter to a receiver. The CRC may have a different length and is added to the user data in the transmitter. In the receiver the CRC data is compared with the CRC data re-generated on the basis of the received user data. If the two generated CRCs match, then it is determined that no serious transmission errors have occurred during the transmission between transmitter and receiver.
The generation of a CRC code is a standard technique and circuits are known in the prior art for generating this CRC code either serially or parallely. As will be explained below with more detail, design tools are available for designing such serial and parallel generation circuits. However, so far it was not known that such design tools for the parallel CRC generation circuit did not take into account redundancies in the feedback lines. That is, if more feedback lines are used than absolutely necessary to perform the parallel CRC generation, then the hardware amount is extensive and the speed of parallely generating the CRC bits is decreased.
The present invention particularly relates to the problem of how the redundancies in the parallel CRC generation circuits can be reduced.
BACKGROUND OF THE INVENTION
When designing a CRC generation circuit for generating a CRC code of length N, a CRC polynomial CRCN is used, which is generally defined by the following equation (1a):
CRCN=a
N
x
N
+a
N−1
x
N−1
+ . . . a
n
x
n
+ . . . a
1
x
n
+a
0
x
0
(1a)
In this equation (1a) the coefficient a
N
=1, a
0
=1 and the coefficients a
n
, n=1, . . . , N−1 are 0 or 1 depending on the CRC code to be formed.
FIG. 1
a
shows the principle of a serial CRC generation circuit realized on the basis of the CRC polynomial in equation (1a). The CRC generation circuit comprises a number N of shift registers C
0
, C
1
, . . . , C
n
, . . . , C
N−1
in series connection. There are also provided a number N of XOR gates XOR
1
. . . XOR
n
, . . . , XOR
N−1
, XOR
N
. A bit stream SI is input serially to the XOR gate XOR
N
. Essentially, depending on the selection of N and a
n
in equation (1a), XOR gates are provided between each two shift registers C
n
, C
n−1
. Depending on the feedbacks from the XOR gate XOR
N
to the individual shift registers (flip-flops) C, a desired CRC code is output from the shift register C
N−1
of the final stage.
Thus, the designer selects the CRC code to be generated by selecting the feedbacks, i.e. by selecting N and which of the coefficients a
n
are 0 or 1 depending on the desired CRC code. In the circuit in
FIG. 1
a
this selection of coefficients a
n
is reflected by the feedback and the insertion of the particular XOR gates between respective two shift registers.
The operation of the circuit in
FIG. 1
a
is as follows. The input bit stream SI of X bits (is for example 100) is serially input to the XOR gate XOR
N
at sequential clock cycles. Thereafter the CRC code stored in the serial shift registers is serially read out. This means, that after using X clocks cycles to clock the X bits into the CRC circuit, another N clock cycles must be used to serially read out the generated CRC code. The read out CRC code is then serially appended to the user data of X bits to be transmitted together with the user data to the receiver.
Therefore, using the serial CRC generation circuit of
FIG. 1
a
, an additional N clock cylces are always needed to read out the generated CRC code, which increases the processing time for generating and transmitting the CRC code.
FIG. 1
b
shows an example of the serial CRC circuit for a special CRC
13
code. That is, in
FIG. 1
b
the polynomial is chosen as:
CRC
13
=
X
13
+X
12
+X
7
+X
6
+X
5
+X
4
+X
2
+1 (1b)
as shown in
FIG. 1
b
above the serial CRC circuit. Thus, in the circuit of
FIG. 1
b
, N=13 and a
13
=a
12
=a
7
=a
6
=a
5
=a
4
=a
2
=a
0
=1. The selection of these coefficients in the CRC polynomial is reflected in the circuit configuration by the feedbacks from the shift register C
12
to the other shift registers C
0
-C
11
via the respective XOR gates between the individual shift register C. In
FIG. 1
b
the CRC having length
13
is output serially at the “CRC 13 serial out” after the X bits have been serially input.
Since in the circuits in
FIG. 1
a
and
FIG. 1
b
the processing is performed serially, the processing time is increased. Therefore an alternative solution is to perform the generation of the CRC code parallely for a data packet of T bits which is a parallel part of the X serial bits.
FIG. 1
c
shows a general configuration of a parallel CRC generation circuit.
In
FIG. 1
c
an input register means I having T input registers I
0
, I
1
, . . . I
t
. . . I
T−1
for simultaneously storing T input bits is provided. Each input register has an output line I(
0
), I(
1
), . . . I(t) . . . I(T−1) which leads to a coupling means CM. An output register means C has N output registers C
0
, C
1
, . . . C
n
. . . , C
N−1
for parallely storing the generated CRC code. Each of the output registers has an input line C
0
(T), C
1
(T), . . . , C
n
(T) . . . C
N−1
(T) and an output line C
0
(
0
), C
1
(
0
) . . . C
n
(
0
) . . . C
N−1
(
0
). Furthermore, there are provided a number N of parallel XOR gates XOR
0
, XOR
1
. . . XOR
n
. . . XOR
N−1
each having an output connected to a respective input line of the output registers and a number of input lines coupled to the coupling means CM. The output lines of the respective output registers are also input to the coupling means CM.
The operation of the parallel CRC generation circuit in
FIG. 1
c
is as follows. From the data stream of X bits, a number of T bits are input (parallely) to the input register means I. The coupling means CM determines which of the outputs lines from the input register means I and which of the output lines from the output registers C are input to the respective XOR gates. The coupling means does not “couple” the outputs from the input registers and the outputs of the output registers but merely determines which of the input lines of the XOR gates must receive a separate input from the respective input and output registers. In one clock cylce the output registers C contain a parallely generated CRC code. Then, in the next clock cycle the next set of T input bits are input to the input register means I. Then they are input to the XOR gates in combination with the previous CRC code held in the output registers C. Thus, for every T input bits only one clock cycle is needed to parallely generate the CRC code. By contrast to the serial circuits in
FIG. 1
a
and
FIG. 1
b
, where the serial generation of the CRC code takes a large amount of time and is therefore undesirable, the parallel generation circuit of
FIG. 1
c
builds the CRC value for the number T of input bits in one clock cycle.
However, generally the design of the coupling means CM which determines which of the output lines of the input register and output lines of the output registers need to be supplied as inputs to the respective XOR gates is not a trivial task. That is, what has been done with internal state shifting in a serial input register now needs to be performed in one step parallely in
FIG. 1
c
. Conventional design tools perform—for a given polynomial and length of the CRC—a simulation of a serial CRC circuit to find out how the individual entries in the serial shift registers change successively with the input of the T bits. On the basis of these simulations the coupling means is determi
Moise Emmanuel L.
Telefonaktiebolaget LM Ericsson
LandOfFree
Parallel CRC generation circuit for generating a CRC code does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel CRC generation circuit for generating a CRC code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel CRC generation circuit for generating a CRC code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3027705