Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2000-03-07
2003-02-11
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S757000, C714S807000
Reexamination Certificate
active
06519737
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The following invention relates generally to error detection in a telecommunications environment and specifically to speeding up cyclic redundancy code (CRC) calculations to speed up error detection.
2. Related Art
The use of a cyclic redundancy check, or CRC, is a standard means for error detection in communication networks. A block, or frame, of binary data to be protected is represented as a polynomial over GF(2), the field of integers modulo 2. Computation of the CRC is defined in terms of division of this polynomial by a so-called generator polynomial, with the division carried out using arithmetic in GF(2). The CRC is appended to the data frame before transmission as a frame-check sequence (or FCS), and is checked at the receiving end using an essentially identical polynomial division process.
A formal definition of the CRC employed in data communication applications is given in a number of communication standards. The ISO definition, taken from [1], is paraphrased here:
The K-bit frame-check sequence shall be the ones complement of the sum (modulo 2) of: (a) the remainder of z
N
U
0
(z) divided (modulo 2) by the generator polynomial G(z), where the number of bits in the input sequence to be protected by the CRC is N, and U
0
(z) is an initialization polynomial of degree less than K; and (b) the remainder of z
k
U
p
(z) divided (modulo 2) by the generator polynomial G(z), where U
p
(z) is the polynomial representing the input sequence to be protected by the CRC.
For purposes of this disclosure, the term “CRC” will be used to refer to the sum of the two remainders referred to in the definition above. The FCS that is appended to the data frame is equal to the ones complement of what we are calling the CRC. Note that in GF(2) finding the ones complement of a number is equivalent to adding 1 to the number.
If we think of the input sequence as a time series u(n) taking on values 0 or 1 and with time index n starting from 0 (so that u(0) is the first bit to be processed), the polynomial representation referred to in the CRC definition is
U
p
(
z
)
=
∑
n
=
0
N
-
1
u
(
n
)
z
N
-
1
-
n
(
1
)
The generator polynomial G(z) is a polynomial of degree K. The ISO standard generator polynomials for K=16 and K=32 are
G
16
(
z
)=
z
16
+z
12
+z
5
+1
G
32
(
z
)=
z
32
+z
26
+z
23
+z
22
+z
16
+z
12
+z
11
+z
10
+z
8
+z
7
+z
5
+z
4
+z
2
+z
1
(2)
The initialization polynomial is generally either zero or the polynomial of degree K−1 all of whose coefficients are 1.
The error detection properties of the CRC depend on the characteristics of polynomials over the field GF(2), are well known (see [2], for example), and are not at issue in this disclosure. Rather, we address here efficient means for high- speed CRC computation.
The usual reference implementation for computing the CRC is derived from a circuit for polynomial division that employs a shift register with feedback (see, for example, Sec. 6.2 in Ref [3]). One form of this reference implementation, generalized from Ref. [4], is shown in FIG.
1
. The blocks labeled z
−1
are unit delay elements that make up the shift register; for the block whose output is x
k
(n), for example, the input is equal to x
k
(n+1). The scale factors of the gain elements are the coefficients of the divisor polynomial G(z); i.e.
G
(
z
)
=
∑
k
=
0
K
g
k
z
k
(
3
)
where we assume the coefficients are normalized with g
k
=1. The input sequence u(n) contains the finite-length block of data to be protected, for n=0, 1, . . . N−1. After the last element of the input sequence has been processed, i.e. at n=N, the shift register contains the remainder of the division required by the CRC definition. More precisely:
Let the shift register be initialized so that it contains a representation of the initialization polynomial U
0
(z); i.e. if
U
o
(
z
)
=
∑
k
=
0
K
-
1
u
ok
z
k
(
4
)
then set x
k
(0)=U
ok
for k=0, 1, . . . , K−1. Then, at n=N, the contents of the shift register represents the sum of the remainder of z
N
U
o
,(z) divided by G(z), and the remainder of z
K
U
p
(z) divided by G(z), where U
p
(z) is the polynomial representation of the input data sequence according to Eqn. (1). In other words, if we call the sum of these two remainders R
T
(z), with
R
T
(
z
)
=
∑
k
=
0
K
-
1
r
Tk
z
k
(
5
)
then the coefficients of this polynomial, which make up the CRC, satisfy:
r
Tk
=x
k
(
N
);
k
0, 1, . . . , K−1 (6)
Note that when the CRC is computed over GF(2) as in the standard definition, the appropriate arithmetic is employed, Thus the summing blocks in
FIG. 1
implement modulo 2 addition, and the negative signs in the figure are irrelevant (because any element in GF(2) is its own additive inverse). In addition, since the coefficients of G(z) are all either 0 or 1, the gain elements shown in the figure would be implemented either as a closed connection (for a 1) or an open circuit (for a 0).
The processing of the input sequence in
FIG. 1
can be described by the difference equation:
x
(
n
+1)=
Ax
(
n
)+
bu
(
n
) (7)
where the K-dimensional state vector x(n) is
x
(
n
)=[
x
0
(
n
)
x
1
(
n
) . . .
x
k−1
(
n
)]
T
(8)
A is a K×K matrix with the form
A
=
[
0
0
…
0
0
-
g
0
1
0
…
0
0
-
g
1
0
1
…
0
0
-
g
2
…
…
…
…
…
…
…
0
0
…
1
0
-
g
k
-
2
0
0
0
0
1
-
g
k
-
1
]
(
9
)
and b is the K×1 matrix
b
=[(−
g
0
)(−
g
1
) . . . (−
g
k−1
)]
T
(10)
where the superscript ‘T’ indicates transpose. The initial condition for the difference equation (7) is determined by the initialization polynomial; with U
0
(z) as in Eqn. (4):
x
k
(0)=u
ok
; k=0, 1, . . . , K−1 (11)
Again, when the CRC is computed over GF(2), the calculation in Eqn. (7) is done using modulo-2 arithmetic, and the negative signs in the A matrix in Eqn. (9) and the b matrix in equation (10) are superfluous. Note also that the shift register contains the CRC. In other words, the state vector of the system described by the state equation (7) is equal to the CRC after the last input element has been processed, at n=N.
Observe that Eqn.(7) is executed once for each element of the input sequence u(n) (i.e. for each bit of the input bitstream). A variety of techniques have been developed to compute the CRC more efficiently by processing some number of bits (i.e. elements of the input sequence u(n)) in parallel. This increased efficiency has been found useful for CRC computation in both hardware and software. Parallel CRC computation was originally described by Patel [5]. Perez [6] has an early example of its implementation in software. References [7] through [13] provide other examples of hardware implementations of parallel CRC computation. A companion disclosure document, the U.S. Patent Application entitled “Method and Apparatus for High-Speed CRC Computation Based on State-Variable Transformation” (listed under the references section above, incorporated herein by reference in its entirety, and referenced hereinafter as “companion patent document”), describes a maximally efficient (in the sense of throughput relative to circuit speed) hardware implementation.
The basis of all reported techniques for parallel CRC computation can be established by describing formally the block-oriented version of the system state equation (7). Let the elements of the input sequence u(n) be grouped into blocks of length M, so that the input to the block-oriented system is now a vector u
M
(m) with
u
M
(
m
)=[
u
(
mM+M
−1)
u
(
mM+M
−2) . . .
Baker Stephen M.
Reid Scott W.
LandOfFree
Computing the CRC bits at a time for data whose length in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computing the CRC bits at a time for data whose length in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the CRC bits at a time for data whose length in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136005